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

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

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

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

5、xt; / p指向第一個結(jié)點while(p) i+; p=p->next; return i;linklist mergel(linklist A,linklist B) /用于實現(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; /用于計數(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; /對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; 六、實驗運行結(jié)果顯示：設(shè)計體會及今后改進(jìn)的意見;短短一周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計結(jié)束了，回想著這一周自己的表現(xiàn)，感覺不是很滿意，感到自己許多不足之處。但同時通過本次課程設(shè)計，我也收獲了不少。這次課程設(shè)計我做的是實現(xiàn)兩個鏈表的合

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