實(shí)現(xiàn)兩個(gè)鏈表的合并

1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目：實(shí)現(xiàn)兩個(gè)鏈表的合并學(xué)生專(zhuān) 業(yè)班 級(jí)指導(dǎo)教師2012年06 月21 日課程設(shè)計(jì)目的：課程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將課本上的理 論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，鍛煉學(xué)生的分析解決實(shí)際問(wèn)題的能力。提高學(xué)生 適應(yīng)實(shí)際，實(shí)踐編程的能力。二、課程設(shè)計(jì)題目：實(shí)現(xiàn)兩個(gè)鏈表的合并要求：1）輸入2個(gè)單鏈表2）輸出2個(gè)單鏈表合并后形成的結(jié)果三、模塊劃分：（1）數(shù)據(jù)模塊參考使用課本上的具有頭結(jié)點(diǎn)的鏈表抽象數(shù)據(jù)類(lèi)型lin klist ，該抽象數(shù)據(jù)類(lèi)型中包含一個(gè)elemtype類(lèi)型的數(shù)據(jù)和一個(gè)指針，在開(kāi)始用時(shí)，elemtype定義為整 型變量，指針用來(lái)指向下一個(gè)元素。對(duì)應(yīng)的

2、使用鏈表抽象數(shù)據(jù)類(lèi)型lin klist 基本操作的函數(shù)有：初始化操作函數(shù) void in i（li nklist *s）。（2）創(chuàng)建鏈表模塊void create（li nklist *s）其功能是創(chuàng)建鏈表錄入數(shù)據(jù)。（3）輸出數(shù)據(jù)模塊void display（l in klist *s）其功能為是輸出s鏈表中的各項(xiàng)元素，從而驗(yàn)證操作是否成功（4）排序模塊void sort（l in klist *s）此函數(shù)功能是s鏈表使用冒泡法對(duì)鏈表進(jìn)行排序（5）合并鏈表模塊void add（li nklist *s1,li nklist *s2）其功能是按照題目要現(xiàn)兩個(gè)鏈表的合并，將s2鏈表插入到si鏈表中

3、。（6）主函數(shù)模塊void mai n()，函數(shù)中調(diào)用了各個(gè)模塊的函數(shù)，從而實(shí)現(xiàn)了題目合并排序的 要求四、流程圖:結(jié)束五、算法設(shè)計(jì)分析這個(gè)兩個(gè)鏈表的交叉合并算法主要運(yùn)用到的是鏈表的基本操作，定義 節(jié)點(diǎn)，將鏈表的創(chuàng)建、鏈表的插入、鏈表容升序排列，通過(guò)主函數(shù)調(diào)用。這 樣就大大精簡(jiǎn)了主函數(shù)的操作。但主函數(shù)中很大篇幅用到了if、else語(yǔ)句,用以指定鏈表指定結(jié)點(diǎn)，這樣就使得本來(lái)很精簡(jiǎn)變得繁瑣，降低了程序的質(zhì) 量。所以其有優(yōu)點(diǎn)和缺點(diǎn)，但需要不斷的改進(jìn)，不斷優(yōu)化該程序。六、數(shù)據(jù)結(jié)構(gòu)：（1）數(shù)據(jù)類(lèi)型DataType定義如下：typedef int elemtype;（2）帶頭結(jié)點(diǎn)鏈表抽象數(shù)據(jù)類(lèi)型的結(jié)點(diǎn)結(jié)構(gòu)定

4、義如下:typedef struct nodeelemtype data;li nklist;七、源程序:#defi ne null 0typedef int elemtype;typedef struct nodeelemtype data;struct node *n ext;li nklist;void in i(li nklist *s)s->n ext=n ull;void create(li nklist *s)li nklist *p,*q=s;elemtype e;prin tf("please in put the data;' n");sc

5、a nf("%d",&e);while(e!=-1)p=(li nklist *)malloc(sizeof(li nklist); p->data=e;q->n ext=p;q=q->n ext;sea nf("%d",&e);q->n ext=n ull;void display(l in klist *s)lin klist *p=s->n ext;if(s->n ext=n ull)prin tf("the lin klist is empty!n");elseprin tf

6、("output the data:n");while(p!=null)prin tf("%5d",p->data);p=p->n ext;prin tf("n");void sort(l in klist *s)lin klist *p,*q;elemtype t;p=s->n ext;while(p!=null)q=p->n ext;while(q!=null)if(p->data>q->data)t=p->data; p->data=q->data;q->data

7、=t; q=q->n ext; p=p->n ext;void add(li nklist *s1,li nklist *s2)lin klist *p1= s1-> next,*p2=s1,*q1=s2-> next,*q2=s2;if(s1=nu II)s1=s2;while(p1!=null&&q1!=null) if(p1->data<q1->data)p1=p1- >n ext;elseq2->n ext=q1- >n ext;q1- >n ext=p2->n ext;p2->n ext=q

8、1;p2=p2->n ext;q1=q2->n ext;if(q1!=n ull)p2->n ext=q1;void mai n()lin klist *s1,*s2;s1=(li nklist *)malloc(sizeof(li nklist);in i(s1);create(s1);display(s1);sort(s1);display(s1);s2=(li nklist *)malloc(sizeof(li nklist);in i(s2);create(s2);display(s2);sort(s2);display(s2);add(s1,s2);display(sl);八、實(shí)驗(yàn)運(yùn)行結(jié)果顯示:outputthedata：1234outpuh七lwdatza "1234pleasejjnput thedata ；& 8 7 <6 -1NDUtpiltthedata 876frll«7a9putputthedata：1234data ；hplease Input the1 2 3 4 5 -1cont inue九、實(shí)驗(yàn)收獲和體會(huì):十、參考文獻(xiàn)1國(guó)玲.