數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)現(xiàn)兩個(gè)鏈表的合并

1、一、 需求分析： 題目： 實(shí)現(xiàn)兩個(gè)鏈表的合并 問(wèn)題描述： 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。 由題目的相關(guān)信息可以分析得到：首先我們需要建立兩個(gè)鏈表AB，A鏈表的元素個(gè)數(shù)為m；B鏈表的元素個(gè)數(shù)為n；在將AB鏈表進(jìn)行合并，更具m和n的大小關(guān)系決定鏈表C的元素順序；再將C經(jīng)行直接插入排序得到一個(gè)新的鏈表D；最后輸出ABCD的相關(guān)信息。

2、 開(kāi)始二、 算法的流程圖 Creat A 鏈表 Creat B 鏈表Mergel(A,B) 合并成C 對(duì)C排序生成D 提示輸入0或1cmd=0 cmd=1 錯(cuò)誤輸入輸入將要操作的鏈表的名字Cmd error輸入將要操作的鏈表的名字正確 錯(cuò)誤 正確 錯(cuò)誤Nameerror刪除，打印Nameerror刪除，打印 打印“over”結(jié)束三、 算法設(shè)計(jì)分析 這個(gè)兩個(gè)鏈表的交叉合并算法主要運(yùn)用到的是鏈表的基本操作，定義節(jié)點(diǎn)，將鏈表的創(chuàng)建、計(jì)算鏈表的長(zhǎng)度、鏈表A,B的交叉組合、鏈表內(nèi)容升序排列、刪除鏈表指定位置元素、刪除指定的元素等算法寫(xiě)成了獨(dú)立函數(shù)，通過(guò)主函數(shù)調(diào)用。這樣就大大精簡(jiǎn)了主函數(shù)的操作。但主函數(shù)中

3、很大篇幅用到了if、else語(yǔ)句，用以指定鏈表指定結(jié)點(diǎn)和指定元素的刪除操作，這樣就使得本來(lái)很精簡(jiǎn)變得繁瑣，降低了程序的質(zhì)量。所以其有優(yōu)點(diǎn)和缺點(diǎn)，但需要不斷的改進(jìn)，不斷優(yōu)化該程序。四、 源代碼 程序源代碼:#include<stdio.h>#include<stdlib.h>typedef struct node /節(jié)點(diǎn)定義 int data; struct node *next; node,*linklist;linklist creat(linklist head) /該函數(shù)用來(lái)創(chuàng)建鏈表 node *r,*s; int a; r = (linklist)malloc(

