2022年2022年链表的合并-实验报告 .pdf

《2022年2022年链表的合并-实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表的合并-实验报告 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.1/14 课程设计报告课程设计题目：两个链表的合并专业：软件工程班级：姓名：学号:指导教师:年月日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -.2/14 目录1.课程设计的目的与要求2.课程设计的容分析和设计3.算法流程图4.详细步骤5.代码6.显示结果7.课程设计的总结名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14 页 -.3/14 一课程设计的目的与要求1.目的：实现两个链表的合并2.要求：1 建立两个链表A 和 B，链表元素个数分别为m 和 n 个。2 假设元素分别为(x1,x2,xm)，和(y1,y2,yn)。把它们合并成一个线形表C

2、，使得：当 m=n 时，C=x1,y1,x2,y2,xn,yn,xm 当 nm 时，C=y1,x1,y2,x2,ym,xm,yn 输出线形表C 3 用直接插入排序法对C 进展升序排序，生成链表D，并输出链表D。4 能删除指定单链表中指定位子和指定值的元素。二课程设计的容分析和设计1.分析由题目的相关信息可以分析得：首先我们需要建立两个链表AB，A 链表的元素个数为m，B 链表的元素个数为n；在将 A、B 链表进展合并，根据 m 和 n 的大小关系决定链表C 的元素顺序；再将C 进展直接插入排序得到一个新的链表D；没次输入完一次链表信息，程序都会对相应的链表进展输入操作以此确保程序输入的数据是你

3、想要输入的数据。同时当你合并好和排序好后都会进展输出操作。最后当排序好后你可以指定你所要删除数据的位置来删除你所要删除的数据。2.设计本次课程设计所需要用到的是关于链表的建立、合并以与直接插入排序的排序算法。需要先建立两个链表，再将其合并为一个无序链表，最后对这个无序链表进展直接插入排序并将其输出。难点在于将AB 合并为链表C 的操作以与对链表C 进展直接插入排序的操作和根据用户的意愿可以对链表进展删除的操作。三算法流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 14 页 -.4/14 四详细步骤(1)结构体的创建：struct Node(2)链表的创建：struct No

4、de*create链表的创建。(3)链表的输出：void print(struct Node*head)功能是对链表进展输出。(4)链表的合并：struct Node*inter_link(struct Node*chain1,int a,struct Node*chain2,int b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5)排序：void InsertSort(struct Node*p,int m)算法的功能是对一合并好的链表进展升序插入排序。(6)按位删除操作：struct Node*delete_link(struct Node*p,int

5、i)。(7)按值删除操作：struct Node*delete_linkz(struct Node*p,int i)。(8)主函数：main()函数主要是对算法进展测试。建立链表 A 建立链表B 合并 A B 链表得到 C 链表得到 D 链表得到 E 链表比拟 m.n 排序删除名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 14 页 -.5/14 五代码struct Node/数据结构定义如下：long int number;struct Node*next;Node,*linkList;#include/源程序：#include#include#include#define e

6、rror 0#define null 1#define L sizeof(struct Node)struct Node*create(int a)/链表创建函数 int n;struct Node*p1,*p2,*head;head=NULL;n=0;p2=p1=(struct Node*)malloc(L);/分配存scanf(%ld,&p1-number);while(a)/录入链表信息 n=n+1;if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(struct Node*)malloc(L);if(a!=1)/分配存scanf(%ld,&p1-numbe

7、r);a-;/控制输入的个数 p2-next=NULL;return(head);/链表创建函数完毕void print(struct Node*head)/输出函数名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -.6/14 struct Node*p;p=head;printf(数字:n);if(head!=NULL)do/循环实现输出 printf(%ld,p-number);printf();p=p-next;while(p!=NULL);printf(n);/链表的交叉合并算法struct Node*inter_link(struct Node*chain1,

8、int a,struct Node*chain2,int b)int temp;struct Node*head,*p1,*p2,*pos;/*判断 a，b 大小并合并*/if(a=b)head=p1=chain1;p2=chain2;else/*ba*/head=p1=chain2;p2=chain1;temp=a,a=b,b=temp;/*交换 a 和 b*/*下面把 p1 的每个元素插在 p2 相应元素之前，p1 长 a,p2长 b*/pos=head;/*此时 pos指向 p1 中的第一个元素*/while(p2!=NULL)/漂亮，蛇形插入p1=p1-next;pos-next=p2

