数据结构实验报告_计算机-数据结构与算法.pdf

《数据结构实验报告_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告_计算机-数据结构与算法.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、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）OrderMerge(&L

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

3、 两个多项式相加 输出第二个多项式和两个多项式得和 2 四、详细设计（画出程序流程图）1.2.创建带头节点的链表 输入两个有序表数据 La Lb 开始 归并两个有序表得有序表 Lc 输出三个有序表 输入需插入数据 e 将 e 插入有序表 Lc 输出插入 e 后的 Lc 结束 链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表

4、输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项3 五、程序代码（给出必要注释）1.#include#include typedef struct LNode int date;struct LNode*next;LNode,*Link;typedef struct LinkList Link head;/头结点 int lenth;/链表中数据元素的个数 Lin

5、kList;int compare(LinkList*L,int e)/有序判定函数 compare int Lc=0;Link p;p=L-head;创建链表 按指数升序输入多项式得序数和指数 开始 输出多项式 按指数升序输入第二个多项式两个多项式相加 输出第二个多项式和两个多项式的和 结束 链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归

6、并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项4 p=p-next;while(p!=NULL)if(ep-date)p=p-next;Lc+;else return Lc;return Lc;void OrderInsert(LinkList*L,int e,int(*compare)()/根据有序判定函数 compare，在有序表 L的适

7、当位置插入元素 e；Link temp,p,q;int Lc,i;temp=(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;else for(i=0;inext;q=q-next;q-next=temp;temp-next=p;+L-lenth;链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在

8、有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项5 void OrderMerge(LinkList*La,LinkList*Lb,int(*comp

9、are)()/根据有序判定函数 compare,将两个有序表 La 和 Lb 归并为一个有序表 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;else for(i=0;inext;temp-next=p-next;p-next=t

10、emp;q=q-next;+Lb-lenth;LinkList*Initialize(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

11、;i2;i+)while(1)scanf(%d,&a);c=getchar();if(c=N)if(ihead-next;while(p!=NULL)printf(%d,p-date);p=p-next;链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输

12、入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项7 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);print

13、f(n);int main()LinkList*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

14、(NewList+2);return 0;2.#include#include typedef struct node 链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并

15、两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项8 int 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

16、,&in);while(or)p=(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;链表了解有序表二实验容必

17、做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项9 head=(N

18、ode*)malloc(sizeof(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;else p-next=p2;p=p2;p2=p2-next;if(p1)p-next=p1;/将 1中剩余结点接到和链表中 因为最终只剩下一

19、段链表多项式 else p-next=p2;/将 2 中剩余结点接到和链表中 这段链的链头接到目标链表就可以了 return head;int main()printf(请输入第一个多项式n);Node*head,*p1,*p2;链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插

20、入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项10 p1=Creat();printf(多项式为:n);visit(p1);printf(请输入第二个多项式n);p2=Creat();printf(多项式为:n);visit(p2);head=Add(p1,p2);printf(n 多项式相加后得：n);visit(head);return 0;六、测试和结果（给出测试用例，并给出测试结果）1.2.链表了解

21、有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项1

22、1 七、用户手册（告诉用户如何使用程序，使用注意事项等）1.按照要求输入 链表了解有序表二实验容必做题假设有序表中数据元素类型是整型请采用顺序表或带头结点单链表实现根据有序判定函数在有序表的适当位置插入元素根据有序判定函数并利用有序插入函数构造有序表根据有序判定函数将两个有序能等于指数不能小于两个升幂多项式的相加三算法描述采用自然语言描述创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的创建链表按指数升序输入多项式项式得和四详细设计画出程序流程图开始创建带头节点的链表输入两个有序表数据归并两个有序表得有序表输出三个有序表输入需插入数据将插入有序表输出插入后的结束开始创建链表按指数升序输入多项式得序数和指数输出多项