实现两个链表的合并.docx

1、实现两个链表的合并数据结构课程设计 题目一：实现两个链表的合并题目二：可变长顺序表设计班 级： 计科1202班姓 名： 学 期：2013-2014学年第二学期题目1：实现两个链表的合并基本要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。 （2）假设元素分别为(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 （3）输出线性表C：（4）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。测试数据：（1）A表（30，41，15，12，56，80

2、） B表（23，56，78，23，12，33，79，90，55） （2）A表（30，41，15，12，56，80，23，12，34） B表（23，56，78，23，12）算法思想 ：首先我们需要建立两个链表A,B，A链表的元素个数为m；B链表的元素个数为n；在将A,B链表进行合并，根据m和n的大小关系决定链表C的元素顺序（当m=n时，应该先插入A表中的数据元素，在偶数位插入A表中的数据元素，在奇数位插入B表中的数据元素，最后在插入A表中剩余的数据元素；当mn时，应该先插入B表中的数据元素，在偶数位插入B表中的数据元素，在奇数位插入A表中的数据元素，最后在插入B表中剩余的数据元素），再将C经行直

3、接插入排序得到一个新的链表D；最后输出ABCD的相关信息。模块划分:(1)结构体structNode的创建。(2)structNode*create（）链表的创建。(3)voidprint(structNode*head)功能是对链表进行输出。 (4)structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5)voidInsertSort(structNode*p,intm)算法的功能是对一合并好的链表进行升序插入排序。 (6)main(

4、)函数主要是对算法进行测试。数据结构：数据结构定义如下：structNodelongintnumber;structNode*next;源程序：#include#include#include#include#defineLsizeof(structNode)structNode/结构体 longintnumber;structNode*next;structNode*create(inta)/链表创建函数 intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);/分配内存 scanf(%ld,&p1-nu

5、mber);while(a)/录入链表信息 n=n+1;if(n=1)head=p1;elsep2-next=p1;p2=p1;p1=(structNode*)malloc(L);if(a!=1)/分配内存 scanf(%ld,&p1-number);a-;/控制输入的个数 p2-next=NULL;return(head);/链表创建函数结束 voidprint(structNode*head)/输出函数 structNode*p;p=head;printf(数字:n); if(head!=NULL)do/循环实现输出 printf(%ld,p-number);printf();p=p-ne

6、xt;while(p!=NULL);printf(n);/链表的交叉合并算法 structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb)inttemp;structNode*head,*p1,*p2,*pos;/*判断a，b大小并合并*/ if(a=b)head=p1=chain1;p2=chain2;else/*ba*/head=p1=chain2;p2=chain1;temp=a,a=b,b=temp;/*交换a和b*/ /*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/ pos=head;/*

7、此时pos指向p1中的第一个元素*/ while(p2!=NULL)/漂亮，蛇形插入 p1=p1-next;pos-next=p2;pos=p2;p2=p2-next;pos-next=p1;pos=p1;returnhead;/对合并好的链表进行排序 voidInsertSort(structNode*p,intm)/排序函数 inti,j,t;structNode*k;k=p;for(i=0;im-1;i+)for(j=0;jnumber(p-next)-number)t=p-number;p-number=(p-next)-number;(p-next)-number=t;p=p-nex

8、t;p=k;/主函数 intmain()/main函数 structNode*p1,*p2;inta;intb;inth;printf(请输入第一个链表:n); printf(n输入链表的长度a:n); scanf(%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

9、(p2);p1=inter_link(p1,a,p2,b);h=a+b;printf(n合并后的链表n：); print(p1);InsertSort(p1,h);printf(n排序后的链表:n); print(p1);return0;测试结果：（1）（2）测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。题目：可变长顺序表设计基本要求：（1）使用动态数组结构。（2）顺序表的操作包括：初始化、求数据元素个数、插入、删除、取数据元素，编写每个操作的函数。（3）设计一个测试主函数。测试数据: 4，5，6，7，8算法思想：可变长顺序表的设计，主要是利用动态数组结构的设计方法。

10、动态数组是指用动态内存分配方法定义的数组，它其中的元素的个数是在用户申请动态数组空间时才确定的。此外，用键盘输入顺序表的元素，进行建立顺序表。依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。 模块划分：（1）结构体typedef struct的创建（2）初始化空表Datatype InitList_Sq(SqList &L)（3）建立顺序表Datatype CreatList_Sq(SqList &L,int n)（4）销毁线性表Datatype DestoryList_Sq(SqList &L)（5）判定是否为空表Datatype ListEmpty_Sq(SqLis

11、t L)（6）求L表中的元素的个数int ListLength_Sq(SqList L)（7）取表中的的第i个元素Datatype GetElem_Sq(SqList L, int i, Datatype &e)（8）插入节点Datatype ListInsert_Sq(SqList &L, int i, Datatype e)（9）删除节点Datatype ListDelete_Sq(SqList &L, int i, Datatype &e)（10）输出线性表L void Output(SqList L)（11）main()函数主要是调用以上函数对算法进行测试数据结构： 1、顺序表结构体定

12、义typedef structDatatype *elem; int length; int listsize; SqList;2、动态数组 动态申请空间：L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);源程序：#define NULL 0#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量#include#includetypedef int Datatype; typedef structDatatype *el

