实现两个链表的合并

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 当n>m时，C=y1,x1,y2,x2,ym,xm,yn （3）输出线性表C：（4） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。测试数据：（1） A表（

2、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

3、表中的数据元素，最后在插入B表中剩余的数据元素），再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。模块划分:(1) 结构体struct Node的创建。(2) struct Node *create（）链表的创建。(3) void print(struct  Node  *head)功能是对链表进行输出。 (4) struct  Node * inter_link(struct  Node

4、60;* chain1, int a, struct  Node * chain2, int b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5) void InsertSort(struct  Node  *p,int m)算法的功能是对一合并好的链表进行升序插入排序。 (6) main()函数主要是对算法进行测试。数据结构：数据结构定义如下：struct Node

5、60;       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 /结构体 &#

6、160;   long int number;    struct Node *next; struct Node *create(int a)/链表创建函数     int n;    struct Node *p1, *p2, *head;    head =

7、60;NULL;    n = 0;    p2 = p1 = (struct Node *) malloc(L); /分配内存     scanf("%ld", &p1->number);    while (a)/录入链表信息     

8、60;       n = n + 1;        if (n = 1)            head = p1;        else &#

9、160;          p2->next = p1;        p2 = p1;        p1 = (struct Node *) malloc(L);      

10、60; if (a != 1)/分配内存             scanf("%ld", &p1->number);        a-; /控制输入的个数         p2->next = N

11、ULL;    return (head);/链表创建函数结束  void print(struct Node *head)/输出函数     struct Node *p;    p = head;    printf("数字:n");     if (head !=

12、 NULL)        do/循环实现输出                     printf("%ld", p->number);           &#

13、160;printf("     ");            p = p->next;         while (p != NULL);    printf("n"); /链表的交叉合并算

14、法  struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)     int temp;    struct Node *head, *p1, *p2, *pos;  &

15、#160; /*判断a，b大小并合并 */     if (a >= b)         head = p1 = chain1;        p2 = chain2;     else/*b>a*/ &#

16、160;       head = p1 = chain2;        p2 = chain1;        temp = a, a = b, b = temp; /*交换a和b*/   

17、60;     /*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/     pos = head; /*此时pos指向p1中的第一个元素*/     while (p2 != NULL) /漂亮，蛇形插入         p1 = p1->next;  &

18、#160;     pos->next = p2;        pos = p2;        p2 = p2->next;        pos->next = p1;   &

19、#160;    pos = p1;        return head;/对合并好的链表进行排序  void InsertSort(struct Node *p, int m)/排序函数     int i, j, t;    struct Node *k

20、;    k = p;    for (i = 0; i < m - 1; i+)         for (j = 0; j < m - i - 1; j+)   &

21、#160;         if (p->number > (p->next)->number)                 t = p->number;        

22、60;       p->number = (p->next)->number;                (p->next)->number = t;            

23、            p = p->next;                p = k;    /主函数  int main()/main函数     struct

24、60;Node *p1, *p2;    int a;    int b;    int h;    printf("请输入第一个链表:n");     printf("n输入链表的长度a:n");     scanf("%d", &

25、;a);    printf("请输入链表数据：");     p1 = create(a);    printf("n你刚才输入的第一个链表信息:n ");     print(p1);    printf("n 请输入第二个链表:n");     prin

26、tf("n输入链表的长度b:n");     scanf("%d", &b);    printf("请输入链表数据：");     p2 = create(b);    printf("n你刚才输入的第二个链表的信息:n");     print(p2);  

27、  p1 = inter_link(p1, a, p2, b);    h = a + b;    printf("n合并后的链表n：");     print(p1);    InsertSort(p1, h);    printf("n排序后的链

28、表:n");     print(p1);return 0;测试结果：   （1）（2）测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。题目：可变长顺序表设计基本要求：（1）使用动态数组结构。（2）顺序表的操作包括：初始化、求数据元素个数、插入、删除、取数据元素，编写每个操作的函数。（3）设计一个测试主函数。测试数据: 4，5，6，7，8算法思想：可变长顺序表的设计，主要是利用动态数组结构的设计方法。动态数组是指用动态内存分配方法定义的数组，它其中的元素的个数是在用户申请动态数组空

29、间时才确定的。此外，用键盘输入顺序表的元素，进行建立顺序表。依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。 模块划分：（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 ListLeng

30、th_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 stru

31、ctDatatype *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

32、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

33、;/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 = (Datatype *) realloc(L.elem,L.length*sizeof(Datatype);printf("输入数据:");for(i = 0;i <= L.length-1;i+) s

34、canf("%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) retu

35、rn 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的合法值

36、为<=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, Data

37、type &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;

38、/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

39、(); 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.输出一个顺序表"

40、); 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

41、 = 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.从顺序表中取出一个元素");

42、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.销毁线性