實現(xiàn)兩個鏈表的合并

1、 數(shù)據(jù)結(jié)構(gòu)課程設計 題目一：實現(xiàn)兩個鏈表的合并 題目二：可變長順序表設計 班 級：計科1202班 姓 名： 學 期：2013-2014學年第二學期題目1：實現(xiàn)兩個鏈表的合并 基本要求： (1) 建立兩個鏈表A和B,鏈表元素個數(shù)分別為 m和n個。 (2) 假設元素分別為(x1,x2,xm),和(y1,y2,yn)。把它們合并成一個線性 表 C： 當 m=n時，C=x1,y1,x2,y2,xn,yn,xm 當 nm時，C=y1,x1,y2,x2,ym,xm,yn ( 3)輸出線性表 C： (4)用直接插入排序法對C進行升序排序，生成鏈表D,并輸出鏈表Db 測試數(shù)據(jù)： ( 1 ) A 表( 30，

2、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鏈表的元素個數(shù)為m B鏈表的 元素個數(shù)為n；在將A,B鏈表進行合并， 根據(jù)m和n的大小關(guān)系決定鏈表C的元 素順序(當m=n時，應該先插入A表中的數(shù)據(jù)元素，在偶數(shù)位插入 A表中的數(shù) 據(jù)元素，在奇數(shù)位插入B表中的數(shù)據(jù)元素，最后在插入 A表中剩余的數(shù)據(jù)元素； 當mn時，應該先插入B表中的數(shù)據(jù)元素，

3、在偶數(shù)位插入B表中的數(shù)據(jù)元素，在 奇數(shù)位插入A表中的數(shù)據(jù)元素，最后在插入 B表中剩余的數(shù)據(jù)元素)，再將C經(jīng) 行直接插入排序得到一個新的鏈表 D;最后輸出ABCD勺相關(guān)信息。 模塊劃分 : (1) 結(jié)構(gòu)體struct Node的創(chuàng)建。 (2) struct Node*create ()鏈表的創(chuàng)建。 (3) void print(struct Node *head) 功能是對鏈表進行輸出。 (4) struct Node* inter_link(struct Node* chain1, int a, struct Nod e * chain2, int b) 算法的功能是實現(xiàn)兩個鏈表的交叉合并，

4、并且可以根據(jù)兩鏈表的長短將行不通的 插入。 void InsertSort(struct Node *p,int m)算法的功能是對一合并好的鏈表 進行升序插入排序。 (6) main() 函數(shù)主要是對算法進行測試 。2 數(shù)據(jù)結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)定義如下： struct Node long int number; struct Node *next; ; 源程序： #include #include #include #include #define L sizeof(struct Node) struct Node / 結(jié)構(gòu)體 long int number; struct Node *next

5、; ; 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); / 分配內(nèi)存 scanf(%ld, &p1-number); 。3 while (a)/ 錄入鏈表信息 n = n + 1; if (n =1) head= p1; else p2-next = p1; p2 = p1; p1 = (struct Node *) malloc(L); if (a != 1)/ 分配內(nèi)存 scanf

6、(%ld, &p1-number); a-; / 控制輸入的個數(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)實現(xiàn)輸出 printf(%ld, p-number); printf( ); p= p-next; 。4 while (p != NULL); printf(n); / 鏈表的交叉合并算法 struct Node* inter_link(st

7、ruct Node* chain1, int a, struct Node* chain 2, int b) int temp; struct Node *head, *p1, *p2, *pos; /* 判斷 a，b 大小并合并 */ if (a = b) head = p1= chain1; p2 = chain2; else/*ba*/ head = p1= chain2; p2 = chain1; temp = a, a =b, b = temp; /* 交換 a 和 b*/ /*下面把pl的每個元素插在p2相應元素之前，pl長a,p2長b*/ pos = head; /* 此時 po

8、s 指向 p1 中的第一個元素 */ while (p2 != NULL)/ 漂亮，蛇形插入 p1 = p1-next; pos-next = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; 。5 return head; / 對合并好的鏈表進行排序 void InsertSort(struct Node*p, int m)/ 排序函數(shù) int i, j, t; struct Node *k; k = p; for (i = 0; i m- 1; i+) for (j =0; j number (p-next)-number) t =

9、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; 。6 int b; int h; printf（ 請輸入第一個鏈表 :n）; printf（n 輸入鏈表的長度 a:n）; scanf（%d, &a）; printf（ 請輸入鏈表數(shù)據(jù)： ）; p1 = create（a）; printf（n 你剛才輸入的第一個鏈表信息 :n ）; print（p1）; printf（n 請輸入

10、第二個鏈表 :n）; printf（n 輸入鏈表的長度 b:n）; scanf（%d, &b）; printf（ 請輸入鏈表數(shù)據(jù)： ）; 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; 測試結(jié)果： （1） 。7 (2)測試結(jié)果分析： 程序運行結(jié)果和人工模擬分

