數(shù)據(jù)結構課程設計---實現(xiàn)兩個鏈表的合并

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：15 大?。?15.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　一、課程設計題目：　　實現(xiàn)兩個鏈表的合并　　二、基本功能要求：　　1. 建立兩個鏈表A和B，鏈表元素個數(shù)分別為m和n個。　　2. 假設元

2、素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線性表C，使得：　　當m>=n時，C=x1,y1,x2,y2,…xn,yn,…,xm　　當n>m時，C=y1,x1,y2,x2,…ym,xm,…,yn　　3. 輸出線性表C：用直接插入排序法對C進行升序排序，生成鏈表D，并輸出

3、鏈表D。　　三、測試數(shù)據(jù)：　　1. A表（30，41，15，12，56，80） 　　B表（23，56，78，23，12，33，79，90，55）　　2. A表（30，41，15，12，56，80，23，12，34）

4、;　　B表（23，56，78，23，12） 　　四、理論分析結果：　　1. A表的數(shù)據(jù)元素個數(shù)m=6，B表的數(shù)據(jù)元素個數(shù) n=9，此時m<n 　　分析合并結果：當m<n時，應該先插入B表中的數(shù)據(jù)元素，在偶數(shù)位插入

5、B表中的數(shù)據(jù)元素，在奇數(shù)位插入A表中的數(shù)據(jù)元素，最后插入B表中剩余的數(shù)據(jù)元素。　　C=23，30，56，41，78，15，23，12，12，56，33，80，79，90，55　　排序結果：　　D=12，12，15，23，23，30，33，41，55，56，56，78，79，

6、80，90　　2. A表的數(shù)據(jù)元素個數(shù)m=9，B表的數(shù)據(jù)元素個數(shù) n=5，此時m>n　　分析合并結果：當m>=n時，應該先插入A表中的數(shù)據(jù)元素，在偶數(shù)位插入A表中的數(shù)據(jù)元素，在奇數(shù)位插入B表中的數(shù)據(jù)元素，最后插入A表中剩余的數(shù)據(jù)元素。　　C=30，23，41，56，15，78，12，23，56，12，

7、80，23，12， 34　　排序結果：　　D=12，12，12，15，23，23，23，30，34，41，56，56，78，80　　五、設計步驟：　　5.1 分析問題，給出數(shù)學模型，設計相應的數(shù)據(jù)

8、結構：　　1) 分析問題特點，用數(shù)學表達式或其它形式描述其數(shù)學模型。 　　2) 選擇能夠體現(xiàn)問題本身特點的一種或幾種邏輯結構。 　　3) 依據(jù)邏輯結構和問題特點，設計并選擇相應的存儲結構（順序存儲結構和鏈式存儲結構對應的算法實現(xiàn)有區(qū)別）。 　　5.2 算法設計：<

9、/p>　　1) 確定所需模塊：對于復雜的程序設計，要充分利用模塊化程序設計方法和面向對象思想，自頂向下，逐步細化。 　　2) 各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。　　3) 模塊之間的調用關系：給出算法各模塊之間的關系圖示。 　　5.3 上機實現(xiàn)程序：<

10、/p>　　為提高工作效率，充分利用上機調試時間，在上機之前應列出程序清單。　　5.4 有代表性的各種測試數(shù)據(jù)去驗證算法及程序的正確性：　　根據(jù)課程設計的要求對給定的數(shù)據(jù)進行測試，驗證算法以及程序的正確性。　　5.5 算法分析及優(yōu)化：　　經過上機

11、調試，源程序運行正確，并且實現(xiàn)算法要求的功能，解決課程設計題目中給出的問題后，分析算法的時間復雜度和空間復雜度，如有可能對程序進行優(yōu)化改進。　　六、模塊劃分：　　單鏈表頭文件：LinList.h　　主要包括單鏈表的存儲結構、初始化、求數(shù)據(jù)元素個數(shù)、插入、刪除數(shù)據(jù)元素、取數(shù)據(jù)元

12、素、撤消單鏈表的函數(shù)。　　2. 單鏈表操作頭文件：MyList.h　　主要包括單鏈表測試、單鏈表合并、單鏈表合并排序函數(shù)。　　3.測試主函數(shù)文件：TestLinList.h　　主要包括文件包含、數(shù)據(jù)導入和操作模塊程序。<b&

