南昌航空大学实验报告课程名称：数据结构实验名称： 实验一线性表的链式存储结构班 级：080611学生姓名：冯武明学号： 16指导教师评定：XXX 签 名：XXX题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成 多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的 多项式链式。一、需求分析1. 先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入 的多项式不同。2. 在演示过程序中，用户需敲击键盘输入值，即可观看结果。3. 程序执行的命令包括：(1)构造多项式链表A (2)构造多项式链表B (3)求两张链表的和(4)删除值为零元素，即不创建链表。二、概要设计1 为实现上述算法，需要线性表的抽象数据类型：ADT Stack 数据对象：D=a :|a UElemSet,i=ln,n三0ii数据关系：R1=elem=(int*)malloc(listinitsize*sizeof(int);L-length=0;L-listsize=listinitsize; /初始化表void add(sqlist *La,sqlist *Lb,sqlist *Lc)int *pa,*pb,*pc,*pa_last,*pb_last; pa=La-elem;pb=Lb-elem;Lc-listsize=Lc-length=La-length+Lb-length; pc=Lc-elem=(int*)malloc(Lc-listsize)*sizeof(int);pa_last=La-elem+(La-length-1);pb_last=Lb-elem+(Lb-length-1); while(pa=pa_last&pb=pb_last)if(*pa_last*pb_last)*pc+=*pb_last-;else*pc=*pa_last;pc+;pa_last-;pb_last-; while(pa=pa_last) *pc=*pa_last-;while(pb=pb_last)*pc=*pb_last-;/将两个表合并成 Lc3. 主函数void main()void initlist(sqlist *L);void add(sqlist *La,sqlist *Lb,sqlist *Lc);sqlist *La,*Lb,*Lc;int i,p,num;initlist(La);initlist(Lb);initlist(Lc);printf(please input the numbers of you want about La:n); scanf(%d,&num);printf(n); for(i=0;ielemi=p; La-length+;printf(please input the numbers of you want about Lb:n); scanf(%d,&num);printf(n); for(i=0;ielemi=p; Lb-length+;printf(nnnnthe list of La:n); for(i=0;ilength;i+) printf(%6d,La-elemi);printf(nnnnthe list of La:n); for(i=0;ilength;i+) printf(%6d,Lb-elemi);printf(nnn);add(La,Lb,Lc);printf(nnnthe list of Lc:n); for(i=0;ilength+Lb-length;i+)printf(%6d,Lc-elemi);getch();4 . 函数调用关系mainMakeListReadCommandInitializationOperateListprintListTaddList*initlistinitlist四、调试分析1. 调试程序时，因为没有注意到指针变量与普通变量对成员的引用所用符号不同，将指针 变量引用所用符号写成 .，导致程序出现大量错误，耽误了大量的调试时间。警告 shunxul.c 18:可能在La 定义以前使用了它在main函数中，将La放在main前即 可消除警告。注意定义各线性表变量为指针变量，这样可以返回函数。2程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错 误等。3. 算法的时空分析各操作的算法时间复杂度比较合理Init ()为 0(1), void add()为 0(mn)。4. 本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使 调试也较顺利，各模块有较好的可重用性。五、用户手册1. 本程序的运行环境为windows xp操作系统，执行文件为shunxubiao.c；2. 进入演示程序后，按规定输入数值后便可看到结果，按任意键退出。六、测试结果1、键入数值2、输出结果thelisto La :654thelisto La:931t：helistof Lc :134Ei693、键入任意字符，退出演示界面，回到编辑状态。七、附录：题一源程序#include#define listinitsize 20#define listincrement 10typedef structint*elem;intlength;intlistsize;sqlist;main()void initlist(sqlist *L);void add(sqlist *La,sqlist *Lb,sqlist *Lc);sqlist *La,*Lb,*Lc;int i,p,num;initlist(La);initlist(Lb);initlist(Lc);printf(please input the numbers of you want about La:n); scanf(%d,&num);printf(n);for(i=0;ielemi=p;La-length+;printf(please input the numbers of you want about Lb:n); scanf(%d,&num);printf(n);for(i=0;ielemi=p;Lb-length+;printf(nnnnthe list of La:n);for(i=0;ilength;i+)printf(%6d,La-elemi);printf(nnnnthe list of La:n);for(i=0;ilength;i+)printf(%6d,Lb-elemi);printf(nnn);add(La,Lb,Lc);printf(nnnthe list of Lc:n);for(i=0;ilength+Lb-length;i+)printf(%6d,Lc-elemi);getch();void add(sqlist *La,sqlist *Lb,sqlist *Lc)int *pa,*pb,*pc,*pa_last,*pb_last;pa=La-elem;pb=Lb-elem; Lc-listsize=Lc-length=La-length+Lb-length; pc=Lc-elem=(int*)malloc(Lc-listsize)*sizeof(int);pa_last=La-elem+(La-length-1);pb_last=Lb-elem+(Lb-length-1);while(pa=pa_las