实现两个链表的合并

1、数据结构课程设计题目一：实现两个链表的合并题目二：可变长顺序表设计班 级：计科1202班姓 名：学 期：2013-2014学年第二学期Word文档题目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(3)输出线性表C:(4)用直接插入排序法对C进行升序排序，生成链表D,并输出链表Do测试数据：(1) A 表(30, 41 ,

2、 15, 12, 56, 80)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表中剩余的数据 元素；当m<n时，应该先插入B表中的数据元素，在

3、偶数位插入 B表中的数据 元素，在奇数位插入A表中的数据元素，最后在插入 B表中剩余的数据元素)， 再将C经行直接插入排序得到一个新的链表 D;最后输出ABCD的相关信息。 模块划分：(1)结构体struct Node的创建。(2) struct Node *create ()链表的创建。void print(struct Node *head)功能是对链表进行输出。(4) struct Node * inter_link(struct Node * chainl, int a, struct Node * chain2, i nt b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的

4、长短将行不通的 插入。(5) void InsertSort(struct Node *p,int m)算法的功能是对一合并好的链表进行 升序插入排序。(6) main()函数主要是对算法进行测试。数据结构：数据结构定义如下:struct Nodelong int number;struct Node *next;；源程序：#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<malloc.h>#define L sizeof(struct Node)struct Node 结构

5、体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;elsep2->next = p1;pl = (struct Node *) malloc(L)

6、;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)do/循环实现输出printf("%ld”, p->number);printf(" ");p = p->next; while (p != N

7、ULL);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/*b>a*/ Word文档head = pl = chain2;p2 = chainl;temp = a, a = b, b = te

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

9、 (i = 0; i < m - 1; i+) for (j = 0; j < m - i - 1; j+) if (p->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&quo

10、t;）;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

11、("n你刚才输入的第二个链表的信息：n");print(p2);pl = inter_link(p1, a, p2, b);h = a + b;printf("n合并后的链表n ：");print(pl);InsertSort(p1, h);printf("n排序后的链表:n");print(pl);return 0;测试结果：(2)测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确题目：可变长顺序表设计基本要求：(1)使用动态数组结构。(2)顺序表的操作包括：初始化、求数据元素个数、插入、删除、取数据元素，编写每

12、个操作的函数。(3)设计一个测试主函数。测试数据：4, 5, 6, 7, 8算法思想：可变长顺序表的设计，主要是利用动态数组结构的设计法。动态数组 是指用动态存分配法定义的数组，它其中的元素的个数是在用户申请动态数组空 问时才确定的。止匕外，用键盘输入顺序表的元素，进行建立顺序表。依次调用初 始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。模块划分：(1)结构体typedef struct的创建(2)初始化空表 Datatype InitList_Sq(SqList &L)(3)建立顺序表 Datatype CreatList_Sq(SqList &L,int n

13、)(4)销毁线性表 Datatype DestoryList_Sq(SqList &L)(5)判定是否为空表 Datatype ListEmpty_Sq(SqList 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(SqLi

14、st &L, int i, Datatype &e)(10)输出线性表 L void Output(SqList L)(II) main()函数主要是调用以上函数对算法进行测试数据结构：1、顺序表结构体定义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 /线性表存储空间的

15、初始分配量#define LISTINCREMENT 10线性表存储空间的分配增量#include<stdio.h>#include<iostream> typedef int Datatype;typedef structDatatype *elem;/存储空间基址int length; /当前长度int listsize; /当前分配的存储容量(以sizeof(ElemType)为单位) SqList;/1.初始化空表Datatype InitList_Sq(SqList &L)L.elem = (Datatype *)malloc(LIST_INIT_SI

16、ZE *sizeof(Datatype);if(! L.elem)exit(-1);/存储分配失败L.length = 0;/空表长度为L.listsize = LIST_INIT_SIZE;/ 初始存储容量return 1;/2.建立顺序表LDatatype CreatList_Sq(SqList &L,int n)int i;Datatype e;printf("输入顺序表的长度:");scanf("%d",&n);L.length = n;if (L.length > LIST_INIT_SIZE)L.elem = (Data

17、type *) 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 &L)if (L.elem)free(L.elem);L.elem = NULL;L.length = L.listsize = 0;return 1;return 0;/4.判定是否空表Dataty

18、pe 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个数据 元素的值，的合法值为<=i <= ListLength_Sq(L) if (i < 1)|(i > L.length) return 0; /i值不合法elsee = L.elemi-

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

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

21、p;q = L.elem + L.length - 1;for (+p;p <= q;+p)*(p-1) = *p;/被删除元素之后的元素左移-L.length;/ 表长减return 1;119 .输出顺序表void Output(SqList L) 输出线性表 Lint 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

22、(i = 0;i < 31;i +) printf("*");printf("n");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 < 1

23、0;i +)printf("");printf("* ");printf("2.输出一个顺序表");for(i = 0;i < 10;i+)printf("");printf("*");printf("n");for(i = 0;i < 10;i +)printf("");printf("* ");printf("3.向顺序表中插入一个元素");for(i = 0;i < 2;i+)printf(&

24、quot;");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(&qu

25、ot;* ");printf("5.从顺序表中取出一个元素");for(i = 0;i < 2;i+)printf("");printf("*");printf("n");for(i = 0;i < 10;i+)printf("");printf("* ");printf("6.求顺序表中数据元素个数");for(i = 0;i < 2;i+)printf("");printf("*");

26、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.销毁线性表&quo

27、t;);for(i = 0;i < 14;i+)printf("请选择-8 :");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

28、,i,j = 0,k = 1,m,q,x,y,e;SqList l,la,lc;InitList_Sq(l);mainpp();while(k)scanf("%d",&m);getchar();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:Word文档fflush(stdin);scanf("%d",&i);ListDelete_Sq(l,i,y);Output