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

实验报告

课程名称：数据结构与算法分析 实验名称：链表的实现与应用

实验日期：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;inext=NULL; p->next=s; p=s;

1 / 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->data<=pb->data) {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;

2 / 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->expnexpn) { 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;

3 / 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)

4 / 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->expnexpn) { 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; }

5 / 8

本文来源：https://www.bwwdw.com/article/g9ht.html