数据结构-实验2-多项式求和

数据结构-实验2-多项式求和.实验目的掌握线性表的顺序存储结构和链式存储结构；掌握线性表插入、删除等基本运算；掌握线性表的典型运用——多项式求和。实验内容编程实现多项式的求和运算：顺序存储结构的实现例如，已知：f(x)=8x^6+5x^5-10x^4+32x^2-x+10，g(x)=7x^5+10x^4-20x^3-10x^2+x，求和结果：f(x)+g(x)=8x^6+12x^5-20x^3+22x^2+10。顺序表的定义类型如下：#defineMAXLEN100typedefstruct{intdata[MAXLEN];Intlast;}SeqList;链式存储结构的实现例如，已知：f(x)=100x^100+5x^50-30x^10+10，g(x)=150x^90-5x^50+40x^20-20x^10+3x，求和结果：f(x)+g(x)=100x^100+150x^90+40x^20-10x^10+3x+10。实验要求利用C〔C++〕语言完成程序设计。上机调试通过实验程序。输入数据，检验程序运行结果。给出具体的算法分析，包括时间复杂度和空间复杂度等。撰写实验报告〔把输入实验数据与运行结果用抓图的形式粘贴到实验报告上〕。实验步骤与源程序=1\*GB2⑴实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，对于用顺序存储结构实现多项式求和而言，需要设计3个main函数调用的子函数，分别实现创建多项式，多项式相加和显示多项式；对于用链式存储结构实现多项式求和，也同样需要3个这样的子函数，最后，编写程序，并调试程序，得出实验结果。=2\*GB2⑵源代码顺序存储结构：#include<stdio.h>#defineMAXLEN100typedefstruct{intdata[MAXLEN];intlast;数据结构-实验2-多项式求和全文共7页，当前为第1页。}SeqList;数据结构-实验2-多项式求和全文共7页，当前为第1页。voidadd_List(SeqListA,SeqListB,SeqList*C){inti; C->last=A.last>B.last?A.last:B.last; for(i=0;i<=C->last;i++) C->data[i]=A.data[i]+B.data[i];}voidshow_list(SeqListC){inti;for(i=C.last;i>=1;i--) if(C.data[i]) printf("\(%dx^%d\)+",C.data[i],i);printf("\(%dx^%d\)\n",C.data[0],0);}voidcreate_list(SeqList*D){intn,i;printf("\t\t请输入多项式X的最高次数："); scanf("%d",&n); for(intk=99;k>=0;k--) D->data[k]=0; printf("\t\t请输入多项式X的次数由大到小输入系数，缺少项用0补齐\n");for(i=n;i>=0;i--) { printf("\t\t输入X^%d项的系数:",i); scanf("%d",&D->data[i]); }D->last=n;}数据结构-实验2-多项式求和全文共7页，当前为第2页。voidmain()数据结构-实验2-多项式求和全文共7页，当前为第2页。{SeqListA,B,C;printf("\t\t创建多项式f(x):\n");create_list(&A);printf("\t\tf(x)=");show_list(A);printf("\t\t创建多项式g(x):\n");create_list(&B);printf("\t\tg(x)=");show_list(B);printf("\t\t多项式f(x)和g(x)的和:");add_List(A,B,&C);printf("\n\t\tf(x)+g(x)=");show_list(C);}链式存储结构：#include<stdio.h>#include<malloc.h>#include<math.h>typedefstructlinknode{floatcoef;intexpn;structlinknode*next;}Node;voidcreate_link_list(Node*L){Node*p,*q;intn=1;floatx=1;q=L;数据结构-实验2-多项式求和全文共7页，当前为第3页。数据结构-实验2-多项式求和全文共7页，当前为第3页。printf("提示:系数和指数间用空格间隔，每组数据之间用回车间隔(系数和指数为0时结束输入)\n");while(fabs(x)>0.000001){scanf("%f%d",&x,&n);if(fabs(x)>0.00001){p=(Node*)malloc(sizeof(Node));p->coef=x; p->expn=n;p->next=NULL;q->next=p;q=p;}}}voidshow_link_list(Node*L){ Node*p;p=L->next; while(p&&p->next) {printf("\(%.1fx^%d\)+",p->coef,p->expn); p=p->next; }printf("\(%.1fx^%d\)",p->coef,p->expn); printf("\n");}voidmergelist(Node*La,Node*Lb,Node*Lc)//多项式合并{Node*pa,*pb,*pc;Node*q1,*q2;数据结构-实验2-多项式求和全文共7页，当前为第4页。数据结构-实验2-多项式求和全文共7页，当前为第4页。 pc=Lc;pa=La->next; pb=Lb->next;while(pa&&pb)if(pa->expn>pb->expn) {pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->expn<pb->expn) {pc->next=pb;pc=pb;pb=pb->next;}elseif(fabs(pa->coef+pb->coef)<0.000001) {q1=pa; q2=pb; pa=pa->next;pb=pb->next; free(q1); free(q2); }else{q1=pb;pa->coef=pa->coef+pb->coef;pc->next=pa; pc=pa; pa=pa->next;pb=pb->next; free(q1); }if(pa) pc->next=pa;else pc->next=pb;}voidmain()数据结构-实验2-多项式求和全文共7页，当前为第5页。数据结构-实验2-多项式求和全文共7页，当前为第5页。 Node*LA,*LB,*LC; LA=(Node*)malloc(sizeof(Node));LA->next=NULL; LB=(Node*)malloc(sizeof(Node));LB->next=NULL;LC=LA;create_link_list(LA);printf("f(x)="); show_link_list(LA); create_link_list(LB); printf("g(x)="); show_link_list(LB); mergelist(LA,LB,LC); printf("\nf(x)+g(x)="); show_link_list(LC);}测试数据与实验结果〔可以抓图粘贴〕顺序存储结构的实现调试结果如图所示：数据结构-实验2-多项式求和全文共7页，当前为第6页。数据结构-实验2-多项式求和全文共7页，当前为第6页。结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。而且，在具体操作中我对顺序存储结构和链式存储结构的优点和缺点有了更深刻的体会，顺序存储结构的算法较为简单，但是在输入的过程中有很大的局限性，必须从大到小依次且连续的输入多项式次数，所以，它只适合最高次数较小的多项式求和，而链式存储结构设计的算法则更灵活