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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)說(shuō)明書</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　2011—2012學(xué)年第二學(xué)期</p><p>　　課程設(shè)計(jì)名稱：

2、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　設(shè) 計(jì) 題 目： 雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn) </p><p>　　完 成 期 限：自 2012 年 2 月 20 日至 2012 年

3、3 月 2 日共 2 周 </p><p>　　設(shè)計(jì)要求、設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁(yè)）：</p><p>　　設(shè)計(jì)內(nèi)容：雙鏈表的建立插入查找刪除算法的實(shí)現(xiàn)，雙鏈表具有雙向鏈接的特點(diǎn)，克服了單鏈表的單向性。要求通過(guò)結(jié)構(gòu)體類型建立空的雙鏈表，在此基礎(chǔ)上調(diào)用函數(shù)實(shí)現(xiàn)雙鏈表的建立、插入、查找和刪除等基本操作。</p><p>　　設(shè)計(jì)要求：1.遵

4、循結(jié)構(gòu)化程序設(shè)計(jì)思想，采用C/C++實(shí)現(xiàn)。</p><p>　　2.界面友好，操作簡(jiǎn)便，容錯(cuò)性好。 </p><p>　　指導(dǎo)教師（簽字）： 教研室主任（簽字）： </p><p>　　批準(zhǔn)日期： 年 月 日</p><p><b>　　摘要<

5、;/b></p><p>　　本課題主要討論在鏈?zhǔn)浇Y(jié)構(gòu)中建立雙向鏈表。雙向鏈表有兩個(gè)指針域，其一指向直接前趨，另一指向直接后繼。并合理利用插入、查找、刪除運(yùn)算。和單鏈的循環(huán)表類似，雙鏈表也可以有相應(yīng)的循環(huán)表。用一個(gè)表頭單元將雙鏈表首尾相接，即將表頭單元中的head指針指向表尾，并將表尾單元的next指針指向表頭單元。</p><p>　　關(guān)鍵詞：雙向鏈表；鏈?zhǔn)浇Y(jié)構(gòu)；直接前趨；直接后繼

6、</p><p><b>　　‘</b></p><p><b>　　目 錄</b></p><p><b>　　1.課題描述1</b></p><p><b>　　2．需求分析2</b></p><p>　　2.1程序功能說(shuō)明

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

8、;p>　　3.4刪除一個(gè)元素6</p><p><b>　　4．概要設(shè)計(jì)7</b></p><p>　　4.1 程序模塊7</p><p>　　4.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)7</p><p>　　4.2.1 雙鏈表結(jié)點(diǎn)的插入7</p><p>　　4.2.2 雙鏈表結(jié)點(diǎn)的刪除7&l

9、t;/p><p>　　5. 調(diào)試分析以及設(shè)計(jì)體會(huì)8</p><p><b>　　6．源程序代碼9</b></p><p>　　7.程序運(yùn)行結(jié)果14</p><p>　　7.1創(chuàng)建雙鏈表14</p><p>　　7.2 輸入元素15</p><p>　　7.3 查找一個(gè)

10、不屬于鏈表的值16</p><p>　　7.4 正確的查找17</p><p>　　7.5不合法的插入一個(gè)數(shù)18</p><p>　　7.6正確的插入一個(gè)數(shù)19</p><p>　　7.7刪除不合法的位次20</p><p>　　7.8刪除位次21</p><p><b>

11、　　總結(jié)22</b></p><p><b>　　參考文獻(xiàn)23</b></p><p><b>　　1.課題描述</b></p><p>　　雙（向）鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接前趨的指針域prior。雙鏈表有以下特點(diǎn)：</p>&

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

13、p><p>　　鏈表是線性表的鏈?zhǔn)奖硎荆捎谒灰筮壿嬌舷噜彽脑卦谖锢砦恢蒙弦蚕噜?，所以它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)在做插入刪除操作時(shí)需要移動(dòng)大量元素的弱點(diǎn)。 雙鏈表的結(jié)點(diǎn)中有兩個(gè)指針域， 一個(gè)指向直接后繼， 一個(gè)指向直接前驅(qū)。本程序包括了的功能有：查找、插入、刪除。</p><p>　　在單循環(huán)鏈表中，雖然從任一單元出發(fā)，可以找到其前驅(qū)單元，但需要O(n)時(shí)間。如果我們希望能快速確定表中任一個(gè)元素

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

15、t;<p>　　雙鏈表的單元類型定義如下： </p><p><b>　　2.2輸入輸出</b></p><p>　　由于本程序?yàn)檠菔境绦颍栌脩艨刂瞥绦虿僮?。輸出方面主要是顯示：經(jīng)指針移動(dòng)所變化后得到的另一組新的元素。輸入方面：運(yùn)用雙向循環(huán)鏈表，這樣子較優(yōu)與普通的雙向鏈表，省去一個(gè)表尾的指針，使查詢代碼更加清晰，程序也更加簡(jiǎn)介。.</p>

16、<p><b>　　3.程序流程圖</b></p><p><b>　　3.1創(chuàng)建雙向鏈表</b></p><p>　　如圖3.1所示 建立一個(gè)雙鏈表最后以0判斷是否結(jié)束接收數(shù)據(jù)。</p><p><b>　　是</b></p><p><b>　　否&l

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

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

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

20、><p><b>　　是</b></p><p>　　圖3.4 雙鏈表刪除運(yùn)算流程圖</p><p><b>　　4．概要設(shè)計(jì)</b></p><p><b>　　4.1 程序模塊</b></p><p>　　本程序?qū)崿F(xiàn)雙鏈表的創(chuàng)建、查找、插入、刪除、顯示、

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

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

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

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

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

