线性表的链式存储结构实验报告.doc

南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验二：线性表的链式存储结构班 级： 080611 学生姓名： 赖凌 学号： 08061101指导教师评定： 签 名: 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。 一、需求分析 实现两张线性表的链式存储，合并及删除值相同元素的操作。 在演示过程序中，用户敲击键盘，即可观看演示结果。 程序执行的命令包括：（1）构造线性链表A （2）构造线性链表B （3）求两张表的并 （4）删除C中值相同的元素二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT LinkList List 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R1=|ai-1,aiD,i=2,n0基本操作:Status InitList( LinkList &L)/操作结果：构造一个空的线性链表L。Status MakeNode ( Link &p, ElemType e );/ 分配由p指向的值为e 的结点，并返回；若分配失败，则返回Status Append (LinkList &L,Link s);/将指针s所指（彼此以指针相链接）的一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点Status ListEmpty(LinkList L);/若线性链表L为空表，则返回TRUE，否则返回ERROR。 Int ListLength(LinkList L); /返回线性链表中L最后一个结点的位置。 ElemType GetCurElem(Link p); /已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 Position GetHead (LinkList L); /返回线性链表L中头结点的位置 Position GetLast( LInkList L); /返回线性链表L中最后一个结点的位置ADT LinkList2. 本程序有三个模块： 主程序模块void main()初始化；接受命令；显示结果； 线性链表单元模块：实现线性链表抽象数据类型； 结点结构单元模块：定义线性链表中的结点结构。三、详细设计元素类型，结点类型struct node int date; struct node *next;2.对抽象数据类型中的部分基本操作的伪码算法如下：struct node * creat() struct node *head,*pa,*pb; head=(struct node *)malloc(sizeof(struct node); if(!head) exit(0); pa=head; pb=(struct node *)malloc(sizeof(struct node); if(!pb) exit(0); scanf(%d,&pb-date); if(!pb-date) head-next=NULL; free(pb); return head; while(pb-date) pa-next=pb; pa=pb; pb=(struct node *)malloc(sizeof(struct node); if(!pb) exit(0); scanf(%d,&pb-date); pa-next=NULL; free(pb); return head;void print(struct node*l) struct node *p;int i=0; p=l-next; if(p) while(p) if(i%5=0) printf(n); printf(%6d,p-date); p=p-next; i+; else printf(The list you haved created is NULL!nn); printf(nn);void addlist(struct node *la,struct node *lb,struct node *lc) struct node *pa,*pb,*pc,*q; pa=la-next; pb=lb-next; pc=lc; while(pa&pb) if(pa-datedate) if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next; else pa=pa-next; else if(pa-datepb-date) if(!(pc-next)|pc-date!=pb-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pb-date; pc-next=q; pc=q; pb=pb-next; else pb=pb-next; else if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next;pb=pb-next; else pa=pa-next;pb=pb-next; while(pa) if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next; else pa=pa-next; while(pb) if(!(pc-next)|pc-date!=pb-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pb-date; pc-next=q; pc=q; pb=pb-next; else pb=pb-next; pc-next=NULL;3.主函数的伪码算法void main()struct node *la,*lb,*lc; printf(Warning:the last element must be ended by 0 !nn); printf(Please input the elements of La:n); la=creat(); printf(Please input the elements of Lb:n); lb=creat(); printf(The La you have created is:n); print(la); printf(The Lb you have created is :n); print(lb); lc=(struct node *)malloc(sizeof(struct node); if(!lc) exit(0); lc-next=NULL; addlist(la,lb,lc); printf(The merged list Lc is:n); print(lc); getch();4 函数调用关系mainCreat() Print() Addlist () Print() 四、调试分析 刚开始输入时，漏掉了一些变量参数的标记*，有的则错加了*,有时候少了“”或者“”使得程序运行出来的结果不正确，使调试程序时费时不少。由于使用的是WINTC，最后要加上getch()语句要不然的结果显示不出来，影响调试。 程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 算法的时空分析各操作的算法时间复杂度比较合理4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册 本程序的运行环境为windows xp操作系统，执行文件为Exp1Prb1.c； 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面，用户键入任一符号，都能看完整个演示过程。六、测试结果七、附录：题一源程序/-头文件 #include#include#include#define NULL 0struct node int date; struct node *next;struct node * creat() /*建立线性链表*/ struct node *head,*pa,*pb; head=(struct node *)malloc(sizeof(struct node); if(!head) exit(0); pa=head; pb=(struct node *)malloc(sizeof(struct node); if(!pb) exit(0); scanf(%d,&pb-date); if(!pb-date) head-next=NULL; free(pb); return head; while(pb-date) pa-next=pb; pa=pb; pb=(struct node *)malloc(sizeof(struct node); if(!pb) exit(0); scanf(%d,&pb-date); pa-next=NULL; free(pb); return head;void print(struct node*l) /*输出函数*/ struct node *p;int i=0; p=l-next; if(p) while(p) if(i%5=0) printf(n); printf(%6d,p-date); p=p-next; i+; else printf(The list you haved created is NULL!nn); printf(nn);void addlist(struct node *la,struct node *lb,struct node *lc) /*合并操作*/ struct node *pa,*pb,*pc,*q; pa=la-next; pb=lb-next; pc=lc; while(pa&pb) if(pa-datedate) if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next; else pa=pa-next; else if(pa-datepb-date) if(!(pc-next)|pc-date!=pb-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pb-date; pc-next=q; pc=q; pb=pb-next; else pb=pb-next; else if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next;pb=pb-next; else pa=pa-next;pb=pb-next; while(pa) if(!(pc-next)|pc-date!=pa-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pa-date; pc-next=q; pc=q; pa=pa-next; else pa=pa-next; while(pb) if(!(pc-next)|pc-date!=pb-date) q=(struct node *)malloc(sizeof(struct node); if(!q) exit(0); q-date=pb-date; pc-next=q; pc=q; pb=pb-next; else pb=pb-next; pc-next=NULL;void main()struct node *la,*lb,*lc; printf(Warning:the last element must be ended by 0 !nn); printf(Please input the elements of La:n); la=creat(); /*建表A*/ printf(Please input the elements of Lb: