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

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

2、勺相關(guān)信息。二、算法的流程圖三、算法設(shè)計(jì)分析這個(gè)兩個(gè)鏈表的交叉合并算法主要運(yùn)用到的是鏈表的基本操作，定義 節(jié)點(diǎn)，將鏈表的創(chuàng)建、計(jì)算鏈表的長(zhǎng)度、鏈表 A,B的交叉組合、鏈表內(nèi)容升 序排列、刪除鏈表指定位置元素、刪除指定的元素等算法寫成了獨(dú)立函數(shù)， 通過主函數(shù)調(diào)用。這樣就大大精簡(jiǎn)了主函數(shù)的操作。但主函數(shù)中很大篇幅用 到了 if、else語句，用以指定鏈表指定結(jié)點(diǎn)和指定元素的刪除操作，這樣就使得本來很精簡(jiǎn)變得繁瑣，降低了程序的質(zhì)量。所以具有優(yōu)點(diǎn)和缺點(diǎn)，但需 要不斷的改進(jìn)，不斷優(yōu)化該程序。源代碼程序源代碼:#include<stdio.h>#include<stdlib.h>t

3、ypedef struct node/int data;struct node *next; node,*linklist;節(jié)點(diǎn)定義linklist creat(linklist head) /node *r,*s;int a;r = (linklist)malloc(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:")

4、; scanf("%d",&a);r->next=NULL;return head;該函數(shù)用來創(chuàng)建鏈表linklist length(linklist l) / int i=0;linklist p=l->next; / p while(p) i+;p=p->next;return i;返回 L 中數(shù)據(jù)元素個(gè)數(shù)指向第一個(gè)結(jié)點(diǎn)鏈表內(nèi)容升序排列用于實(shí)現(xiàn)鏈表A,B的交叉組合linklist mergel(linklist A,linklist B) / int m,n;node *p,*q,*s,*t;linklist C;p=A->next;q=

5、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=q->next;q->next=s;p=s;q=t;return C;linklist sort(linklist L) /linklist p,q,min;int temp;p=L;while( p=p->next )q=min=p;while(q=q->next)if( q->data<min-&

6、gt;data )min = q;if( min!=p )temp = p->data;p->data = min->data;min->data=temp;return L;linklist 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;elseprintf("input indext error

7、");return l;linklist Delete_element(linklist l,int data) / linklist p;p=l;if(p->next)while(p->next->data!=data)p=p->next;刪除鏈表指定位置元素刪除指定的元素p->next=p->next->next;elseprintf("don't faind the element");return l;linklist display(linklist l) /打印 linklist p;printf(&q

8、uot;new linklist :n");p = l->next;while(p)printf("%dn",p->data);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");/printf("please input a data:");A = creat(A);創(chuàng)建A鏈表，并打印printf("Creat link

9、list B:n");/printf("please input a data:");B = creat(B);C = mergel(A,B);/printf("linklist Cn");p = C->next;while(p)printf("%dn",p->data);p=p->next;創(chuàng)建B 鏈表, 并打印生成C鏈表，并打印對(duì) C 進(jìn)行排序生成DD=C;/sort(D); printf("linklist D:n");q = D->next; while(q) printf

10、("%dn",q->data); q = q->next;printf("nplease input 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");scan

11、f("%d",&indexs);fflush(stdin);if(name='A')Delete(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);elseprintf("nameError");else if(cmd=1)/

12、元素刪除fflush(stdin);/清除緩沖printf("please input linklist namen ");/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);di

13、splay(B);else if(name='C')Delete_element(C,datas);display(C);else if(name='D')Delete_element(D,datas);display(D);elseprintf("name2error"); elseprintf("cmdError");printf("nOvern");getchar();return 0;六、實(shí)驗(yàn)運(yùn)行結(jié)果顯示：設(shè)計(jì)體會(huì)及今后改進(jìn)的意見短短一周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)結(jié)束了，回想著這一周自己的表現(xiàn)，感覺不是很滿意，感到自己許多不足之處。但同時(shí)通過本次課程設(shè)計(jì)，我也收獲了不少。這次課程設(shè)計(jì)我做的是實(shí)現(xiàn)兩個(gè)鏈表的合并，由于有C語言的編程，而編程一直對(duì)我來說就是一個(gè)弱項(xiàng)，我覺的我選的這個(gè)題比較基礎(chǔ)，自己也有一些思路，但在程序編寫過程中還是遇到了不少問題，在開始前， 我查閱相關(guān)資料，對(duì)這次課程誰過程中用到的知識(shí)做出了一個(gè)系統(tǒng)的歸納：如鏈表的建立、鏈表的合并、直接插入排序以及SWITCH語句等知識(shí)點(diǎn)。但在板鞋程序過程中還是遇到了一些問題。經(jīng)過修改、調(diào)試、運(yùn)行然后再修改、調(diào)試、運(yùn)行，有時(shí)雖然能運(yùn)行，但對(duì)本次實(shí)驗(yàn)來說缺少一定程度的完整性，然后就上網(wǎng)查資料，在書上查看相關(guān)方面的知識(shí)，當(dāng)編寫的程序感覺符合要求時(shí)