1、数据结构实验线性表的顺序存储结构南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验一 线性表的链式存储结构 班 级： 080611 学生姓名： 冯武明 学号： 16 指导教师评定： XXX 签 名: XXX 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析 先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入的多项式不同。 在演示过程序中，用户需敲击键盘输入值，即可观看结果。 程序执行的命令包括： （1）构造多项式链表A （2）构造多项式链表B （3）求
2、两张链表的和 （4）删除值为零元素，即不创建链表。二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Stack 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R1=|ai-1,aiD,i=2,n0基本操作:init(linklist *L)操作结果：destroylist(List *L)clearlist(List *L)初始条件：线性表L已经存在，1iListLength(&L)操作结果：用e返回L中第i个数据元素的值。insfirst(link h,link s)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的
3、依据。 delfirst(link h,link *q)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的来判定e1,e2是否有 的关系。append(linklist *L,link s)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。remove(linklist *L,link *q)初始条件：非递减线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。UnionList(List *La ,List *Lb)初始条件：线性表La，Lb已经存在操作结果：将所有在Lb而不在La中的元素插入到La中表尾的位置。Pr
4、intList(List L)初始条件：线性表L已经存在操作结果：打印出表L。ListInsert(List *L, int i, struct STU e)初始条件：线性表L已经存在，1iListLength(&L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。 ADT List2. 本程序有三个模块： 主程序模块void main()初始化；接受命令；显示结果； 链表单元模块：实现表抽象数据类型；三、详细设计 元素类型，结点类型 typedef struct int *elem; int length; int listsize; sqlist; sqlist *La,*Lb
5、,*Lc; 2. 对抽象数据类型中的部分基本操作的伪码算法如下：void initlist(sqlist *L) L-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
6、=(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 m
7、ain() 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 wan
8、t 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+) prin
9、tf(%6d,Lc-elemi); getch();4 .函数调用关系mainInitialization MakeList OperateList ReadCommand printList addList initlist initlist 四、调试分析1调试程序时，因为没有注意到指针变量与普通变量对成员的引用所用符号不同，将指针变量引用所用符号写成.，导致程序出现大量错误，耽误了大量的调试时间。警告 shunxu1.c 18: 可能在La定义以前使用了它在 main 函数中，将La放在main前即可消除警告。注意定义各线性表变量为指针变量，这样可以返回函数。 程序采用逐个输入的方法创建L
10、a,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 算法的时空分析 各操作的算法时间复杂度比较合理 Init（）为O(1)，void add()为O(mn)。 4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统，执行文件为shunxubiao.c； 进入演示程序后，按规定输入数值后便可看到结果，按任意键退出。 六、测试结果1、键入数值2、输出结果3、 键入任意字符，退出演示界面，回到编辑状态。七、附录：题一源程序#include#define listini
11、tsize 20#define listincrement 10typedef struct int *elem; int length; int listsize; 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
12、(%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-elem
13、i); 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)*
14、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(pbelem=(int*)malloc(listinitsize*sizeof(int); L-length=0; L-listsize=listinitsize; （注：文档可能无法思考全面，请浏览后下载，供参考。可复制、编制，期待你的好评与关注）
