狼追兔子數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、<p><b>　　游戲算法實(shí)踐報(bào)告</b></p><p><b>　　目錄</b></p><p>　　1 問(wèn)題定義與描述3</p><p>　　1.1 問(wèn)題定義3</p><p>　　1.2 問(wèn)題描述3</p><p><b>　　2 關(guān)鍵技術(shù)

2、3</b></p><p><b>　　3 數(shù)據(jù)的組織3</b></p><p>　　3.1數(shù)據(jù)類型定義3</p><p>　　3.2數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)4</p><p><b>　　4 總體設(shè)計(jì)4</b></p><p>　　4.1 系統(tǒng)模塊圖4</

3、p><p>　　4.2棧的基本操作4</p><p>　　4.3順序表的基本操作4</p><p><b>　　5 詳細(xì)設(shè)計(jì)5</b></p><p>　　5.1順序存儲(chǔ)的線性表5</p><p>　　6 測(cè)試結(jié)果及分析7</p><p><b>　　7 心

4、得體會(huì)8</b></p><p><b>　　附錄：程序代碼9</b></p><p><b>　　1問(wèn)題定義與描述</b></p><p><b>　　1.1 問(wèn)題定義</b></p><p>　　現(xiàn)實(shí)中很多利用順序表，棧解決一些數(shù)學(xué)模型問(wèn)題</p>

5、;<p><b>　　1.2 問(wèn)題描述</b></p><p>　　圍繞著山頂有10個(gè)圓形排列的洞，狐貍要吃兔子，兔子說(shuō)：“可以，但必須找到我，我就藏身于這十個(gè)洞中，你可以先到1號(hào)洞找我，第二次隔一個(gè)洞（即3號(hào)洞）找，第三次隔兩個(gè)洞（即6號(hào)洞）找，以后如此類推，次數(shù)不限?！钡倧脑绲酵磉M(jìn)進(jìn)出出1000次，但仍沒(méi)有找到兔子，問(wèn)兔子究竟藏身于哪個(gè)洞里</p><

6、;p><b>　　2.關(guān)鍵技術(shù)</b></p><p>　　順序表一次申請(qǐng)多個(gè)空間，包括結(jié)構(gòu)體定義的。N為整數(shù)，這樣得到的就是N個(gè)連續(xù)的空間。順序表可以利用類似于數(shù)組的形式訪問(wèn)，即通過(guò)下標(biāo)訪問(wèn)。當(dāng)然定義的變量類型必須是指針類型的，很方便，當(dāng)然也可以通過(guò)像鏈表一樣的訪問(wèn)。單鏈表只是將空間分散開(kāi)了，這樣的優(yōu)點(diǎn)就是動(dòng)態(tài)申請(qǐng)，需要多少就申請(qǐng)多少，一般一次申請(qǐng)一個(gè)空間結(jié)點(diǎn)，即N=1。</p

7、><p><b>　　3 數(shù)據(jù)的組織</b></p><p><b>　　3.1數(shù)據(jù)類型定義</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)，順序表，棧，單鏈表，數(shù)組。在程序設(shè)計(jì)中，為了處理方便， 把具有相同類型的若干變量按有序的形式組織起來(lái)。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。在C語(yǔ)言中， 數(shù)組屬于構(gòu)造數(shù)據(jù)類型。一個(gè)數(shù)組可以分解

8、為多個(gè)數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類型或是構(gòu)造類型。因此按數(shù)組元素的類型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、指針數(shù)組、結(jié)構(gòu)數(shù)組等各種類別。</p><p><b>　　3.2數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)</b></p><p>　　棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。順序存儲(chǔ),大概意思就是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)

9、系來(lái)體現(xiàn)主要用在線性的數(shù)據(jù)結(jié)構(gòu)</p><p><b>　　4總體設(shè)計(jì)</b></p><p>　　4.1 順序表系統(tǒng)模塊圖</p><p>　　圖4.1 順序表系統(tǒng)模塊圖</p><p><b>　　4.2棧的基本操作</b></p><p>　　定義棧的順序存取結(jié)構(gòu)，