13、gt;　　七、算法設計：　　7.1 帶頭結點的單鏈表存儲結構　　typedef struct Node 　　{　　DataType data;　　struct Node *

14、next;　　}SLNode;　　7.2 單鏈表的初始化　　void ListInitiate(SLNode **head)　　{　　/*如果有內存空間

15、，申請頭結點空間并使頭指針head指向頭結點*/　　if((*head = (SLNode *)malloc(sizeof(SLNode)))==NULL) 　　exit(1);　　(*head)->next = NULL;/*尾標記NULL */

16、　　}　　7.3 求單鏈表中的數(shù)據(jù)元素個數(shù)　　int ListLength(SLNode *head)　　{　　SLNode *p = head; /*p指向頭結點*/<

17、/p>　　int size = 0; /*size初始為0*/　　while(p->next != NULL) /*循環(huán)計數(shù)*/　　{　　p = p->next;size ++;

18、;　　}　　return size;　　}　　7.4 向單鏈表中插入數(shù)據(jù)元素　　int ListInsert(SLNode *head,int i,DataType x)&

19、lt;b>　　{　　SLNode *p, *q; 　　int j; 　　p = head;　　j = -1;　　while(p

20、->next!=NULL && j<i-1) 　　{　　p = p->next; j++;　　}　　if(j != i - 1)<

21、p>　　{　　printf("Eorror: 插入位置參數(shù)錯!\n");　　return 0; 　　}　　if((q = (SLNode *)malloc(sizeof

22、(SLNode))) == NULL) 　　exit(1);　　q->data = x;　　q->next = p->next;　　p->next = q;　　ret

23、urn 1; 　　}//注：此單鏈表是帶頭結點的　　7.5 從單鏈表中刪除數(shù)據(jù)元素　　int ListDelete(SLNode *head,int i,DataType *x)　　{

24、;　　SLNode *p, *s;int j;　　p=head;　　j = -1;　　while(p->next != NULL && p->next->next!=NULL && j&

25、lt;i-1) 　　{　　p=p->next;j++;　　}　　if(j!=i-1)　　{

26、　　printf("Eorror: 刪除位置參數(shù)錯!\n");　　return 0;　　}　　s = p->next; 　　*x=s->dat

27、a; 　　p->next = p->next->next;　　free(s); 　　return 1;　　}<

28、;p>　　7.6 從單鏈表中取數(shù)據(jù)元素　　ListGet(SLNode *head,int i,DataType *x)　　{　　SLNode *p;　　int j;

29、　　p=head;　　j=-1;　　while(p->next!=NULL && j<i)　　{　　p=p-&g

30、t;next;j++;　　}　　if(j!=i)　　{　　printf("Eorror: 取數(shù)據(jù)元素位置參數(shù)出錯!\n");</p&

31、gt;　　return 0;　　}　　*x=p->data;　　return 1;　　}&l

32、t;/p>　　7.7 撤消單鏈表　　void Destroy(SLNode **head)　　{　　SLNode *p,*p1;　　p=*head;&

33、lt;/b>　　while(p!=NULL)　　{　　p1=p;p=p->next;free(p1);　　}　　*head=NULL;<

34、/p>　　}　　7.8 單鏈表測試函數(shù)　　void SingleList(int a[],int al)　　{　　int i,x;

35、　　SLNode *head;　　ListInitiate(&head);　　//向單鏈表插入數(shù)據(jù)元素　　for(i=0;i<al;i++)　　{<

36、p>　　if(ListInsert(head,i,a[i]) == 0)　　{ 　　printf("Error:插入數(shù)據(jù)元素錯誤! \n");return; 　　}&l

37、t;b>　　}　　//從單鏈表取數(shù)據(jù)元素　　printf("結果:");　　for(i=0; i<ListLength(head); i++)　　{<

38、p>　　if(ListGet(head,i,&x) == 0)　　{ 　　printf("Error:取數(shù)據(jù)元素錯誤! \n");return; 　　}

39、　else printf("%d ", x);　　}　　printf("\n");　　Destroy(&head);//撤消單鏈表　　printf("\n");<

40、;/p>　　}　　7.9 單鏈表合并函數(shù)　　void CombineList(int a[],int b[],int al,int bl)　　{　　int i,j=0,

41、x;　　int *list;　　SLNode *head;　　list=(int *)malloc((al+bl)*sizeof(int));　　if(al<bl)//a[]數(shù)組的數(shù)據(jù)元素個數(shù) < b[]數(shù)組的數(shù)據(jù)元素個數(shù)<p&

42、gt;　　{　　//較長數(shù)組的數(shù)據(jù)元素賦給動態(tài)數(shù)組的偶數(shù)位　　for(i=0;i<2*al;i+=2)　　{　　if(i%2==0)

43、;　　{　　list[i]=b[j];j++;　　}　　}　　j=0;//恢復公共下標初始值　　//較短數(shù)組的數(shù)據(jù)元素賦給動態(tài)數(shù)組的奇

44、數(shù)位　　for(i=0;i<2*al;i++)　　{　　if(i%2==1)　　{　　list[i]=a[j];j++;&l

45、t;p>　　}　　}　　//較長數(shù)組剩余數(shù)據(jù)元素賦值　　for(i=2*al;i<al+bl;i++)　　{<p&g

46、t;　　list[i]=b[j];j++;　　}　　}　　else//a[]數(shù)組的數(shù)據(jù)元素個數(shù) >= b[]數(shù)組的數(shù)據(jù)元素個數(shù)　　{

