數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-鏈表操作

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-鏈表操作_第1頁

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　目錄　　1 選題背景1　　2 方案與論證1　　2.1 鏈表的概念和作用1　　2.2 實驗的基本要求（軟硬件）1

2、;　　2.3 算法的設(shè)計思想1　　2.4 相關(guān)圖例2　　2.4.1 單鏈表的結(jié)點結(jié)構(gòu)2　　2.4.2 算法流程圖2　　3 過程論述3　　3.1 鏈表的建立3

3、　　3.2 取出鏈表中的元素4　　3.3 插入元素4　　3.4 刪除元素5　　3.5 查找元素6　　4 結(jié)果分析6　　4.1 單鏈表的結(jié)構(gòu)

4、6　　4.2 單鏈表6　　4.2.1 順鏈操作技術(shù)6　　4.2.2 指針保留技術(shù)7　　5 結(jié)論與總結(jié)7　　參考文獻8</

5、b>　　附錄代碼：9　　1 選題背景　　陳火旺院士把計算機60多年的發(fā)展成就概括為五個“一”：開辟一個新時代----信息時代，形成一個新產(chǎn)業(yè)----信息產(chǎn)業(yè)，產(chǎn)生一個新科學----計算機科學與技術(shù)，開創(chuàng)一種新的科研方法----計算

6、方法，開辟一種新文化----計算機文化，這一概括深刻影響了計算機對社會發(fā)展所產(chǎn)生的廣泛而深遠的影響。　　數(shù)據(jù)結(jié)構(gòu)和算法是計算機求解問題過程的兩大基石。著名的計算機科學家P.Wegner指出，“在工業(yè)革命中其核心作用的是能量，而在計算機革命中其核心作用的是信息”。計算機科學就是“一種關(guān)于信息結(jié)構(gòu)轉(zhuǎn)換的科學”。信息結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）是計算機科學研究的基本課題，數(shù)據(jù)結(jié)構(gòu)又是算法研究的基礎(chǔ)。</p&

7、gt;　　2 方案與論證　　2.1 鏈表的概念和作用 　　鏈表是一種鏈式存儲結(jié)構(gòu)，鏈表屬于線性表，采用鏈式存儲結(jié)構(gòu)，也是常用的動態(tài)存儲方法。為了克服順序表的缺陷，可以采用鏈式方式存儲線性表。通常將采用鏈式存儲結(jié)構(gòu)的線性表稱為線性鏈表。單鏈表的結(jié)構(gòu)包括數(shù)據(jù)域和指針域，這兩部分總稱為結(jié)點（Node）

8、。單鏈表中每個結(jié)點的存儲地址放在其前驅(qū)結(jié)點的指針域中，由于線性表中的第一個結(jié)點無前驅(qū)，所以應(yīng)設(shè)一個頭指針H指向第一個結(jié)點。由于線性表的最后一個節(jié)點沒有直接后繼，則制定單鏈表的最后一個結(jié)點的指針域為空（NULL）。它可以和隨意的在其任意一個位置進行插入和刪除操作，這對于動態(tài)的數(shù)據(jù)處理十分的有利。利用頭插建立一個帶頭結(jié)點的單鏈表，并用算法實現(xiàn)該單鏈表的插入、刪除查找、輸出、求前驅(qū)和后繼、再把此單鏈表逆置，然后在屏幕上顯示每次操作的結(jié)果當所有

9、操作完成后能撤銷該單鏈表。　　2.2 實驗的基本要求（軟硬件）　　用VC++6.0軟件平臺，操作系統(tǒng)：Windows XP 硬件：內(nèi)存要求：內(nèi)存大小在256MB，其他配置一般就行。 　　2.3 算法的設(shè)計思想　?。?）定義一個創(chuàng)建鏈表的函數(shù)，通過該函數(shù)可以創(chuàng)建一個鏈

10、表，并為下面的函數(shù)應(yīng)用做好準備。　?。?）定義輸出鏈表的算法，通過對第一步已經(jīng)定義好的創(chuàng)建鏈表函數(shù)的調(diào)用，在這一步通過調(diào)用輸出鏈表的函數(shù)算法來實現(xiàn)對鏈表的輸出操作。　?。?）定義一個遍歷查找的算法，通過此算法可以查找到鏈表中的每一個節(jié)點是否存在。　?。?）定義查找鏈表的每一個前驅(qū)和后繼，通過定義這個算法，可以很容

11、易的實現(xiàn)對鏈表的前驅(qū)和后繼的查找工作。 　?。?）定義插入節(jié)點的算法，通過定義這個算法，并結(jié)合這查找前驅(qū)和后繼的算法便可以在連鏈表的任意位置進行插入一個新節(jié)點。　　（6）定義刪除節(jié)點的操作，這個算法用于對鏈表中某個多余節(jié)點的刪除工作。　　2.4 相關(guān)圖例

12、　　2.4.1 單鏈表的結(jié)點結(jié)構(gòu)　　如圖2-1所示,為單鏈表的結(jié)點結(jié)構(gòu)示意圖：　　圖2-1 單鏈表的結(jié)點結(jié)構(gòu)　　2.4.2 算法流程圖　　如圖2-2所示，為此算法流程圖：　　圖2-2 算法流程圖</p&g