10、分別定義棧的基本操作（初始化棧、判棧為空、入棧、出棧等），通過(guò)定義函數(shù)實(shí)現(xiàn)。</p><p>　　4.3順序表的基本操作</p><p>　　在順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)基本操作：初始化、創(chuàng)建、插入、刪除、查找等運(yùn)算。</p><p><b>　　5 詳細(xì)設(shè)計(jì)</b></p><p>　　5.1順序存儲(chǔ)的線性表</p>

11、<p>　　（1）程序中包括哪些函數(shù)？畫(huà)出函數(shù)之間的調(diào)用關(guān)系。</p><p>　　答：程序中包含12個(gè)成員函數(shù)和1個(gè)主函數(shù)。12個(gè)成員函數(shù)。如下，</p><p>　　:SqList,~SqList,CreateList,Insert,Delete,GetElem,Locate,Clear,Eepty,Full,Length,ListDisp</p><

12、p>　?。?）程序中數(shù)據(jù)采用了什么樣的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)？</p><p>　　答：邏輯結(jié)構(gòu)為依次存放線性表中的數(shù)據(jù)；</p><p>　　物理結(jié)構(gòu)為一組地址連續(xù)的儲(chǔ)存單元。</p><p>　　（3）程序中那個(gè)函數(shù)實(shí)現(xiàn)順序表的創(chuàng)建？其中包括順序表的初始化嗎？</p><p>　　答：函數(shù)SqList用于實(shí)現(xiàn)順序表的創(chuàng)建，不包括表的初始

13、化。</p><p>　　（4）程序中哪個(gè)函數(shù)實(shí)現(xiàn)結(jié)點(diǎn)的插入？畫(huà)出流程圖。</p><p>　　答： 函數(shù)Insert實(shí)現(xiàn)結(jié)點(diǎn)的插入。</p><p>　　圖5.1實(shí)現(xiàn)結(jié)點(diǎn)插入</p><p>　?。?）程序中哪個(gè)函數(shù)實(shí)現(xiàn)結(jié)點(diǎn)的刪除？畫(huà)出流程圖。</p><p>　　答：函數(shù)Delete實(shí)現(xiàn)了結(jié)點(diǎn)的刪除。</p&

14、gt;<p>　　圖5.2實(shí)現(xiàn)結(jié)點(diǎn)刪除</p><p>　　（6）程序中提供了幾種元素查找方法？分別在哪個(gè)函數(shù)中實(shí)現(xiàn)？</p><p>　　答：一種是按位置查找，在GetElem中實(shí)現(xiàn)；另一種是按元素查找在Locate 中實(shí)現(xiàn)。</p><p>　　（7）程序退出時(shí)，調(diào)用了哪個(gè)函數(shù)？該函數(shù)主要操作有哪些？</p><p>　　答

15、：調(diào)用~SqList函數(shù)，該函數(shù)主要操作是：刪除順序表元素，使表長(zhǎng)和表容量為0.</p><p>　　6 測(cè)試結(jié)果及分析</p><p>　　運(yùn)行程序，程序主界面如圖6.1所示。</p><p>　　圖6.1 程序的主界面</p><p><b>　　運(yùn)行結(jié)果如圖6.2</b></p><p>

16、　　圖6.2 程序的運(yùn)行結(jié)果</p><p><b>　　7心得體會(huì)</b></p><p>　　本次課程設(shè)計(jì)，使我對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程有了更深入的理解。《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性較強(qiáng)的課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。</p><p>　　我的課程設(shè)計(jì)題目關(guān)于順序表和棧。剛開(kāi)始做這個(gè)程序的時(shí)候，感到完全無(wú)從下手，

17、甚至讓我覺(jué)得完成這次程序設(shè)計(jì)根本就是不可能的，于是開(kāi)始查 閱各種資料以及參考文獻(xiàn)，之后便開(kāi)始著手寫(xiě)程序，寫(xiě)完運(yùn)行時(shí)有很多問(wèn)題。特別是實(shí)現(xiàn)線索二叉樹(shù)的刪除運(yùn)算時(shí)很多情況沒(méi)有考慮周全，經(jīng)常運(yùn)行出現(xiàn)錯(cuò)誤，但通 過(guò)同學(xué)間的幫助最終基本解決問(wèn)題。</p><p>　　在本課程設(shè)計(jì)中，我明白了理論與實(shí)際應(yīng)用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫(xiě)大型程序的能力。培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能以及合 作能力。這次課程設(shè)計(jì)同

