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

南昌航空大学实验报告课程名称：数据结构 实验名称： 实验一线性表的链式存储结构 班级： 080611 学生姓名： 冯武明 学号： 16 指导教师评定： XXX 签名: XXX 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析⒈ 先构造两个多项式链表，实现两个多项式的和及删除和值为零元素的操作，不同用户输入的多项式不同。⒉ 在演示过程序中，用户需敲击键盘输入多项式，即可观看结果。⒊ 程序执行的命令包括：（1）构造多项式链表pa （2）构造多项式链表pb （3）求两张链表的和 （4）删除和值为零元素，即不创建链表结点。二、概要设计⒈ 为实现上述算法，需要线性表的抽象数据类型：ADT Stack{数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n≥0}基本操作:init(list *L)操作结果：构造一个空的线性表L。ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。 GetElem(List L, inti,ElemType *e)初始条件：线性表L已经存在，1≤i≤ListLength(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,ElemTypee,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, inti, struct STU e)初始条件：线性表L已经存在，1≤i≤ListLength(L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。}ADT List2. 本程序有三个模块：⑴ 主程序模块void main(){初始化；{接受命令；显示结果；｝｝⑵ 链表单元模块：实现表抽象数据类型；⑶ 结点结构单元模块：定义线性表中的结点结构。三、详细设计⒈ 元素类型，结点类型typedefstruct node {intcoef;intexpn;struct node *next; } node;node *pa,*pb,*pc,*p;inti,n,m;2. 对抽象数据类型中的部分基本操作的伪码算法如下：node* creat(node *p,int n){node *l;inti; 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!=NULLpb-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