数据结构课程设计_n元多项式乘法

数据结构课程设计报告 ——N元多项式乘法

目录

1 课程设计内容 ----------------------------------------------------------------- - 1 - 2 课程设计分析 ----------------------------------------------------------------- - 1 - 3 思路原理 ------------------------------------------------------------------------ - 3 - 4 程序简图 ------------------------------------------------------------------------ - 3 - 5 算法（数据结构）描述 ---------------------------------------------------- - 4 - 6 程序清单 ------------------------------------------------------------------------ - 5 - 6.1 单链表表示 --------------------------------------------------------------- - 6 - 6.2 数组表示 ----------------------------------------------------------------- - 13 - 7 运行与调试分析 ------------------------------------------------------------- - 14 - 8 收获与体会 -------------------------------------------------------------------- - 15 - 9 参考文献 ----------------------------------------------------------------------- - 16 -

1 课程设计内容

功能：

完成两个n元多项式作乘法，给出明确的等式形式。 分步实施：

1)初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2)完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。 3)进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。

2 课程设计分析

本程序用的存储方式是单链表，单链表在C语言中是一种非常常见的结构，而在C++中的实现却又有不同，在一些地方更简单，更严密。同时，由于C++的一些特点，使它具有C语言所不具有的“安全化”，所以本程序用C++。

有了链表特定的数据类型Mulpoly，接下来就需要建立这个链表。这里定义了一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点，存储多项式的信息（项数），为head分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用c++语言中的malloc来实现；这时输入多项式的项数num，把它赋值给head的coef域，exp域赋值为1，此时再定义一个CreatePoly型的指针变量r指向head头结点。还要用类似的算法建立多项式的其它结点，剩余节点的插入用一个while循环来实现，while循环中的控制变量i从大于0的数n开始递增，直到到达num，此时while循环结束。While 循环的循环体由两部分组成，第一部分是为指针变量s分配存储空间和为其数据域赋值，分配存储空间同样用c++语言中的malloc来实现；第二部分是节点的指针域转换过程，将r的指针域指向新生成的结点s，相当于将生成结点依次用指针连接，然后将最后一个结点的指针域设置为NULL，具体代码如下： MulPoly *CreatePoly(){

MulPoly *head,*r,*s; int m,n,num,i=1;

head=(MulPoly *)malloc(sizeof(MulPoly)); cout<<\"请输入多项式的项数:\"<>num;

head->coef=num; head->exp=1; r=head;

while(i<=num) //n不为0时建立多项式链表 {

s=(MulPoly *)malloc(sizeof(MulPoly));

cout<<\"输入第\"<- 1 -

cin>>n>>m; s->exp=m; s->coef=n; r->next=s; r=s; i++;}

r->next=null; return(head); }

在处理多项式相乘的问题时，定义一个PolyMulti函数实现，需要再建立一个MulPoly型的链表存储相乘之后的链表，定义结果链表的系数等于链表P1的系数乘以链表P2的系数：(p->coef)=(p1->coef)*(p2->coef) 结果链表的指数等于链表P1的指数乘以链表P2的指数：(p->exp)=(p1->exp)+(p2->exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个while循环来完成。具体代码如下： while(p!=q) {s=q;

q=q->next;}

s->next=q->next; free(q); }

还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。在主函数的开始需要定义三个MulPoly型指针变量，分别用来存储调用CreatePoly函数和PolyMulti函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间，s=(MulPoly

*)malloc(sizeof(MulPoly));这条语句便可完成此操作。此条语句运用了c++语言库函数中的malloc函数，这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。调用构建链表函数CreatePoly后链表Pl便构建完成。接下来需要执行m=PolyMulti(p,q);语句，这条语句的目的是把多项式P1和P2相乘的结果多项式存储在链表m当中，然后执行Print(m);语句显示输出。主函数的程序框架如下： int main(){

MulPoly *p,*q,*m; p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m);

