数据结构实验《线性表的链式存储结构》.docx

南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验一 线性表的链式存储结构 班 级： 080611 学生姓名： 冯武明 学号： 16 指导教师评定： XXX 签 名: XXX 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析 先构造两个多项式链表，实现两个多项式的和及删除和值为零元素的操作，不同用户输入的多项式不同。 在演示过程序中，用户需敲击键盘输入多项式，即可观看结果。 程序执行的命令包括：（1）构造多项式链表pa （2）构造多项式链表pb （3）求两张链表的和 （4）删除和值为零元素，即不创建链表结点。二、概要设计 为实现上述算法，需要线性表的抽象数据类型：ADT Stack 数据对象：D=ai:|aiElemSet,i=1n,n0数据关系：R1=|ai-1,aiD,i=2,n0基本操作:init(list *L)操作结果：构造一个空的线性表L。ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。 GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1iListLength(&L)操作结果：用e返回L中第i个数据元素的值。EqualList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。Less_EquaList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的来判定e1,e2是否有的关系。LocateElem(List *La,ElemType e,int type)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。MergeList(List *La,List *Lb,List *Lc)初始条件：非递减线性表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 node int coef; int expn; struct node *next; node;node *pa,*pb,*pc,*p;int i,n,m;2. 对抽象数据类型中的部分基本操作的伪码算法如下：node* creat(node *p,int n) node *l; int i; p=(node*)malloc(sizeof(node); p-next=NULL; printf(input the node date:n); for(i=n;i=1;i-) l=(node*)malloc(sizeof(node); scanf(%d%d,&l-coef,&l-expn); l-next=p-next; p-next=l; printf(n); return p;/创建链表struct node* add(node *pa,node *pb,node *pc) node *l,*q; pc=(node*)malloc(sizeof(node); pc-next=NULL; p=pc; while(pa-next!=NULL&pb-next!=NULL) if(pa-next-expnpb-next-expn) l=(node*)malloc(sizeof(node); l-expn=pa-next-expn; l-coef=pa-next-coef; p-next=l; l-next=NULL; p=p-next; pa=pa-next; if(pa-next-expnnext-expn) l=(node*)malloc(sizeof(node); l-expn=pb-next-expn; l-coef=pb-next-coef; p-next=l; l-next=NULL; p=p-next; pb=pb-next; if(pa-next-expn=pb-next-expn) if(pa-next-coef)+(pb-next-coef)=0) pa=pa-next; pb=pb-next; else l=(node*)malloc(sizeof(node); l-expn=pa-next-expn; l-coef=(pa-next-coef)+(pb-next-coef); pa=pa-next; p-next=l; l-next=NULL; p=p-next; pb=pb-next; p-next=NULL; while(pa-next!=NULL) l=(node*)malloc(sizeof(node); l-coef=pa-next-coef; l-expn=pa-next-expn; p-next=l; p=l; l-next=NULL; pa=pa-next; while(pb-next!=NULL) l=(node*)malloc(sizeof(node); l-coef=pb-next-coef; l-expn=pb-next-expn; p-next=l; p=l; l-next=NULL; pb=pb-next; return pc;/将两多项式相加3. 主函数void main() node* creat(node *p,int n);struct node* add(node *pa,node *pb,node *pc);printf(input the pa n:n);scanf(%d,&n);printf(n);pa=creat(pa,n);printf(n);printf(y=);while(pa-next!=NULL) printf(%+dx(%d),pa-next-coef,pa-next-expn); pa=pa-next; printf(n);printf(input the pb m:n);scanf(%d,&m);printf(n);pb=creat(pb,m);printf(n);printf(y=);while(pb-next!=NULL) printf(%+dx(%d),pb-next-coef,pb-next-expn); pb=pb-next; printf(n);printf(nnn);pc=add(pa,pb,pc);printf(the pc date:n);printf(n);printf(y=);while(pc-next!=NULL) printf(%+dx(%d),pc-next-coef,pc-next-expn); pc=pc-next; printf(nn); getch();4 .函数调用关系mainInitialization Makelinklist OperateList ReadCommand printList addlinklistist creatlinklist creatlinklist 四、调试分析1 该程序主要是运用链表对两个多项式进行相加，在调试程序过程中，算法倒是没有出现什么问题，主要是语法出现大量错误，指针调用、指针指向总是被搞混淆，导致浪费大量时间，最后程序调试成功后确不能输出结果，发现是程序没有返回值，加上retrn()即可。 程序采用逐个输入的方法创建pa,p，在元素较多时，会使得程序很庞大，不利于检查错误等。本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。五、用户手册1 本程序的运行环境为windows xp操作系统，执行文件为lianbiao.c；2 进入演示程序后，按规定多项式后便可看到结果，按任意键退出。 六、测试结果1、键入多项式：y=；y=2、输出结果3、 键入任意字符，退出演示界面，回到编辑状态。七、附录：题一源程序#include#includetypedef struct node int coef; int expn; struct node *next; node;node *pa,*pb,*pc,*p;int i,n,m;void main()node* creat(node *p,int n);struct node* add(node *pa,node *pb,node *pc);printf(input the pa n:n);scanf(%d,&n);printf(n);pa=creat(pa,n);printf(n);printf(y=);while(pa-next!=NULL) printf(%+dx(%d),pa-next-coef,pa-next-expn); pa=pa-next; printf(n);printf(input the pb m:n);scanf(%d,&m);printf(n);pb=creat(pb,m);printf(n);printf(y=);while(pb-next!=NULL) printf(%+dx(%d),pb-next-coef,pb-next-expn); pb=pb-next; printf(n);printf(nnn);pc=add(pa,pb,pc);printf(the pc date:n);printf(n);printf(y=);while(pc-next!=NULL) printf(%+dx(%d),pc-next-coef,pc-next-expn); pc=pc-next; printf(nn); getch();node* creat(node *p,int n) node *l; int i; p=(node*)malloc(sizeof(node); p-next=NULL; printf(input the node date:n); for(i=n;i=1;i-) l=(node*)malloc(sizeof(node); scanf(%d%d,&l-coef,&l-expn); l-next=p-next; p-next=l; printf(n); return p;struct node* add(node *pa,node *pb,node *pc) node *l,*q; pc=(node*)malloc(sizeof(node); pc-next=NULL; p=pc; while(pa-next!=NULL&pb-next!=NULL) if(pa-next-expnpb-next-expn) l=(node*)malloc(sizeof(node); l-expn=pa-next-expn; l-coef=pa-next-coef; p-next=l; l-next=NULL; p=p-next; pa=pa-next; if(pa-next-expnnext-expn) l=(node*)malloc(sizeof(node); l-expn=pb-next-expn; l-coef=pb-next-coef; p-next=l; l-next=NULL; p=p-next; pb=pb-next; if(pa-next-expn=pb-next-expn) if(pa-next-coef)+(pb-next-coef)=0) pa=pa-next; pb=pb-next; else l=(node*)malloc(sizeof(node); l-expn=pa-next-expn; l-coef=(pa-next-coef)+(pb-next-coef); pa=pa-next; p-next=l; l-next=NULL; p=p-next; pb=pb-next;