實(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)nm時(shí)，C=y1,x1,y2,x2,ym,xm,yn （3）輸出線性表C：（4）用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。測(cè)試數(shù)據(jù)：（1）A表（30，41，15，12，56，80） B表（

2、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)mn時(shí)，應(yīng)該先插入B表中的數(shù)據(jù)元素，在偶數(shù)位插入B表中的數(shù)據(jù)元素，在奇數(shù)位插入A表中的數(shù)據(jù)元素，最后在插入B表中剩余的數(shù)據(jù)元素），再將C經(jīng)行直接插入排序

3、得到一個(gè)新的鏈表D；最后輸出ABCD的相關(guān)信息。模塊劃分:(1)結(jié)構(gòu)體structNode的創(chuàng)建。(2)structNode*create（）鏈表的創(chuàng)建。(3)voidprint(structNode*head)功能是對(duì)鏈表進(jìn)行輸出。 (4)structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb)算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈表的長(zhǎng)短將行不通的插入。(5)voidInsertSort(structNode*p,intm)算法的功能是對(duì)一合并好的鏈表進(jìn)行升序插入排序。 (6)main()函數(shù)主要

4、是對(duì)算法進(jìn)行測(cè)試。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)定義如下：structNodelongintnumber;structNode*next;源程序：#include#include#include#include#defineLsizeof(structNode)structNode/結(jié)構(gòu)體 longintnumber;structNode*next;structNode*create(inta)/鏈表創(chuàng)建函數(shù) intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);/分配內(nèi)存 scanf(%ld,&p1-number)

5、;while(a)/錄入鏈表信息 n=n+1;if(n=1)head=p1;elsep2-next=p1;p2=p1;p1=(structNode*)malloc(L);if(a!=1)/分配內(nèi)存 scanf(%ld,&p1-number);a-;/控制輸入的個(gè)數(shù) p2-next=NULL;return(head);/鏈表創(chuàng)建函數(shù)結(jié)束 voidprint(structNode*head)/輸出函數(shù) structNode*p;p=head;printf(數(shù)字:n); if(head!=NULL)do/循環(huán)實(shí)現(xiàn)輸出 printf(%ld,p-number);printf();p=p-next;wh

6、ile(p!=NULL);printf(n);/鏈表的交叉合并算法 structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb)inttemp;structNode*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*/ /*下面把p1的每個(gè)元素插在p2相應(yīng)元素之前，p1長(zhǎng)a,p2長(zhǎng)b*/ pos=head;/*此時(shí)pos

7、指向p1中的第一個(gè)元素*/ while(p2!=NULL)/漂亮，蛇形插入 p1=p1-next;pos-next=p2;pos=p2;p2=p2-next;pos-next=p1;pos=p1;returnhead;/對(duì)合并好的鏈表進(jìn)行排序 voidInsertSort(structNode*p,intm)/排序函數(shù) inti,j,t;structNode*k;k=p;for(i=0;im-1;i+)for(j=0;jnumber(p-next)-number)t=p-number;p-number=(p-next)-number;(p-next)-number=t;p=p-next;p=k

8、;/主函數(shù) intmain()/main函數(shù) structNode*p1,*p2;inta;intb;inth;printf(請(qǐng)輸入第一個(gè)鏈表:n); 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(n你剛才輸入的第二個(gè)鏈表的信息:n); print(p2);

9、p1=inter_link(p1,a,p2,b);h=a+b;printf(n合并后的鏈表n：); print(p1);InsertSort(p1,h);printf(n排序后的鏈表:n); print(p1);return0;測(cè)試結(jié)果：（1）（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ù)元素，編寫每個(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ù)組是

10、指用動(dòng)態(tài)內(nè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)（4）銷毀線性表Datatype DestoryList_Sq(SqList &L)（5）判定是否為空表Datatype ListEmpty_Sq(SqList L)（

11、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(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)體定義type

12、def 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ǔ)空間的初始分配量#define LISTINCREMENT 10 /線性表存儲(chǔ)空間的分配增量#include#includetypedef int Datatype; typedef structDatatype *elem; /

13、存儲(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;/2.建立順序表LDatatype CreatLis

14、t_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+) scanf(%d,&e); L.elemi = e; return 1;/3.銷毀線性表Datatype DestoryList_Sq(SqList &L)if

15、(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) return L.length;/6.取表第i個(gè)元素Datatype GetElem_Sq(SqList L, int i, Datatype &e) /用e返回順序表L中第i個(gè)數(shù)據(jù)元素的值,i的合法值為=

16、i = ListLength_Sq(L)if (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的合法值為=i=ListLength_Sq(L)+1Datatype *q,*p,*newbase; if(i L.length+1) return 0; /i值不合法q = &(L.elemi-1); /q為插入位置for (p = &(L.elemL.length -

17、 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, Datatype &e) /在順序線性表L中刪除第i個(gè)元素,并用e返回其值,i的合法值為= i = ListLength_Sq(L) Datatype *p,*q;if(i L.length) return 0; /i值不合法p = &(L.elemi - 1); /p為被刪除元素的位置e = *p; /被刪除元素的值賦給eq = L.elem +

18、L.length - 1; /表尾元素的位置for (+p;p = q;+p) *(p-1) = *p; /被刪除元素之后的元素左移-L.length; /表長(zhǎng)減return 1;/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()/

19、顯示窗口 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 10;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.向

20、順序表中插入一個(gè)元素); for(i = 0;i 2;i+) printf( ); 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(* ); printf(5.從順序表中取出一個(gè)元素); for(i = 0;i 2;i+) printf( ); printf(*); printf(n); for

21、(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.銷毀線性表); for(i = 0;i 14;i

22、+) 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(); int main()/主函數(shù) int n = 0,i,j = 0,k = 1,m,q,x,y,e; SqList l,la,lc; InitList_Sq(l); mainpp(); while(k) printf(請(qǐng)選擇-8：); scanf(%d,&m); getchar(); switch(m) case 0: