数据结构实验线性表的链式存储结构

《数据结构实验线性表的链式存储结构》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、南昌航空大学实验报告课程名称：数据结构实验名称：实验一线性表的链式存储结构班级：080611学生姓名：冯武明学号：16指导教师评定：XXX签名:XXX题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。一、需求分析⒈先构造两个多项式链表，实现两个多项式的和及删除和值为零元素的操作，不同用户输入的多项式不同。⒉在演示过程序中，用户需敲击键盘输入多项式，即可观看结果。⒊程序执行的命令包括：（1）构造多项式链

2、表pa（2）构造多项式链表pb（3）求两张链表的和（4）删除和值为零元素，即不创建链表结点。二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADTStack{数据对象：D={ai:

3、ai∈ElemSet,i=1…n,n≥0}数据关系：R1={

4、ai-1,ai∈D,i=2,…n≥0}基本操作:init(list*L)操作结果：构造一个空的线性表L。ListLength(List*L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。GetElem(ListL,i

5、nti,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是否有≤的关系。Locat

6、eElem(List*La,ElemTypee,inttype)初始条件：线性表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(ListL)初始条件：线性表L

7、已经存在操作结果：打印出表L。ListInsert(List*L,inti,structSTUe)初始条件：线性表L已经存在，1≤i≤ListLength(&L)+1操作结果：在表L中第i个位置前插入元素e，L的长度加1。}ADTList2.本程序有三个模块：⑴主程序模块voidmain(){初始化；{接受命令；显示结果；｝｝⑵链表单元模块：实现表抽象数据类型；⑶结点结构单元模块：定义线性表中的结点结构。三、详细设计⒈元素类型，结点类型typedefstructnode{intcoef;inte

8、xpn;structnode*next;}node;node*pa,*pb,*pc,*p;inti,n,m;2.对抽象数据类型中的部分基本操作的伪码算法如下：node*creat(node*p,intn){node*l;inti;p=(node*)malloc(sizeof(node));p->next=NULL;printf("inputthenodedate:");for(i=n;i>=1;i--){l=(node*)malloc(sizeof(node));scanf("%d%d",&

9、l->coef,&l->expn);l->next=p->next;p->next=l;printf("");}returnp;}//创建链表structnode*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->expn>pb->next->expn){l=(no

10、de*)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;