13、t;　　3 過程論述　　3.1 鏈表的建立　　圖 3-1 鏈表的建立　　圖 3-2 建立鏈表并打印鏈表中的元素　　3.2 取出鏈表中的元素<p&

14、gt;　　圖3-3 取出鏈表中的元素　　3.3 插入元素　　圖3-4 插入元素　　3.4 刪除元素　　圖3-5 刪除元素

15、　　圖3-6 刪除元素后打印鏈表　　3.5 查找元素　　圖3-7 查找位置為6的元素　　4 結(jié)果分析　　4.1 單鏈表的結(jié)構(gòu)<

16、;p>　　一般情況下，使用鏈表，只關(guān)心鏈表中結(jié)點間的邏輯順序，并不關(guān)心每個結(jié)點的實際存儲位置，因此通常情況下用箭頭來表示鏈域中的指針，于是鏈表就可以更直觀的畫成用箭頭鏈接起來的結(jié)點序列，如下圖所示：　　H　　圖4-1 單鏈表的示例圖　　4.2 單鏈表&

17、lt;/b>　　4.2.1 順鏈操作技術(shù)　　從“頭”開始，訪問單鏈表L中的結(jié)點i（p指向該節(jié)點）時，由于第i個結(jié)點的地址在第i-1個結(jié)點（pre指向該結(jié)點，為p的前驅(qū)）的指針域中存放，查找必須從單鏈表的“首結(jié)點”開始（p=L）；通過p=p->next并輔助計數(shù)器來實現(xiàn)。　　4.2.2 指針保留技術(shù)&l

18、t;/p>　　通過對第i個結(jié)點進行插入、刪除等操作時，需要對第i-1個結(jié)點的指針域進行鏈址操作（pre->next），因此在處理過程中始終需要維持當前指針p與其前驅(qū)指針pre的關(guān)系，將這種技術(shù)稱為“指針保留技術(shù)”。　　5 結(jié)論與總結(jié)　　通過這十幾天的時間，最后終于完成了這次數(shù)據(jù)結(jié)構(gòu)課

19、程設(shè)計任務(wù)，內(nèi)心激動的同時，也是十分的辛苦的，從選題、審題、查資料到開始構(gòu)思，這個過程是最慢的，也是最難的。通過這次的課程設(shè)計，我們對數(shù)據(jù)結(jié)構(gòu)中單鏈表的應(yīng)用有了更深的理解，并且使我們深刻的認識到實踐的重要性，只有理論與實踐相結(jié)合才能達到很好的學習效果，學到很多東西，同時也發(fā)現(xiàn)僅僅書本的知識是遠遠不夠的，需要把知識運用到實踐中去，能力才能得到提高。由于剛開始對單鏈表的應(yīng)用總體結(jié)構(gòu)不熟悉，對書本知識的學習不夠扎實，剛拿到題目的時候，還不好下

20、手，就請教了一些學習成績好一點的同學，并認真查找了一些資料，才對這次課程設(shè)計有了初步的了解。　　根據(jù)對數(shù)據(jù)結(jié)構(gòu)的了解，我們覺得我們對單鏈表的認識要深一點。因此我們選擇了單鏈表的實驗，作為線性表的一種存儲結(jié)構(gòu)，它的特點是可以從分利用存儲單元來存儲數(shù)據(jù)，并且可以方便的實現(xiàn)對數(shù)據(jù)進行插入、刪除、輸出等操作。在我們進行課程設(shè)計時，雖然在大體上算法是正確的，但時常會出現(xiàn)一些小問題，使我們不得不花一些時間來

21、查找、修改錯誤。　　通過這次課程設(shè)計，讓我們充分認識到數(shù)據(jù)結(jié)構(gòu)在編寫程序方面的重要地位。由于我們在課程設(shè)計中編寫的是對單鏈表的基本操作，因此我們在這次課程設(shè)計中收獲了很多關(guān)于單鏈表的應(yīng)用方面的知識。由于課程設(shè)計的題目還有很多，因此沒有對其他的題目進行深入的了解而感到遺憾，因此我們希望在以后的學習過程中，能夠多多的學習這方面沒知識來彌補不足。　　最后，通過

22、本次數(shù)據(jù)結(jié)構(gòu)課設(shè)，我學會了如何與別人共同探討、解決問題；當發(fā)現(xiàn)問題時，能學會利用身邊一切資料，包括圖書、網(wǎng)上資料等等來解決問題，并最終完成任務(wù)。　　參考文獻　　[1]耿國華.數(shù)據(jù)結(jié)構(gòu)--用C語言描述[M].北京:高等教育出版社,2011.6.　　[2]譚浩強.C程序設(shè)計[M]

23、.北京:清華大學出版社,2004.6.　　附錄代碼：　　#include <stdio.h>　　#include<stdlib.h>　　typedef struct node//定義node結(jié)點</p&g

