課程設計---雙鏈表的建立插入查找刪除算法的實現(xiàn)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：27 大?。?87.50KB 人氣指數：12 舉報 版權申訴

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

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

文檔簡介

1、　　數據結構課程設計　　設計說明書　　課程設計任務書　　2011—2012學年第二學期　　課程設計名稱：

2、數據結構課程設計 　　設計題目：雙鏈表的建立插入查找刪除算法的實現(xiàn) 　　完成期限：自 2012 年 2 月 20 日至 2012 年

3、3 月 2 日共 2 周 　　設計要求、設計依據、要求及主要內容（可另加附頁）：　　設計內容：雙鏈表的建立插入查找刪除算法的實現(xiàn)，雙鏈表具有雙向鏈接的特點，克服了單鏈表的單向性。要求通過結構體類型建立空的雙鏈表，在此基礎上調用函數實現(xiàn)雙鏈表的建立、插入、查找和刪除等基本操作。　　設計要求：1.遵

4、循結構化程序設計思想，采用C/C++實現(xiàn)。　　2.界面友好，操作簡便，容錯性好。 　　指導教師（簽字）：教研室主任（簽字）： 　　批準日期：年月日　　摘要<

5、;/b>　　本課題主要討論在鏈式結構中建立雙向鏈表。雙向鏈表有兩個指針域，其一指向直接前趨，另一指向直接后繼。并合理利用插入、查找、刪除運算。和單鏈的循環(huán)表類似，雙鏈表也可以有相應的循環(huán)表。用一個表頭單元將雙鏈表首尾相接，即將表頭單元中的head指針指向表尾，并將表尾單元的next指針指向表頭單元。　　關鍵詞：雙向鏈表；鏈式結構；直接前趨；直接后繼

6、　　‘　　目錄　　1.課題描述1　　2．需求分析2　　2.1程序功能說明

7、2　　2.2輸入輸出2　　3.程序流程圖3　　3.1創(chuàng)建雙向鏈表3　　3.2按位次查找4　　3.3插入新的元素5<

8、;p>　　3.4刪除一個元素6　　4．概要設計7　　4.1 程序模塊7　　4.2 課題涉及的數據結構7　　4.2.1 雙鏈表結點的插入7　　4.2.2 雙鏈表結點的刪除7&l

9、t;/p>　　5. 調試分析以及設計體會8　　6．源程序代碼9　　7.程序運行結果14　　7.1創(chuàng)建雙鏈表14　　7.2 輸入元素15　　7.3 查找一個

10、不屬于鏈表的值16　　7.4 正確的查找17　　7.5不合法的插入一個數18　　7.6正確的插入一個數19　　7.7刪除不合法的位次20　　7.8刪除位次21

11、　　總結22　　參考文獻23　　1.課題描述　　雙（向）鏈表中有兩條方向不同的鏈，即每個結點中除next域存放后繼結點地址外，還增加一個指向其直接前趨的指針域prior。雙鏈表有以下特點：&

12、lt;p>　　雙鏈表由頭指針head惟一確定的。 　　帶頭結點的雙鏈表的某些運算變得方便。 　　將頭結點和尾結點鏈接起來，為雙（向）循環(huán)鏈表。　　2．需求分析　　2.1程序功能說明</

13、p>　　鏈表是線性表的鏈式表示，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，所以它沒有順序存儲結構在做插入刪除操作時需要移動大量元素的弱點。雙鏈表的結點中有兩個指針域，一個指向直接后繼，一個指向直接前驅。本程序包括了的功能有：查找、插入、刪除。　　在單循環(huán)鏈表中，雖然從任一單元出發(fā)，可以找到其前驅單元，但需要O(n)時間。如果我們希望能快速確定表中任一個元素

14、的前驅和后繼元素所在的單元，可以在鏈表的每個單元中設置兩個指針，一個指向后繼，另一個指向前驅，形成如圖2.1所示的雙向鏈表或簡稱為雙鏈表。　　圖2.1雙鏈表示意圖　　由于在雙鏈表中可以直接確定一個單元的前驅單元和后繼單元，我們可以用一種更自然的方式表示元素的位置，即用指向雙鏈表中第i個單元而不是指向其前一個單元的指針來表示表的第i個位置。</p&g

