实现两个链表地合并大数据结构课程设计c语言版.docx
《实现两个链表地合并大数据结构课程设计c语言版.docx》由会员分享，可在线阅读，更多相关《实现两个链表地合并大数据结构课程设计c语言版.docx（9页珍藏版）》请在冰点文库上搜索。
实现两个链表地合并大数据结构课程设计c语言版
课程设计报告
课程设计题目：
实现两个链表的合并
学生姓名
专业
班级
指导教师
2012年06月21日
一、课程设计目的：
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。
提高学生适应实际，实践编程的能力。
二、课程设计题目：
实现两个链表的合并
要求：
1）输入2个单链表
2）输出2个单链表合并后形成的结果。
三、模块划分：
（1）数据模块
参考使用课本上的具有头结点的链表抽象数据类型linklist，该抽象数据类型中包含一个elemtype类型的数据和一个指针，在开始用时，elemtype定义为整型变量，指针用来指向下一个元素。
对应的使用链表抽象数据类型linklist基本操作的函数有：
初始化操作函数voidini（linklist*s）。
（2）创建链表模块
voidcreate（linklist*s）
其功能是创建链表录入数据。
（3）输出数据模块
voiddisplay（linklist*s）
其功能为是输出s链表中的各项元素，从而验证操作是否成功
（4）排序模块
voidsort（linklist*s）
此函数功能是s链表使用冒泡法对链表进行排序
（5）合并链表模块
voidadd（linklist*s1,linklist*s2）
其功能是按照题目要求实现两个链表的合并，将s2链表插入到s1链表中。
（6）主函数模块
voidmain（），函数中调用了各个模块的函数，从而实现了题目合并排序的要求
四、流程图：
S1为nulls1!
=null
五、算法设计分析
这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、链表的插入、链表内容升序排列，通过主函数调用。
这样就大大精简了主函数的操作。
但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点，这样就使得本来很精简变得繁琐，降低了程序的质量。
所以其有优点和缺点，但需要不断的改进，不断优化该程序。
六、数据结构：
（1）数据类型DataType定义如下：
typedefintelemtype;
（2）带头结点链表抽象数据类型的结点结构定义如下：
typedefstructnode
{
elemtypedata;
structnode*next;
}linklist;
七、源程序：
#definenull0
typedefintelemtype;
typedefstructnode
{
elemtypedata;
structnode*next;
}linklist;
voidini（linklist*s）
{
s->next=null;
}
voidcreate（linklist*s）
{
linklist*p,*q=s;
elemtypee;
printf（"pleaseinputthedata;\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;
}
voiddisplay（linklist*s）
{
linklist*p=s->next;
if（s->next==null）
printf（"thelinklistisempty!
\n"）;
else
{
printf（"outputthedata:
\n"）;
while（p!
=null）
{
printf（"%5d",p->data）;
p=p->next;
}
}
printf（"\n"）;
}
voidsort（linklist*s）
{
linklist*p,*q;
elemtypet;
p=s->next;
while（p!
=null）
{
q=p->next;
while（q!
=null）
{
if（p->data>q->data）
{
t=p->data;
p->data=q->data;
q->data=t;
}
q=q->next;
}
p=p->next;
}
}
voidadd（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->next
}
else
{
q2->next=q1->next;
q1->next=p2->next;
p2->next=q1;
p2=p2->next;
q1=q2->next;
}
}
if（q1!
=null）
p2->next=q1;
}
voidmain（）
{
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-146
[2]严蔚敏,吴伟民.数据结构（C语言版）[M].北京：
清华大学出版社，2006.10：
44-52
[3]严蔚敏.数据结构C语言[M].北京:
清华大学出版社,2006.10：
110-135
[4]谭浩强.C程序设计指导[M].北京：
清华大学出版社,2005
升级会员 