26、　}</b></p><p>　　5. 調(diào)試分析以及設(shè)計(jì)體會(huì)</p><p>　　程序調(diào)試中遇到的問(wèn)題以及解決問(wèn)題的方法。主要是在結(jié)點(diǎn)插入判斷方面有難度，一開始不能準(zhǔn)確的進(jìn)行結(jié)點(diǎn)的判斷和插入，然后就是插入結(jié)點(diǎn)的過(guò)程中位置不對(duì)，后面在網(wǎng)上找到了一段演示代碼，通過(guò)研究這段代碼解決了這個(gè)問(wèn)題。還有就是在顯示指針變化方面有問(wèn)題，經(jīng)過(guò)查詢資料，解決結(jié)點(diǎn)插入方面的問(wèn)題，用畫箭頭的方式來(lái)表現(xiàn)

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

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

29、t;<p>　　#define OK 1</p><p>　　#define ERROR 0</p><p>　　#define OVERFLOW -2</p><p>　　typedef struct DuLnode</p><p><b>　　{</b></p><p>&

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

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

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

33、<p>　　printf("請(qǐng)輸入元素(0 結(jié)束)\n");</p><p>　　scanf("%d",&x);</p><p>　　while(x!=0)</p><p><b>　　{</b></p><p>　　s=(DuLinkList*)malloc(

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、 | 3. 插入 \n"); </p><p>　　printf("\t\t | 4. 刪除 \n");</p><p>　　printf("\t\t | 5. 顯示數(shù)據(jù) \n");</p><p>

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

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

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

56、gt;　　system("pause");</p><p><b>　　break;</b></p><p>　　case 2:printf("請(qǐng)輸入查找的元素：");</p><p>　　scanf("%d",&e);</p><p>　　Locate

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

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

59、break;</b></p><p><b>　　}</b></p><p>　　printf("請(qǐng)輸入插入元素");</p><p>　　scanf("%d",&e);</p><p>　　ListInsert_DuL(L,i,e); </p>

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

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

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

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

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

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

66、1 菜單</b></p><p><b>　　7.2 輸入元素</b></p><p>　　如圖7.2所示 用戶輸入元素最后以0結(jié)束</p><p>　　圖7.2 在雙鏈表中輸入元素</p><p>　　7.3 查找一個(gè)不屬于鏈表的值</p><p>　　如圖7.3所示 用戶輸出一個(gè)不

67、合法的位置</p><p>　　圖7.3 不合法的查找</p><p><b>　　7.4 正確的查找</b></p><p>　　如圖7.4所示 用戶輸入正確的位置并且輸出正確的結(jié)果</p><p><b>　　圖7.4 查找成功</b></p><p>　　7.5不合法的

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

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

70、gt;<p><b>　　圖7.8 刪除成功</b></p><p><b>　　總結(jié)</b></p><p>　　在進(jìn)行本次課程設(shè)計(jì)的實(shí)驗(yàn)操作中，由于自己的基礎(chǔ)知識(shí)不是很好，出現(xiàn)了一些問(wèn)題：在編程方面不熟，所以寫出的代碼總是出錯(cuò)；數(shù)據(jù)結(jié)構(gòu)課程以前也沒(méi)有好好學(xué)過(guò)，造成在構(gòu)建程序數(shù)據(jù)結(jié)構(gòu)時(shí)出現(xiàn)由于概念模糊而寫錯(cuò)功能的問(wèn)題。 但是在老師

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

72、后在編寫每一個(gè)函數(shù)之前，可以仔細(xì)斟酌比對(duì)，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的程序還沒(méi)有寫出來(lái)之前，自己心中已經(jīng)有了明確的原圖了。這樣無(wú)形中就提高了自己編寫的程序的質(zhì)量，通過(guò)這次課程設(shè)計(jì)，使我意識(shí)到作為一個(gè)計(jì)算機(jī)系的學(xué)生，正確掌握一門程序語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)的重要性，想要在程序設(shè)計(jì)上面做出成績(jī)，必須要有扎實(shí)的編程序語(yǔ)言基礎(chǔ)和良好的數(shù)據(jù)結(jié)</p><p>　　在此，我要感謝所有曾經(jīng)教導(dǎo)過(guò)我的老師和關(guān)心過(guò)我的同學(xué)

73、，他們?cè)谖页砷L(zhǎng)過(guò)程中給予了我很大的幫助。在完成課設(shè)時(shí)，我們?cè)谝黄鹛接戇^(guò)，爭(zhēng)論過(guò)，從中我們學(xué)到許多在課堂理論中沒(méi)有見過(guò)的東西，為我們今后的學(xué)習(xí)帶來(lái)了非常大的益處。本文能夠成功的完成，要特別感謝我的指導(dǎo)老師李婧老師的教導(dǎo)。李老師對(duì)工作認(rèn)真負(fù)責(zé)，耐心輔導(dǎo)，知識(shí)豐富。在這次課程設(shè)計(jì)中給了我很大的幫助。她嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我獲益非淺。同時(shí)還要感謝我的同學(xué)，他們?yōu)槲姨岢隽撕芏嘤杏玫慕ㄗh，幫助我完成了這次的課程設(shè)計(jì)。最后也要感謝我們學(xué)

74、校為我們提供良好的編程環(huán)境，使我們能夠按時(shí)完成任務(wù)。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社，1997.</p><p>　　[2] 譚浩強(qiáng). C程序設(shè)計(jì)（第三版）[M]. 北京：清華大學(xué)出版社，2005. </p><p>