1、 课程设计报告课程设计报告 课程设计题目：课程设计题目：实现两个链表的合并实现两个链表的合并 2013 年年 01 月月 08 日日 一、一、 课程设计目的：课程设计目的： 课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理 论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生 适应实际，实践编程的能力。 二、二、 课程设计题目：课程设计题目： 实现两个链表的合并 要求：1）输入 2 个单链表 2）输出 2 个单链表合并后形成的结果。 三、模块划分：三、模块划分： （1）数据模块 参考使用课本上的具有头结点的链表抽象数据类型 linklist， 该抽象数据类型
2、中包 含一个 elemtype 类型的数据和一个指针， 在开始用时， elemtype 定义为整型变量， 指针用来指向下一个元素。对应的使用链表抽象数据类型 linklist 基本操作的函 数有：初始化操作函数 void ini(linklist *s)。 （2）创建链表模块 void create(linklist *s) 其功能是创建链表录入数据。 （3）输出数据模块 void display(linklist *s) 其功能为是输出 s 链表中的各项元素，从而验证操作是否成功 （4）排序模块 void sort(linklist *s) 此函数功能是 s 链表使用冒泡法对链表进行排序 （
3、5）合并链表模块 void add(linklist *s1,linklist *s2) 其功能是按照题目要求实现两个链表的合并，将 s2 链表插入到 s1 链表中。 （6）主函数模块 void main()，函数中调用了各个模块的函数，从而实现了题目合并排序的要 求 四、流程图：四、流程图： S1 为 null s1!=null Creat s1 链表 对 s1 进行排序 对 s2 进行排序 对排序后的 s1.s2 链表合并 Creat s2 链表 S1=s2 将 s2 插入 s1 中 显示 s1（即合并后的链表） 结束 五、算法设计分析五、算法设计分析 这个两个链表的交叉合并算法主要运用到
4、的是链表的基本操作，定义 节点，将链表的创建、链表的插入、链表内容升序排列，通过主函数调用。 这样就大大精简了主函数的操作。 但主函数中很大篇幅用到了 if、 else 语句， 用以指定链表指定结点，这样就使得本来很精简变得繁琐，降低了程序的质 量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。 六、数据结构：六、数据结构： （1）数据类型 DataType 定义如下： typedef int elemtype; （2）带头结点链表抽象数据类型的结点结构定义如下： typedef struct node elemtype data; struct node *next; linklis
5、t; 七、源程序：七、源程序： #define null 0 typedef int elemtype; typedef struct node elemtype data; struct node *next; lin; void inia(lin *a) a-next=null; void create(lin *a) lin *p,*q=a; elemtype e; printf(“please input the data;n“); scanf(“%d“, while(e!=-1) p=(lin *)malloc(sizeof(lin); p-data=e; q-next=p; q=q
6、-next; scanf(“%d“, q-next=null; void display(lin *a) lin *p=a-next; if(a-next=null) printf(“the lin is empty!n“); else printf(“output the data:n“); while(p!=null) printf(“%5d“,p-data); p=p-next; printf(“n“); void sort(lin *a) lin *p,*q; elemtype t; p=s-next; while(p!=null) q=p-next; while(q!=null) if(p-dataq-data) t=p-data; p-data=q-data; q-data=t; q=q-next; p=p-nex
