数据结构课程设计-两个链表合并-星(共16页).doc

《数据结构课程设计-两个链表合并-星(共16页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-两个链表合并-星(共16页).doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上两个链表的合并1.课程设计目的 实现对两个的链表的交叉合并，输出线形表C用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。掌握对线性表的链式表示和实现，实现插入的操作。了解链表交叉合并的方法和直接插入排序法的思想，并深刻掌握算法的格式和应用。提高对数据结构的理解和应用，增强个人动手实践能力和逻辑分析能力。2.设计方案论证2.1设计思路本课程设计将对链表的交叉合并和直接插入排序的实现。首先将两个链表进行交叉合并，合并的要求如下：建立两个链表A和B，链表元素个数分别为m和n个。假设元素分别为(x1,x2,xm)，和(y1,y2, yn)。把它们合并成一个线形表C

2、，使得：当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链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结

3、点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。通常我们把链表画成用箭头相连接的结点的序列，节点之间的箭头表示指针。在c语言中，链表用结构指针来描述。 相比于线性表顺序结构，链表比较方便插入和删除操作。（1）线性表的单链表存储结构ypedef struct Node ElemType 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=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, +k ai);+i;Else Listinsert(Lc, +k bj);+j;While(i=La_len)Getelem（La, i+, ai）;Listinsert

