数据结构实验报告4

1、数据结构实验报告实验4学号：得分： _一、实验目的1、复习线性表的逻辑结构、存储结构及基本操作；2、掌握顺序表和（带头结点）单链表；3、了解有序表。二、实验容1、（必做题）假设有序表中数据元素类型是整型，请采用顺序表或（带头结点）单链表实现：（ 1） OrderInsert(&L, e, int (*compare)(a, b)/ 根据有序判定函数compare，在有序表L 的适当位置插入元素e；（ 2） OrderInput(&L, int (*compare)(a, b)/ 根据有序判定函数 compare，并利用有序插入函数 OrderInsert，构造有序表 L；（ 3） OrderM

2、erge(&La, &Lb, &Lc, int (*compare)()/ 根据有序判定函数 compare，将两个有序表 La 和 Lb 归并为一个有序表 Lc 。2、（必做题）请实现：（ 1）升幂多项式的构造，升幂多项式是指多项式的各项按指数升序有序，约定系数不能等于0，指数不能小于 0；（ 2）两个升幂多项式的相加。三、算法描述（采用自然语言描述）1.创建带头节点的链表，输入两个有序表数据La Lb归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将 e 插入有序表Lc输出插入e 后的 Lc2.创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式得序数和指数

3、两个多项式相加输出第二个多项式和两个多项式得和四、详细设计（画出程序流程图）1.开始创建带头节点的链表输入两个有序表数据La Lb归并两个有序表得有序表Lc输出三个有序表输入需插入数据e将 e 插入有序表Lc输出插入e 后的 Lc结束2.开始创建链表按指数升序输入多项式得序数和指数输出多项式按指数升序输入第二个多项式两个多项式相加输出第二个多项式和两个多项式的和结束五、程序代码（给出必要注释）1.#include#includetypedef struct LNodeint date;struct LNode *next; LNode,*Link;typedef struct LinkList

4、Link head;/ 头结点int lenth;/ 链表中数据元素的个数 LinkList;int compare (LinkList *L,int e)/有序判定函数compareint Lc=0;Link p;p=L-head;p=p-next;while(p!=NULL)if(ep-date)p=p-next;Lc+;elsereturn Lc;return Lc;void OrderInsert (LinkList *L,int e,int (*compare)()/根据有序判定函数compare，在有序表L 的适当位置插入元素e；Link temp,p,q;int Lc,i;tem

5、p=(Link)malloc(sizeof(LNode);temp-date=e;p=q=L-head;p=p-next;Lc=(*compare)(L,e);if(Lc=L-lenth)while(q-next!=NULL)q=q-next;q-next=temp;temp-next=NULL;elsefor(i=0; inext;q=q-next;q-next=temp;temp-next=p;+L-lenth;void OrderMerge (LinkList *La,LinkList *Lb,int (*compare)()/根据有序判定函数compare ,将两个有序表La 和 Lb

6、 归并为一个有序表int i,Lc=0;Link temp,p,q;q=La-head-next;while(q!=NULL)p=Lb-head;temp=(Link)malloc(sizeof(LNode);temp-date=q-date;Lc=(*compare)(Lb,q-date);if(Lc=Lb-lenth)while(p-next!=NULL)p=p-next;p-next=temp;temp-next=NULL;elsefor(i=0; inext;temp-next=p-next;p-next=temp;q=q-next;+Lb-lenth;LinkList *Initia

7、lize (LinkList *NewList)int i;Link temp;NewList=(LinkList *)malloc(2+1)*sizeof(LinkList);for(i=0; idate=0;temp-next=NULL;(NewList+i)-head=temp;(NewList+i)-lenth=0;return NewList;void Insert (LinkList *NewList)int a,i;char c;printf( 在第 1 个表中插入数据,输入“N ”再对下个表插入数据n);for(i=0; i2; i+)while(1)scanf(%d,&a);

8、c=getchar();if(c=N)if(ihead-next;while(p!=NULL)printf(%d ,p-date);p=p-next;void visit(LinkList *NewList,void (*Show)()printf( 有序表如下 :n);printf( 第一个有序表为:n);(*Show)(NewList+0);printf(n);printf( 第二个有序表为:n);(*Show)(NewList+1);printf(n);printf( 归并后有序表为:n);(*Show)(NewList+2);printf(n);int main()LinkList *

9、NewList=NULL;LinkList *L;int i, e;printf( 请按要求输入数据n);NewList=Initialize(NewList);Insert(NewList);for(i=0; i2; i+)OrderMerge (NewList+i,NewList+2,compare);visit(NewList,Show);L=NewList;printf(n 请输入将要插入的e:n);scanf(%d,&e);OrderInsert(NewList+i),e,compare);printf( 对归并后有序表插入e 后得 n);Show(NewList+2);return

10、 0;2.#include#includetypedef struct nodeint xi;int zi;struct node *next; Node;Node *Creat()/ 用链表储存多项式的序数与指数Node *head,*p,*q;int or,in;head=(Node *)malloc(sizeof(Node);head-next=NULL;q=head;printf( 请输入多项式的序数与指数n（注意：按照指数升序输入，系数不能等于0 且指数不能小于0，序数与指数用空格隔开,并以 0 0 结束输入） n);scanf(%d %d,&or,&in);while(or)p=(

11、Node *)malloc(sizeof(Node);p-xi=or;p-zi=in;p-next=q-next;q-next=p;q=p;scanf(%d %d,&or,&in);return head;void visit(Node *head) / 输出多项式Node *p=head-next;while(p)printf(%dX%d+,p-xi,p-zi);p=p-next;printf(NULLnn);Node *Add(Node *head1,Node *head2)/多项式相加Node *p,*head,*p1,*p2;int sum;head=(Node *)malloc(si

12、zeof(Node);p=head;p1=head1-next;p2=head2-next;while(p1&p2) /当两多项式都存在时if(p1-zi=p2-zi) /如果指数相等sum=p1-xi+p2-xi;if(sum)p1-xi=sum;p-next=p1;p=p1;p1=p1-next;p2=p2-next;else /指数不相等分两种情况if(p1-zizi)p-next=p1;p=p1;p1=p1-next;elsep-next=p2;p=p2;p2=p2-next;if(p1) p-next=p1; / 将 1 中剩余结点接到和链表中else p-next=p2; / 将 2 中剩余结点接到和链表中return head;因为最终只剩下一段链表多项式这段链的链头接到目标链表就可以了int main()printf( 请输入第一个多项式n);Node *head,*p1,*p2;p1=Creat();printf(