實(shí)現(xiàn)兩個(gè)鏈表的合并

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目一：實(shí)現(xiàn)兩個(gè)鏈表的合并題目二：可變長(zhǎng)順序表設(shè)計(jì)班 級(jí)： 計(jì)科1202班姓 名： 學(xué) 期：2013-2014學(xué)年第二學(xué)期題目1：實(shí)現(xiàn)兩個(gè)鏈表的合并基本要求：（1）建立兩個(gè)鏈表A和B，鏈表元素個(gè)數(shù)分別為m和n個(gè)。 （2）假設(shè)元素分別為(x1,x2,xm)，和(y1,y2, yn)。把它們合并成一個(gè)線性表C： 當(dāng)m>=n時(shí)，C=x1,y1,x2,y2,xn,yn,xm 當(dāng)n>m時(shí)，C=y1,x1,y2,x2,ym,xm,yn （3）輸出線性表C：（4） 用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。測(cè)試數(shù)據(jù)：（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）算法思想 ：首先我們需要建立兩個(gè)鏈表A,B，A鏈表的元素個(gè)數(shù)為m；B鏈表的元素個(gè)數(shù)為n；在將A,B鏈表進(jìn)行合并，根據(jù)m和n的大小關(guān)系決定鏈表C的元素順序（當(dāng)m>=n時(shí)，應(yīng)該先插入A表中的數(shù)據(jù)元素，在偶數(shù)位插入A表中的數(shù)據(jù)元素，在奇數(shù)位插入B表中的數(shù)據(jù)元素，最后在插入A表中剩余的數(shù)據(jù)元素；當(dāng)m<n時(shí)，應(yīng)該先插入B表中的數(shù)據(jù)元素，在偶數(shù)位插入B表中的數(shù)據(jù)元素，在奇數(shù)位插入A

3、表中的數(shù)據(jù)元素，最后在插入B表中剩余的數(shù)據(jù)元素），再將C經(jīng)行直接插入排序得到一個(gè)新的鏈表D；最后輸出ABCD的相關(guān)信息。模塊劃分:(1) 結(jié)構(gòu)體struct Node的創(chuàng)建。(2) struct Node *create（）鏈表的創(chuàng)建。(3) void print(struct  Node  *head)功能是對(duì)鏈表進(jìn)行輸出。 (4) struct  Node * inter_link(struct  Node

4、60;* chain1, int a, struct  Node * chain2, int b)算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈表的長(zhǎng)短將行不通的插入。(5) void InsertSort(struct  Node  *p,int m)算法的功能是對(duì)一合并好的鏈表進(jìn)行升序插入排序。 (6) main()函數(shù)主要是對(duì)算法進(jìn)行測(cè)試。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)定義如下：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 /結(jié)構(gòu)體 &#

6、160;   long int number;    struct Node *next; struct Node *create(int a)/鏈表創(chuàng)建函數(shù)     int n;    struct Node *p1, *p2, *head;    head =

7、60;NULL;    n = 0;    p2 = p1 = (struct Node *) malloc(L); /分配內(nèi)存     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)/分配內(nèi)存             scanf("%ld", &p1->number);        a-; /控制輸入的個(gè)數(shù)         p2->next = N

11、ULL;    return (head);/鏈表創(chuàng)建函數(shù)結(jié)束  void print(struct Node *head)/輸出函數(shù)     struct Node *p;    p = head;    printf("數(shù)字:n");     if (head !=

12、 NULL)        do/循環(huán)實(shí)現(xiàn)輸出                     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的每個(gè)元素插在p2相應(yīng)元素之前，p1長(zhǎng)a,p2長(zhǎng)b*/     pos = head; /*此時(shí)pos指向p1中的第一個(gè)元素*/     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;/對(duì)合并好的鏈表進(jìn)行排序  void InsertSort(struct Node *p, int m)/排序函數(shù)     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;    /主函數(shù)  int main()/main函數(shù)     struct

24、60;Node *p1, *p2;    int a;    int b;    int h;    printf("請(qǐng)輸入第一個(gè)鏈表:n");     printf("n輸入鏈表的長(zhǎng)度a:n");     scanf("%d", &

25、;a);    printf("請(qǐng)輸入鏈表數(shù)據(jù)：");     p1 = create(a);    printf("n你剛才輸入的第一個(gè)鏈表信息:n ");     print(p1);    printf("n 請(qǐng)輸入第二個(gè)鏈表:n");     prin

26、tf("n輸入鏈表的長(zhǎng)度b:n");     scanf("%d", &b);    printf("請(qǐng)輸入鏈表數(shù)據(jù)：");     p2 = create(b);    printf("n你剛才輸入的第二個(gè)鏈表的信息: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;測(cè)試結(jié)果：   （1）（2）測(cè)試結(jié)果分析：程序運(yùn)行結(jié)果和人工模擬分析過(guò)程完全相同，說(shuō)明程序設(shè)計(jì)正確。題目：可變長(zhǎng)順序表設(shè)計(jì)基本要求：（1）使用動(dòng)態(tài)數(shù)組結(jié)構(gòu)。（2）順序表的操作包括：初始化、求數(shù)據(jù)元素個(gè)數(shù)、插入、刪除、取數(shù)據(jù)元素，編寫(xiě)每個(gè)操作的函數(shù)。（3）設(shè)計(jì)一個(gè)測(cè)試主函數(shù)。測(cè)試數(shù)據(jù): 4，5，6，7，8算法思想：可變長(zhǎng)順序表的設(shè)計(jì)，主要是利用動(dòng)態(tài)數(shù)組結(jié)構(gòu)的設(shè)計(jì)方法。動(dòng)態(tài)數(shù)組是指用動(dòng)態(tài)內(nèi)存分配方法定義的數(shù)組，它其中的元素的個(gè)數(shù)是在用戶(hù)申請(qǐng)動(dòng)態(tài)數(shù)組空

29、間時(shí)才確定的。此外，用鍵盤(pán)輸入順序表的元素，進(jìn)行建立順序表。依次調(diào)用初始化、求數(shù)據(jù)元素個(gè)數(shù)，插入、刪除和取數(shù)據(jù)元素并輸出新的順序表。 模塊劃分：（1）結(jié)構(gòu)體typedef struct的創(chuàng)建（2）初始化空表Datatype InitList_Sq(SqList &L)（3）建立順序表Datatype CreatList_Sq(SqList &L,int n)（4）銷(xiāo)毀線性表Datatype DestoryList_Sq(SqList &L)（5）判定是否為空表Datatype ListEmpty_Sq(SqList L)（6）求L表中的元素的個(gè)數(shù)int ListLeng

30、th_Sq(SqList L)（7）取表中的的第i個(gè)元素Datatype GetElem_Sq(SqList L, int i, Datatype &e)（8）插入節(jié)點(diǎn)Datatype ListInsert_Sq(SqList &L, int i, Datatype e)（9）刪除節(jié)點(diǎn)Datatype ListDelete_Sq(SqList &L, int i, Datatype &e)（10）輸出線性表L void Output(SqList L)（11）main()函數(shù)主要是調(diào)用以上函數(shù)對(duì)算法進(jìn)行測(cè)試數(shù)據(jù)結(jié)構(gòu)： 1、順序表結(jié)構(gòu)體定義typedef stru

31、ctDatatype *elem; int length; int listsize; SqList;2、動(dòng)態(tài)數(shù)組 動(dòng)態(tài)申請(qǐng)空間：L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);源程序：#define NULL 0#define LIST_INIT_SIZE 100 /線性表存儲(chǔ)空間的初始分配量#define LISTINCREMENT 10 /線性表存儲(chǔ)空間的分配增量#include<stdio.h>#include<iostream>typedef int Datatype; typedef

32、structDatatype *elem; /存儲(chǔ)空間基址int length; / 當(dāng)前長(zhǎng)度int listsize; / 當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)SqList;/1.初始化空表Datatype InitList_Sq(SqList &L)L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);if(! L.elem) exit(-1); /存儲(chǔ)分配失敗 L.length = 0; /空表長(zhǎng)度為L(zhǎng).listsize = LIST_INIT_SIZE; /初始存儲(chǔ)容量return 1

33、;/2.建立順序表LDatatype CreatList_Sq(SqList &L,int n) int i; Datatype e;printf("輸入順序表的長(zhǎng)度:");scanf("%d",&n);L.length = n;if (L.length > LIST_INIT_SIZE) L.elem = (Datatype *) realloc(L.elem,L.length*sizeof(Datatype);printf("輸入數(shù)據(jù):");for(i = 0;i <= L.length-1;i+) s

34、canf("%d",&e); L.elemi = e; return 1;/3.銷(xiāo)毀線性表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中數(shù)據(jù)元素的個(gè)數(shù)int ListLength_Sq(SqList L) retu

35、rn L.length;/6.取表第i個(gè)元素Datatype GetElem_Sq(SqList L, int i, Datatype &e) /用e返回順序表L中第i個(gè)數(shù)據(jù)元素的值,i的合法值為<= i <= ListLength_Sq(L)if (i < 1)|(i > L.length) return 0; /i值不合法elsee = L.elemi-1;return 1;/7.插入結(jié)點(diǎn)Datatype ListInsert_Sq(SqList &L, int i, Datatype e) /在順序線性表L中第i個(gè)位置之前插入新的元素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; /表長(zhǎng)增return 1;/8.刪除結(jié)點(diǎn)Datatype ListDelete_Sq(SqList &L, int i, Data

37、type &e) /在順序線性表L中刪除第i個(gè)元素,并用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; /表長(zhǎng)減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.建立一個(gè)順序表"); for(i = 0;i < 10;i+) printf(" "); printf("*"); printf("n"); for(i = 0;i < 10;i +) printf(" "); printf("* "); printf("2.輸出一個(gè)順序表"

40、); for(i = 0;i < 10;i+) printf(" "); printf("*"); printf("n"); for(i = 0;i < 10;i +) printf(" "); printf("* "); printf("3.向順序表中插入一個(gè)元素"); for(i = 0;i < 2;i+) printf(" "); printf("*"); printf("n"); for(i

41、 = 0;i < 10;i +) printf(" "); printf("* "); printf("4.刪除順序表中的一個(gè)元素"); for(i = 0;i < 2;i+) printf(" "); printf("*"); printf("n"); for(i = 0;i < 10;i+) printf(" "); printf("* "); printf("5.從順序表中取出一個(gè)元素");

42、for(i = 0;i < 2;i+) printf(" "); printf("*"); printf("n"); for(i = 0;i < 10;i+) printf(" "); printf("* ");printf("6.求順序表中數(shù)據(jù)元素個(gè)數(shù)"); 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.銷(xiāo)毀線性