1、数据结构上海交通大学网络教育课程上海交通大学网络教育数据结构协同作业实验线性表 1 顺序表操作验证1.1 实验目的 (1) 掌握线性表的顺序存储结构； (2) 验证顺序表及其基本操作的实现； (3) 掌握数据结构及算法的程序实现的基本方法。 1.2 实验内容 (1) 建立含有若干个元素的顺序表； (2) 对已建立的顺序表实现插入、删除、查找等基本操作。2 一元多项式相加实验已知 A( x )= a0 + a1x + a2x2 + + anxn 和B(x) = b0 + b1x + b2x2 + + amxm ，并在 A( x ) 和 B( x ) 中指数相差很多，求 A( x ) = A( x
2、 ) + B(x) 。3 开发环境软件平台：Windows XP软件环境：Microsoft Visual C+ 6.0 最低硬件配置：内存64MB或以上、硬盘3.2G或以上4 算法设计介绍4.1 设计思路分析:1存储结构分析根据一元多项式的特点，要表示一个多项式，只要存储第i项以及ai的值，并且如果ai为0的话，该项就不用存储了，从而减少一个存储空间。在线性表中可以通过顺序和链式存储，并用Ti表示一个数据项Ti=（ai,i）。下面以图示表示两种存储结构(假设a2=0)。 图1 顺序存储表 图2 单链表存储 以上两个图可知，在存储空间分配量上两种结构是一致的，但如果两多项式相加的话需要频繁的做
3、插入操作，顺序表的结构特性决定了插入操作的时间复杂度为O(n/2)，链式表的时间复杂度为O(1)，并且如果存储的是一个排好序的多项式的话，不需要双向查找，因此选择单链表存储。 2相加算法分析首先，由于两个多项式A(x)和B(x)的指数相差非常多，因此一定要把输入的多项式按照指数i排好序，防止过高的查找时间复杂度；其次，两个AB多项式同时从head开始查找，AB指数i相同的计算相加ai值存入A表，并且回收不需要的B空间，指数不同的，B指数小的节点插到A指数大的前面。以此往后推移。其时间复杂度为O(n)。举例：A(x)=2+3x+1x3B(x)=1+3x+2x2+2x4+12x7+32x8+42x
4、11+2x12整个相加过程如下： 见注释1图3 初始化后的A(x) pA=headA图4 初始化后的B(x) pB=HeadB-next第一步：图5 A(x) pA-next系数pB系数图6 B(x) pA-next指数0与pB指数0相等 free pB所指节点第二步与第一步做法一致第三步 将pB的节点插入pA后第四步pA-next指数小于pB指数,pA=pA-next， pB不动第五步pA没有后继节点，直接把pB的所有节点接到pA后即可4.2 详细设计a) 数据结构 typedef struct term float coef; /系数 int expn; /指数 struct term *
5、next /指向下一节点 term b) 输入输出输入：两个多项式A,B输出：A+B样式：输入一元多项式的项数2请依次输入非零2个非零项，请注意输入格式2 23 33X3+2X214 （+ - * 退出）4个选项再输入一元多项式的项数3请依次输入非零3个非零项，请注意输入格式2 23 34 43X3+2X2 + 4X4+3X3+2X2 = 4X4+6X3+4X2c) 函数原型主函数：void main()输入函数: InputPolynomial(LinkList &p)多项式相加函数: term* APolyn(term *Pa, term *Pb)多项式相减函数: term* BPolyn
6、(term *Pa, term *Pb)多项式相乘函数: term* CPolyn(term *Pa, term *Pb)输出函数: void PrintfPoly(term *P)5 界面流程展示第一步：先输入第一个“一元多项式的项数”第二步，根据一元多项式的项数，输入非零项。注意输入格式，系数和指数之间要有空格。第三步，选择要进行的运算方式编码第四步，再输入第二个“一元多项式的项数”，方式如第二步一致，最后回车进行运算6 检查及测试报告6.1 检查报告检查名称检查任务完成情况是否安装程序运行环境已经正确设定程序代码检查程序单位首部有程序说明和修改备注变量、过程、函数命令符合规则程序中有足够
7、的说明信息修改注释符合要求类库的使用符合要求画面及报表格式检查画面及报表格式符合规定需求程序命名符合格式需求画面和报表的字段位置和宽度与设计文档一致6.2 测试报告测试名称测试任务完成情况是否功能键、触发键、按钮、菜单、选择项功能正确数据项关联及限制功能正确设计文档规定的其他功能正确性测试读/写/删除操作结果正确各种组合条件之查询或报价正确设计文档规定的其他操作可靠性测试非法键容错测试异常字符容错测试程序副作用检查残留文件检查效率测试输入画面效率测试报表及查询效率测试其他测试7 附程序源代码7.1 一元多项式验证：#include #include #include typedef struc
8、t term /项的表示，多项式的项作为LinkList的数据元素 float coef; /系数 int expn; /指数 struct term *next; term; term* CreatPolyn(term *P,int m) / 输入m项的系数和指数，建立表示一元多项式的有序链表P if(m coef = 0.0; int i; printf(依次输入%d个非零项,请注意输入格式，系数和指数之间要有空格，ex:2 2 3 1n,m); for (i = 1; i coef,&P-expn); if(P-coef) q = P; P = P-next = (term*)mallo
9、c(sizeof(term); q-next = NULL; 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 expn) f = p-coef;i = p-expn; p-coef = q-coef;p-exp
10、n = 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) printf(%g,q-coef); if
11、(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); 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)
12、 putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); q = q-next; Compare(term *a, term *b) if (a-expn expn) return -1; if (a-expn b-expn) return 1; return 0; term* APolyn(term *Pa, term *Pb)/ 多项式加法：Pa = PaPb，利用两个多项式的结点构成和多项式。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (te
13、rm*)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 != 0.0) / 修改多项式PA中当前结点的系数值 p-next = qa; qa-coef = sum; p = qa; qa = qa-next; else / 删除多项式
14、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 *P
15、b) int n; puts(再输入一元多项式的项数); scanf(%d,&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); if(Pb & Pb-coef0) 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
16、 = 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,&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa); printf( - ); putchar();PrintfPoly(Pb);putchar(); Pa = BPolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); Pr
17、intfPoly(Pa); return Pa; term* CPolyn(term *Pa, term *Pb) /多项式乘法：Pa = Pa*Pb，利用两个多项式的结点构成积多项式。 if(!Pb) return NULL; term *pa = Pa, *p, *q, *r, *s, *t; r = p = (term*)malloc(sizeof(term); while(pa) p-coef = pa-coef; p-expn = pa-expn; q = p; p = p-next = (term*)malloc(sizeof(term); pa = pa-next; q-next
18、 = NULL; free(p); pa = Pa; t = s = (term*)malloc(sizeof(term); while(pa) q = s; s = s-next = (term*)malloc(sizeof(term); pa = pa-next; q-next = NULL; free(s); pa = Pa; while(pa) pa-coef *= Pb-coef; pa-expn += Pb-expn; pa = pa-next; Pb = Pb-next; while(Pb) p = r; s = t; while(p) s-coef = p-coef * Pb-
19、coef; s-expn = p-expn + Pb-expn; p = p-next; s = s-next; Pa = APolyn(Pa,t); Pb = Pb-next; return Pa; / CPolyn term* C(term *Pa, term *Pb) int n; puts(再输入一元多项式的项数); scanf(%d,&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); putchar();PrintfPoly(Pa);putchar(); printf( * ); putchar();PrintfPoly(Pb);putchar
20、(); printf( = ); Pa = CPolyn(Pa,Pb); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() term *M,*N; char s2; int i,n; puts(一元多项式计算:n输入一元多项式的项数); scanf(%d,&n); M = CreatPolyn(M,n); M = selsort(M); PrintfPoly(M); p: puts(n1:加n2:减n3:乘n4:退出); getchar(); q: gets(s); if(s1!=0 | !isdigit(*s) puts(输入有
21、误,请重新输入!);goto q; i = *s-48; switch(i) case 1:M = A(M,N);goto p; case 2:M = B(M,N);goto p; case 3:M = C(M,N);goto p; case 4:break; default:puts(输入有误,请重新输入!);goto q; 7.2 顺序表操作验证：#include #include #include typedef struct term /项的表示，多项式的项作为LinkList的数据元素 int expn; /指数 struct term *next; term, *LinkList;
22、 term* CreatPolyn(term *P,int m) / 输入m项的系数和指数，建立表示一元多项式的有序链表P if(m = 0) return NULL; term *h = P = (term*)malloc(sizeof(term), *q; int i; printf(输入整数要有空格，ex:2 2 3 1n,m); for (i = 1; i expn); q=P; P = P-next = (term*)malloc(sizeof(term); q-next = NULL; free(P); return h; / CreatPolyn void FindData(te
23、rm *p, int data) term *q=p; while(q) if(q-expn=data) break; else q=q-next; if(q) printf(查找到数据n); term* DeleteData(LinkList *p, int data) LinkList *q; term *h; term *r; q=p; h=r=*p; if(!q) printf(连表为空); return h; while(*q) if(*q)-expn=data) term *t=(*q); r-next=t-next; free(t); break; else r=*q; (*q)
24、=(*q)-next; return h;void PrintList(term *h) printf(连表数据:n); while(h) printf(%d , h-expn); h=h-next; term *InsertData(LinkList *p, int fData, int iData) LinkList *q; term *r,*h; term* data; q=p; r=*q; h=*q; if(!q) printf(连表为空); return h; while(*q) if(*q)-expn=fData) data= (term *)malloc(sizeof(term)
25、; data-expn=iData; data-next=(*q); r-next=data; break; else r=*q; (*q)=(*q)-next; return h;void main() term *M,*N; char s2; int i,n,data1,data2; puts(请输入数据个数); scanf(%d,&n); M = CreatPolyn(M,n); PrintList(M); p: puts(n1:查找n2:删除n3:插入n4:退出); getchar(); q: gets(s); if(s1!=0 | !isdigit(*s) puts(输入有误,请重新输入!);goto q; i = *s-48; switch(i) case 1: puts(请输入查找数据); scanf(%d,&data1); FindData(M,data1); goto p; case 2: puts(请输入需要删除的数据); scanf(%d,&data1); M=DeleteDa