24、t;　　{ 　　int data;　　struct node *next;　　}linklist;　　void setnull(linklist *H)//清空單鏈表<

25、/p>　　{　　H->next=NULL;　　}　　void creatlist(linklist *H)//創(chuàng)建單鏈表　　{

26、;　　linklist *p,*s;int x;　　p=H;　　printf("please input x:");　　scanf("%d",&x);<p&

27、gt;　　while(x!=-1){　　s=(linklist *)malloc(sizeof(linklist));　　s->data=x;　　s->next =p->next;　　p->next =s;

28、　　p=p->next ;　　printf("please input x:");　　scanf("%d",&x);　　}　　p->next=NULL ;

29、　　}　　void Leng(linklist *H)//求單鏈表長度　　{ 　　linklist *p;　　int k;</p&

30、gt;　　p=H;k=0;　　while(p->next!=NULL){　　p=p->next;　　k++;　　}</

31、p>　　printf("The linklist is:%d\n",k);　　}　　int GetElem(linklist *H,int i)//取單鏈表中的某個元素　　{</p&g

32、t;　　linklist *p;　　int k;　　p=H;k=0;　　while(p->next!=NULL&&k<i){　　p=p->n

33、ext;　　k++;　　}　　if(k==i&&p!=NULL)　　printf("i position data is %d\n",p->data);&

34、lt;/p>　　else　　printf("No find!\n");　　}　　void Insert(linklist *H,int i,int x)//向單鏈表中插入某個元素</p

35、>　　{　　linklist *p;int k;linklist *s;　　p=H;k=0;　　while(p->next!=NULL&&k<i-1){<

36、;p>　　p=p->next;k++;　　}　　if(k==i-1&&p->next!=NULL){　　s=(linklist *)malloc(sizeof(linklist));　　s->d

37、ata=x;　　s->next=p->next;　　p->next=s;　　}　　else　　printf("插入錯誤r\n&

38、quot;);　　}　　void Delete(linklist *H,int x)//刪除元素　　{　　linklist *p,*q;int k;<

39、;b>　　p=H;k=0;　　while(p->next!=NULL&&p->next->data!=x){　　p=p->next;　　k++;　　}

40、　　if(p->next->data==x) { 　　q=p->next;　　p->next=q->next;　　free(q);<b&

41、gt;　　}　　else printf("no find!\n");　　}　　void print(linklist *H)//輸出單鏈表　　{</p

42、>　　linklist *p;int k;　　p=H;k=0;　　if(p->next==NULL)　　printf("鏈表為空!");　　while(p->next!=NU

43、LL){　　k++;　　p=p->next;　　printf("%3d",p->data);　　}　　}

44、　　int Locate(linklist *H,int x)//查找元素　　{　　linklist *p;int k;　　p=H;k=0;<p&

45、gt;　　while(p->next!=NULL&&p->data!=x){ 　　p=p->next;　　k++;　　}　　if(p->data==x)&l

46、t;/p>　　printf("要查詢元素的位置是%d\n",k);　　else　　printf("沒有找到!\n");　　}&l

47、t;b>　　/*　　void destroylist(linklist *H)//銷毀單鏈表　　{ 　　H->next=NULL;　　H->data=NULL;<

48、p>　　}　　*/　　void main()　　{ 　　linklist *H;int k,x,i;int f;

49、;　　H=(linklist *)malloc(sizeof(linklist));　　setnull(H);　　printf("\n請選擇以下操作數(shù)，選擇-1為結(jié)束");　　printf("\n1:creatlinklist(H)");<p&

50、gt;　　printf("\n2:leng(H)");　　printf("\n3:GetElem(H,i)");　　printf("\n4:Insert(H,i,x)");　　printf("\n5:Delete(H,x)");<

51、;/p>　　printf("\n6:print(H)");　　printf("\n7:Locate(H,x)\n");　　scanf("%d",&f);　　while(f!=-1){ <

52、p>　　switch (f)　　{ 　　case 1:creatlist(H);break;　　case 2:Leng(H);break;　　case 3:printf("\n請輸入要得到元素的位置:");&

53、lt;/p>　　scanf("%d",&i);　　GetElem(H,i);break;　　case 4:printf("\n請輸入的插入位置、長度以及元素:");　　scanf("%d,%d",&i,&

54、;x);　　Insert(H,i,x);break;　　case 5:printf("\n請輸入要刪除的位置及元素:");　　scanf("%d",&x);　　Delete(H,x);break;&l

55、t;p>　　case 6: print(H);break;　　case 7:printf("請輸入要查找的元素:");　　scanf("%d",&x);　　Locate(H,x);break;　　}&

56、lt;/b>　　printf("\n請選擇以下操作數(shù)，選擇-1為結(jié)束");　　printf("\n1:creatlinklist(H)");　　printf("\n2:leng(H)");　　printf(

57、"\n3:GetElem(H,i)");　　printf("\n4:Insert(H,i,x)");　　printf("\n5:Delete(H,x)");　　printf("\n6:print(H)");&l

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-鏈表操作

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-鏈表操作

文檔簡介

溫馨提示

最新文檔

評論

免費下載