线性表的链式存储结构设计.doc

实验一：设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C。 实验二：设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减。 实验目的：掌握线性表的链式存储结构设计与基本操作的实现。 实验内容与要求： ⑴定义线性表的链式存储表示； ⑵基于所设计的存储结构实现线性表的基本操作； ⑶编写一个主程序对所实现的线性表进行测试； 3.数据结构设计 实验一： 逻辑结构：线性结构 存储结构：链式存储结构 实验二： 逻辑结构：线性结构 存储结构：链式存储结构 4.算法设计 实验一 #includestdio.h #includestdlib.h typedef int datatype; typedef struct node { datatype data; //结点值 struct node *next; //存储下一个结点的地址 }LinkList; LinkList *CREATLISTF(LinkList *L,int n) { int num,i; LinkList *head,*s,*r; head=L; r=head; head-next=NULL; printf(请输入集合中的元素(由小到大)：\n); for(i=0;in;i++) { scanf(%d,num); s=(LinkList *)malloc(sizeof(LinkList)); s-data=num; r-next=s; //链接到表中 r=s; //r指向新的尾结点 } r-next=NULL; return head; } LinkList *merge(LinkList *L1,LinkList *L2) { LinkList *L3,*pa,*pb1,*pb2,*pc; L3=(LinkList*)malloc(sizeof(LinkList));//申请结点 L3-next=NULL; //初始化链表L3 pa=L1-next; //pa是链表L1的工作指针,指向第一个结点 pb1=pb2=L2-next; //pb1是链表L2的工作指针,指向第一个结点 pc=L3; //pc是链表L3的工作指针,指向头结点 while(pa pb1) //L1和L2均非空 if(pa-datapb1-data) { //L1中元素插入L3 pc-next=pa; pc=pa; pa=pa-next; } else if(pa-datapb1-data) { //L2中元素插入L3 pc-next=pb1; pc=pb1; pb1=pb1-next; } else { pc-next=pa; pc=pa;pa=pa-next; pb1=pb2=pb1-next; } if(pa) pc-next=pa; //若pa未到尾，将pc指向pa else pc-next=pb1; //若pb1未到尾，将pc指向pb1 return(L3); } void display(LinkList *L) { LinkList *head; head=L-next; do { printf(%d\t,head-data); head=head-next; }while(head!=NULL); } void main() { int an,bn; LinkList *L1,*L2,*L3; L1=(LinkList*)malloc(sizeof(LinkList)); L2=(LinkList*)malloc(sizeof(LinkList)); printf(\n请输入集合A中元素的个数：\n); scanf(%d,an); *L1=*CREATLISTF(L1,an); printf(集合A的元素为：\n); display(L1); printf(\n请输入集合B中元素的个数：\n); scanf(%d,bn); *L2=*CREATLISTF(L2,bn); printf(集合B的元素为：\n); display(L2); L3=merge(L1,L2); printf(交集为：\n); display(L3); } 实验二 typedef struct node { int coef; int exp; struct no