18、樣提高了我的綜合運(yùn)用所學(xué)知識(shí)的能力。并對(duì)C有了更深入的了解。《數(shù)據(jù)結(jié)構(gòu)》是一門實(shí)踐性很強(qiáng)的課程，上機(jī)實(shí)習(xí)是對(duì)學(xué)生全面綜合 素質(zhì)進(jìn)行訓(xùn)練的一種最基本的方法，是與課堂聽(tīng)講、自學(xué)和練習(xí)相輔相成的、必不可少的一個(gè)教學(xué)環(huán)節(jié)。上機(jī)實(shí)習(xí)一方面能使書(shū)本上的知識(shí)變“活”，起到深化理解 和靈活掌握教學(xué)內(nèi)容的目的;另一方面，上機(jī)實(shí)習(xí)是對(duì)學(xué)生軟件設(shè)計(jì)的綜合能力的訓(xùn)練，包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧的訓(xùn)練。此外，還 有更重要的一點(diǎn)是：機(jī)器是比

19、任何更嚴(yán)厲的檢查者。因此，在“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)過(guò)程中，必須嚴(yán)格按照老師的要求，主動(dòng)地、積極地、認(rèn)真地做好每一個(gè)實(shí)驗(yàn)，以不斷提高自己的編程能力與專業(yè)素質(zhì)。</p><p>　　通過(guò)這段時(shí)間的課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時(shí)間上機(jī)練習(xí)。這次的程序訓(xùn)練培養(yǎng)了我實(shí)際分析問(wèn)題、編程和動(dòng)手能力，使我掌握了程序設(shè)計(jì)的基本技能，提高了我適應(yīng)實(shí)際，實(shí)踐編程的能力。</p><p>　

20、　總的來(lái)說(shuō)，這次課程設(shè)計(jì)讓我獲益匪淺，對(duì)數(shù)據(jù)結(jié)構(gòu)也有了進(jìn)一步的理解和認(rèn)識(shí)。</p><p><b>　　附錄：程序代碼</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include <windo

21、ws.h></p><p>　　#define StackSize 100</p><p>　　typedef int DataType;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　DataType stack[StackS

22、ize];</p><p><b>　　int top;</b></p><p>　　}SeqStack;</p><p>　　#define MAXSIZE 1100</p><p>　　typedef struct </p><p><b>　　{</b></p&g

23、t;<p>　　DataType list[MAXSIZE];</p><p><b>　　int last;</b></p><p><b>　　}SeqList;</b></p><p>　　void InitList(SeqList *L)</p><p>　　/*順序表的初始化

24、*/</p><p><b>　　{</b></p><p>　　L->last=-1;</p><p><b>　　}</b></p><p>　　int ListEmpty(SeqList L)</p><p>　　/*判斷順序表是否為空*/</p>

