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

1、数据结构课程设计报告N元多项式乘法目录1 课程设计内容- 1 -2 课程设计分析- 1 -3 思路原理- 3 -4 程序简图- 4 -5 算法（数据结构）描述- 4 -6 程序清单- 6 -6.1 单链表表示- 6 -6.2 数组表示- 13 -7 运行与调试分析- 15 -8 收获与体会- 16 -9 参考文献- 16 -1 课程设计内容功能：完成两个n元多项式作乘法，给出明确的等式形式。分步实施：1)初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2)完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。3)进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系

2、统功能。2 课程设计分析本程序用的存储方式是单链表，单链表在C语言中是一种非常常见的结构，而在C+中的实现却又有不同，在一些地方更简单，更严密。同时，由于C+的一些特点，使它具有C语言所不具有的“安全化”，所以本程序用C+。有了链表特定的数据类型Mulpoly，接下来就需要建立这个链表。这里定义了一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点，存储多项式的信息（项数），为head分配存储空间建立一个头结点并为其数据域赋值，分配存储空间用c+语言中的malloc来实现；这时输入多项式的项数num，把它赋值给head的coef域，exp域

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

4、 *head,*r,*s; int m,n,num,i=1; head=(MulPoly *)malloc(sizeof(MulPoly); cout<<"请输入多项式的项数:"<<endl; cin>>num; head->coef=num; head->exp=1; r=head; while(i<=num) /n不为0时建立多项式链表 s=(MulPoly *)malloc(sizeof(MulPoly); cout<<"输入第"<<i<<"组系数和

5、指数:"<<endl; 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->

6、;exp)+(p2->exp)。在整理之后可能出现零结点，那么就需要进行判断和删除操作同时释放零结点，这些操作是通过一个while循环来完成。具体代码如下：while(p!=q) s=q; q=q->next; s->next=q->next; free(q); 还需要定义一个输出函数，在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。在主函数的开始需要定义三个MulPoly型指针变量，分

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

8、int main() MulPoly *p,*q,*m; p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m); system("pause"); 程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确，是否带有空结点，合并是否完全。决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。如果这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候

9、可以在程序中加入删除、释放空结点操作，此操作便是由Delete函数完成的，若输出的多项式没有空结点说明函数正确，可以继续向下进行。接下来就是相乘后的合并同类项，控制此操作的关键是一个Merge_Same函数，调用Delete函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作正确。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善直到满足要求。下面分析一下程序的性能。在主函数中，首先调用的是构造单链表函数CreatePoly，在这个函数中需要通过一个for循环为每个结点分配存储空间，变换节点的

10、next域，时间复杂度为O（n）。接下来执行一个双重for循环，在内部的for循环中是对结点的相加、相乘操作，因为是按着指针的方向就可以对结点进行相加、相乘操作，所以每个结点的操作都需要m次，共n个结点，则需要mn次操作，时间复杂度为O（nn）。3 思路原理先要设置两个单链表，每个单链表中可写入一个多项式。 加法：取第两个链表中最高项和另一链表各项比指数，若不同则放在第三个空链表里作为第一项，若相同则系数相加指数不变，放在第三个空链表里作为第一项，并且要删除两链表里此指数项。取第两个链表中最高项和另一链表各项比指数，以此类推。 乘法：取第一个链表第一项和第二链表的每一项相乘，系数相乘，指数相加

11、，作为一个新链表。取第一个链表第二项和第二链表的每一项相乘.最后再把每个新链表做加法。 最后显示答案。4 程序简图5 算法（数据结构）描述定义单链表的抽象数据类型：ADT LinkList数据对象：D=ai|aiElemSet,i=1,2,3,，n>=0数据关系：R=<ai,ai+1>|ai,ai+1 D/-线性表的单链表基本操作-/LinkList InitList(void); 构造一个空的线性表 void DestroyList(LinkList *L);初始条件：线性表L已存在。 操作结果：销毁线性表L。 LinkList MakeEmpty(LinkList L)初

12、始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 int IsEmpty(LinkList L);初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。 int ListLength(LinkList L);初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。 LNode IsLast(LinkList L);初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。 LNode NewLNode(ElemType X);构造一个数据域为X的新结点 LNode FindPrefious(ElemType X, LinkList L);初始条件：线性表

13、L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。 void ListDelete(LNode Pre);初始条件：线性表L中结点P已找到。 操作结果：删除该结点。 链表的结点结构:datanext data域-存放结点值的数据域next域-存放结点的直接后继的地址（位置）的指针域（链域）此题定义系数和指数结构如下： coefexpnext/-线性表的单链表存储结构-/Typedef struct Lnode ElemType data;/结点的数据域 Struct Lnode *next;/结点的指针域Lnode, *LinkList;/-基本操

