数据结构-上海交通大学网络教育课程

1、-10 -上海交通大学网络教育数据结构协同作业实验线性表1 顺序表操作验证21.1 实验目的21.2 实验内容22 一元多项式相加实验 23 开发环境24 算法设计介绍34.1 设计思路 34.2 详细设计65 界面流程展示76 检查及测试报告96.1 检查报告96.2 测试报告97 附程序源代码107.1 一元多项式验证： 107.2 顺序表操作验证： 16-2 -1顺序表操作验证1.1实验目的(1) 掌握线性表的顺序存储结构；(2) 验证顺序表及其根本操作的实现；(3) 掌握数据结构及算法的程序实现的根本方法.1.2实验内容(1) 建立含有假设干个元素的顺序表；(2) 对已建立的顺序表实现

2、插入、删除、查找等根本操作.2 一元多项式相加实验 A( x ) = a0 + a1x + a2x + +ax 和 b(x)= b0 + b1x + b2x + +amXm,并在 A( x )和B( x )中指数相差很多,求A( x ) = A( x ) + B(x).3开发环境软件平台：Win dows XP软件环境：Microsoft Visual C+ 6.0最低硬件配置：内存 64MB或以上、硬盘 3.2G或以上-3 -4算法设计介绍4.1设计思路分析：1 存储结构分析根据一元多项式的特点,要表示一个多项式,只要存储第i项以及ai的值,并且如果ai为0的话,该项就不用存储了,从而减少一

3、个存储空间.在线性表中可以通过顺序和链式存储, 并用Ti表示一个数据项 Ti=( ai,i ).下面以图示表示两种存储结构(假设a2=0).图2单链表存储T0T1T3Tn图1顺序存储表1-4 -以上两个图可知,在存储空间分配量上两种结构是一致的,但如果两多项式相加的话需要频繁的做插入操作,顺序表的结构特性决定了插入操作的时间复杂度为0(n/2),链式表的时间复杂度为 0(1),并且如果存储的是一个排好序的多项式的话,不需要双向查找,因此 选择单链表存储.2 相加算法分析首先,由于两个多项式A(x)和B(x)的指数相差非常多,因此一定要把输入的多项式根据指数i排好序,预防过高的查找时间复杂度；其

4、次,两个 AB多项式同时从head开始查找, AB指数i相同的计算相加ai值存入A表,并且回收不需要的 B空间,指数不同的,B指数 小的节点插到A指数大的前面.以此往后推移.其时间复杂度为|0(n).举例：A(x)=2+3x+1x3B(x)=1+3x+2x2+2x4+12x7+32x8+42x11+2x12整个相加过程如下：见注释1Data区域20表示该节点的系数为2指数为0-10 -图3 初始化后的A(x) pA=headA-20 -图 4 初始化后的 B(x) pB=HeadB->next步:图 5 A(x) pA->next 系数+ pB 系数图 6 B(x) pA->

5、next指数0与pB指数0相等free pB所指节点第二步与第一步做法一致第三步 将pB的节点插入pA后127Next328Next4211NextII pBl124Next212A第四步pA->next 指数小于pB指数,pA=pA->next, pB不动127Next328Next4211Next24Next212A第五步pA没有后继节点,直接把pB的所有节点接到 pA后即可4.2详细设计a)数据结构typedef struct term float coef; / 系数 int exp n; / 指数 struct term *next / 指向下一节点 termb 输入输出