15、t;　　雙鏈表的單元類型定義如下： 　　2.2輸入輸出　　由于本程序為演示程序，需用戶控制程序操作。輸出方面主要是顯示：經指針移動所變化后得到的另一組新的元素。輸入方面：運用雙向循環(huán)鏈表，這樣子較優(yōu)與普通的雙向鏈表，省去一個表尾的指針，使查詢代碼更加清晰，程序也更加簡介。.

16、　　3.程序流程圖　　3.1創(chuàng)建雙向鏈表　　如圖3.1所示建立一個雙鏈表最后以0判斷是否結束接收數據。　　是　　否&l

17、t;/b>　　圖3.1 創(chuàng)建雙鏈表流程圖　　3.2按位次查找　　如圖2.2所示查找元素，判斷位置是否合法，若合法進行查找運算。　　否<b&g

18、t;　　是　　圖3.2 雙鏈表查找運算流程圖　　3.3插入新的元素　　如圖2.3所示查找元素，判斷位置是否合法，若合法進行查插入運算。　　否否<p

19、>　　是　　圖3.3 雙鏈表插入運算流程圖　　3.4刪除一個元素　　如圖3.4所示刪除元素，判斷位置是否合法，若合法進行查刪除運算。　　否 </p

20、>　　是　　圖3.4 雙鏈表刪除運算流程圖　　4．概要設計　　4.1 程序模塊　　本程序實現(xiàn)雙鏈表的創(chuàng)建、查找、插入、刪除、顯示、

21、菜單為主的六個函數組成。大致分為：雙鏈表創(chuàng)建演示主程序，雙鏈表創(chuàng)建指針變化演示，結果輸出，三大模塊。　　4.2 課題涉及的數據結構　　本課題所用到的數據結構主要是雙向鏈表　　4.2.1 雙鏈表結點的插入 　　Status ListInsert_DuL(DuLinkList

22、 &;L, int i, ElemType e)　　{　　if(!(s=(DuLinklist)malloc(sizeof(DuLNode))))　　return ERROR;　　s->data=e;

23、　　s->prior=p->prior;　　p->piror-next=s;　　s->next=p;　　p->prior=s;　　return OK;　　} &

24、lt;/b>　　4.2.2 雙鏈表結點的刪除 　　Status ListDelete_DuL(DuLinkList&;L,int i,ElemType &;e)　　{ 　　e=p->data; </p

25、>　　p->prior->next=p->next;　　p->next->prior=p->prior;　　free(p); 　　return OK;

26、　}　　5. 調試分析以及設計體會　　程序調試中遇到的問題以及解決問題的方法。主要是在結點插入判斷方面有難度，一開始不能準確的進行結點的判斷和插入，然后就是插入結點的過程中位置不對，后面在網上找到了一段演示代碼，通過研究這段代碼解決了這個問題。還有就是在顯示指針變化方面有問題，經過查詢資料，解決結點插入方面的問題，用畫箭頭的方式來表現(xiàn)

27、指針的變化。在運行程序時發(fā)現(xiàn)程序不能對不合法的位置進行判斷，最后通過修改加上一個計數的變量解決了這個問題。　　6．源程序代碼　　#include<stdio.h>　　#include<malloc.h>　　#i

28、nclude<stdlib.h>　　#define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量　　#define LISTINCREMENT 10 //線性表存儲空間的增配量</p&g

29、t;　　#define OK 1　　#define ERROR 0　　#define OVERFLOW -2　　typedef struct DuLnode　　{&

30、lt;b>　　int data;　　struct DuLnode *prior, *next;　　int L;　　}DuLinkList;　　DuLinkList *head;&l