14、作-/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

15、的值赋给A中指定下标的元素。 ADT Array6 程序清单6.1 单链表表示/*程序源代码：*/#include<stdlib.h> #include<stdio.h> #include<ctype.h> #include<iostream>#define null 0using namespace std;typedef struct term/项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 struct term *next;term;int Empty(term *L)if

16、(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 *)m

17、alloc(sizeof(term);/建立一个新结点cout << "输入第" << i << "组系数和指数:" << endl;cin >> n >> m;s->expn = m;s->coef = n;r->next = s;r = s;i+;r->next = null;return(head);term *PolyMulti(term *f, term*g)term *p1, *p2, *p, *r, *head;head = (term *)ma

18、lloc(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->nex

19、t = 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)for (p

20、 = L->next; p != null; p = p->next)cout << "(" << p->coef << ")" << "x" << "" << p->expn << "+"cout << "b"elsecout << "0"void Merge_Same(term *f)term *p, *q;for (p

21、= 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;ter

22、m *h = P = (term*)malloc(sizeof(term), *q = NULL;P->coef = 0.0;int i;printf("依次输入%d个数（前一个为系数，后一个为指数）n", m * 2);for (i = 1; i <= m; +i) / 依次输入m个非零项 scanf("%f%d", &P->coef, &P->expn);if (P->coef)q = P;P = P->next = (term*)malloc(sizeof(term);q->next = N

23、ULL;free(P);return h; / CreatPolyn 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->ex

24、pn;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 PrintfP

25、oly(term *P)term *q = P;if (!q)putchar('0');return;if (q->coef != 1)printf("%g", q->coef);if (q->expn = 1) putchar('X');else if (q->expn) printf("X%d", q->expn);else if (!q->expn) putchar('1');else if (q->expn = 1) putchar('X')

26、;else printf("X%d", q->expn);q = q->next;while (q)if (q->coef > 0) putchar('+');if (q->coef != 1)printf("%g", q->coef);if (q->expn = 1) putchar('X');else if (q->expn) printf("X%d", q->expn);else if (!q->expn) putchar('1&

27、#39;);else if (q->expn = 1) putchar('X');else printf("X%d", q->expn);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 = PaPb，利用两个多项式的结点构成"和多项

28、式"。 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;qb = qb->next;break;case 0: / 两者的指数值相等 sum = qa->coef + qb->coef;if (sum !=

29、 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

30、 (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", &n);Pb = CreatPolyn(Pb, n);Pb = selsort(Pb);PrintfPoly(Pa);if (Pb && Pb->coef>0) printf(" + ");PrintfP

31、oly(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(&

32、quot;输入第二个一元多项式的项数");scanf("%d", &n);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=NU

33、LL, *N=NULL;term *p, *q, *m;char s2;int i, n;f: puts("n1:加n2:乘n3:下一步");cin >> i;switch (i)case 1:puts("一元多项式计算:n输入第一个一元多项式的项数");scanf("%d", &n);M = CreatPolyn(M, n);M = selsort(M);PrintfPoly(M);M = A(M, N);goto f;case 2:p = CreatePoly();q = CreatePoly();m = Po

34、lyMulti(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):

35、n", k);for (i = 0; i <= na; i+)/输入各项系数scanf("%f", &ai);while (a0 = 0)/首项系数不为0printf("首项系数不能为0，请重新输入首项系数：");scanf("%f", &a0);printf("P%d(x)=%0.2f*x%d", k, a0, na);for (i = 1; i<na; i+)/打印输入的多项式if (ai != 0)printf("+%0.2f*x%d", ai, na

36、 - i);if (ana != 0)printf("+%0.2f", ana);printf("n");k+;/自增，记录下个多项式void mul(float a, float b, int na, int nb)/系数相乘int n, i, j;float cN;/记录乘积的系数n = na + nb;/乘积的最高系数for (i = 0; i <= n; i+)/乘积系数初始化为0ci = 0;for (i = 0; i <= na; i+)for (j = 0; j <= nb; j+)ci + j += ai * bj;/对应相同次数的系数相加printf("乘积P(x)=%0.2f*x%d", c0, n);for (i = 1; i<n; i+)/打印输入的多项式if (ai != 0)printf("+%0.2f*x%d", ci, n - i);if (an != 0)printf("+%0.2f", an);printf("n");void main()float A