11、析過程完全相同，說明程序設計正確 題目：可變長順序表設計 基本要求： (1)使用動態(tài)數(shù)組結(jié)構(gòu)。 (2)順序表的操作包括：初始化、求數(shù)據(jù)元素個數(shù)、插入、刪除、取數(shù)據(jù)元素， 編寫每個操作的函數(shù)。 (3)設計一個測試主函數(shù)。 測試數(shù)據(jù) : 4 ，5，6， 7， 8 算法思想 ：可變長順序表的設計， 主要是利用動態(tài)數(shù)組結(jié)構(gòu)的設計方法。 動態(tài)數(shù) 組是指用動態(tài)內(nèi)存分配方法定義的數(shù)組， 它其中的元素的個數(shù)是在用戶申請動態(tài) 數(shù)組空間時才確定的。此外，用鍵盤輸入順序表的元素，進行建立順序表。依次 調(diào)用初始化、求數(shù)據(jù)元素個數(shù)，插入、刪除和取數(shù)據(jù)元素并輸出新的順序表。 模塊劃分： ( 1)結(jié)構(gòu)體 typedef s

12、truct 的創(chuàng)建 ( 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 表中的元素的個數(shù) int ListLength_Sq(SqList L) ( 7)取表中的的第 i 個元素 Datatype GetElem_Sq(SqList L, int i,

13、Datatype &e) ( 8)插入節(jié)點 Datatype ListInsert_Sq(SqList &L, int i, Datatype e) ( 9)刪除節(jié)點 Datatype ListDelete_Sq(SqList &L, int i, Datatype &e) ( 10)輸出線性表 L void Output(SqList L) ( 11) main() 函數(shù)主要是調(diào)用以上函數(shù)對算法進行測試 數(shù)據(jù)結(jié)構(gòu)： 1、順序表結(jié)構(gòu)體定義 typedef struct Datatype *elem; int length; int listsize; SqLis

14、t; 1。0 2、動態(tài)數(shù)組 動態(tài)申請空間： L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype); 源程序： #define NULL 0 #define LIST_INIT_SIZE 100 / 線性表存儲空間的初始分配量 #define LISTINCREMENT 10 / 線性表存儲空間的分配增量 #include #include typedef int Datatype; typedef struct Datatype *elem; / int length; / int listsize; / SqList; 存儲

15、空間基址 當前長度 當前分配的存儲容量(以sizeof(ElemType)為單位) /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. 建立順序表 L Datatype CreatList_Sq(SqList &L,

16、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( 輸入數(shù)據(jù) :); for(i = 0;i = L.length-1;i+) 1。1 scanf(%d,&e); L.elemi = e; return 1; /3. 銷毀線性表 Datatype DestoryList_Sq(SqL

17、ist &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; 115.求L中數(shù)據(jù)元素的個數(shù) int ListLength_Sq(SqList L) return L.length; /6. 取表第 i 個元素 Datatype GetElem_Sq(SqList L, int i, Datatype &am

18、p;e) / 用e返回順序表 L中第 i 個數(shù)據(jù)元素的值 ,i 的合法值為 = i = ListLength_Sq(L) if (i L.length) return 0; /i 值不合法 else e = L.elemi-1; return 1; /7. 插入結(jié)點 Datatype ListInsert_Sq(SqList &L, int i, Datatype e) / 在順序線性表 L 中第i個位置之前插入新的元素e,i的合法值為=i=ListLength_Sq(L)+1 1。2 Datatype *q,*p,*newbase; if(i L.length+1) return 0

19、; /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. 刪除結(jié)點 Datatype ListDelete_Sq(SqList &L, int i, Datatype &e) / 在順序線性表 L 中刪除第i個元素,并用e返回其值,i的合法值為=i = ListLength_Sq(L) /9. 輸出順序表 void Ou

20、tput(SqList L)/ 輸出線性表 L int i; for(i = 0;i L.length;i+) printf(%d ,L.elemi); printf(n); int i; for(i = 0;i 10;i +) 1。3 printf( ); Datatype *p,*q; if(i L.length) return 0; /i 值不合法 p = &(L.elemi - 1); e = *p; q = L.elem + L.length - 1; for (+p;p = q;+p) *(p-1) = *p; / -L.length; return 1; /p / / 為

21、被刪除元素的位置 被刪除元素的值賦給 e 表尾元素的位置 / 被刪除元素之后的元素左移 表長減 void put()/ 窗口邊框 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(* );

22、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(*);

23、printf(n); for(i = 0;i 10;i+) printf( ); 1。4 printf(* ); printf(5. 從順序表中取出一個元素 ); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* ); printf(6. 求順序表中數(shù)據(jù)元素個數(shù) ); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for(i = 0;i 10;i+) printf( ); printf(* ); printf(

24、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(); in

25、t main()/ 主函數(shù) 1。5 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

26、(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( 取出的第個元素為：dn,i,e); break; 1。6 case 6: printf( 順序表中數(shù)據(jù)元素的個數(shù) 為： %d,ListLength_