system(\"pause\"); }

程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程

- 2 -

序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作便是由Delete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个Merge_Same函数，调用Delete函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。

下面分析一下程序的性能。在主函数中，首先调用的是构造单链表函数CreatePoly，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的next域，时间复杂度为O（n）。接下来执行一个双重for循环，在内部的for循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点的操作都需要m次，共n个结点，则需要𝑚𝑛次操作，时间复杂度为O（𝑛𝑛）。

3 思路原理

先要设置两个单链表，每个单链表中可写入一个多项式。 加法：取第两个链表中最高项和另一链表各项比指数，若不同则放在第三个空链表里作为第一项，若相同则系数相加指数不变，放在第三个空链表里作为第一项，并且要删除两链表里此指数项。取第两个链表中最高项和另一链表各项比指数，以此类推。

乘法：取第一个链表第一项和第二链表的每一项相乘，系数相乘，指数相加，作为一个新链表。取第一个链表第二项和第二链表的每一项相乘.......最后再把每个新链表做加法。

最后显示答案。

4 程序简图

- 3 -

5 算法（数据结构）描述

定义单链表的抽象数据类型： ADT LinkList{

数据对象：D={ai|ai∈ElemSet,i=1,2,3,„，n>=0} 数据关系：R={|ai,ai+1 ∈D}

//----------------------线性表的单链表基本操作---------------------// LinkList InitList(void); 构造一个空的线性表

void DestroyList(LinkList *L);

初始条件：线性表L已存在。 操作结果：销毁线性表L。 LinkList MakeEmpty(LinkList L)‘

初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 int IsEmpty(LinkList L);

初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 int ListLength(LinkList L);

初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 LNode IsLast(LinkList L);

初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。

LNode NewLNode(ElemType X);

- 4 -

构造一个数据域为X的新结点

LNode FindPrefious(ElemType X, LinkList L);

初始条件：线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 void ListDelete(LNode Pre);

初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 链表的结点结构:

┌──┬──┐ │data│next│ └──┴──┘ data域--存放结点值的数据域

next域--存放结点的直接后继的地址（位置）的指针域（链域） 此题定义系数和指数结构如下： coef exp next

//----------------------线性表的单链表存储结构---------------------// Typedef struct Lnode{

ElemType data;//结点的数据域

Struct Lnode *next;//结点的指针域 }Lnode, *LinkList;

//-----------------------------基本操作----------------------------// InitArray(&A, n, bound1, ..., boundn)

操作结果：若维数 n 和各维长度合法则构造相应数组 A。 DestroyArray(&A)

初始条件：数组 A 已经存在。 操作结果：销毁数组 A。

Value(A, &e, index1, ..., indexn)

初始条件：A 是 n 维数组，e 为元素变量， n 个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。 Assign(&A, e, index1, ..., indexn)

初始条件：A 是 n 维数组，e 为元素变量，n 个下标值。

操作结果：若下标不超界，则将 e 的值赋给A中指定下标的元素。 } ADT Array

6 程序清单

- 5 -

6.1 单链表表示

/*程序源代码：*/ #include #include #include #include #define null 0

using namespace std; typedef struct term {

//项的表示，多项式的项作为LinkList的数据元素 float coef; //系数 int expn; //指数 struct term *next; }term;

int Empty(term *L) {

if (L->next != null) return 1; return 0; }

term *CreatePoly() {

term *head, *r, *s; int m, n, num, i = 1;

head = (term *)malloc(sizeof(term));//建立一个头结点 cout << \"请输入多项式的项数:\" << endl; cin >> num;

head->coef = num; head->expn = 1; r = head;

while (i <= num) //n不为0时建立多项式链表 {

s = (term *)malloc(sizeof(term));//建立一个新结点 cout << \"输入第\" << i << \"组系数和指数:\" << endl; cin >> n >> m; s->expn = m; s->coef = n; r->next = s; r = s; i++;

- 6 -

}

r->next = null; return(head);

}

term *PolyMulti(term *f, term*g) {

term *p1, *p2, *p, *r, *head;

head = (term *)malloc(sizeof(term)); head->coef = null; head->expn = null; r = head;

for (p1 = f->next; p1 != null; p1 = p1->next) {

for (p2 = g->next; p2 != null; p2 = p2->next) {

p = (term *)malloc(sizeof(term)); (p->coef) = (p1->coef)*(p2->coef); (p->expn) = (p1->expn) + (p2->expn); r->next = p; r = p; } }

r->next = null; return head; }

void Delete(term * L, term * p) {

term * s, *q; s = L;

q = L->next; while (p != q) {

s = q;

q = q->next; }

s->next = q->next; free(q); }

void Print(term * L) {

term * p;

cout << \"两个多项式相乘的结果为：\" << endl << \"P(x)=\"; if (Empty(L)) {

- 7 -

for (p = L->next; p != null; p = p->next)

cout << \"(\" << p->coef << \")\" << \"x\" << \"^\" << p->expn << \"+\";

cout << \"\\b\"; } else

cout << \"0\";

}

void Merge_Same(term *f) {

term *p, *q;

for (p = f->next; p != null; p = p->next)

for (q = p->next; q != null; q = q->next) {

if (p->expn == q->expn) {

(p->coef) = (p->coef) + (q->coef); Delete(f, q); }

if (p->coef == 0) {

Delete(f, p); break; } }

}

term* CreatPolyn(term *P, int m) {

// 输入m项的系数和指数，建立表示一元多项式的有序链表P if (m <= 0) return NULL;

term *h = P = (term*)malloc(sizeof(term)), *q = NULL; P->coef = 0.0; int i;

printf(\"依次输入%d个数（前一个为系数，后一个为指数）\\n\for (i = 1; i <= m; ++i) { // 依次输入m个非零项

scanf(\"%f%d\if (P->coef)

q = P;

P = P->next = (term*)malloc(sizeof(term)); }

q->next = NULL; free(P); return h; } // CreatPolyn

- 8 -

term* selsort(term *h) {

term *g, *p, *q; if (!h) return NULL; float f;

int i, fini = 1;

for (g = h; g->next&&fini; g = g->next) {

fini = 0;

for (p = h, q = h->next; q; p = p->next, q = q->next)

if (p->expn < q->expn) {

f = p->coef; i = p->expn;

p->coef = q->coef; p->expn = q->expn; q->coef = f; q->expn = i; fini = 1; }

}

for (g = h, p = g->next; p;)

if (g->expn == p->expn) {

g->coef += p->coef; g->next = p->next; q = p;

p = p->next; free(q); }

else if (g->next) {

g = g->next; p = p->next; }

return h; }

void PrintfPoly(term *P) {

term *q = P; if (!q) {

putchar('0'); return; }

if (q->coef != 1) {

- 9 -

printf(\"%g\

if (q->expn == 1) putchar('X');

else if (q->expn) printf(\"X^%d\}

else if (!q->expn) putchar('1'); else if (q->expn == 1) putchar('X'); else printf(\"X^%d\q = q->next; while (q) {

if (q->coef > 0) putchar('+'); if (q->coef != 1) {

printf(\"%g\

if (q->expn == 1) putchar('X');

else if (q->expn) printf(\"X^%d\}

else if (!q->expn) putchar('1'); else if (q->expn == 1) putchar('X'); else printf(\"X^%d\q = q->next; }

}

int Compare(term *a, term *b) {

if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; }

term* APolyn(term *Pa, term *Pb) {

// 多项式加法：Pa = Pa＋Pb，利用两个多项式的结点构成\"和多项式\"。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum;

h = p = (term*)malloc(sizeof(term)); p->next = NULL; while (qa && qb) {

// Pa和Pb均非空

switch (Compare(qa, qb)) {

case -1: // 多项式PA中当前结点的指数值小

p->next = qb; p = qb;

- 10 -

qb = qb->next; break;

case 0: // 两者的指数值相等

sum = qa->coef + qb->coef; if (sum != 0.0) {

// 修改多项式PA中当前结点的系数值 p->next = qa; qa->coef = sum; p = qa;

qa = qa->next; } else {

// 删除多项式PA中当前结点 q = qa;

qa = qa->next; free(q); }

q = qb;

qb = qb->next; free(q); break;

case 1: // 多项式PB中当前结点的指数值小

p->next = qa; p = qa;

qa = qa->next; break; } // switch } // while

if (Pa) p->next = qa; // 链接Pa中剩余结点 if (Pb) p->next = qb; // 链接Pb中剩余结点 q = h;

h = h->next; free(q); return h; } // APolyn

term* A(term *Pa, term *Pb) {

int n;

puts(\"输入第二个一元多项式的项数\"); scanf(\"%d\

Pb = CreatPolyn(Pb, n); Pb = selsort(Pb);

- 11 -

PrintfPoly(Pa);

if (Pb && Pb->coef>0) printf(\" + \"); PrintfPoly(Pb);

Pa = APolyn(Pa, Pb); printf(\" = \"); Pa = selsort(Pa); PrintfPoly(Pa); return Pa;

}

term* BPolyn(term *Pa, term *Pb) {

// 多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成\"差多项式\"。 term *p = Pb; while (p) {

p->coef *= -1; p = p->next; }

return APolyn(Pa, Pb); } // BPolyn

term* B(term *Pa, term *Pb) {

int n;

puts(\"输入第二个一元多项式的项数\"); scanf(\"%d\

Pb = CreatPolyn(Pb, n); Pb = selsort(Pb); PrintfPoly(Pa); printf(\" - \");

putchar('('); PrintfPoly(Pb); putchar(')'); Pa = BPolyn(Pa, Pb); printf(\" = \"); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; }

int main() {

term *M=NULL, *N=NULL; term *p, *q, *m; char s[2]; int i, n;

f: puts(\"\\n1:加\\n2:乘\\n3:下一步\");

cin >> i;

- 12 -

switch (i) {

case 1:

puts(\"一元多项式计算:\\n输入第一个一元多项式的项数\"); scanf(\"%d\

M = CreatPolyn(M, n); M = selsort(M); PrintfPoly(M); M = A(M, N); goto f; case 2:

p = CreatePoly(); q = CreatePoly(); m = PolyMulti(p, q); Merge_Same(m); Print(m); goto f; case 3:break;

default:puts(\"输入有误,请重新输入!\"); } }

6.2 数组表示

/*程序源代码：*/ #include \"stdio.h\"

#define N 100 //宏定义，为多项式的系数数组开辟空间 static int k = 1;//记录多项式的个数

void input(float a[], int na){//多项式a的系数输入，其中na为次数

int i;

printf(\"请输入多项式P%d(x)的各项系数数(从高次项到低次项，中间缺项则为0):\\n\

for (i = 0; i <= na; i++){//输入各项系数

scanf(\"%f\}

while (a[0] == 0){//首项系数不为0

printf(\"首项系数不能为0，请重新输入首项系数：\"); scanf(\"%f\}

printf(\"P%d(x)=%0.2f*x^%d\for (i = 1; iif (a[i] != 0)

- 13 -

printf(\"+%0.2f*x^%d\

}

if (a[na] != 0)

printf(\"+%0.2f\printf(\"\\n\");

k++;//自增，记录下个多项式

}

void mul(float a[], float b[], int na, int nb){//系数相乘

int n, i, j;

float c[N];//记录乘积的系数 n = na + nb;//乘积的最高系数

for (i = 0; i <= n; i++)//乘积系数初始化为0

c[i] = 0;

for (i = 0; i <= na; i++){

for (j = 0; j <= nb; j++)

c[i + j] += a[i] * b[j];//对应相同次数的系数相加

}

printf(\"乘积P(x)=%0.2f*x^%d\for (i = 1; iif (a[i] != 0)

printf(\"+%0.2f*x^%d\

}

if (a[n] != 0)

printf(\"+%0.2f\printf(\"\\n\"); }

void main(){

float A[N], B[N];//开辟两个数组，记录多项式的值 int n1, n2;

printf(\"请输入多项式P%d(x)的次数：\scanf(\"%d\input(A, n1);

printf(\"请输入多项式P%d(x)的次数：\scanf(\"%d\input(B, n2);

mul(A, B, n1, n2); }

7 运行与调试分析

- 14 -

下面我们测试P1=2x^1+3x^2+4x^3;P2=1x^3+4x^0;

P=P1*P2=(2x^1+3x^2+4x^3)*( 1x^3+4x^0)=2x^4+8x^1+3x^5+12x^2+4x^6+16x^3

测试P1=4.00x^3+5.00x^2+6.00x^1+7.00;P2=1.00x^2+3.00x^1+6.00 P=P1*P2=(4.00x^3+5.00x^2+6.00x^1+7.00)*( 1.00x^2+3.00x^1+6.00) 数组测试结果：

8 收获与体会

- 15 -

计算多项式乘法，其结果取决于多项式的各项系数，因此程序核心是处理两个多项式的系数。将多项式的各项系数存放在数组中为程序的循环控制提供了可能，利用对数组下标的运算来确定结果多项式的各项次数，利用对数组元素值的运算确定相应的各项系数。同理算出相应的幂数。数组是在计算机内存中使用一组连续的存储单元保存数据类型和名字相同的变量。就数组这种数据类型而言，可以是一维的，就像上述的队列差不多。也可以是的，在排列上采用的方法也是按序排放，先存放第一行，接着存放第二行，„„，直到所有数据元素被存放。多项式采用的是数组形式，以牺牲一定的空间提高程序的运行速度和可行性，在系数大多数不为0时比较实效，当然，若多项式的系数大多数为0，则应采用链式存储更好。

算法思想：采用数组形式存储多项式，用数组下标标记多项式的次数，以数组中的对应元素记录系数值，下列程序中采用的是n表示最高次系数，进行乘法运算时，下标相加即为乘积的对应次数，下标和相同则表示为同类项，数组元素相乘则为乘积的系数值

了解链表与数组的区别：表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。链表顾名思义，要把各个元素链接起来才算撒。 通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。

9 参考文献

- 16 -