5、(Lc, +k, ai);While(jnext=pnext;pnext=s;单链表中插入结点时的指针变化情况如图所示： p Abx图1 单链表中插入结点时的指针变化情插入元素的代码如下：status ListInsert_L(LinkList &L, int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素ep=l;j=0;while(p&jnext;+j;/寻找第i-1个结点if(!P|ji-1)return ERROR; /i小于1或者大于表长+1s=（LinkList）malloc(sizeof(LNode); /生成新结点s-date=e; s-next=

6、p-next; /插入L中p-next=s;return OK;/ListInsert_L （4）在链表中删除元素在线性表中删除元素b时，为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需改动节点a中的指针域即可。假设p为指向节点a的指针，则修改指针的语句为p-next=p-next-next;删除节点时指针变化情况如图2所示abc图2 单链表删除节点时指针变化情况在已知单链表中元素插入或插入或删除的确切位置的情况下，在单链表中插入删除一个结点时，仅需修改指针而不需要移动元素。删除元素代码如下:Status ListInsert_L(LinkList&L,int I,ElemType e

7、)/在带头结点的单链表线性表L中,删除第i个元素，并由e返回其值p=L;j=0;while (p&jnext;+j:If(!(pnext)|ji-1)return ERROR;/删除位置不合理q=pnext;pnext=qnext;/删除并释放结点e=qdata; free(q);/释放函数retrun OK;/ListDelete_L2.1.2链表的合并 链表的合并是将两个链表合并成一个链表。假设两个链表LA和LB头指针为La，Lb，要归并La和Lb得到链表Lc，pa和pb分别指向La和Lb表中当前待比较插入的结点，而pc指向Lc当前最后一个结点，若padatadata,则将pa所指结点链接

8、到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，则是要将另一个表的剩余段链接在pc所指结点之在内部排序中，如果按照排序过程中依据的不同原则进行分类，则大致可以分为插入排序、交换排序、选择排序、归并排序、和计数排序5类。通常在排序过程中需进行一下两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置转移到另一个位置。前一个基本操作是对于任何排序方法来说都是必要

9、的，而后者可以通过改变记录的储存方式来来予以避免。且为了研究方便起见，设关键字均为整数。待排序、记录的数typedef structKeyType key; /关键字项InfoType otherinfo;/其他数据项Typedef structRedType rMSXSIZE+1;/r0闲置或用作哨兵单元Int length;/顺序表长度SqList/顺序表类型本课程设计主要是应用直接插入排序将合并的链表进行排序。直接插入排序是一种最简单的排序方法，他的基本操作是将一个记录插入已排好序的有序表中，从而得到一个新的、数据记录增一得有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记

10、录的有序子序列r1.i-1中插入一个记录ri后，变成含有i个记录的有序子序列r1.i；并且和顺序表查找类似，在r0处设置监视哨。在自i-1起往前收索的过程中，可以同时后已记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看做一个有序的子序列，然后从第二个记录起逐个插入，直至整个序列变成按关键字有序序列为止。链表直接插入排序的算法如下图3所示void InsertSort (SqList&L) /对顺序表L作直接插入排序。For（i=2;inext=NULL;/先建立一个带头结点的单链表For(i=n;in;-i)p=(LinkList)malloc(sizeof(LNode),

11、/生成新结点scanf(&pdata);pnext=Lnext;Lnext=p;/CrateList_L2.1.4算法设计 程序的基本功能，首先建立建立单链表，向单链表中输入元素，然后输出单链表，将两个单链表进行合并。先建立两个链表，假设分别为La=(x1,x2,xn)， Lb=(y1,y2, yn)，它们的长度分别 为a,b。若ab,则把这两个链表合并后，要求新链表Lc Lc=x1,y1,x2,y2,xn,yn, 。若ab，则新表Lc= y1,x1，y2, x2,yn,xn并输出Lc。本程序经过调试后运行以后有中文提示输入链表a的长度，然后手动输入链表中的元素，回车键后提示输入链表b的长度，

12、再输入链表b的元素，回车键后本程序将按照设计需求自动进行两个链表的合并，最后进行新链表c的插入排序。输出排好序的新链表d的相关信息。程序的流程图如下所示：建立链表a 建立链表b合并ab链表得到c链表判断 m n 的大小 对c链表进行插入排序得到d链表图3 程序流程图（1）创建链表函数的设计创建链表，首先由主函数输入要创建的链表长度n，在由主函数将参数传递到创建链表函数creat，由For循环控制表节点的创建，由malloc函数开辟新的结点空间，创建链表结束后，由print函数将链表元素输出。创建链表函数的实现代码如下：#include#include#include#include#defin

13、e L sizeof(struct Node)struct Node /结构体 long int number; struct Node *next;struct Node *create(int a)/链表创建函数 int n; struct Node *p1, *p2, *head; head = NULL; n = 0; p2 = p1 = (struct Node *) malloc(L); /分配内存 scanf(%ld, &p1-number); while (a)/录入链表信息 n = n + 1; if (n = 1) head = p1; else p2-next = p1;

14、 p2 = p1; p1 = (struct Node *) malloc(L); if (a != 1)/分配内存 scanf(%ld, &p1-number); a-; /控制输入的个数 p2-next = NULL; return (head);/链表创建函数结束（2）输出链表的函数的实现待链表输入完成后，定义单链表的头结点*p，通过运用一个循环语句，将链表内的元素一一输出在执行程序界面上。void print(struct Node *head)/输出函数 struct Node *p; p = head; printf(数字:n); if (head != NULL) do/循环实现

15、输出 printf(%ld, p-number); printf( ); p = p-next; while (p != NULL); printf(n);（3）链表的交叉合并struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp; struct Node *head, *p1, *p2, *pos; /*判断a，b大小并合并 */ if (a = b) head = p1 = chain1; p2 = chain2; else/*ba*/ head = p1 = c

16、hain2; p2 = chain1; temp = a, a = b, b = temp; /*交换a和b*/ /*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/ pos = head; /*此时pos指向p1中的第一个元素*/ while (p2 != NULL) /漂亮，蛇形插入 p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; return head;（4）对合并好的链表进行插入排序void InsertSort(struct Node *p, int m)/排序

17、函数 int i, j, t; struct Node *k; k = p; for (i = 0; i m - 1; i+) for (j = 0; j number (p-next)-number) t = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next; p = k; （5）主函数的定义int main()/main函数 struct Node *p1, *p2; int a; int b; int h; printf(请输入第一个链表:n); printf(n输入链表的长度a:n); scanf

18、(%d, &a); printf(请输入链表数据：); p1 = create(a); printf(n你刚才输入的第一个链表信息:n ); print(p1); printf(n 请输入第二个链表:n); printf(n输入链表的长度b:n); scanf(%d, &b); printf(请输入链表数据：); p2 = create(b); printf(n你刚才输入的第二个链表的信息:n); print(p2); p1 = inter_link(p1, a, p2, b); h = a + b; printf(n合并后的链表n：); print(p1); InsertSort(p1, h

19、); printf(n排序后的链表:n); print(p1); return 0;3运行结果与分析（1）打开软件，输入代码，运行程序，然后中文提示输入链表a的长度，回车之后提示输入链表中的数据元素。录入第一组测试数据完成以后显示链表a的信息，这里mn。如下图所示：图4 建立链表（2）如果输入的元素个数超过链表定义的长度，则只录入前面的链表定义长度的那些元素。演示如下图所示：图5 错误操作结果继续按照提示输入链表b的长度和数据元素。 如下所示：图6 第一组数据运行结果(3)录入第二组测试数据运行结果如下图所示：图7第二组数据运行结果4课程设计体会这几天的课程设计，让我对以往课堂上学习到的理论知

20、识得到了更深刻的理解，通过自己设计算法，调试程序一系列操作，最后才能使程序正确无误的运行，这一系列操作虽然对于我来说很复杂困难，但是通过查阅资料，以及同学的帮忙最终还是完成了本次课程设计。以往对于链表的问题有些一知半解，有些东西也不是特别的明白清楚，有了这次课设感觉自己把以往认为很抽象的问题变得更具体，自己亲手来做这次课程设计，感觉有些明白了数据结构这门课程其中的奥妙。我做两个链表的合并，想象起来并不是特别的困难，用语言很容易的就可以表达出来，对于这次课设就是编写代码来完成这一系列的操作，编写代码需要相当的加小心，一个字母的错误就能导致整个程序的错误，所以编写代码需要心细不能马虎任何一个小的字

21、母。我经过查阅资料，询问同学，多次的修改程序才使得程序最后的成功运行。有了这次课设，不仅让我对这门课程有了新的认识和对知识的更深刻的理解，同时也磨练了自己的耐心和毅力。以后学习中还需要继续努力学好这门课程。5参考文献1赵国玲. C语言与数据结构M. 北京：电子工业出版社，1999.11：120-1462严蔚敏,吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，2006.10：44-523 严蔚敏.数据结构 C语言M.北京: 清华大学出版社,2006.10：110-1354 谭浩强. C程序设计指导M.北京：清华大学出版社,20055 潘新民, 王燕芳. 微型计算机控制技术M, 第2版.

22、 北京: 电子工业出版社, 2003.4：305-350附录:源程序#include#include#include#include#define L sizeof(struct Node)struct Node /结构体 long int number; struct Node *next;struct Node *create(int a)/链表创建函数 int n; struct Node *p1, *p2, *head; head = NULL; n = 0; p2 = p1 = (struct Node *) malloc(L); /分配内存 scanf(%ld, &p1-numbe

23、r); while (a)/录入链表信息 n = n + 1; if (n = 1) head = p1; else p2-next = p1; p2 = p1; p1 = (struct Node *) malloc(L); if (a != 1)/分配内存 scanf(%ld, &p1-number); a-; /控制输入的个数 p2-next = NULL; return (head);/链表创建函数结束void print(struct Node *head)/输出函数 struct Node *p; p = head; printf(数字:n); if (head != NULL)

24、do/循环实现输出 printf(%ld, p-number); printf( ); p = p-next; while (p != NULL); printf(n);/链表的交叉合并算法struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp; struct Node *head, *p1, *p2, *pos; /*判断a，b大小并合并 */ if (a = b) head = p1 = chain1; p2 = chain2; else/*ba*/ head =

25、 p1 = chain2; p2 = chain1; temp = a, a = b, b = temp; /*交换a和b*/ /*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/ pos = head; /*此时pos指向p1中的第一个元素*/ while (p2 != NULL) /漂亮，蛇形插入 p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; return head;/对合并好的链表进行排序void InsertSort(struct Node *p, int m)

26、/排序函数 int i, j, t; struct Node *k; k = p; for (i = 0; i m - 1; i+) for (j = 0; j number (p-next)-number) t = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next; p = k; /主函数int main()/main函数 struct Node *p1, *p2; int a; int b; int h; printf(请输入第一个链表:n); printf(n输入链表的长度a:n); scanf(%

27、d, &a); printf(请输入链表数据：); p1 = create(a); printf(n你刚才输入的第一个链表信息:n ); print(p1); printf(n 请输入第二个链表:n); printf(n输入链表的长度b:n); scanf(%d, &b); printf(请输入链表数据：); p2 = create(b); printf(n你刚才输入的第二个链表的信息:n); print(p2); p1 = inter_link(p1, a, p2, b); h = a + b; printf(n合并后的链表n：); print(p1); InsertSort(p1, h); printf(n排序后的链表:n); print(p1); return 0;专心-专注-专业