鏈表的合并實(shí)驗(yàn)報(bào)告

1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：兩個鏈表的合并專業(yè)：軟件工程班級：姓名：學(xué)號: 指導(dǎo)教師 :年 月 日目錄1.課程設(shè)計(jì)的目的及要求2.課程設(shè)計(jì)的內(nèi)容（分析和設(shè)計(jì)）3.算法流程圖4.詳細(xì)步驟5.代碼6.顯示結(jié)果7.課程設(shè)計(jì)的總結(jié)一課程設(shè)計(jì)的目的及要求1.目的：實(shí)現(xiàn)兩個鏈表的合并2.要求：（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) nm 時， c=y1,x1,y2,x2,ym,xm,yn 輸出線形表c

2、（3） 用直接插入排序法對c 進(jìn)行升序排序，生成鏈表d，并輸出鏈表d。（4） 能刪除指定單鏈表中指定位子和指定值的元素。二課程設(shè)計(jì)的內(nèi)容（分析和設(shè)計(jì)）1.分析由題目的相關(guān)信息可以分析得：首先我們需要建立兩個鏈表ab ，a 鏈表的元素個數(shù)為m，b 鏈表的元素個數(shù)為n；在將 a、b 鏈表進(jìn)行合并， 根據(jù) m 和 n 的大小關(guān)系決定鏈表c 的元素順序；再將c 進(jìn)行直接插入排序得到一個新的鏈表d；沒次輸入完一次鏈表信息，程序都會對相應(yīng)的鏈表進(jìn)行輸入操作以此確保程序輸入的數(shù)據(jù)是你想要輸入的數(shù)據(jù)。同時當(dāng)你合并好和排序好后都會進(jìn)行輸出操作。最后當(dāng)排序好后你可以指定你所要刪除數(shù)據(jù)的位置來刪除你所要刪除的數(shù)據(jù)。

3、2.設(shè)計(jì)本次課程設(shè)計(jì)所需要用到的是關(guān)于鏈表的建立、合并以及直接插入排序的排序算法。需要先建立兩個鏈表， 再將其合并為一個無序鏈表，最后對這個無序鏈表進(jìn)行直接插入排序并將其輸出。難點(diǎn)在于將ab 合并為鏈表c 的操作以及對鏈表c 進(jìn)行直接插入排序的操作和根據(jù)用戶的意愿可以對鏈表進(jìn)行刪除的操作。三算法流程圖四詳細(xì)步驟(1)結(jié)構(gòu)體的創(chuàng)建：struct node (2)鏈表的創(chuàng)建： struct node *create（）鏈表的創(chuàng)建。(3)鏈表的輸出： void print(struct node *head)功能是對鏈表進(jìn)行輸出。(4)鏈表的合并： struct node * inter_link(

4、struct node * chain1, int a, struct node * chain2, int b)算法的功能是實(shí)現(xiàn)兩個鏈表的交叉合并，并且可以根據(jù)兩鏈表的長短將行不通的插入。(5)排序：void insertsort(struct node *p,int m) 算法的功能是對一合并好的鏈表進(jìn)行升序插入排序。(6)按位刪除操作：struct node * delete_link(struct node *p,int i)。(7)按值刪除操作：struct node * delete_linkz(struct node *p,int i)。(8)主函數(shù)： main() 函數(shù)主要是對

5、算法進(jìn)行測試。建立鏈表a 建立鏈表b 合并 a b 鏈表得到 c 鏈表得到 d 鏈表得到 e 鏈表比較 m.n 排序刪除五代碼struct node /數(shù)據(jù)結(jié)構(gòu)定義如下： long int number; struct node *next; node,*linklist; #include /源程序：#include #include #include #define error 0 #define null 1 #define l sizeof(struct node) struct node *create(int a)/鏈表創(chuàng)建函數(shù) int n; struct node *p1, *p

6、2, *head; head = null; n = 0; p2 = p1 = (struct node *) malloc(l); /分配內(nèi)存scanf(%ld, &p1-number); 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(%ld, &p1-number); a-; /控制輸入的個數(shù) p2-next = null; return (head); /

7、鏈表創(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 != null); printf(n); /鏈表的交叉合并算法struct node * inter_link(struct node * chain1, int a, struct node * chain2, int b) int temp; struct no

8、de *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 的每個元素插在 p2 相應(yīng)元素之前， p1 長 a,p2長 b*/ pos = head; /*此時 pos指向 p1 中的第一個元素 */ while (p2 != null) / 漂亮，蛇形插入p1 = p1-next; pos-ne

9、xt = p2; pos = p2; p2 = p2-next; pos-next = p1; pos = p1; return head; /對合并好的鏈表進(jìn)行排序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 = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next;

10、 p = k; struct node * delete_link(struct node *p,int i) /按位刪除 struct node *q; int j=0; while(jnext) p=p-next; j+; if(j=i-1&p-next) q=p-next; p-next=q-next; free(q); else return error; struct node * delete_linkz(struct node *p,int i)/按值刪除 struct node *q; struct node *k; int j=0; int h=0; while(p&

11、amp;p-number!=i) p=p-next; j+; if (p) while (hnext) p=p-next; h+; if(h=j-1&p-next) k=p-next; p-next=k-next; free(k); else return error; /主函數(shù)int main()/main 函數(shù) struct node *p1, *p2; int a; int b; int h; int t; int m; printf( 請輸入第一個鏈表 :n); printf(n 輸入鏈表的長度a:n); scanf(%d, &a); printf( 請輸入鏈表數(shù)據(jù)：

12、); 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(n 你剛才輸入的第二個鏈表的信息:n); print(p2); p1 = inter_link(p1, a, p2, b); h = a + b; printf(n 合并后的鏈表 n：); print(p1); insertsort(p1, h); printf(n 排

13、序后的鏈表 :n); print(p1); printf(n 請輸入鏈表中你所要刪除數(shù)據(jù)的所在位置:n); scanf(%d,&t); delete_link(p1,t); printf(n 鏈表刪除數(shù)據(jù)后鏈表的信息:n); print(p1); printf(n 請輸入你想要刪除的數(shù)值 :n); scanf(%d,&m); delete_linkz(p1,m); printf(n 鏈表刪除數(shù)據(jù)后鏈表的信息:n); print(p1); return 0; 六顯示結(jié)果（1）mn 3.m=n 4.按位刪除操作5.按值刪除七課程設(shè)計(jì)的總結(jié)通過進(jìn)一周的學(xué)習(xí)和實(shí)踐， 解決實(shí)際問題， 讓我對鏈表有了更深的了解，也讓我提高了解決實(shí)際問題的能力。在上機(jī)的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關(guān)鍵算法，有了算法設(shè)計(jì)思想和流程圖， 并用c 語言描繪出關(guān)鍵算法。在運(yùn)行過程中，用戶可輸入你所需合并的兩個鏈表，首先輸入你所要輸入鏈表的長度再輸入鏈表的數(shù)據(jù)，完成第一個鏈表的輸入后，按照同樣的方法輸入第二個鏈表， 每輸入完一個鏈表程序都會執(zhí)行輸出函數(shù)void print(struct node *head)對鏈表進(jìn)行輸出， 以此讓用戶可以確認(rèn)自己輸入的數(shù)據(jù)是