31、t;p>　　int PutYuansu_DuL(DuLinkList &L)　　{ DuLinkList *p,*s;　　int x; 　　head=(DuLinkList*)malloc(sizeof(DuLinkList));&

32、lt;p>　　head->data=-1;　　head->next=head;　　head->prior=head;　　p=head;　　L.L=0;

33、　　printf("請輸入元素(0 結束)\n");　　scanf("%d",&x);　　while(x!=0)　　{　　s=(DuLinkList*)malloc(

34、sizeof(DuLinkList));　　s->data=x;　　s->next=p->next;　　s->prior=p;　　p->next->prior=s;　　p->next=s;

35、　　p=s;　　scanf("%d",&x);　　L.L++;　　}　　return

36、OK;　　}　　void Display_Dul(DuLinkList &L)　　{　　DuLinkList * p=head->next;

37、　　while(p!=head)　　{printf("%d ",p->data);　　p=p->next;　　}　　printf("\n");<p&g

38、t;　　}　　int Locate_DuL(DuLinkList &L,int e) //查找　　{ DuLinkList * p=head->next; 　　int i=1;</p

39、>　　if(p==NULL)　　return ERROR;　　while(p->data!=e&& p->next!=head) //尋找值為x的元素 　　{p=p-&g

40、t;next;　　i++;　　}　　if(p->data==e)　　printf("查找出的位次是：%d \n",i);<

41、;b>　　else　　printf("\t沒有這個元素\n");　　return OK;　　}　　int ListInsert_DuL(DuLinkList &L,int i,in

42、t e) //插入 　　{　　int j;　　j=0;　　DuLinkList *p=head->next,*s;&

43、lt;p>　　while((p->next!=head)&&(j<i-1)) 　　{　　p=p->next;　　j++;&l

44、t;b>　　}　　if((i>0)&&(j=i-1))　　{　　s=(DuLinkList*)malloc(sizeof(DuLinkList));　　s->data=e;<

45、/p>　　s->prior=p->prior;　　p->prior->next=s;　　s->next=p;　　p->prior=s;　　}

46、　　Display_Dul(L);　　return OK;　　}　　int ListDelet_DuL(DuLinkList &L,int i) //刪除　　{ int e,j=0;</p&

47、gt;　　DuLinkList *p=head->next;　　while((p->next!=head)&&(j<i-1)) //找到第i個節(jié)點　　{p=p->next;　　j++;&

48、lt;/p>　　} 　　if((i>0)&&(j==i))　　e=p->data;　　p->prior->next=p->next;　　p->next-&

49、gt;prior=p->prior;　　free(p);　　Display_Dul(L);　　return OK;　　}　　int menu_sel