13、em; /存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位)SqList;/1.初始化空表Datatype InitList_Sq(SqList &L) L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);if(! L.elem) exit(-1); /存储分配失败 L.length = 0; /空表长度为L.listsize = LIST_INIT_SIZE; /初始存储容量return 1;/2.建立顺序表LDatatype Cr

14、eatList_Sq(SqList &L,int n) int i; Datatype e;printf(输入顺序表的长度:);scanf(%d,&n);L.length = n;if (L.length LIST_INIT_SIZE) L.elem = (Datatype *) realloc(L.elem,L.length*sizeof(Datatype);printf(输入数据:);for(i = 0;i = L.length-1;i+) scanf(%d,&e); L.elemi = e; return 1;/3.销毁线性表Datatype DestoryList_Sq(SqList

15、&L) if (L.elem) free(L.elem); L.elem = NULL; L.length = L.listsize = 0; return 1; return 0;/4.判定是否空表Datatype ListEmpty_Sq(SqList L) if (L.length) return 0; return 1;/5.求L中数据元素的个数int ListLength_Sq(SqList L) return L.length;/6.取表第i个元素Datatype GetElem_Sq(SqList L, int i, Datatype &e) /用e返回顺序表L中第i个数据元素的

16、值,i的合法值为= i = ListLength_Sq(L) if (i L.length) return 0; /i值不合法 else e = L.elemi-1; return 1;/7.插入结点Datatype ListInsert_Sq(SqList &L, int i, Datatype e) /在顺序线性表L中第i个位置之前插入新的元素e,i的合法值为=i=ListLength_Sq(L)+1Datatype *q,*p,*newbase; if(i L.length+1) return 0; /i值不合法q = &(L.elemi-1); /q为插入位置for (p = &(L.

17、elemL.length - 1);p = q;-p) *(p+1) = *p; /插入位置及之后的元素后移*q = e; /插入e+L.length; /表长增return 1;/8.删除结点Datatype ListDelete_Sq(SqList &L, int i, Datatype &e) /在顺序线性表L中删除第i个元素,并用e返回其值,i的合法值为= i = ListLength_Sq(L) Datatype *p,*q;if(i L.length) return 0; /i值不合法p = &(L.elemi - 1); /p为被删除元素的位置e = *p; /被删除元素的值赋给

18、eq = L.elem + L.length - 1; /表尾元素的位置for (+p;p = q;+p) *(p-1) = *p; /被删除元素之后的元素左移-L.length; /表长减return 1;/9.输出顺序表void Output(SqList L)/输出线性表L int i; for(i = 0;i L.length;i+) printf(%d ,L.elemi); printf(n); void put()/窗口边框 int i; for(i = 0;i 10;i +) printf( ); for(i = 0;i 31;i +) printf(*); printf(n);

19、void mainpp()/显示窗口 int i; put(); for(i = 0;i 10;i +) printf( ); printf(* ); printf(1.建立一个顺序表); for(i = 0;i 10;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i +) printf( ); printf(* ); printf(2.输出一个顺序表); for(i = 0;i 10;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i +) printf( ); printf(*

20、 ); printf(3.向顺序表中插入一个元素); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i +) printf( ); printf(* ); printf(4.删除顺序表中的一个元素); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* ); printf(5.从顺序表中取出一个元素); for(i = 0;i 2;i+) printf( ); printf(*);

21、printf(n); for(i = 0;i 10;i+) printf( ); printf(* );printf(6.求顺序表中数据元素个数); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* );printf(7.判断顺序表中是否为空); for(i = 0;i 4;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* );printf(8.销毁线性表); fo

22、r(i = 0;i 14;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* ); printf(0.退 出); for(i = 0;i 8;i+) printf( ); printf(*); printf(n); put(); int main()/主函数 int n = 0,i,j = 0,k = 1,m,q,x,y,e; SqList l,la,lc; InitList_Sq(l); mainpp(); while(k) printf(请选择-8：); scanf(%d,&m); getc

23、har(); switch(m) case 0:exit(0); case 1: CreatList_Sq(l,n); Output(l); break; case 2:Output(l);printf(n);break; case 3: printf(请输入要插入的元素的位置及其值：); fflush(stdin); scanf(%d,%d,&i,&x); ListInsert_Sq(l,i,x); Output(l); printf(n); break; case 4: printf(请输入要删除元素的位置：); fflush(stdin); scanf(%d,&i); ListDelet

24、e_Sq(l,i,y); Output(l); printf(n); break; case 5: printf(请输入要取出的元素的序号：); fflush(stdin); scanf(%d,&i); GetElem_Sq(l,i,e); printf(取出的第%d个元素为：%dn,i,e); break; case 6: printf(顺序表中数据元素的个数为：%d,ListLength_Sq(l); case 7: q = ListEmpty_Sq(l); if(q = 1) printf(此表为空); else printf(此表不空); printf(n); break; case 8: DestoryList_Sq(l); break; default :exit(0); printf(继续运行吗？Y（）/N（）：); scanf(%d,&k); if(!k) exit(0); return 0; 测试结果：（2）测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。