《数据结构课程设计-两个链表合并-星》由会员分享，可在线阅读，更多相关《数据结构课程设计-两个链表合并-星（19页珍藏版）》请在金锄头文库上搜索。
1、两个链表的合并1课程设计目的实现对两个的链表的交叉合并，输出线形表C用直接插入排序法对C进行升序排序， 生成链表D,并输出链表D。掌握对线性表的链式表示和实现，实现插入的操作。了解 链表交叉合并的方法和直接插入排序法的思想，并深刻掌握算法的格式和应用。提高对 数据结构的理解和应用，增强个人动手实践能力和逻辑分析能力。2.设计方案论证2.1设计思路本课程设计将对链表的交叉合并和直接插入排序的实现。首先将两个链表进行交叉 合并，合并的要求如下：建立两个链表A和B，链表元素个数分别为m和n个。假设元素分别为(xl,x2,xm)， 和(yl,y2,丫口)。把它们合并成一个线形表C，使得：当m二n时，C
2、=xl,yl,x2,y2, *xn,yn,，xm当nm时，C=y1,x1,y2,x2, *ym,xm,，yn输出线形表C。对合并的链表C进行直接插入排序，输出链表D。此次课程设计实验的数据位A表(30，41,15,12,56,80)B表(23,56,78,23,12,33,79,90,55)A表(30，41,15,12,56,80,23,12,34)B表(23,56,78,23,12)2.1.1链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组 成，结点可以在运行时动态生成。每个结点包括两个
3、部分：一个是存储数据元素的数据 域，另一个是存储下一个结点地址的指针域。通常我们把链表画成用箭头相连接的结点相比于线的序列，节点之间的箭头表示指针。在c语言中，链表用结构指针来描述。 性表顺序结构，链表比较方便插入和删除操作。(1) 线性表的单链表存储结构ypedef struct NodeElemType data;struct Node *next; Node;typedef struct Node *Linklist;(2) 实现两个链表的简单合并算法如下：Void Mergelist_L(Linklist & La,Linklist & Lb,Linklist & Lc)已知单线性链表
4、La和Lb的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的数据元素也按非递减排列。InitList(Lc);i=j=l;k=O;Laen=Listlength(La);Lben=ListLength(Lb);While(iv=Laen)&(j=Lb_len)/La和 Lb 均非空Getelem(La, i, ai);Getelem(Lb, j, bj);If(ai=bj)Listinsert(Lc, +k ai);+i;Else Listinsert(Lc, +k bj);+j;While(iv=La_len)Getelem(La, i+, ai);Listinsert(Lc,
5、+k, ai);While(jnex t=N ULL;/先建立一个带头结点的单链表For(i=n;in; i)p=(LinkLis t)malloc(sizeof(LNode), /生成新结点scanf(&pdata);pnext=Lnext;Lnext二p;/CrateList_L2.1.4算法设计程序的基本功能，首先建立建立单链表，向单链表中输入元素，然后输出单链表, 将两个单链表进行合并。先建立两个链表，假设分别为La=(xl,x2,xn)，Lb=(yl,y2,丫口)，它们的长度 分别 为a,b。若ab,则把这两个链表合并后，要求新链表Lc Lc=xl,yl,x2,y2, xn,yn,若ab，则新表Lc= yl,xl，y2, x2,yn,xn并输出Lc。本程序经过调试后运行以后有中文提示输入链表a的长度，然后手动输入链表中的 元素，回车键后提示输入链表b的长度，再输入链表b的元素，回车键后本程序将按照 设计需求自动进行两个链表的合并，最后