4、sizeof(node); head = r; scanf("%d",&a); while(a != 0) s =(node*)malloc(sizeof(node); s->data=a; r->next=s; r=s; printf("please input a data:"); scanf("%d",&a); r->next=NULL; return head;linklist length(linklist l) / 返回L中數(shù)據(jù)元素個(gè)數(shù)int i=0;linklist p=l->ne

5、xt; / p指向第一個(gè)結(jié)點(diǎn)while(p) i+; p=p->next; return i;linklist mergel(linklist A,linklist B) /用于實(shí)現(xiàn)鏈表A,B的交叉組合 int m,n; node *p,*q,*s,*t; linklist C; p=A->next; q=B->next; m=length(A); n=length(B); C=A; if(m<n) p=B->next;q=A->next;C=B; while(p&&q) s=p->next; p->next=q; if(s) t

6、=q->next; q->next=s; p=s; q=t; return C; linklist sort(linklist L) /鏈表內(nèi)容升序排列 linklist p,q,min; int temp; p=L; while( p=p->next ) q=min=p; while(q=q->next) if( q->data<min->data ) min = q; if( min!=p ) temp = p->data; p->data = min->data; min->data=temp; return L;link

7、list Delete(linklist l,int index) /刪除鏈表指定位置元素 linklist p,t; int cx=1; /用于計(jì)數(shù) p=l; if(index<length(l) while(p&&(cx<index) t=p; p=p->next; cx+; t->next=p->next; else printf("input indext error");return l;linklist Delete_element(linklist l,int data) /刪除指定的元素 linklist p;

8、p=l; if(p->next) while(p->next->data!=data) p=p->next; p->next=p->next->next; else printf("don't faind the element"); return l;linklist display(linklist l) /打印 linklist p;printf("new linklist :n");p = l->next;while(p) printf("%dn",p->data)

9、;p= p->next; return l; main() linklist p,q,A,B,C,D;int indexs;int datas;char name;int cmd; printf("Creat linklist A:n"); /創(chuàng)建A鏈表,并打印 printf("please input a data:");A = creat(A); printf("Creat linklist B:n"); /創(chuàng)建B鏈表,并打印printf("please input a data:"); B = crea

10、t(B); C = mergel(A,B); /生成C鏈表 ，并打印 printf("linklist Cn");p = C->next; while(p) printf("%dn",p->data); p=p->next; D=C; /對(duì)C進(jìn)行排序生成D sort(D); printf("linklist D:n");q = D->next; while(q) printf("%dn",q->data); q = q->next; printf("nplease in

11、put 0 or 1 n"); /用1和0判斷是按位置刪除還是直接刪除元素scanf("%d",&cmd);if(cmd=0) /位置刪除 printf("please input linklist namen ");fflush(stdin);scanf("%c",&name);printf("nplease input index n"); scanf("%d",&indexs);fflush(stdin);if(name='A')Delet

12、e(A,indexs); display(A);else if(name='B')Delete(B,indexs);display(B);else if(name='C')Delete(C,indexs);display(C);else if(name='D')Delete(D,indexs);display(D);else printf("nameError"); else if(cmd=1) /元素刪除 fflush(stdin); /清除緩沖 printf("please input linklist name

13、n ");/fflush(stdin);scanf("%c",&name);printf("nplease input datas n");scanf("%d",&datas);if(name='A')Delete_element(A,datas);display(A);else if(name='B')Delete_element(B,datas);display(B);else if(name='C') Delete_element(C,datas); di

14、splay(C);else if(name='D')Delete_element(D,datas); display(D);else printf("name2error"); else printf("cmdError");printf("nOvern"); getchar(); return 0; 六、實(shí)驗(yàn)運(yùn)行結(jié)果顯示：設(shè)計(jì)體會(huì)及今后改進(jìn)的意見(jiàn);短短一周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)結(jié)束了，回想著這一周自己的表現(xiàn)，感覺(jué)不是很滿意，感到自己許多不足之處。但同時(shí)通過(guò)本次課程設(shè)計(jì)，我也收獲了不少。這次課程設(shè)計(jì)我做的是實(shí)現(xiàn)兩個(gè)鏈表的合

15、并，由于有C語(yǔ)言的編程，而編程一直對(duì)我來(lái)說(shuō)就是一個(gè)弱項(xiàng)，我覺(jué)的我選的這個(gè)題比較基礎(chǔ)，自己也有一些思路，但在程序編寫(xiě)過(guò)程中還是遇到了不少問(wèn)題，在開(kāi)始前，我查閱相關(guān)資料，對(duì)這次課程誰(shuí)過(guò)程中用到的知識(shí)做出了一個(gè)系統(tǒng)的歸納：如鏈表的建立、鏈表的合并、直接插入排序以及SWITCH語(yǔ)句 等知識(shí)點(diǎn)。但在板鞋程序過(guò)程中還是遇到了一些問(wèn)題。經(jīng)過(guò)修改、調(diào)試、運(yùn)行然后再修改、調(diào)試、運(yùn)行，有時(shí)雖然能運(yùn)行，但對(duì)本次實(shí)驗(yàn)來(lái)說(shuō)缺少一定程度的完整性，然后就上網(wǎng)查資料，在書(shū)上查看相關(guān)方面的知識(shí)，當(dāng)編寫(xiě)的程序感覺(jué)符合要求時(shí)，在運(yùn)行時(shí)卻出現(xiàn)一些小錯(cuò)誤導(dǎo)致整個(gè)程序無(wú)法正常運(yùn)行。最后在同學(xué)和老師的幫助下，我終于運(yùn)行出結(jié)果，達(dá)到比本次實(shí)驗(yàn)的目的。通過(guò)本次實(shí)驗(yàn)，我在C語(yǔ)