实现两个链表的合并

1、课程设计报告课程设计题目：实现两个链表的合并学生专 业班 级指导教师2012年06 月21 日课程设计目的：课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理 论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生 适应实际，实践编程的能力。二、课程设计题目：实现两个链表的合并要求：1）输入2个单链表2）输出2个单链表合并后形成的结果三、模块划分：（1）数据模块参考使用课本上的具有头结点的链表抽象数据类型lin klist ，该抽象数据类型中包含一个elemtype类型的数据和一个指针，在开始用时，elemtype定义为整 型变量，指针用来指向下一个元素。对应的

2、使用链表抽象数据类型lin klist 基本操作的函数有：初始化操作函数 void in i（li nklist *s）。（2）创建链表模块void create（li nklist *s）其功能是创建链表录入数据。（3）输出数据模块void display（l in klist *s）其功能为是输出s链表中的各项元素，从而验证操作是否成功（4）排序模块void sort（l in klist *s）此函数功能是s链表使用冒泡法对链表进行排序（5）合并链表模块void add（li nklist *s1,li nklist *s2）其功能是按照题目要现两个链表的合并，将s2链表插入到si链表中

3、。（6）主函数模块void mai n()，函数中调用了各个模块的函数，从而实现了题目合并排序的 要求四、流程图:结束五、算法设计分析这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义 节点，将链表的创建、链表的插入、链表容升序排列，通过主函数调用。这 样就大大精简了主函数的操作。但主函数中很大篇幅用到了if、else语句,用以指定链表指定结点，这样就使得本来很精简变得繁琐，降低了程序的质 量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。六、数据结构：（1）数据类型DataType定义如下：typedef int elemtype;（2）带头结点链表抽象数据类型的结点结构定

4、义如下:typedef struct nodeelemtype data;li nklist;七、源程序:#defi ne null 0typedef int elemtype;typedef struct nodeelemtype data;struct node *n ext;li nklist;void in i(li nklist *s)s->n ext=n ull;void create(li nklist *s)li nklist *p,*q=s;elemtype e;prin tf("please in put the data;' n");sc

5、a nf("%d",&e);while(e!=-1)p=(li nklist *)malloc(sizeof(li nklist); p->data=e;q->n ext=p;q=q->n ext;sea nf("%d",&e);q->n ext=n ull;void display(l in klist *s)lin klist *p=s->n ext;if(s->n ext=n ull)prin tf("the lin klist is empty!n");elseprin tf

6、("output the data:n");while(p!=null)prin tf("%5d",p->data);p=p->n ext;prin tf("n");void sort(l in klist *s)lin klist *p,*q;elemtype t;p=s->n ext;while(p!=null)q=p->n ext;while(q!=null)if(p->data>q->data)t=p->data; p->data=q->data;q->data

7、=t; q=q->n ext; p=p->n ext;void add(li nklist *s1,li nklist *s2)lin klist *p1= s1-> next,*p2=s1,*q1=s2-> next,*q2=s2;if(s1=nu II)s1=s2;while(p1!=null&&q1!=null) if(p1->data<q1->data)p1=p1- >n ext;elseq2->n ext=q1- >n ext;q1- >n ext=p2->n ext;p2->n ext=q

8、1;p2=p2->n ext;q1=q2->n ext;if(q1!=n ull)p2->n ext=q1;void mai n()lin klist *s1,*s2;s1=(li nklist *)malloc(sizeof(li nklist);in i(s1);create(s1);display(s1);sort(s1);display(s1);s2=(li nklist *)malloc(sizeof(li nklist);in i(s2);create(s2);display(s2);sort(s2);display(s2);add(s1,s2);display(sl);八、实验运行结果显示:outputthedata：1234outpuh七lwdatza "1234pleasejjnput thedata ；& 8 7 <6 -1NDUtpiltthedata 876frll«7a9putputthedata：1234data ；hplease Input the1 2 3 4 5 -1cont inue九、实验收获和体会:十、参考文献1国玲.