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

《算法设计与分析》实验报告-1-1、实验目的（1)掌握线性表的顺序存储结构和链式存储结构；（2)掌握线性表插入、删除等基本运算；（3)掌握线性表的典型运用——多项式求和。2、实验内容编程实现多项式的求和运算：（1)顺序存储结构的实现例如，已知：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;（2)链式存储结构的实现例如，已知：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。3、实验要求（1)利用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，对于用顺序存储结构实现多项式求和而言，需要设计3个main函数调用的子函数，分别实现创建多项式，多项式相加和显示多项式；对于用链式存储结构实现多项式求和，也同样需要3个这样的子函数，最后，编写程序，并调试程序，得出实验结果。⑵源代码顺序存储结构：#includestdio.h#defineMAXLEN100typedefstruct{intdata[MAXLEN];intlast;}SeqList;《算法设计与分析》实验报告-2-voidadd_List(SeqListA,SeqListB,SeqList*C){inti;C-last=A.lastB.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;}voidmain()《算法设计与分析》实验报告-3-{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);}链式存储结构：#includestdio.h#includemalloc.h#includemath.htypedefstructlinknode{floatcoef;intexpn;structlinknode*next;}Node;voidcreate_link_list(Node*L){Node*p,*q;intn=1;floatx=1;q=L;printf(\n请按多项式指数由大到小输入系数和指数:\n);《算法设计与分析》实验报告-4-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;Lc=La;《算法设计与分析》实验报告-5-pc=Lc;pa=La-next;pb=Lb-next;while(pa&&pb)if(pa-expnpb-expn){pc-next=pa;pc=pa;pa=pa-next;}elseif(pa-expnpb-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;elsepc-next=pb;}voidmain(){《算法设计与分析》实验报告-6-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);}5、测试数据与实验结果（可以抓图粘贴）顺序存储结构的实现调试结果如图所示：链式存储结构的实现调试结果如图所示：《算法设计与分析》实验报告-7-6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。而且，在具体操作中我对顺序存储结构和链式存储结构的优点和缺点有了更深刻的体会，顺序存储结构的算法较为简单，但是在输入的过程中有很大的局限性，必须从大到小依次且连续的输入多项式次数，所以，它只适合最高次数较小的多项式求和，而链式存储结构设计的算法则更灵活，输入时，不需要次数在数值上连续，所以，它更具有普遍性、实用性。再从算法效率的角度来评价，顺序存储结构在做次数大小跨度大的多项式求和时，会浪费很多的存储空间，而链式存储结构则可以充分利用，不会浪费，即其空间复杂度较小。最后，我想说，通过调试程序，我不光学会编程了的基本步骤、基本算法，也使自己更有耐心去做好每一件事情。