链表合并

课程设计说明书 NO.1

两个链表合并 1、课程设计目的： （1）较熟练地掌握Ｃ语言的基本内容及程序设计的基本方法与编程技巧。巩固和加深学生对C语言课程的基本知识的理解和掌握。掌握C语言编程和程序调试的基本技能。 利用C语言进行基本的软件设计。掌握书写程序设计说明文档的能力。提高运用C语言解决实际问题的能力。 （2）较熟练地掌握在系统上编辑、编译、连接和运行C程序的方法。 （3）通过设计一个完整程序，掌握数据结构的算法编写、类C语言算法转换成C程序并上机调试的基本方法。 （4）根据课堂讲授内容，学生做相应的自主练习，消化课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。 2、课程设计方案论证： 2.1设计要求 建立两个链表A和B，链表元素个数分别为m和n个。假设元素分别(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。 测试数据： ① A表（30，41，15，12，56，80） B表（23，56，78，23，12，33，79，90，55） ② A表（30，41，15，12，56，80，23，12，34） B表（23，56，78，23，12） 2.1.1主要功能图： 沈 阳 大 学

课程设计说明书 NO.2

两个链表合并 输 入 链 表 1 输 入 链 表 2 创 建链 表 3 并合 并再 进行 排序 输 出 链 表 3 图1 主要功能图 2.1.2数据结构结构体设计： 结构体是由一系列具有相同类型或不同类型的数据构成的数据集合，也叫结构。结构体和其他类型基础数据类型一样，例如int类型，char类型 只不过结构体可以做成今后需要的数据类型。结构体在函数中最主要的作用就是封装。封装的好处就是可以再次利用。让使用者不必关心这个是什么，只要根据定义使用就可以了。 typedef struct S { long num; int score; struct S *next; }STU; 2.1.3创建循环单链表： 线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其 沈 阳 大 学

课程设计说明书 NO.3

本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个\结点\，表示线性表中一个数据元素。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。 创建链表的算法如下： struct STU *creat(int a) { printf(“please input %d numbers”,&a); int n; STU *head,*p1,*p2; n=0; p1=p2=(STU *)malloc(LEN); scanf(\ while (a) { n = n + 1; if (n == 1) head = p1; else p2->next = p1; p2 = p1; p1 = (struct S *) malloc(L); if (a != 1) scanf(\ a--; } p2->next = NULL; return (head); } 链表的结点结构： L ..... L是STU型的变量，为单链表的头指针，指向第一个结点 data next data next data data域--存放结点值的数据域 沈 阳 大 学

课程设计说明书 NO.4

next域--存放结点的直接后继的地址（位置）的指针域（链域） 2.1.3对链表进行排序 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。 STU *sort(STU *head) { STU *p,*head1,*p1,*p2,*pre; p=head; head1=NULL; p2=NULL; while(p!=NULL) { pre=p->next; p->next=NULL; if(head1==NULL)head1=p; else { p1=head1; p2=NULL; while((p1!=NULL)&&(p->num>p1->num)) { p2=p1; p1=p1->next; } if(p2==NULL) { p->next=head1; head1=p; } else { p->next=p1; p2->next=p; } } 沈 阳 大 学

课程设计说明书 NO.5

p=pre; } return head1; } 我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。 插入算法图例(如图8个数字中每次找出一个数，插入之前数列的排序中，完成插入同时就可以排序)： 图2 插入排序的算法图例 2.1.4主函数的建立： 日常生活中，要完成一件复杂的功能，我们总是习惯把“大功能”分解为多个“小功能”以实现。在C程序里，“功能”可称呼为“函数”，因此“函数”其实就是一段实现了某种功能的代码，并且可以供其它代码调用。 main() { STU *p,*head1,*head2; printf(\ int a; 沈 阳 大 学

课程设计说明书 NO.6

scanf(\ printf(\ int b; scanf(\head1=creat(a); head2=creat(b); p=head1; if(head1!=NULL&&head1->next==NULL)head1->next=head2; else if(head1!=NULL) { do { p=p->next; }while(p->next!=NULL); p->next=head2; } head1=sort(head1); p=head1; printf(\printf(\printf(\if(head1!=NULL) do { printf(\p=p->next; }while(p!=NULL); getch(); } 3、课程设计运行结果与分析 3.1输入数据 测试数据： A表（30，41，15，12，56，80） B表（23，56，78，23，12，33，79，90，55） 按照所给数据输入第一个链表，如下图所示： 沈 阳 大 学

课程设计说明书 NO.7

图3 输入链表1 按照所给数据输入第二个链表，如下图所示： 图4 输入链表2 点击回车，程序自动进行插入，并用插入排序进行数据的整理，最终将排序后的数据输出： 沈 阳 大 学

课程设计说明书 NO.8

图5 输出排序后的链表3 3.2输入数据 测试数据： A表（30，41，15，12，56，80，23，12，34） B表（23，56，78，23，12） 方法同3.2，输入测试数据，按照所给数据输入第一个链表，如下图所示： 图6 输入链表1 输入链表2数据： 沈 阳 大 学

课程设计说明书 NO.9

图7 输入链表2 操作结果： 图8 输出排序后的链表3 沈 阳 大 学

课程设计说明书 NO.10

4、课程设计体会 通过这次数据结构设计，本人在多方面都有所提高。比如平时对链表的学习马马虎虎，但在这次课设，我需要自己来编码，就需要自己一个节点一个节点的对比画图和自己设计储存结构方式和算法的应用。同时，也对排序的算法进行了了解，实验要求的插入排序即是平常难遇到，但在课设中得到了进一步的巩固。而且这次课程设计加深了对C语言中指针，函数调用的运算操作。在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 通过这次数据结构设计，综合运用本专业所学课程的理论和C语言知识进行一次合并的实际训练从而培养和提高学生独立编码，写算法的能力，巩固与扩充了数据结构设计等课程所学的内容，掌握数据结构和算法设计的方法和步骤，提高了计算能力，编码能力，熟悉了规范和标准，同时各科相关的课程都有了全面的复习，独立思考的能力也有了提高。 在这次设计过程中，体现出自己编程的能力以及算法，数据结构综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 在此感谢我们的数据结构老师.，老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；这次数据结构设计的每个实验细节和每个数据，都离不开老师您的细心指导。 所以，不得不说，数据结构的课程设计的确是我们得到了很多，从中受益匪浅，希望能对以后的学习，项目有所帮助！ 沈 阳 大 学

课程设计说明书 NO.11

5.参考文献 [1]黄保和，江戈.C语言程序设计[M].北京清华大学出版社，2008：80-95 [2] 赵国玲. C语言与数据结构[M]. 北京：电子工业出版社，1999.11：120-146 [3] 严蔚敏,吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2006.10：44-52 [4] 蔡子经，施伯乐. 数据结构教程[M]. 上海：复旦大学出版社，2006.4：168-207 [5]李春褒.数据结构教程(第二版)[M].北京：清华大学出版社,2007.3：22-46 [6] 严蔚敏.数据结构 C语言[M].北京: 清华大学出版社,2006.10：110-135 沈 阳 大 学

课程设计说明书 NO.12

附录： 源代码： #include #define LEN sizeof(STU) #define NULL 0 typedef struct S { long num; struct S *next; }STU; int n; struct STU *creat(int a) { printf(“please input %d numbers”,&a); int n; STU *head,*p1,*p2; n=0; p1=p2=(STU *)malloc(LEN); scanf(\ while (a) { n = n + 1; if (n == 1) head = p1; else p2->next = p1; p2 = p1; p1 = (struct S *) malloc(L); if (a != 1) scanf(\ a--; } p2->next = NULL; return (head); } STU *sort(STU *head) { STU *p,*head1,*p1,*p2,*pre; p=head; 沈 阳 大 学

课程设计说明书 NO.13

head1=NULL; p2=NULL; while(p!=NULL) { pre=p->next; p->next=NULL; if(head1==NULL)head1=p; else { p1=head1; p2=NULL; while((p1!=NULL)&&(p->num>p1->num)) { p2=p1; p1=p1->next; } if(p2==NULL) { p->next=head1; head1=p; } else { p->next=p1; p2->next=p; } } p=pre; } return head1; } main() { STU *p,*head1,*head2; printf(\ int a; scanf(\ printf(\ int b; scanf(\ 沈 阳 大 学

课程设计说明书 NO.14

head1=creat(a); head2=creat(b); p=head1; if(head1!=NULL&&head1->next==NULL)head1->next=head2; else if(head1!=NULL) { do { p=p->next; }while(p->next!=NULL); p->next=head2; } head1=sort(head1); p=head1; printf(\printf(\printf(\if(head1!=NULL) do { printf(\p=p->next; }while(p!=NULL); getch(); } 沈 阳 大 学

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