实现两个链表的合并(数据结构课程教学设计c语言学习知识版).doc

.*课程设计报告 课程设计题目：实现两个链表的合并 学生姓名 专 业 班 级 指导教师 2012年 06 月 21 日一、 课程设计目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。二、 课程设计题目： 实现两个链表的合并要求：1）输入2个单链表 2）输出2个单链表合并后形成的结果。三、模块划分：（1）数据模块参考使用课本上的具有头结点的链表抽象数据类型linklist，该抽象数据类型中包含一个elemtype类型的数据和一个指针，在开始用时，elemtype定义为整型变量，指针用来指向下一个元素。对应的使用链表抽象数据类型linklist基本操作的函数有：初始化操作函数void ini(linklist *s)。（2）创建链表模块void create(linklist *s)其功能是创建链表录入数据。（3）输出数据模块void display(linklist *s)其功能为是输出s链表中的各项元素，从而验证操作是否成功（4）排序模块void sort(linklist *s)此函数功能是s链表使用冒泡法对链表进行排序（5）合并链表模块void add(linklist *s1,linklist *s2)其功能是按照题目要求实现两个链表的合并，将s2链表插入到s1链表中。（6）主函数模块void main()，函数中调用了各个模块的函数，从而实现了题目合并排序的要求四、流程图： Creat s1链表对s1进行排序 Creat s2链表 对s2进行排序 对排序后的s1.s2链表合并S1为null s1!=null将s2插入s1中S1=s2 显示s1（即合并后的链表）结束 五、算法设计分析 这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、链表的插入、链表内容升序排列，通过主函数调用。这样就大大精简了主函数的操作。但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。六、数据结构：（1）数据类型DataType定义如下：typedef int elemtype;（2）带头结点链表抽象数据类型的结点结构定义如下： typedef struct node elemtype data; struct node *next;linklist;七、源程序：#define null 0typedef int elemtype;typedef struct node elemtype data; struct node *next;linklist;void ini(linklist *s) s-next=null;void create(linklist *s) linklist *p,*q=s; elemtype e; printf(please input the data;n); scanf(%d,&e); while(e!=-1) p=(linklist *)malloc(sizeof(linklist); p-data=e; q-next=p; q=q-next; scanf(%d,&e); q-next=null;void display(linklist *s) linklist *p=s-next; if(s-next=null) printf(the linklist is empty!n); else printf(output the data:n);while(p!=null)printf(%5d,p-data); p=p-next; printf(n);void sort(linklist *s) linklist *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-next;void add(linklist *s1,linklist *s2) linklist *p1=s1-next,*p2=s1,*q1=s2-next,*q2=s2; if(s1=null) s1=s2; while(p1!=null&q1!=null) if(p1-datadata) p1=p1-next; p2=p2-nextelse q2-next=q1-next; q1-next=p2-next; p2-next=q1; p2=p2-next; q1=q2-next; if(q1!=null) p2-next=q1;void main() linklist *s1,*s2; s1=(linklist *)malloc(sizeof(linklist); ini(s1); create(s1); display(s1); sort(s1); display(s1); s2=(linklist *)malloc(sizeof(linklist); ini(s2); create(s2); display(s2); sort(s2); display(s2); add(s1,s2); display(s1);八、实验运行结果显示：9、 实验收获和体会：十、参考文献1赵国玲. C语言与数据结构M. 北京：电子工业出版社，1999.11：120-1462严蔚敏,吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，2006.10：44-523 严蔚敏.数据结构 C语言M.北京: 清华大学出版社,2006.10：110-1354 谭浩强. C程序设计指导M.北京：清华大学出版社,2005