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

課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：兩個(gè)鏈表的合并 專 業(yè)：軟件工程班 級(jí)：姓 名：學(xué) 號(hào): 指導(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)兩個(gè)鏈表的合并2.要求：（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)n>m時(shí)，C=y1,x1,y2,x2,ym,xm,yn 輸出線形表C （3） 用直接插入排序法對(duì)C進(jìn)行升序排序，生成鏈表D，并輸出鏈表D。 （4） 能刪除指定單鏈表中指定位子和指定值的元素。二課程設(shè)計(jì)的內(nèi)容（分析和設(shè)計(jì)）1.分析由題目的相關(guān)信息可以分析得：首先我們需要建立兩個(gè)鏈表AB，A鏈表的元素個(gè)數(shù)為m，B鏈表的元素個(gè)數(shù)為n；在將A、B鏈表進(jìn)行合并，根據(jù)m和n的大小關(guān)系決定鏈表C的元素順序；再將C進(jìn)行直接插入排序得到一個(gè)新的鏈表D；沒次輸入完一次鏈表信息，程序都會(huì)對(duì)相應(yīng)的鏈表進(jìn)行輸入操作以此確保程序輸入的數(shù)據(jù)是你想要輸入的數(shù)據(jù)。同時(shí)當(dāng)你合并好和排序好后都會(huì)進(jìn)行輸出操作。最后當(dāng)排序好后你可以指定你所要?jiǎng)h除數(shù)據(jù)的位置來刪除你所要?jiǎng)h除的數(shù)據(jù)。2.設(shè)計(jì)本次課程設(shè)計(jì)所需要用到的是關(guān)于鏈表的建立、合并以及直接插入排序的排序算法。需要先建立兩個(gè)鏈表，再將其合并為一個(gè)無序鏈表，最后對(duì)這個(gè)無序鏈表進(jìn)行直接插入排序并將其輸出。難點(diǎn)在于將AB合并為鏈表C的操作以及對(duì)鏈表C進(jìn)行直接插入排序的操作和根據(jù)用戶的意愿可以對(duì)鏈表進(jìn)行刪除的操作。三算法流程圖建立鏈表A建立鏈表B合并A B鏈表得到C鏈表得到D鏈表得到E鏈表比較m.n排序刪除四詳細(xì)步驟(1) 結(jié)構(gòu)體的創(chuàng)建：struct Node(2) 鏈表的創(chuàng)建：struct Node *create（）鏈表的創(chuàng)建。(3) 鏈表的輸出：void print(struct Node *head)功能是對(duì)鏈表進(jìn)行輸出。(4) 鏈表的合并：struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)算法的功能是實(shí)現(xiàn)兩個(gè)鏈表的交叉合并，并且可以根據(jù)兩鏈表的長短將行不通的插入。(5) 排序：void InsertSort(struct Node *p,int m)算法的功能是對(duì)一合并好的鏈表進(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ù)主要是對(duì)算法進(jìn)行測(cè)試。五代碼struct Node /數(shù)據(jù)結(jié)構(gòu)定義如下： long int number; struct Node *next;Node,*linkList;#include<stdlib.h> /源程序：#include<stdio.h>#include<conio.h>#include<malloc.h>#define error 0#define null 1#define L sizeof(struct Node)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); 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-; /控制輸入的個(gè)數(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)實(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 Node *head, *p1, *p2, *pos; /*判斷a，b大小并合并 */ if (a >= b) head = p1 = chain1; p2 = chain2; else/*b>a*/ head = p1 = chain2; p2 = chain1; temp = a, a = b, b = temp; /*交換a和b*/ /*下面把p1的每個(gè)元素插在p2相應(yīng)元素之前，p1長a,p2長b*/ pos = head; /*此時(shí)pos指向p1中的第一個(gè)元素*/ while (p2 != NULL) /漂亮，蛇形插入 p1 = p1->next; pos->next = p2; pos = p2; p2 = p2->next; pos->next = p1; pos = p1; return head;/對(duì)合并好的鏈表進(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 < 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; struct Node * delete_link(struct Node *p,int i) /按位刪除 struct Node *q; int j=0; while(j<i-1&&p->next) 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&&p->number!=i) p=p->next; j+; if (p) while (h<j-1&&p->next) 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("請(qǐng)輸入第一個(gè)鏈表:n"); printf("n輸入鏈表的長度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輸入鏈表的長度b:n"); scanf("%d", &b); printf("請(qǐng)輸入鏈表數(shù)據(jù)："); p2 = create(b); printf("n你剛才輸入的第二個(gè)鏈表的信息: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);printf("n請(qǐng)輸入鏈表中你所要?jiǎng)h除數(shù)據(jù)的所在位置:n");scanf("%d",&t); delete_link(p1,t);printf("n鏈表刪除數(shù)據(jù)后鏈表的信息:n");print(p1);printf("n請(qǐng)輸入你想要?jiǎng)h除的數(shù)值:n");scanf("%d",&m);delete_linkz(p1,m);printf("n鏈表刪除數(shù)據(jù)后鏈表的信息:n");print(p1); return 0;六顯示結(jié)果（1）m<n（2）m>n3.m=n4.按位刪除操作5.按值刪除七課程設(shè)計(jì)的總結(jié)通過進(jìn)一周的學(xué)習(xí)和實(shí)踐，解決實(shí)際問題，讓我對(duì)鏈表有了更深的了解，也讓我提高了解決實(shí)際問題的能力。在上機(jī)的同時(shí)改正了自己對(duì)某些算法的錯(cuò)誤使用，使自己在通過程序解決問題時(shí)抓住關(guān)鍵算法，有了算法設(shè)計(jì)思想和流程圖，并用C語言描繪出關(guān)鍵算法。 在運(yùn)行過程中，用戶可輸入你所需合并的兩個(gè)鏈表，首先輸入你所要輸入鏈表的長度再輸入鏈表的數(shù)據(jù)，完成第一個(gè)鏈表的輸入后，按照同樣的方法輸入第二個(gè)鏈表，每輸入完一個(gè)鏈表程序都會(huì)執(zhí)行輸出函數(shù)void print(struct Node *head)對(duì)鏈表進(jìn)行輸出，以此讓用戶可以確認(rèn)自己輸入的數(shù)據(jù)是否準(zhǔn)確。當(dāng)用戶輸入完第二個(gè)鏈表時(shí)，程序會(huì)先執(zhí)行struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)再執(zhí)行void InsertSort(struct Node *p,int m)來進(jìn)行合并和排序。合并之后和排序后又分別會(huì)再次執(zhí)行輸出函數(shù)，以此輸出合并后和排序后的鏈表數(shù)據(jù)。之后相應(yīng)的按照用戶的需要可以刪除所要?jiǎng)h除的數(shù)據(jù)。