6、输入：两个多项式 A,B输出：A+B样式：输入一元多项式的项数2请依次输入非零2个非零项,请注意输入格式2 23 33XA3+2XA214 + - *退出4个选项再输入一元多项式的项数3请依次输入非零3个非零项,请注意输入格式2 23 34 43XA3+2XA2+4XA4+3XA3+2XA2 = 4乂人4+6乂人3+4乂人2c)函数原型主函数：void mai n()输入函数：InputPolynomial(LinkList&p)多项式相加函数：term* APolyn(term *Pa, term *Pb) 多项式相减函数：term* BPolyn(term *Pa, term *P

7、b) 多项式相乘函数：term* CPolyn(term *Pa, term *Pb) 输出函数：void PrintfPoly(term *P)5界面流程展示第一步：先输入第一个“一元多项式的项数第二步,根据一元多项式的项数,输入非零项.注意输入格式,系数和指数之间要有空格.第三步,选择要进行的运算方式编码5 C: VDocuMent s and Set t ingszhaopili桌面Iult inoB.ii al Add it ion ( 1. . . |输入一元多鼓式的项数氐次询入弓个非零项'请注意输入格式系数和指数之间要有空检ex：2 2 3 11 4+4A22 X+3出33

8、f加减乘退6检查及测试报告6.1检查报告检查名称检杳任务完成情况是否安装程序运行环境已经正确设定V程序代码检查程序单位首部有程序说明和修改备注V变量、过程、函数命令符合规那么V程序中有足够的说明信息V修改注释符合要求V类库的使用符合要求V画面及报表格式检查画面及报表格式符合规定需求V程序命名符合格式需求V画面和报表的字段位置和宽度与设计文档一致V6.2测试报告测试任务完成情况是否测试名称功能键、触发键、按钮、菜单、选择项功能正确V数据项关联及限制功能正确V设计文档规定的其他功能读/写/删除操作结果正确V试确各种组合条件之查询或报价正确V性设计文档规定的其他操作非法键容错测试V异常字符容错测试V

9、程序副作用检查V残留文件检查V输入画面效率测试效率测试报表及查询效率测试其他测试7附程序源代码7.1 一元多项式验证：#in clude<stdlib.h>#in clude<stdio.h>#in clude<ctype.h>typedef struct term /项的表示,多项式的项作为LinkList的数据元素float coef; / 系数int exp n; / 指数struct term *n ext;term;term* CreatPolyn(term *P,int m) / 输入m项的系数和指数,建立表示一元多项式的有序链表Pif(m &l

10、t;= 0) return NULL;term *h = P = (term*)malloc(sizeof(term), *q;P->coef = 0.0;int i;printf("依次输入%d个非零项,请注意输入格式,系数和指数之间要有空格,ex:2 2 31n",m);for (i = 1; i <= m; +i) / 依次输入 m个非零项sca nf("%f%d",&P->coef,&P->exp n);if(P->coef)q = P;P = P->n ext = (term*)malloc(

11、sizeof(term);q->next = NULL;free(P);return h; / CreatPoly nterm* selsort(term *h)term *g, *p, *q;if(!h) return NULL;float f;int i, fini = 1;for(g = h;g->n ext&&fin i;g = g->n ext)fini = 0;for(p = h,q = h->n ext;q;p = p->n ext,q = q->n ext)if (p->exp n < q->exp n)f

12、= p->coef;i = p->exp n; p->coef = q->coef;p->exp n = q_>exp n; q->coef = f;q->exp n = i;fini = 1;for(g = h,p = g-> next;p;)if(g->exp n=p_>exp n)g->coef += p->coef;g_>n ext = p_>n ext;q = p;p = p_>n ext;free(q);else if(g- >n ext)g = g-> next;p = p

13、_>n ext;return h; void Prin tfPoly(term *P)term *q = P;if(!q)putchar('O');return;if(q->coef!=1)prin tf("%g",q->coef);if(q->exp n=1) putchar('X');else if(q->exp n) pri ntf("XA%d",q->exp n);else if(!q->exp n) putchar('l');else if(q->e

14、xp n=1) putchar('X');else prin tf("XA%d",q->exp n);q = q_>n ext;while (q)if(q->coef > 0) putchar('+');if(q->coef!=1)prin tf("%g",q->coef);if(q->exp n=1) putchar('X');else if(q->expn) printf("XA%d",q->expn);else if(!q-&g

15、t;exp n) putchar('1');else if(q->exp n=1) putchar('X');else prin tf("XA%d",q->exp n);q = q->n ext;Compare(term *a, term *b)if (a->exp n < b->exp n) retur n -1;if (a->exp n > b->exp n) retur n 1;return 0;term* APoly n(term *Pa, term *Pb)多项式加法：Pa =

16、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->n ext = qb;p = qb;qb = qb->n ext;break;case 0: /两者的指数值相等sum = qa->coef + qb->c

17、oef;if (sum != 0.0)修改多项式PA中当前结点的系数值p->next = qa;qa->coef = sum;p = qa;qa = qa->n ext;else 删除多项式PA中当前结点q = qa;qa = qa->n ext;free(q);q = qb;qb = qb->n ext;free(q);break;case 1: /多项式PB中当前结点的指数值小p->n ext = qa;p = qa;qa = qa->n ext;break; / switch / whileif (Pa) p->next = qa; /链接

18、Pa中剩余结点 if (Pb) p->next = qb; / 链接Pb中剩余结点 q = h;h = h->n ext;free(q);return h; / APoly n term* A(term *Pa, term *Pb)int n;puts("再输入一元多项式的项数");scan f("%d",&n);Pb = CreatPoly n(Pb, n);Pb = selsort(Pb);Prin tfPoly(Pa);if(Pb && Pb->coef>0) printf( + ");Pr

19、in tfPoly(Pb);Pa = APoly n(Pa,Pb);printf("=");Pa = selsort(Pa);Prin tfPoly(Pa);return Pa;term* BPolyn(term *Pa, term *Pb) /多项式减法：Pa = Pa-Pb,利用两个多项式的结点构成 多项式.term *p = Pb;while(p)p->coef *= -1;p = p->n ext;return APoly n(Pa,Pb); / BPoly nterm* B(term *Pa, term *Pb)int n;puts("再输入

20、一元多项式的项数");scan f("%d",&n);Pb = CreatPoly n(Pb, n);Pb = selsort(Pb);Prin tfPoly(Pa);printf("-");putchar('(');Pri ntfPoly(Pb);putchar(')');Pa = BPoly n(Pa,Pb);printf("=");Pa = selsort(Pa);Prin tfPoly(Pa);return Pa;term* CPolyn(term *Pa, term *Pb)

21、 /多项式乘法：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->exp n = pa->exp n;q = p;p = p->n ext = (term*)malloc(sizeof(term);pa = pa->n ext;q->next = NULL;free(p);pa = Pa;t = s = (t

22、erm*)malloc(sizeof(term);while(pa) q = s;s = s->n ext = (term*)malloc(sizeof(term);pa = pa->n ext;q->next = NULL;free(s);pa = Pa;while(pa) pa->coef *= Pb->coef;pa->exp n += Pb->exp n;pa = pa->n ext; Pb = Pb-> next;while(Pb)p = r;s = t;while(p)s->coef = p->coef * Pb-&

23、gt;coef;s->exp n = p->exp n + Pb->exp n;p = p->n ext;s = s->n ext;Pa = APoly n( Pa,t);Pb = Pb->n ext;return Pa; / CPoly nterm* C(term *Pa, term *Pb)int n;puts(再输入一元多项式的项数)；scan f("%d",&n);Pb = CreatPoly n(Pb, n);Pb = selsort(Pb);putchar('(');Pri ntfPoly(Pa);pu

24、tchar(')');printf(" * ");putchar('(');Pri ntfPoly(Pb);putchar(')');printf("=");Pa = CPoly n(Pa,Pb);Pa = selsort(Pa);Prin tfPoly(Pa);return Pa;void mai n()term *M,*N;char s2;int i,n;puts("一元多项式计算：n输入一元多项式的项数");scan f("%d",&n);M = Cre

25、atPoly n(M, n);M = selsort(M);Prin tfPoly(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: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("输入有误,请

26、重新输入);goto q;7.2顺序表操作验证:#in clude<stdlib.h>#in clude<stdio.h>#in clude<ctype.h>typedef struct term /项的表示,多项式的项作为LinkList的数据元素int exp n; / 指数struct term *n ext;term, *L in kList;元多项式的有序链表term* CreatPolyn(term *P,int m) / 输入 m项的系数和指数,建立表示Pif(m <= 0) return NULL;term *h = P = (term

27、*)malloc(sizeof(term), *q;int i;printf("输入整数要有空格,ex:2 2 3 1n",m);for (i = 1; i <= m; +i) /依次输入 m个非零项sca nf("%d",&P->exp n);q=P;P = P->n ext = (term*)malloc(sizeof(term);q->next = NULL;free(P);return h; / CreatPoly nvoid Fin dData(term *p, int data)term *q=p;while(

28、q)if(q->exp n=data)break;elseq=q->n ext;if(q)printf"查找到数据n"-10 -term* DeleteData(L in kList *p, i nt data)Li nkList *q;term *h;term *r;q=p;h=r=*p;if(!q)printf(连表为空); return h;while(*q)if(*q)->exp n=data)term *t=(*q);r->n ext=t- >n ext;free(t);break;elser=*q;(*q)=(*q)-> next;return h;void Prin tList(term *h)printf("连表数据:n");while(h)prin tf("%d ", h->exp n);h=h->n ext;term *InsertData(LinkList *p, int fData, int iData)