9、;pos=p2;p2=p2-next;pos-next=p1;pos=p1;return head;/对合并好的链表进展排序void InsertSort(struct Node*p,int m)/排序函数 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 14 页 -.7/14 int i,j,t;struct Node*k;k=p;for(i=0;i m-1;i+)for(j=0;j number (p-next)-number)t=p-number;p-number=(p-next)-number;(p-next)-number=t;p=p-next;p=k;struct N

10、ode*delete_link(struct Node*p,int i)/按位删除 struct Node*q;int j=0;while(jnext)p=p-next;j+;if(j=i-1&p-next)q=p-next;p-next=q-next;free(q);else return error;struct Node*delete_linkz(struct Node*p,int i)/按值删除 struct Node*q;struct Node*k;int j=0;int h=0;while(p&p-number!=i)p=p-next;j+;if(p)while(hnext)p=p

11、-next;h+;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -.8/14 if(h=j-1&p-next)k=p-next;p-next=k-next;free(k);else return error;/主函数int main()/main 函数 struct Node*p1,*p2;int a;int b;int h;int t;int m;printf(请输入第一个链表:n);printf(n 输入链表的长度a:n);scanf(%d,&a);printf(请输入链表数据：);p1=create(a);printf(n 你刚刚输入的第一个链表信息:n);pr

12、int(p1);printf(n 请输入第二个链表:n);printf(n 输入链表的长度b:n);scanf(%d,&b);printf(请输入链表数据：);p2=create(b);printf(n 你刚刚输入的第二个链表的信息:n);print(p2);p1=inter_link(p1,a,p2,b);h=a+b;printf(n 合并后的链表 n：);print(p1);InsertSort(p1,h);printf(n 排序后的链表:n);print(p1);printf(n 请输入链表中你所要删除数据的所在位置:n);scanf(%d,&t);delete_link(p1,t);p

13、rintf(n 链表删除数据后链表的信息:n);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -.9/14 print(p1);printf(n 请输入你想要删除的数值:n);scanf(%d,&m);delete_linkz(p1,m);printf(n 链表删除数据后链表的信息:n);print(p1);return 0;六显示结果1mn 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -.11/14 3.m=n 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 14 页 -.12/14 4.按位删除操作名师资料总结-精品资

14、料欢迎下载-名师精心整理-第 12 页，共 14 页 -.13/14 5.按值删除名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 14 页 -.14/14 七课程设计的总结通过进一周的学习和实践，解决实际问题，让我对链表有了更深的了解，也让我提高了解决实际问题的能力。在上机的同时改正了自己对某些算法的错误使用，使自己在通过程序解决问题时抓住关键算法，有了算法设计思想和流程图，并用C 语言描绘出关键算法。在运行过程中，用户可输入你所需合并的两个链表，首先输入你所要输入链表的长度再输入链表的数据，完成第一个链表的输入后，按照同样的方法输入第二个链表，每输入完一个链表程序都会执行输出

15、函数void print(struct Node*head)对链表进展输出，以此让用户可以确认自己输入的数据是否准确。当用户输入完第二个链表时，程序会先执行struct Node*inter_link(struct Node*chain1,int a,struct Node*chain2,int b)再执行 void InsertSort(struct Node*p,int m)来进展合并和排序。合并之后和排序后又分别会再次执行输出函数，以此输出合并后和排序后的链表数据。之后相应的按照用户的需要可以删除所要删除的数据。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -