数据结构课程教学设计实现两个链表的合并.doc
.*一、 需求分析： 题目： 实现两个链表的合并 问题描述： 1. 建立两个链表A和B，链表元素个数分别为m和n个。 2. 假设元素分别为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线形表C，使得： 当m=n时，C=x1,y1,x2,y2,xn,yn,xm 当nm时，C=y1,x1,y2,x2,ym,xm,yn 输出线性表C。 由题目的相关信息可以分析得到：首先我们需要建立两个链表AB，A链表的元素个数为m；B链表的元素个数为n；在将AB链表进行合并，更具m和n的大小关系决定链表C的元素顺序；再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。 开始二、 算法的流程图 Creat A 链表 Creat B 链表Mergel(A,B) 合并成C 对C排序生成D 提示输入0或1cmd=0 cmd=1 错误输入输入将要操作的链表的名字Cmd error输入将要操作的链表的名字正确 错误 正确 错误Nameerror删除，打印Nameerror删除，打印 打印“over”结束三、 算法设计分析 这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、计算链表的长度、链表A,B的交叉组合、链表内容升序排列、删除链表指定位置元素、删除指定的元素等算法写成了独立函数，通过主函数调用。这样就大大精简了主函数的操作。但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。四、 源代码 程序源代码:#include#includetypedef struct node /节点定义 int data; struct node *next; node,*linklist;linklist creat(linklist head) /该函数用来创建链表 node *r,*s; int a; r = (linklist)malloc(sizeof(node); head = r; scanf(%d,&a); while(a != 0) s =(node*)malloc(sizeof(node); s-data=a; r-next=s; r=s; printf(please input a data:); scanf(%d,&a); r-next=NULL; return head;linklist length(linklist l) / 返回L中数据元素个数int i=0;linklist p=l-next; / p指向第一个结点while(p) i+; p=p-next; return i;linklist mergel(linklist A,linklist B) /用于实现链表A,B的交叉组合 int m,n; node *p,*q,*s,*t; linklist C; p=A-next; q=B-next; m=length(A); n=length(B); C=A; if(mnext;q=A-next;C=B; while(p&q) s=p-next; p-next=q; if(s) t=q-next; q-next=s; p=s; q=t; return C; linklist sort(linklist L) /链表内容升序排列 linklist p,q,min; int temp; p=L; while( p=p-next ) q=min=p; while(q=q-next) if( q-datadata ) min = q; if( min!=p ) temp = p-data; p-data = min-data; min-data=temp; return L;linklist Delete(linklist l,int index) /删除链表指定位置元素 linklist p,t; int cx=1; /用于计数 p=l; if(indexlength(l) while(p&(cxnext; cx+; t-next=p-next; else printf(input indext error);return l;linklist Delete_element(linklist l,int data) /删除指定的元素 linklist p; p=l; if(p-next) while(p-next-data!=data) p=p-next; p-next=p-next-next; else printf(dont faind the element); return l;linklist display(linklist l) /打印 linklist p;printf(new linklist :n);p = l-next;while(p) printf(%dn,p-data);p= p-next; return l; main() linklist p,q,A,B,C,D;int indexs;int datas;char name;int cmd; printf(Creat linklist A:n); /创建A链表,并打印 printf(please input a data:);A = creat(A); printf(Creat linklist B:n); /创建B链表,并打印printf(please input a data:); B = creat(B); C = mergel(A,B); /生成C链表 ，并打印 printf(linklist Cn);p = C-next; while(p) printf(%dn,p-data); p=p-next; D=C; /对C进行排序生成D sort(D); printf(linklist D:n);q = D-next; while(q) printf(%dn,q-data); q = q-next; printf(nplease input 0 or 1 n); /用1和0判断是按位置删除还是直接删除元素scanf(%d,&cmd);if(cmd=0) /位置删除 printf(please input linklist namen );fflush(stdin);scanf(%c,&name);printf(nplease input index n); scanf(%d,&indexs);fflush(stdin);if(name=A)Delete(A,indexs); display(A);else if(name=B)Delete(B,indexs);display(B);else if(name=C)Delete(C,indexs);display(C);else if(name=D)Delete(D,indexs);display(D);else printf(nameError); else if(cmd=1) /元素删除 fflush(stdin); /清除缓冲 printf(please input linklist namen );/fflush(stdin);scanf(%c,&name);printf(nplease input datas n);scanf(%d,&datas);if(name=A)Delete_element(A,datas);display(A);else if(name=B)Delete_element(B,datas);display(B);else if(name=C) Delete_element(C,datas); display(C);else if(name=D)Delete_element(D,datas); display(D);else printf(name2error); else printf(cmdError);printf(nOvern); getchar(); return 0; 六、实验运行结果显示：设计体会及今后改进的意见;短短一周的数据结构课程设计结束了，回想着这一周自己的表现，感觉不是很满意，感到自己许多不足之处。但同时通过本次课程设计，我也收获了不少。这次课程设计我做的是实现两个链表的合并，由于有C语言的编程，而编程一直对我来说就是一个弱项，我觉的我选的这个题比较基础，自己也有一些思路，但在程序编写过程中还是遇到了不少问题，在开始前，我查阅相关资料，对这次课程谁过程中用到的知识做出了一个系统的归纳：如链表的建立、链表的合并、直接插入排序以及SWITCH语句 等知识点。但在板鞋程序过程中还是遇到了一些问题。经过修改、调试、运行然后再修改、调试、运行，有时虽然能运行，但对本次实验来说缺少一定程度的完整性，然后就上网查资料，在书上查看相关方面的知识，当编写的程序感觉符合要求时，在运行时却出现一些小错误导致整个程序无法正常运行。最后在同学和老师的帮助下，我终于运行出结果，达到比本次实验的目的。通过本次实验，我在C语言编程方面又有了一定程度的提高， 同时也发现自己的不足，在今后的学习中，我一定会不断学习，努力弥补自己的一些缺点，让自己更优秀。参考文献耿国华 数据结构-C语言描述 高等教育出版社 谭浩强 C语言课程设计（第2版） 清华大学出版社 209年 李根强 数据结构（C+版）（第2版） 中国水利水电出版社 2009年
收藏
- 资源描述：
-
.*
一、 需求分析：
题目： 实现两个链表的合并
问题描述：
1. 建立两个链表A和B，链表元素个数分别为m和n个。
2. 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得：
当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm
当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn
输出线性表C。
由题目的相关信息可以分析得到：首先我们需要建立两个链表AB，A链表的元素个数为m；B链表的元素个数为n；在将A\B链表进行合并，更具m和n的大小关系决定链表C的元素顺序；再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。
开始
二、 算法的流程图
Creat A 链表
Creat B 链表
Mergel(A,B) 合并成C
对C排序生成D
提示输入0或1
cmd=0 cmd=1 错误输入
输入将要操作的链表的名字
Cmd error
输入将要操作的链表的名字
正确 错误 正确 错误
Nameerror
删除，打印
Nameerror
删除，打印
打印“over”
结束
三、 算法设计分析
这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、计算链表的长度、链表A,B的交叉组合、链表内容升序排列、删除链表指定位置元素、删除指定的元素等算法写成了独立函数，通过主函数调用。这样就大大精简了主函数的操作。但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。
四、 源代码
程序源代码:
#include
#include
typedef struct node //节点定义
{
int data;
struct node *next;
} node,*linklist;
linklist creat(linklist head) //该函数用来创建链表
{
node *r,*s;
int a;
r = (linklist)malloc(sizeof(node));
head = r;
scanf("%d",&a);
while(a != 0)
{
s =(node*)malloc(sizeof(node));
s->data=a;
r->next=s;
r=s;
printf("please input a data:");
scanf("%d",&a);
}
r->next=NULL;
return head;
}
linklist length(linklist l) // 返回L中数据元素个数
{
int i=0;
linklist p=l->next; // p指向第一个结点
while(p)
{
i++;
p=p->next;
}
return i;
}
linklist mergel(linklist A,linklist B) //用于实现链表A,B的交叉组合
{
int m,n;
node *p,*q,*s,*t;
linklist C;
p=A->next;
q=B->next;
m=length(A);
n=length(B);
C=A;
if(mnext;
q=A->next;
C=B;
}
while(p&&q)
{
s=p->next;
p->next=q;
if(s)
{
t=q->next;
q->next=s;
}
p=s;
q=t;
}
return C;
}
linklist sort(linklist L) //链表内容升序排列
{
linklist p,q,min;
int temp;
p=L;
while( p=p->next )
{
q=min=p;
while(q=q->next){
if( q->datadata )
min = q;
}
if( min!=p )
{
temp = p->data;
p->data = min->data;
min->data=temp;
}
}
return L;
}
linklist Delete(linklist l,int index) //删除链表指定位置元素
{ linklist p,t;
int cx=1; //用于计数
p=l;
if(indexnext;
cx++;
}
t->next=p->next;
}
else
printf("input indext error");
return l;
}
linklist Delete_element(linklist l,int data) //删除指定的元素
{ linklist p;
p=l;
if(p->next)
{
while(p->next->data!=data)
{
p=p->next;
}
p->next=p->next->next;
}
else
printf("dont faind the element");
return l;
}
linklist display(linklist l) //打印
{ linklist p;
printf("new linklist :\n");
p = l->next;
while(p)
{
printf("%d\n",p->data);
p= p->next;
}
return l;
}
main()
{
linklist p,q,A,B,C,D;
int indexs;
int datas;
char name;
int cmd;
printf("Creat linklist A:\n"); //创建A链表,并打印
printf("please input a data:");
A = creat(A);
printf("Creat linklist B:\n"); //创建B链表,并打印
printf("please input a data:");
B = creat(B);
C = mergel(A,B); //生成C链表 ，并打印
printf("linklist C\n");
p = C->next;
while(p)
{
printf("%d\n",p->data);
p=p->next;
}
D=C; //对C进行排序生成D
sort(D);
printf("linklist D:\n");
q = D->next;
while(q)
{
printf("%d\n",q->data);
q = q->next;
}
printf("\nplease input 0 or 1 \n");
//用1和0判断是按位置删除还是直接删除元素
scanf("%d",&cmd);
if(cmd==0) //位置删除
{
printf("please input linklist name\n ");
fflush(stdin);
scanf("%c",&name);
printf("\nplease input index \n");
scanf("%d",&indexs);
fflush(stdin);
if(name==A)
{
Delete(A,indexs);
display(A);
}
else if(name==B)
{
Delete(B,indexs);
display(B);
}
else if(name==C)
{
Delete(C,indexs);
display(C);
}
else if(name==D)
{
Delete(D,indexs);
display(D);
}
else
printf("nameError");
}
else if(cmd==1) //元素删除
{
fflush(stdin); //清除缓冲
printf("please input linklist name\n ");
//fflush(stdin);
scanf("%c",&name);
printf("\nplease input datas \n");
scanf("%d",&datas);
if(name==A)
{
Delete_element(A,datas);
display(A);
}
else if(name==B)
{
Delete_element(B,datas);
display(B);
}
else if(name==C)
{
Delete_element(C,datas);
display(C);
}
else if(name==D)
{
Delete_element(D,datas);
display(D);
}
else
printf("name2error");
}
else
printf("cmdError");
printf("\nOver\n");
getchar();
return 0;
}
六、实验运行结果显示：
设计体会及今后改进的意见;
短短一周的数据结构课程设计结束了，回想着这一周自己的表现，感觉不是很满意，感到自己许多不足之处。但同时通过本次课程设计，我也收获了不少。这次课程设计我做的是实现两个链表的合并，由于有C语言的编程，而编程一直对我来说就是一个弱项，我觉的我选的这个题比较基础，自己也有一些思路，但在程序编写过程中还是遇到了不少问题，在开始前，我查阅相关资料，对这次课程谁过程中用到的知识做出了一个系统的归纳：如链表的建立、链表的合并、直接插入排序以及SWITCH语句 等知识点。但在板鞋程序过程中还是遇到了一些问题。经过修改、调试、运行然后再修改、调试、运行，有时虽然能运行，但对本次实验来说缺少一定程度的完整性，然后就上网查资料，在书上查看相关方面的知识，当编写的程序感觉符合要求时，在运行时却出现一些小错误导致整个程序无法正常运行。最后在同学和老师的帮助下，我终于运行出结果，达到比本次实验的目的。
通过本次实验，我在C语言编程方面又有了一定程度的提高， 同时也发现自己的不足，在今后的学习中，我一定会不断学习，努力弥补自己的一些缺点，让自己更优秀。
参考文献
耿国华 数据结构----C语言描述 高等教育出版社
谭浩强 C语言课程设计（第2版） 清华大学出版社 209年
李根强 数据结构（C++版）（第2版） 中国水利水电出版社 2009年
展开阅读全文
