线性表的链式存储结构实验报告_线性表的链式存储实验
线性表的链式存储结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“线性表的链式存储实验”。
实验报告
课程名称：数据结构与算法分析 实验名称：链表的实现与应用
实验日期：2015.01.30 班级： 数媒1401 姓名： 范业嘉 学号 1030514108
一、实验目的 掌握线性表的链式存储结构设计与基本操作的实现。
二、实验内容与要求
⑴定义线性表的链式存储表示；
⑵基于所设计的存储结构实现线性表的基本操作；
⑶编写一个主程序对所实现的线性表进行测试；
⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用
线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。
⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。
三、数据结构设计
1.按所用指针的类型、个数、方法等的不同，又可分为：
线性链表（单链表）
静态链表
循环链表
双向链表
双向循环链表
2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。
四、算法设计
1.定义一个链表
void creatlist(Linklist &L,int n){ int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i
s=(Linklist)malloc(sizeof(Lnode));
scanf(“%d”,&s->data);
s->next=NULL;
p->next=s;
p=s;
/ 8
} } 2.（1）两个链表的合并
void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc){ Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){
if(pa->datadata)
{pc->next=pa;pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb;free(Lb);}（2）两个链表的并集
Linklist unionlist(Linklist &La,Linklist &Lb){ Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){
flag=0;
p2=Lb->next;
while(p2)
{
if(p1->data==p2->data)
{
flag=1;
break;
}
p2=p2->next;
}
if(flag==0)
{
s=(Linklist)malloc(sizeof(Lnode));
s->data=p1->data;
q->next=s;
q=s;
}
p1=p1->next;/ 8
}
q->next=Lb->next;return head;
}
3.（1）一元多项式的加法
List addpoly(List pa,List pb)
//一元多项式的加法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){
if(pa->expn>pb->expn)
{
s=(List)malloc(sizeof(struct Linklist));
s->expn=pa->expn;
s->coef=pa->coef;
s->next=NULL;
p->next=s;
p=s;
pa=pa->next;
}
else if(pa->expn
expn)
{
s=(List)malloc(sizeof(struct Linklist));
s->expn=pb->expn;
s->coef=pb->coef;
s->next=NULL;
p->next=s;
p=s;
pb=pb->next;
}
else
{
n=pa->coef+pb->coef;
if(n!=0)
{
s=(List)malloc(sizeof(struct Linklist));
s->expn=pa->expn;/ 8
s->coef=n;
s->next=NULL;
p->next=s;
p=s;
}
pb=pb->next;
pa=pa->next;
} } while(pa!=NULL){
s=(List)malloc(sizeof(struct Linklist));
s->expn=pa->expn;
s->coef=pa->coef;
s->next=NULL;
p->next=s;
p=s;
pa=pa->next;} while(pb!=NULL){
s=(List)malloc(sizeof(struct Linklist));
s->expn=pb->expn;
s->coef=pb->coef;
s->next=NULL;
p->next=s;
p=s;
pb=pb->next;} return pc;}
（2）一元多项式的减法
List subpoly(List pa,List pb)
//一元多项式的减法 { int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){
if(pa->expn>pb->expn)
/ 8
{
s=(List)malloc(sizeof(struct Linklist));
s->expn=pa->expn;
s->coef=pa->coef;
s->next=NULL;
p->next=s;
p=s;
pa=pa->next;} else if(pa->expn
expn){
s=(List)malloc(sizeof(struct Linklist));
s->expn=pb->expn;
s->coef=-pb->coef;
s->next=NULL;
p->next=s;
p=s;
pb=pb->next;} else {
n=pa->coef-pb->coef;
if(n!=0)
{
s=(List)malloc(sizeof(struct Linklist));
s->expn=pa->expn;
s->coef=n;
s->next=NULL;
p->next=s;
p=s;
}
pb=pb->next;
pa=pa->next;} } while(pa!=NULL){ s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}/ 8
while(pb!=NULL){
s=(List)malloc(sizeof(struct Linklist));
s->expn=pb->expn;
s->coef=-pb->coef;
s->next=NULL;
p->next=s;
p=s;
pb=pb->next;} return pc;}（3）一元多项式的乘法
void mulpolyn(polynomail pa,polynomail pb,polynomail &pc){
LNode *p,*q,*s,*hc;p=pa->next;q=pb->next;hc=pc;while(p!=NULL){
while(q!=NULL)
{
s=(polynomail)malloc(sizeof(LNode));
hc->next=s;
hc=hc->next;
hc->coef=q->coef*p->coef;
hc->expn=q->expn+p->expn;
q=q->next;
}
p=p->next;
q=pb->next;} hc->next=NULL;}
/ 8
五、测试结果
2.3.7 / 8
六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）
1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。
2.当写一元多项式的加减时，前提是弄清楚各种情况，系数相同时就相加减，系数不同就保留原有多项式；当系数相加减为0时，就free这个节点。在做减法时，我考虑到了减数与被减数之间的关系。
3.在做多项式时，我准备按照书上的算法一个一个写小函数，结果到最后发现写不下去了，就去问问同学和上网看看，结果感觉写这个数据结构的程序其实不必想麻烦了，只是指针，数组的高级运用。
/ 8
