数据结构实验线性表的顺序存储结构.docx

南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验一 线性表的链式存储结构 班 级： 080611 学生姓名： 冯武明 学号： 16 指导教师评定： XXX 签 名: XXX 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析 先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入的多项式不同。 在演示过程序中，用户需敲击键盘输入值，即可观看结果。 程序执行的命令包括：（1）构造多项式链表A （2）构造多项式链表B （3）求两张链表的和 （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是否相等的依据。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中表尾的位置。PrintList(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,*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=(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 .函数调用关系mainInitialization MakeList OperateList ReadCommand printList addList initlist initlist 四、调试分析1 调试程序时，因为没有注意到指针变量与普通变量对成员的引用所用符号不同，将指针变量引用所用符号写成.，导致程序出现大量错误，耽误了大量的调试时间。警告 shunxu1.c 18: 可能在La定义以前使用了它在 main 函数中，将La放在main前即可消除警告。注意定义各线性表变量为指针变量，这样可以返回函数。 程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 算法的时空分析各操作的算法时间复杂度比较合理Init（）为O(1)，void add()为O(mn)。 4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统，执行文件为shunxubiao.c； 进入演示程序后，按规定输入数值后便可看到结果，按任意键退出。 六、测试结果1、键入数值2、输出结果3、 键入任意字符，退出演示界面，回到编辑状态。七、附录：题一源程序#include#define listinitsize 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(%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_last&pb=pb_