47、　　//較長數(shù)組b[]的數(shù)據(jù)元素賦給動態(tài)數(shù)組的偶數(shù)位　　for(i=0;i<2*bl;i+=2)　　{　　if(i%2==0)　　{<p&

48、gt;　　list[i]=a[j];j++;　　}　　}　　j=0;//恢復公共下標初始值　　//較短數(shù)組a[]的數(shù)據(jù)元素賦給動態(tài)數(shù)組的奇數(shù)位　　for(

49、i=0;i<2*bl;i++)　　{　　if(i%2==1)　　{　　list[i]=b[j];j++;　　}

50、　　}　　//較長數(shù)組a[]剩余數(shù)據(jù)元素賦值　　for(i=2*bl;i<al+bl;i++)　　{　　list[i]=a[j];j++;</

51、p>　　}　　}　　ListInitiate(&head);　　//向單鏈表插入數(shù)據(jù)元素　　for(i=0;i<al+bl;i++)

52、　　{　　if(ListInsert(head,i,list[i]) == 0)　　{ 　　printf("Error:插入A的數(shù)據(jù)元素錯誤! \n");<p&g

53、t;　　}　　}　　free(list);　　//從單鏈表取數(shù)據(jù)元素　　for(i=0;i<ListLength(head);i++)<b&g

54、t;　　{　　if(ListGet(head,i,&x) == 0)　　{ 　　printf("Error:取數(shù)據(jù)元素錯誤! \n");return; 　　}&

55、lt;/b>　　else 　　printf("%d ", x);　　}　　printf("\n");　　De

56、stroy(&head);//撤消單鏈表　　}　　7.10 直接插入法排序　　for(i=0;i<al+bl-1;i++)　　{　　temp

57、=list[i+1];　　j=i;　　while(j>-1 && temp<list[j])　　{　　list[j+1]=list[j];j--;

58、　　}　　list[j+1]=temp;　　}//直接插入法對數(shù)組list[]排序　　7.11 操作模塊設計　　printf("**********數(shù)據(jù)結構單鏈表合并測試實驗************\n&