25、<p><b>　　{</b></p><p>　　if(L.last==-1)/*判斷最后一個(gè)元素的序號(hào)是否為-1*/</p><p>　　return 1;/*當(dāng)順序表為空時(shí)返回1；否則返回0*/</p><p><b>　　else </b></p><p>　　return 0;/

26、*否則返回0*/</p><p><b>　　}</b></p><p>　　int ListLength(SeqList L)</p><p>　　/*求線性表的長(zhǎng)度*/</p><p><b>　　{</b></p><p>　　return L.last+1;</

27、p><p><b>　　}</b></p><p>　　int GetElem(SeqList L,int i,DataType *e)</p><p>　　/*按序號(hào)順序查找元素。查找成功將該值返回給e，并返回1表示成功；否則返回-1表示失敗*/</p><p><b>　　{</b></p&g

28、t;<p>　　if(i<1||i>L.last+1)/*在查找第i個(gè)元素之前，先判斷該序號(hào)是否合法*/</p><p>　　return -1;</p><p>　　*e=L.list[i-1];/*將第i個(gè)元素值賦值給e*/</p><p><b>　　return 1;</b></p><p&

29、gt;<b>　　}</b></p><p>　　int LocateElem(SeqList *L,DataType x)</p><p>　　/*按內(nèi)容查找，查找成功，將對(duì)應(yīng)元素的序號(hào)返回；否則返回-1*/</p><p><b>　　{</b></p><p><b>　　int i

30、=0;</b></p><p>　　while(i<=L->last&&L->list[i]!=x)</p><p><b>　　i++;</b></p><p>　　if(i>L->last)</p><p>　　return -1;</p>&l

31、t;p><b>　　else </b></p><p>　　return i+1;</p><p><b>　　}</b></p><p>　　int InsertList(SeqList *L,int i,DataType x)</p><p><b>　　{</b>&

32、lt;/p><p><b>　　int j;</b></p><p>　　if(L->last==MAXSIZE-1)/*表空間已滿，不能插入*/</p><p><b>　　{</b></p><p>　　printf("表滿，不能插入");</p><p

33、>　　return -1;</p><p><b>　　}</b></p><p>　　if(i>L->last+2)/*檢查插入位置是否合法*/</p><p><b>　　{</b></p><p>　　printf("插入位置非法");</p>

34、<p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　for(j=L->last;j>=i-1;j--)</p><p>　　L->list[j+1]=L->list[j];/*結(jié)點(diǎn)移動(dòng)*/</p><p>

35、　　L->list[i-1]=x;/*新元素插入*/</p><p>　　L->last++;/*last仍指向最后一個(gè)元素*/</p><p>　　return 1;/*插入成功，返回*/</p><p><b>　　}</b></p><p>　　int DeleteList(SeqList *L,int

36、 i,DataType *e)</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　if(L->last<0)</p><p><b>　　{</b></p><p>　　printf

37、("順序表已空,不能插入進(jìn)行操作!\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　else if(i<0||i>L->last+1)</p><p><b>　　{<

38、/b></p><p>　　printf("插入位置不合法!\n");</p><p>　　return -1;</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{<

39、/b></p><p>　　*e=L->list[i-1];</p><p>　　for(j=i;j<=L->last;j++)</p><p>　　L->list[j-1]=L->list[j];</p><p>　　L->last--;</p><p><b>　

40、　return 1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void InitStack(SeqStack *S)</p><p><b>　　/*棧的初始化*/</b></p>&

41、lt;p><b>　　{</b></p><p>　　S->top=-1;/*把棧頂指針置為-1*/</p><p><b>　　}</b></p><p>　　int StackEmpty(SeqStack S)</p><p>　　/*判斷棧是否為空*/</p><

42、;p><b>　　{</b></p><p>　　if(S.top==-1)/*判斷棧頂指針top是否為-1*/</p><p>　　return 1;/*當(dāng)棧為空時(shí)，返回1；否則返回0*/</p><p><b>　　else</b></p><p><b>　　return 0;

43、</b></p><p><b>　　}</b></p><p>　　int GetTop(SeqStack S,DataType *e)</p><p><b>　　/*取棧頂元素*/</b></p><p><b>　　{</b></p><

44、p>　　if(S.top<0)/*在取棧頂元素之前，判斷棧是否為空*/</p><p><b>　　{</b></p><p>　　printf("棧已經(jīng)空！\n");</p><p><b>　　return 0;</b></p><p><b>　　}&

45、lt;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　*e=S.stack[S.top];/*再取棧頂元素*/</p><p><b>　　return 1;</b></p><p>

46、;<b>　　}</b></p><p><b>　　}</b></p><p>　　int PushStack(SeqStack *S,DataType x)</p><p>　　/*將元素x進(jìn)棧，元素進(jìn)棧成功返回1，否則返回0*/</p><p><b>　　{</b>&l

47、t;/p><p>　　if(S->top>=StackSize)/*在元素進(jìn)棧前，判斷棧是否已滿*/</p><p><b>　　{</b></p><p>　　printf("棧已滿,不能進(jìn)棧！\n");</p><p><b>　　return 0;</b></

48、p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　S->top++;/*修改棧頂指針*/</p><p>　　S->stack[S->top]=x;

49、/*元素x進(jìn)棧*/</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int PopStack(SeqStack *S,DataType *e)</p>&l

50、t;p>　　/*出棧操作，出棧成功返回1，否則返回0*/</p><p><b>　　{</b></p><p>　　if(S->top==-1)/*元素出棧前，判斷棧是否為空*/</p><p><b>　　{</b></p><p>　　printf("棧已經(jīng)沒(méi)有元素,不能

51、出棧!\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　*

52、e=S->stack[S->top];/*將出棧元素賦值給e*/</p><p>　　S->top--;/*修改棧頂指針，即出棧*/</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　}</b

53、></p><p>　　void main()</p><p><b>　　{</b></p><p>　　SeqList a;</p><p>　　InitList(&a);</p><p>　　int b[10]={0,0,0,0,0,0,0,0,0,0};</p>

54、<p>　　int i=0;//表示第n-1次</p><p>　　int f_n_1=0;//表示f(n-1);</p><p>　　int f_n=0;//表示f(n)</p><p>　　a.list[0]=1;</p><p><b>　　a.last++;</b></p><p&

55、gt;　　for(i=1;i<1000;i++)</p><p><b>　　{</b></p><p>　　GetElem(a,i,&f_n_1);//從數(shù)組a中將f(n-1)取出</p><p>　　f_n=f_n_1+(i+1);</p><p>　　if(f_n>10)</p>

56、<p>　　f_n=(f_n%10);</p><p>　　InsertList(&a,i+1,f_n);//將第n次的結(jié)果輸入到數(shù)組a</p><p><b>　　}</b></p><p>　　for(i=0;i<1000;i++)</p><p><b>　　{</b>

57、</p><p>　　switch(a.list[i])</p><p><b>　　{</b></p><p>　　case 1:b[0]++;break;</p><p>　　case 2:b[1]++;break;</p><p>　　case 3:b[2]++;break;</p&g

58、t;<p>　　case 4:b[3]++;break;</p><p>　　case 5:b[4]++;break;</p><p>　　case 6:b[5]++;break;</p><p>　　case 7:b[6]++;break;</p><p>　　case 8:b[7]++;break;</p>&

59、lt;p>　　case 9:b[8]++;break;</p><p>　　case 10:case 0:b[9]++;break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("┏━━━━━━━━━━━━━━━━

60、━━━━━━━┓\n");</p><p>　　printf("┃ ┃\n");</p><p>　　printf("┃ 狼追兔子 ┃\n");</p><p&

61、gt;　　printf("┃ 狼追蹤的次數(shù)為1000次 ┃\n");</p><p>　　printf("┃ 狼找的洞的號(hào)數(shù)f(n)=f(n-1)+n ┃\n");</p><p>　　printf("┃ 求狼追兔子的洞的號(hào)數(shù)

62、 ┃\n");</p><p>　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");</p><p>　　printf("請(qǐng)稍等，程序正在運(yùn)行中............................\n");</p><p>　　Sleep(10000);</p>

63、;<p>　　printf("┏━━━━━━━━━━━━━━━━━━━━━━━┓\n");</p><p>　　printf("┃ ┃\n");</p><p>　　printf("┃ 狼追蹤的次數(shù)為1000次

64、 ┃\n");</p><p>　　printf("┃ 狼找的洞的號(hào)數(shù)f(n)=f(n-1)+n ┃\n");</p><p>　　printf("┃ 求狼追兔子的洞的號(hào)數(shù)與被狼需找的次數(shù) ┃\n");</p><p>　　printf("

65、;┃ 1 2 3 4 5 6 7 8 9 10 ┃\n");</p><p>　　printf("--------------------------------------------------\n");</p><p>　　printf(" ");</p><p&

66、gt;　　for(i=0;i<10;i++)</p><p>　　printf("%3d ",b[i]);</p><p>　　printf("\n");</p><p>　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");</p><p><