实现两个链表的合并(13页).doc
-实现两个链表的合并-第 13 页数据结构课程设计 题目一：实现两个链表的合并题目二：可变长顺序表设计班 级： 计科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 当n>m时，C=y1,x1,y2,x2,ym,xm,yn （3）输出线性表C：（4） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。测试数据：（1） A表（30，41，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表中的数据元素，在偶数位插入B表中的数据元素，在奇数位插入A表中的数据元素，最后在插入B表中剩余的数据元素），再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。模块划分:(1) 结构体struct Node的创建。(2) struct Node *create（）链表的创建。(3) void print(struct Node *head)功能是对链表进行输出。 (4) struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5) void InsertSort(struct Node *p,int m)算法的功能是对一合并好的链表进行升序插入排序。 (6) main()函数主要是对算法进行测试。数据结构：数据结构定义如下：struct Node long int number; struct Node *next;源程序：#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<malloc.h>#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->number); 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) 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/*b>a*/ head = 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)/排序函数 int i, j, t; struct Node *k; k = p; for (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"); 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(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;测试结果： （1）（2）测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。题目：可变长顺序表设计基本要求：（1）使用动态数组结构。（2）顺序表的操作包括：初始化、求数据元素个数、插入、删除、取数据元素，编写每个操作的函数。（3）设计一个测试主函数。测试数据: 4，5，6，7，8算法思想：可变长顺序表的设计，主要是利用动态数组结构的设计方法。动态数组是指用动态内存分配方法定义的数组，它其中的元素的个数是在用户申请动态数组空间时才确定的。此外，用键盘输入顺序表的元素，进行建立顺序表。依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。 模块划分：（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(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(SqList &L, int i, Datatype &e)（10）输出线性表L void Output(SqList L)（11）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 /线性表存储空间的初始分配量#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_SIZE *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) em = (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 &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个数据元素的值,i的合法值为<= i <= ListLength_Sq(L)if (i < 1)|(i > L.length) return 0; /i值不合法elsee = 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 < 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; /插入位置及之后的元素后移*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 < 1) | (i > L.length) return 0; /i值不合法p = &(L.elemi - 1); /p为被删除元素的位置e = *p; /被删除元素的值赋给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");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("* "); 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("*"); 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.销毁线性表"); for(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); 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: printf("请输入要删除元素的位置："); fflush(stdin); scanf("%d",&i); ListDelete_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）测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。
