数据结构课程设计-两个链表合并-星

课程设计说明书NO.1沈阳大学两个链表的合并1.课程设计目的实现对两个的链表的交叉合并，输出线形表C用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。掌握对线性表的链式表示和实现，实现插入的操作。了解链表交叉合并的方法和直接插入排序法的思想，并深刻掌握算法的格式和应用。提高对数据结构的理解和应用，增强个人动手实践能力和逻辑分析能力。2.设计方案论证2.1设计思路本课程设计将对链表的交叉合并和直接插入排序的实现。首先将两个链表进行交叉合并，合并的要求如下：建立两个链表A和B，链表元素个数分别为m和n个。假设元素分别为(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。对合并的链表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链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。通常我们把链表画成用箭头相连接的结点课程设计说明书NO.2沈阳大学的序列，节点之间的箭头表示指针。在c语言中，链表用结构指针来描述。相比于线性表顺序结构，链表比较方便插入和删除操作。（1）线性表的单链表存储结构ypedefstructNode{ElemTypedata;structNode*next;}Node;typedefstructNode*Linklist;（2）实现两个链表的简单合并算法如下：VoidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){//已知单线性链表La和Lb的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，Lc的数据元素也按非递减排列。InitList(Lc);i=j=1;k=0;La_len=Listlength(La);Lb_len=ListLength(Lb);While((i=La_len)&&(j=Lb_len)){//La和Lb均非空Getelem(La,i,ai);Getelem(Lb,j,bj);If(ai=bj){Listinsert(Lc,++kai);++i;}Else{Listinsert(Lc,++kbj);++j;}}While(i=La_len){Getelem（La,i++,ai）;Listinsert(Lc,++k,ai);}While(j=Lb_len){Getelem(Lb,j++,bj);Listinsert(Lc,++k,bj);}}//Mergelist（3）把元素插入到链表当中课程设计说明书NO.3沈阳大学在链表的合并中常用的操作是插入，要在线性表的两个元素之间出入一个新的元素x。为了插入元素x，首先要生成一个数据域为x的结点，然后插入数据元素x。根据插入操作的逻辑定义，还要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a，b和x之间的逻辑变化。上述指针修改语句描述为,s—next=p—next;p—next=s;单链表中插入结点时的指针变化情况如图所示：p图1单链表中插入结点时的指针变化情插入元素的代码如下：statusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的单链线性表L中第i个位置之前插入元素ep=l;j=0;while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点if(!P||ji-1)returnERROR;//i小于1或者大于表长+1s=（LinkList）malloc(sizeof(LNode));//生成新结点s-date=e;s-next=p-next;//插入L中p-next=s;returnOK;}//ListInsert_L（4）在链表中删除元素在线性表中删除元素b时，为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需改动节点a中的指针域即可。假设p为指向节点a的指针，则修改指针的语句为Abx课程设计说明书NO.4沈阳大学p-next=p-next-next;删除节点时指针变化情况如图2所示图2单链表删除节点时指针变化情况在已知单链表中元素插入或插入或删除的确切位置的情况下，在单链表中插入删除一个结点时，仅需修改指针而不需要移动元素。删除元素代码如下:StatusListInsert_L(LinkList&L,intI,ElemTypee){//在带头结点的单链表线性表L中,删除第i个元素，并由e返回其值p=L;j=0;while(p&&ji-1){//寻找第i-1个结点，并令p指向其前驱p=p—next;+j:}If(!(p—next)||ji-1)returnERROR;//删除位置不合理q=p—next;p—next=q—next;//删除并释放结点e=q—data;free(q);//释放函数retrunOK;}//ListDelete_L2.1.2链表的合并链表的合并是将两个链表合并成一个链表。假设两个链表LA和LB头指针为La，Lb，要归并La和Lb得到链表Lc，pa和pb分别指向La和Lb表中当前待比较插入的结点，而pc指向Lc当前最后一个结点，若pa—datapb—data,则将pa所指结点链接到pc所指结点之后，，否则将pb所指结点链接到pc所指结点之后。当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件pa和pb皆非空，当其中一abc课程设计说明书NO.5沈阳大学个为空时，说明有一个表的元素已归并完，则是要将另一个表的剩余段链接在pc所指结点之在内部排序中，如果按照排序过程中依据的不同原则进行分类，则大致可以分为插入排序、交换排序、选择排序、归并排序、和计数排序5类。通常在排序过程中需进行一下两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置转移到另一个位置。前一个基本操作是对于任何排序方法来说都是必要的，而后者可以通过改变记录的储存方式来来予以避免。且为了研究方便起见，设关键字均为整数。待排序、记录的数typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项Typedefstruct{RedTyper[MSXSIZE+1];//r[0]闲置或用作哨兵单元Intlength;//顺序表长度}SqList//顺序表类型本课程设计主要是应用直接插入排序将合并的链表进行排序。直接插入排序是一种最简单的排序方法，他的基本操作是将一个记录插入已排好序的有序表中，从而得到一个新的、数据记录增一得有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1.i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r1.i[]；并且和顺序表查找类似，在r[0]处设置监视哨。在自i-1起往前收索的过程中，可以同时后已记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看做一个有序的子序列，然后从第二个记录起逐个插入，直至整个序列变成按关键字有序序列为止。链表直接插入排序的算法如下图3所示voidInsertSort(SqList&L){//对顺序表L作直接插入排序。For（i=2;i=L.length;++i）If(LT(L.r[i].Key,L.r[i-1].Key)){//“（”，需要将L.r[i]插入有序子表L.r[0]=L.r[i]L.r[i]=L.r[i-1];For(j=i-2;LT(L.r[0].Key,L.r[j].Key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}课程设计说明书NO.6沈阳大学}//InsertSort2.1.3链表的排序排序是计算机程序设计中的一个重要操作，他的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中的存储器不同，可将排序方法分为两大类；一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程。另一类是外部排序，指的是待排序记录的数量很大，，以至内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。在链表的操作中常用到两个标准函数malloc和free。通常,在设有“指针”数据类型的高级语言中均存在与其相应的过程与函数。假设p和q是LinkList型的结点，则执行p=(LinkList)malloc(sizeof(LNode))的作用是由系统生成一个Lnode型的结点，同时将该结点的起始位置赋给指针变量p；反之执行free的作用是由系统回收一个LNode型的结点，，回收后的空间可以备做再次生成结点时用。因此，单链表和顺序存储不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需要预先分配划定，而是可以由系统即使生成。因此建立线性表的链式存储结构的过程就是动态生成链表的过程。即从“空表”的初始状态起，一次建立个元素的结点，并逐个插入链表。单链表的建立算法如下，其时间复杂度为O(n×n)。ViodCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。L=（LinkList）malloc(sizef(LNode));L—next=NULL;//先建立一个带头结点的单链表For(i=n;in;--i){p=(LinkList)malloc(sizeof(LNode)),//生成新结点scanf(&p—data);p—next=L—next;L—next=p;}}//CrateList_L课程设计说明书NO.7沈阳大学2.1.4算法设计程序的基本功能，首先建立建立单链表，向单链表中输入元素，然后输出单链表，将两个单链表进行合并。先建立两个链表，假设分别为La=(x1,x2,…xn)，Lb=(y1,y2,…yn)，它们的长度分别为a,b。若ab,则把这两个链表合并后，要求新链表LcLc=x1,y1,x2,y2,…xn,yn…,。若ab，则新表Lc=y1,x1，y2,x2,…yn,xn并输出Lc。本程序经过调试后运行以后有中文提示输入链表a的长度，然后手动输入链表中的元素，回车键后提示输入链表b的长度，再输入链表b的元素，回车键后本程序将按照设计需求自动进行两个链表的合并，最后进行新链表c的插入排序。输出排好序的新链表d的相关信息。程序的流程图如下所示：判断mn的大小对c链表进行插入排序图3程序流程图建立链表a建立链表b合并ab链表得到c链表得到d链表课程设计说明书NO.8沈阳大学（1）创建链表函数的设计创建链表，首先由主函数输入要创建的链表长度n，在由主函数将参数传递到创建链表函数creat，由For循环控制表节点的创建，由malloc函数开辟新的结点空间，创建链表结束后，由print函数将链表元素输出。创建链表函数的实现代码如下：#includestdlib.h#includestdio.h#includeconio.h#includemalloc.h#defineLsizeof(structNode)structNode//结构体{longintnumber;struct