数据结构课程设计实现两个链表的合并

《数据结构课程设计实现两个链表的合并》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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；最后输出ABCD的相关信息。开始二、算法的

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

3、定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。所以其有优点和缺点，但需要不断的改进，不断优化该程序。四、源代码程序源代码:#include#includetypedefstructnode//节点定义{intdata;structnode*next;}node,*linklist;linklistcreat(linklisthead)//该函数用来创建链表{node*r,*s;inta;r=(linklist)malloc(sizeof(node));head=r;scanf("%d",&a);while(a!=0){s

4、=(node*)malloc(sizeof(node));s->data=a;r->next=s;r=s;printf("pleaseinputadata:");scanf("%d",&a);}r->next=NULL;returnhead;}linklistlength(linklistl)//返回L中数据元素个数{inti=0;linklistp=l->next;//p指向第一个结点while(p){i++;p=p->next;}returni;}linklistmergel(linklistA,linklistB)//用于实现链表A,B的交叉组合{intm,n;node*p,*q,

5、*s,*t;linklistC;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;}returnC;}linklistsort(linklistL)//链表内容升序排列{linklistp,q,min;inttemp;p=L;while(p=p->next){q=min=p;while(q=q->next){if(q->datadat

6、a)min=q;}if(min!=p){temp=p->data;p->data=min->data;min->data=temp;}}returnL;}linklistDelete(linklistl,intindex)//删除链表指定位置元素{linklistp,t;intcx=1;//用于计数p=l;if(indexnext;cx++;}t->next=p->next;}elseprintf("inputindexterror");returnl;}linklistDelete_element(li

7、nklistl,intdata)//删除指定的元素{linklistp;p=l;if(p->next){while(p->next->data!=data){p=p->next;}p->next=p->next->next;}elseprintf("don'tfaindtheelement");returnl;}linklistdisplay(linklistl)//打印{linklistp;printf("newlinklist: