實(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é)期Word文檔題目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,并輸出鏈表Do測(cè)試數(shù)據(jù)：(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)算法思想：首先我們需要建立兩個(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ù)元素，在

3、偶數(shù)位插入 B表中的數(shù)據(jù) 元素，在奇數(shù)位插入A表中的數(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)建。void print(struct Node *head)功能是對(duì)鏈表進(jìn)行輸出。(4) struct Node * inter_link(struct Node * chainl, int a, struct Node * chain2, i nt b)算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈表的

4、長(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 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 結(jié)構(gòu)

5、體long int number;struct Node *next;struct Node *create(int a)/鏈表創(chuàng)建函數(shù)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-; 控制輸入的個(gè)數(shù)p2->next = NULL;return (head);/鏈表創(chuàng)建函數(shù)結(jié)束void print(struct Node *head)輸出函數(shù)struct Node *p;p = head;printf("數(shù)字:n");if (head != NULL)do/循環(huán)實(shí)現(xiàn)輸出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的每個(gè)元素插在p2相應(yīng)元素之前，pl長(zhǎng)a,p2長(zhǎng)b*/pos = head; /*此時(shí)pos指向pl中的第一個(gè)元素*/while (p2 != NULL) /漂亮,蛇形插入pl = p1->next;pos->next = p2;pos = p2;p2 = p2->next;pos->next = p1;pos = p1;return head;/對(duì)合并好的鏈表進(jìn)行排序void InsertSort(struct Node *p, int m)排序函數(shù) 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;/主函數(shù)int main（）main 函數(shù)struct Node *p1, *p2;int a;int b;int h;printf（"請(qǐng)輸入第一個(gè)鏈表：n&quo

10、t;）;printf（"n輸入鏈表的長(zhǎng)度a:n"）;scanf（"%d",&a）;printf（"請(qǐng)輸入鏈表數(shù)據(jù)："）;p1 = create（a）;printf（"n你剛才輸入的第一個(gè)鏈表信息：n "）;print（p1）;printf（"n請(qǐng)輸入第二個(gè)鏈表:n"）;printf（"n輸入鏈表的長(zhǎng)度b:n"）;scanf("%d",&b);printf("請(qǐng)輸入鏈表數(shù)據(jù)：");p2 = create(b);printf

11、("n你剛才輸入的第二個(gè)鏈表的信息：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;測(cè)試結(jié)果：(2)測(cè)試結(jié)果分析：程序運(yùn)行結(jié)果和人工模擬分析過程完全相同，說明程序設(shè)計(jì)正確題目：可變長(zhǎng)順序表設(shè)計(jì)基本要求：(1)使用動(dòng)態(tài)數(shù)組結(jié)構(gòu)。(2)順序表的操作包括：初始化、求數(shù)據(jù)元素個(gè)數(shù)、插入、刪除、取數(shù)據(jù)元素，編寫每

12、個(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)存分配法定義的數(shù)組，它其中的元素的個(gè)數(shù)是在用戶申請(qǐng)動(dòng)態(tài)數(shù)組空 問時(shí)才確定的。止匕外，用鍵盤輸入順序表的元素，進(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

13、)(4)銷毀線性表 Datatype DestoryList_Sq(SqList &L)(5)判定是否為空表 Datatype ListEmpty_Sq(SqList L)(6)求 L表中的元素的個(gè)數(shù) int ListLength_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(SqLi

14、st &L, int i, Datatype &e)(10)輸出線性表 L void Output(SqList L)(II) main()函數(shù)主要是調(diào)用以上函數(shù)對(duì)算法進(jìn)行測(cè)試數(shù)據(jù)結(jié)構(gòu)：1、順序表結(jié)構(gòu)體定義typedef structDatatype *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ǔ)空間的

15、初始分配量#define LISTINCREMENT 10線性表存儲(chǔ)空間的分配增量#include<stdio.h>#include<iostream> typedef int Datatype;typedef 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_SI

16、ZE *sizeof(Datatype);if(! L.elem)exit(-1);/存儲(chǔ)分配失敗L.length = 0;/空表長(zhǎng)度為L(zhǎng).listsize = LIST_INIT_SIZE;/ 初始存儲(chǔ)容量return 1;/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 = (Data

17、type *) realloc(L.elem,L.length*sizeof(Datatype);printf("輸入數(shù)據(jù):");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中數(shù)據(jù)元素的個(gè)數(shù)int ListLength_Sq(SqList L)return L.length;/6.取表第i個(gè)元素Datatype GetElem_Sq(SqList L, int i, Datatype &e) / 用 e返回順序表 L中第 i個(gè)數(shù)據(jù) 元素的值，的合法值為<=i <= ListLength_Sq(L) if (i < 1)|(i > L.length) return 0; /i值不合法elsee = L.elemi-

19、1;return 1;/7.插入結(jié)點(diǎn)Datatype ListInsert_Sq(SqList &L, int i, Datatype e) / 在順序線性表 L中第i個(gè)位置 之前插入新的元素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;表長(zhǎng)增return 1;118 .刪除結(jié)點(diǎn)Datatype ListDelete_Sq(SqList &L, int i, Datatype &e)/ 在順序線性表 L中刪除第i個(gè)元素，并用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;/ 表長(zhǎng)減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.建立一個(gè)順序表");for(i = 0;i < 10;i+)printf("");printf("*");printf("n");for(i = 0;i < 1

23、0;i +)printf("");printf("* ");printf("2.輸出一個(gè)順序表");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(&

24、quot;");printf("*");printf("n");for(i = 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(&qu

25、ot;* ");printf("5.從順序表中取出一個(gè)元素");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("*");

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("請(qǐng)選擇-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() 主函數(shù)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("請(qǐng)輸入要插入的元素的位置及其值：");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