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

1、數(shù)據(jù)結構課程設計題目一：實現(xiàn)兩個鏈表的合并題目二：可變長順序表設計班 級：計科1202班姓 名：學 期：2013-2014學年第二學期Word文檔題目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當 n>m 時，C=y1,x1,y2,x2, ym,xm,yn(3)輸出線性表C:(4)用直接插入排序法對C進行升序排序，生成鏈表D,并輸出鏈表Do測試數(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)算法思想：首先我們需要建立兩個鏈表 A,B, A鏈表的元素個數(shù)為m； B鏈表的 元素個數(shù)為n；在將A,B鏈表進行合并，根據(jù) m和n的大小關系決定鏈表C的 元素順序(當m>=n時，應該先插入A表中的數(shù)據(jù)元素，在偶數(shù)位插入 A表中 的數(shù)據(jù)元素，在奇數(shù)位插入 B表中的數(shù)據(jù)元素，最后在插入 A表中剩余的數(shù)據(jù) 元素；當m<n時，應該先插入B表中的數(shù)據(jù)元素，在

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

4、長短將行不通的 插入。(5) void InsertSort(struct Node *p,int m)算法的功能是對一合并好的鏈表進行 升序插入排序。(6) main()函數(shù)主要是對算法進行測試。數(shù)據(jù)結構：數(shù)據(jù)結構定義如下: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 結構

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-; 控制輸入的個數(shù)p2->next = NULL;return (head);/鏈表創(chuàng)建函數(shù)結束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; 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的每個元素插在p2相應元素之前，pl長a,p2長b*/pos = head; /*此時pos指向pl中的第一個元素*/while (p2 != NULL) /漂亮,蛇形插入pl = p1->next;pos->next = p2;pos = p2;p2 = p2->next;pos->next = p1;pos = p1;return head;/對合并好的鏈表進行排序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（"請輸入第一個鏈表：n&quo

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

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

12、個操作的函數(shù)。(3)設計一個測試主函數(shù)。測試數(shù)據(jù)：4, 5, 6, 7, 8算法思想：可變長順序表的設計，主要是利用動態(tài)數(shù)組結構的設計法。動態(tài)數(shù)組 是指用動態(tài)存分配法定義的數(shù)組，它其中的元素的個數(shù)是在用戶申請動態(tài)數(shù)組空 問時才確定的。止匕外，用鍵盤輸入順序表的元素，進行建立順序表。依次調(diào)用初 始化、求數(shù)據(jù)元素個數(shù)，插入、刪除和取數(shù)據(jù)元素并輸出新的順序表。模塊劃分：(1)結構體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表中的元素的個數(shù) int ListLength_Sq(SqList L)(7)取表中的的第 i 個元素 Datatype GetElem_Sq(SqList L, int i, Datatype &e)(8)插入節(jié)點 Datatype ListInsert_Sq(SqList &L, int i, Datatype e)(9)刪除節(jié)點 Datatype ListDelete_Sq(SqLi

14、st &L, int i, Datatype &e)(10)輸出線性表 L void Output(SqList L)(II) main()函數(shù)主要是調(diào)用以上函數(shù)對算法進行測試數(shù)據(jù)結構：1、順序表結構體定義typedef structDatatype *elem;int length;int listsize;SqList;2、動態(tài)數(shù)組動態(tài)申請空間：L.elem = (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);源程序：#define NULL 0 #define LIST_INIT_SIZE 100 /線性表存儲空間的

15、初始分配量#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_SI

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

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

23、0;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(&

24、quot;");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(&qu

25、ot;* ");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("*");

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("請選擇-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("請輸入要插入的元素的位置及其值：");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