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

1、<p><b>　　課程設(shè)計報告</b></p><p>　　課程設(shè)計題目：實現(xiàn)兩個鏈表的合并</p><p>　　2013年 01月 08 日</p><p><b>　　課程設(shè)計目的：</b></p><p>　　課程設(shè)計為學(xué)生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理

2、論知識和實際有機的結(jié)合起來，鍛煉學(xué)生的分析解決實際問題的能力。提高學(xué)生適應(yīng)實際，實踐編程的能力。</p><p><b>　　課程設(shè)計題目：</b></p><p><b>　　實現(xiàn)兩個鏈表的合并</b></p><p>　　要求：1）輸入2個單鏈表</p><p>　　2）輸出2個單鏈表合并后形成

3、的結(jié)果。</p><p><b>　　三、模塊劃分：</b></p><p><b>　?。?）數(shù)據(jù)模塊</b></p><p>　　參考使用課本上的具有頭結(jié)點的鏈表抽象數(shù)據(jù)類型linklist，該抽象數(shù)據(jù)類型中包含一個elemtype類型的數(shù)據(jù)和一個指針，在開始用時，elemtype定義為整型變量，指針用來指向下一個元素

4、。對應(yīng)的使用鏈表抽象數(shù)據(jù)類型linklist基本操作的函數(shù)有：初始化操作函數(shù)void ini(linklist *s)。</p><p><b>　　（2）創(chuàng)建鏈表模塊</b></p><p>　　void create(linklist *s)</p><p>　　其功能是創(chuàng)建鏈表錄入數(shù)據(jù)。</p><p><b

5、>　?。?）輸出數(shù)據(jù)模塊</b></p><p>　　void display(linklist *s)</p><p>　　其功能為是輸出s鏈表中的各項元素，從而驗證操作是否成功</p><p><b>　?。?）排序模塊</b></p><p>　　void sort(linklist *s)<

6、;/p><p>　　此函數(shù)功能是s鏈表使用冒泡法對鏈表進行排序</p><p><b>　?。?）合并鏈表模塊</b></p><p>　　void add(linklist *s1,linklist *s2)</p><p>　　其功能是按照題目要求實現(xiàn)兩個鏈表的合并，將s2鏈表插入到s1鏈表中。</p>&

7、lt;p><b>　　（6）主函數(shù)模塊</b></p><p>　　void main()，函數(shù)中調(diào)用了各個模塊的函數(shù)，從而實現(xiàn)了題目合并排序的要求</p><p><b>　　四、流程圖：</b></p><p>　　S1為null s1!=null</p>

8、<p><b>　　五、算法設(shè)計分析</b></p><p>　　這個兩個鏈表的交叉合并算法主要運用到的是鏈表的基本操作，定義節(jié)點，將鏈表的創(chuàng)建、鏈表的插入、鏈表內(nèi)容升序排列，通過主函數(shù)調(diào)用。這樣就大大精簡了主函數(shù)的操作。但主函數(shù)中很大篇幅用到了if、else語句，用以指定鏈表指定結(jié)點，這樣就使得本來很精簡變得繁瑣，降低了程序的質(zhì)量。所以其有優(yōu)點和缺點，但需要不斷的改進，不斷優(yōu)化該

9、程序。</p><p><b>　　六、數(shù)據(jù)結(jié)構(gòu)：</b></p><p>　?。?）數(shù)據(jù)類型DataType定義如下：</p><p>　　typedef int elemtype;</p><p>　　（2）帶頭結(jié)點鏈表抽象數(shù)據(jù)類型的結(jié)點結(jié)構(gòu)定義如下： </p><p>　　typedef s

10、truct node</p><p><b>　　{</b></p><p>　　elemtype data;</p><p>　　struct node *next;</p><p>　　}linklist;</p><p><b>　　七、源程序：</b></p&g

11、t;<p>　　#define null 0 </p><p>　　typedef int elemtype;</p><p>　　typedef struct node </p><p><b>　　{ </b></p><p>　　elemtype data;</p><p>

12、　　struct node *next;</p><p><b>　　}</b></p><p><b>　　lin; </b></p><p>　　void inia(lin *a) </p><p><b>　　{ </b></p><p>　　a-

13、>next=null;</p><p><b>　　} </b></p><p>　　void create(lin *a) </p><p>　　{ lin *p,*q=a; </p><p>　　elemtype e; </p><p>　　printf("please

14、input the data;\n"); </p><p>　　scanf("%d",&e); </p><p>　　while(e!=-1) </p><p><b>　　{ </b></p><p>　　p=(lin *)malloc(sizeof(lin)); </p

15、><p>　　p->data=e; </p><p>　　q->next=p; </p><p>　　q=q->next; </p><p>　　scanf("%d",&e); </p><p><b>　　} </b></p>

16、<p>　　q->next=null;</p><p><b>　　} </b></p><p>　　void display(lin *a)</p><p><b>　　{ </b></p><p>　　lin *p=a->next; </p><

17、p>　　if(a->next==null) </p><p>　　printf("the lin is empty!\n"); </p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　printf(&

18、quot;output the data:\n"); </p><p>　　while(p!=null) </p><p><b>　　{ </b></p><p>　　printf("%5d",p->data); </p><p>　　p=p->next;</p&g

19、t;<p><b>　　} </b></p><p><b>　　} </b></p><p>　　printf("\n");</p><p><b>　　} </b></p><p>　　void sort(lin *a)</p>

20、;<p><b>　　{ </b></p><p>　　lin *p,*q;</p><p>　　elemtype t;</p><p>　　p=s->next;</p><p>　　while(p!=null) </p><p><b>　　{ </b&g

21、t;</p><p>　　q=p->next;</p><p>　　while(q!=null) </p><p><b>　　{ </b></p><p>　　if(p->data>q->data) </p><p>　　{ t=p->data;

22、 </p><p>　　p->data=q->data; </p><p>　　q->data=t; </p><p><b>　　} </b></p><p>　　q=q->next; </p><p><b>　　} </b><

23、/p><p>　　p=p->next; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　void add(lin *s1,lin *s2)</p><p><b>　　{ </b></

24、p><p>　　lin *p1=a1->next,*p2=a1,*q1=a2->next,*q2=a2;</p><p>　　if(s1==null) </p><p><b>　　a1=a2; </b></p><p>　　while(p1!=null&&q1!=null) </p&

25、gt;<p><b>　　{ </b></p><p>　　if(p1->data<q1->data) </p><p>　　{ p1=p1->next; </p><p>　　p2=p2->next </p><p><b>　　}</b>&l

26、t;/p><p><b>　　else </b></p><p>　　{ q2->next=q1->next;</p><p>　　q1->next=p2->next;</p><p>　　p2->next=q1;</p><p>　　p2=p2->next; &

27、lt;/p><p>　　q1=q2->next; </p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　if(q1!=null) </p><p>　　p2->next=q1;</p><

28、p>　　} void main()</p><p><b>　　{ </b></p><p>　　lin *a1,*a2; </p><p>　　s1=(lin *)malloc(sizeof(lin)); </p><p>　　inia(a1); </p><p>　　create(a

29、1); </p><p>　　display(a1); </p><p><b>　　sort(a1);</b></p><p>　　display(a1); </p><p>　　a2=(lin *)malloc(sizeof(lin)); </p><p>　　inia(a2); &l

30、t;/p><p>　　create(a2); </p><p>　　display(a2);</p><p>　　sort(a2); </p><p>　　display(a2); </p><p>　　add(a1,a2); </p><p>　　display(a1)</p>

31、<p><b>　　}</b></p><p>　　八、實驗運行結(jié)果顯示：</p><p><b>　　實驗收獲和體會：</b></p><p>　　這次的課程設(shè)計，加強了我們動手、思考和解決問題的能力。鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學(xué)知識的能力。培養(yǎng)了我選用參考書，查閱手冊及文獻(xiàn)資料的能力

32、。從中我意識到程序的成功不僅僅是消除語法上的錯誤，而且還要執(zhí)行成功。缺乏完整的思路，盡管語法正確，程序還是無法執(zhí)行。數(shù)據(jù)結(jié)構(gòu)的設(shè)計考驗的不僅僅是我們對書本知識的理解，還考驗了我們分析事物時思維的邏輯緊密性，加深并鞏固了我對數(shù)據(jù)結(jié)構(gòu)的認(rèn)識。平時看課本時，有些問題就不是很能理解，做完課程設(shè)計，那些問題就迎刃而解了。而且還可以記住很多東西。認(rèn)識來源于實踐，實踐是認(rèn)識的動力和最終目的，實踐是檢驗真理的唯一標(biāo)準(zhǔn)。所以這個期末測試之后的課程設(shè)計對我