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

1、百度文庫- 讓每個人平等地提升自我數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目一：實現(xiàn)兩個鏈表的合并題目二：可變長順序表設(shè)計班級：計科 1202 班姓名：學(xué)期： 2013-2014 學(xué)年第二學(xué)期11百度文庫- 讓每個人平等地提升自我題目 1：實現(xiàn)兩個鏈表的合并基本要求：（ 1）建立兩個鏈表 A 和 B，鏈表元素個數(shù)分別為 m 和 n 個。（ 2）假設(shè)元素分別為 (x1,x2,xm)，和 (y1,y2, yn)。把它們合并成一個線性表C：當(dāng) m>=n 時， C=x1,y1,x2,y2,xn,yn,xm當(dāng) n>m 時， C=y1,x1,y2,x2,ym,xm, ,yn（ 3）輸出線性表 C：（ 4） 用直接插

2、入排序法對 C 進行升序排序，生成鏈表 D，并輸出鏈表 D。測試數(shù)據(jù)：（ 1） A 表（ 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）算法思想 ：首先我們需要建立兩個鏈表 A,B ，A 鏈表的元素個數(shù)為 m； B 鏈表的元素個數(shù)為 n；在將 A,B 鏈表進行合并，根據(jù) m 和 n 的大小關(guān)系決定鏈表 C 的元素順序（當(dāng) m>=n 時，應(yīng)該先插入 A 表中的數(shù)據(jù)元素，在偶數(shù)位插入 A 表中的數(shù)據(jù)元素，在奇數(shù)位插

3、入 B 表中的數(shù)據(jù)元素，最后在插入 A 表中剩余的數(shù)據(jù)元素；當(dāng) m<n 時，應(yīng)該先插入 B 表中的數(shù)據(jù)元素，在偶數(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 * cha

4、in1, int a, struct Node * chain 2, int b)算法的功能是實現(xiàn)兩個鏈表的交叉合并， 并且可以根據(jù)兩鏈表的長短將行不通的插入。(5) void InsertSort(struct Node *p,int m)算法的功能是對一合并好的鏈表進行升序插入排序。(6) main() 函數(shù)主要是對算法進行測試。22百度文庫- 讓每個人平等地提升自我數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)定義如下：struct Nodelong int number;struct Node *next;源程序：#include<>#include<>#include<>#i

5、nclude<>#define L sizeof(struct Node)struct Node33百度文庫- 讓每個人平等地提升自我44百度文庫- 讓每個人平等地提升自我始化空表Datatype InitList_Sq(SqList &L)= (Datatype *)malloc(LIST_INIT_SIZE *sizeof(Datatype);if(!exit(-1);立順序表 LDatatype CreatList_Sq(SqList &L,int n)int i;Datatype e;55百度文庫- 讓每個人平等地提升自我printf("輸入順序表

6、的長度 :");scanf("%d",&n);= n;if > LIST_INIT_SIZE)= (Datatype *) realloc,*sizeof(Datatype); printf(" 輸入數(shù)據(jù) :");for(i = 0;i <= ;i+)scanf("%d",&e);i = e;return 1;毀線性表Datatype DestoryList_Sq(SqList &L)iffree;= NULL;= =0;return 1;return 0;定是否空表Datatype Li

7、stEmpty_Sq(SqList L)ifreturn 0;return 1;L中數(shù)據(jù)元素的個數(shù)int ListLength_Sq(SqList L)return ;表第 i 個元素Datatype GetElem_Sq(SqList L, int i, Datatype &e)入結(jié)點Datatype ListInsert_Sq(SqList &L, int i, Datatype e)除結(jié)點Datatype ListDelete_Sq(SqList &L, int i, Datatype &e)出順序表void Output(SqList L)立一個順序表

8、");for(i = 0;i < 10;i+)66百度文庫- 讓每個人平等地提升自我printf(" ");printf("*");printf("n");for(i = 0;i < 10;i +)printf(" ");printf("*");printf("2.輸出一個順序表 ");for(i = 0;i < 10;i+)printf(" ");printf("*");printf("n&quo

9、t;);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(

10、i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)printf(" ");printf("*");printf("5.從順序表中取出一個元素");for(i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)prin

11、tf(" ");printf("*");printf("6.求順序表中數(shù)據(jù)元素個數(shù)");for(i = 0;i < 2;i+)printf(" ");printf("*");printf("n");for(i = 0;i < 10;i+)77百度文庫- 讓每個人平等地提升自我printf(" ");printf("*");printf("7.判斷順序表中是否為空 ");for(i = 0;i < 4

12、;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(" ");

13、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("請選擇 -8 ：");scanf("%d",&m);getcha

14、r();switch(m)case 0:exit(0);case 1:CreatList_Sq(l,n);Output(l);88百度文庫- 讓每個人平等地提升自我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:p

15、rintf("請輸入要刪除元素的位置：");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("取出的第 %d個元素為： %dn",i,e);break;case 6:printf(" 順序表中數(shù)據(jù)元素的個數(shù)為： %d",ListLength_Sq(l);case 7:q = ListEmpty_Sq(l);if(q = 1)printf("此表為空 ");elseprintf("此表不空 ");printf("