59、quot;);　　printf("**** 1. 測試單鏈表A ****\n");　　printf("**** 2. 測試單鏈表B ****\n");　　printf("

60、;**** 3. 合并單鏈表A、B得到單鏈表C ****\n");　　printf("**** 4. 對單鏈表C升序排序得到單鏈表D ****\n");　　printf("**** 0. 退出合并單鏈表的測試程序 ****\n");

61、;　　printf("**********數(shù)據(jù)結構單鏈表合并測試實驗************\n");　　…… ……　　while(flag==1)　　{

62、　　printf("輸入功能號碼:");　　scanf("%d",&flag);　　switch(flag)　　{　　case 1:</p&g

63、t;　　printf("測試單鏈表A\n");　　SingleList(&a,al);　　flag=1;//功能循環(huán)標志　　break;　　case 2:</b

64、>　　printf("測試單鏈表B\n");　　SingleList(&b,bl);　　flag=1;//功能循環(huán)標志　　break;　　c

65、ase 3:　　printf("測試單鏈表A、B的合并\n");　　CombineList(&a,&b,al,bl);　　flag=1;//功能循環(huán)標志　　break;</

66、p>　　case 4:　　printf("測試單鏈表C的排序\n");　　SortList(&a,&b,al,bl);　　flag=1;//功能循環(huán)標志

67、　　break;　　case 0:　　printf("Message:歡迎下次再次測試單鏈表合并程序!\n");　　break;//flag!=0退出程序標志　　default

68、:　　printf("Error:功能號碼選擇錯誤,請重新選擇!\n");　　flag=1;//功能循環(huán)標志　　break;　　}&

69、lt;p>　　}　　八、測試程序運行結果：　　8.1 測試第1組數(shù)據(jù)　?。?）單鏈表測試：　　測試目的：測試單鏈表是否能夠進行插入、讀取等操作。

70、測試結果：單鏈表A=30，41，15，12，56，80　　單鏈表B=23，56，78，23，12，33，79，90，55　　（2）單鏈表合并測試：　　測試目的：測試兩個單鏈表是否能夠按照要求進行合并　　測試結果：單鏈表C=23，30，56，41，78，15，23，12，1

71、2，56，33，80，79，90，55　　（3）單鏈表合并后排序測試：　　測試目的：測試兩個合并后的單鏈表是否能夠升序排序后輸出　　測試結果：單鏈表D=12，12，15，23，23，30，33，41，55，56，56，78，79，80，90　　8.2 測試第2組數(shù)據(jù)<

72、;/p>　　（1）單鏈表測試：　　測試目的：測試單鏈表是否能夠進行插入、讀取等操作。　　測試結果：單鏈表A= 30，41，15，12，56，80，23，12，34　　單鏈表B= 23，56，78，23，12

73、　?。?）單鏈表合并測試：　　測試目的：測試兩個單鏈表是否能夠按照要求進行合并　　測試結果：單鏈表C= 30，23，41，56，15，78，12，23，56，12，80，23，12， 34　?。?）單鏈表合并后排序測試：　　測試目的：測試兩個合并后的單鏈表是否能夠升序排序

74、后輸出　　測試結果：單鏈表D= 12，12，12，15，23，23，23，30，34，41，56，56，78，80　　8.3 測試說明：　　經過反復的程序調試和修改，最終實現(xiàn)了本次課程設計的任務。限于篇幅，程序運行結果只有調試修改正確以后的的運行結果。

75、　　為了方便測試，在測試過程中，把要測試的數(shù)據(jù)直接通過添加數(shù)據(jù)程序代碼導入到程序中。把程序運行結果和理論分析結果進行對比，驗證程序的正確性。　　8.4 測試結論：　　在程序完成編寫之后，程序的連接、編譯、運行開始不能夠正常通過，經過調試、修改之后，最終都能夠正常通過，修改過后的程序中沒有語法錯誤。&

76、lt;/p>　　把測試結構和理論的分析結構進行對比，通過程序運行結果的觀察得知程序運行結果和理論分析結果基本吻合。　　通過單鏈表的操作可以完成兩個單鏈表的合并，除此之外，還能夠對單鏈表合并后的數(shù)據(jù)元素進行排序。　　課程設計總結：　　9.1 課程設計

77、題目的選擇　　在本次的數(shù)據(jù)結構課程設計中，我選擇的題目是“實現(xiàn)兩個單鏈表的合并”，從所學習過的知識入手進行課程的設計。程序設計語言選擇C語言，由于學習的時間較早，經過一段時間的編程積累用的相對比較熟練。　　9.2 對題目的認識　　單鏈表是數(shù)據(jù)結構里面典型的線性表，適用范圍比較廣泛，使用方法也相對靈活，在課堂上我們

78、學習了單鏈表的基本數(shù)據(jù)結構和單鏈表的基本操作，但是并沒有運用到實際的程序中，這次課程設計把我們的理論知識和程序實踐聯(lián)系起來了。　　9.3 編程心得　　通過本次的課程設計，使我學會了如何去組織代碼量較大大程序。與此同時，也使我學會了一些對代碼量較大的的程序進行編寫、連接、編譯運行、以及調試和修改的技巧。</p&g

79、t;　　9.4 課程設計感想　　這次的課程設計涉及到編程語言和數(shù)據(jù)結構的知識，要求和平時的實驗相比相對較高。從本次的課程設計可以檢驗我們對C語言和數(shù)據(jù)結構的掌握情況，同時也檢驗了我們對所學習過的知識的靈活運用情況。在創(chuàng)新性方面，這次的課程設計雖然完成了課程設計的任務，但是缺乏創(chuàng)造性的設計思想，在以后的學習過程中還得繼續(xù)努力。　　參

80、考文獻資料　　[1].嚴蔚敏編著.數(shù)據(jù)結構（C語言版）.清華大學出版社，2002　　[2].朱戰(zhàn)立. 編著.數(shù)據(jù)結構——使用C語言.西安交通大學出版社，2004　　[3].朱戰(zhàn)立，張選平編著.數(shù)據(jù)機構學習指導和典型題解.西安交通大學出版社，2002　　[4].蘇小

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計---實現(xiàn)兩個鏈表的合并

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計---實現(xiàn)兩個鏈表的合并

文檔簡介

溫馨提示

最新文檔

評論

免費下載