数据结构课程设计实现两个链表的合并(共11页)

1、精选优质文档-倾情为你奉上一、 需求分析： 题目： 实现两个链表的合并 问题描述： 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；在将AB链表进行合并，更具m和n的大小关系决定链表C的元素顺序；再将C经行直接插入排序得到一个新的链表D；最

2、后输出ABCD的相关信息。 开始二、 算法的流程图 Creat A 链表 Creat B 链表Mergel(A,B) 合并成C 对C排序生成D 提示输入0或1cmd=0 cmd=1 错误输入输入将要操作的链表的名字Cmd error输入将要操作的链表的名字正确 错误 正确 错误Nameerror删除，打印Nameerror删除，打印 打印“over”结束三、 算法设计分析 这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、计算链表的长度、链表A,B的交叉组合、链表内容升序排列、删除链表指定位置元素、删除指定的元素等算法写成了独立函数，通过主函数调用。这样就大大精简

3、了主函数的操作。但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。四、 源代码 程序源代码:#include<stdio.h>#include<stdlib.h>typedef struct node /节点定义 int data; struct node *next; node,*linklist;linklist creat(linklist head) /该函数用来创建链表 node *r,*s; int a; r = (lin

4、klist)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;linkli

5、st 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(m<n) p=B->next;q=A->next;C=B; while(p&&q) s=p->next; p->ne

6、xt=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->data<min->data ) min = q; if( min!=p ) temp = p->data; p->data = min->data; min->data=temp;

7、return L;linklist Delete(linklist l,int index) /删除链表指定位置元素 linklist p,t; int cx=1; /用于计数 p=l; if(index<length(l) while(p&&(cx<index) t=p; p=p->next; cx+; t->next=p->next; else printf("input indext error");return l;linklist Delete_element(linklist l,int data) /删除指定的元素

8、 linklist p; p=l; if(p->next) while(p->next->data!=data) p=p->next; p->next=p->next->next; else printf("don't faind the element"); return l;linklist display(linklist l) /打印 linklist p;printf("new linklist :n");p = l->next;while(p) printf("%dn"

9、;,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:&quo

10、t;); 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(&qu

11、ot;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='

12、;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

13、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

14、(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语句 等知识点。但在板鞋程序过程中还是遇到了一些问题。经过修改、调试、运行然后再修改、调试、运行，有时虽然能运行，但对本次实验来说缺少一定程度的完整性，然后就上网查资料，在书上查看相关方面的知识，当编写的程序感觉符合要求