50、ect()　　{ int a;　　do{system("cls"); /*運行前清屏*/　　printf("\t\t****查找、插入、刪除 System***

51、*\n"); /*菜單選擇*/　　printf("\t\t | 1. 輸入元素 \n");　　printf("\t\t | 2. 查找 \n");　　printf("\t\t

52、 | 3. 插入 \n"); 　　printf("\t\t | 4. 刪除 \n");　　printf("\t\t | 5. 顯示數據 \n");

53、　　printf("\t\t | 6. Quit \n");　　printf("\t\t\tGive your Choice(1-6):");　　scanf("%d",&a); 　　}whi

54、le(a<0&&a>6);　　return (a);　　}　　int main(int argc, char* argv[])　　{ &l

55、t;p>　　DuLinkList L;　　for(;;) 　　switch(menu_select())　　{ int e,i; 　　case 1:PutYuansu_DuL(L);<p&

56、gt;　　system("pause");　　break;　　case 2:printf("請輸入查找的元素：");　　scanf("%d",&e);　　Locate

57、_DuL(L,e);　　system("pause");　　break;　　case 3:printf("輸入插入的數的位次");　　scanf("%d",&i);&

58、lt;/p>　　if(i<1||i>L.L) 　　{　　printf("\t輸入不合法\t");　　system("pause");

59、break;　　}　　printf("請輸入插入元素");　　scanf("%d",&e);　　ListInsert_DuL(L,i,e);

60、　　system("pause");　　break;　　case 4:printf("輸入刪除的位次");　　scanf("%d",&i);　　if

61、(i<1||i>L.L) 　　{　　printf("\t輸入不合法\t");　　system("pause");　　break;</p&g

62、t;　　}　　ListDelet_DuL(L,i);　　system("pause");　　break;　　case 5:Display_Dul(L);&

63、lt;/p>　　system("pause");　　case 6:printf("\t\t\tHave a Good Luck,Bye-bye!\n"); 　　printf("\t\t\t");　　system(&qu

64、ot;pause");　　exit(0);　　}　　return 0;　　}<p

65、>　　7.程序運行結果 　　本程序是演示程序，根據提示輸入數據，也可以在等待所有過程結束后再退出。　　7.1創(chuàng)建雙鏈表　　如圖7.1所示用戶進入菜單開始操作程序　　圖7.

66、1 菜單　　7.2 輸入元素　　如圖7.2所示用戶輸入元素最后以0結束　　圖7.2 在雙鏈表中輸入元素　　7.3 查找一個不屬于鏈表的值　　如圖7.3所示用戶輸出一個不

67、合法的位置　　圖7.3 不合法的查找　　7.4 正確的查找　　如圖7.4所示用戶輸入正確的位置并且輸出正確的結果　　圖7.4 查找成功　　7.5不合法的

68、插入一個數 　　如圖7.5所示用戶輸入一個不合法的插入位次　　圖7.5 不合法的插入　　7.6正確的插入一個數 　　如圖7.6所示用戶輸入一個正確的位次并且輸出正確的結果　　圖7.6 插入成功</b&g

69、t;　　7.7刪除不合法的位次　　如圖7.7所示用戶輸入一個不合法的刪除位次　　圖7.7不合法的刪除　　7.8刪除位次　　如圖7.8所示用戶輸入正確的刪除位次并且刪除所選元素</p&

70、gt;　　圖7.8 刪除成功　　總結　　在進行本次課程設計的實驗操作中，由于自己的基礎知識不是很好，出現(xiàn)了一些問題：在編程方面不熟，所以寫出的代碼總是出錯；數據結構課程以前也沒有好好學過，造成在構建程序數據結構時出現(xiàn)由于概念模糊而寫錯功能的問題。但是在老師

71、和同學們的幫助下，再通過查閱資料，最后終于寫出了可以正確運行結果的代碼，所以要感謝給我?guī)椭睦蠋熀屯瑢W。以前用 C 編程，只是注重如何編寫函數能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術，只是憑單純的意識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀，只要能完成任務就行。但現(xiàn)在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素首先選取自己需要的數據結構。然后選定一種或幾種存儲結構來具體的決定后面的函數的主要風格。最

72、后在編寫每一個函數之前，可以仔細斟酌比對，挑選出最適合當前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自己心中已經有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質量，通過這次課程設計，使我意識到作為一個計算機系的學生，正確掌握一門程序語言和數據結構的重要性，想要在程序設計上面做出成績，必須要有扎實的編程序語言基礎和良好的數據結　　在此，我要感謝所有曾經教導過我的老師和關心過我的同學

73、，他們在我成長過程中給予了我很大的幫助。在完成課設時，我們在一起探討過，爭論過，從中我們學到許多在課堂理論中沒有見過的東西，為我們今后的學習帶來了非常大的益處。本文能夠成功的完成，要特別感謝我的指導老師李婧老師的教導。李老師對工作認真負責，耐心輔導，知識豐富。在這次課程設計中給了我很大的幫助。她嚴謹的治學精神和深厚的理論水平都使我獲益非淺。同時還要感謝我的同學，他們?yōu)槲姨岢隽撕芏嘤杏玫慕ㄗh，幫助我完成了這次的課程設計。最后也要感謝我們學

74、校為我們提供良好的編程環(huán)境，使我們能夠按時完成任務。　　參考文獻　　[1] 嚴蔚敏. 數據結構（C語言版）[M]. 北京：清華大學出版社，1997.　　[2] 譚浩強. C程序設計（第三版）[M]. 北京：清華大學出版社，2005.

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

溫馨提示

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

課程設計---雙鏈表的建立插入查找刪除算法的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

課程設計---雙鏈表的建立插入查找刪除算法的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

免費下載