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

1、青島大學(xué)軟件技術(shù)學(xué)院游戲算法實(shí)踐報(bào)告姓 名 曹寧 專 業(yè) 數(shù)字媒體藝術(shù) 班 級(jí) 10級(jí) 4班 指導(dǎo)教師 劉春秋 2013年 1 月 16日目錄1 問題定義與描述31.1 問題定義31.2 問題描述32 關(guān)鍵技術(shù)33 數(shù)據(jù)的組織33.1數(shù)據(jù)類型定義33.2數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)44 總體設(shè)計(jì)44.1 系統(tǒng)模塊圖44.2棧的基本操作44.3順序表的基本操作45 詳細(xì)設(shè)計(jì)55.1順序存儲(chǔ)的線性表56 測(cè)試結(jié)果及分析77 心得體會(huì)8附錄：程序代碼91問題定義與描述1.1 問題定義現(xiàn)實(shí)中很多利用順序表，棧解決一些數(shù)學(xué)模型問題1.2 問題描述圍繞著山頂有10個(gè)圓形排列的洞，狐貍要吃兔子，兔子說：“可以，但必須找到我

2、，我就藏身于這十個(gè)洞中，你可以先到1號(hào)洞找我，第二次隔一個(gè)洞（即3號(hào)洞）找，第三次隔兩個(gè)洞（即6號(hào)洞）找，以后如此類推，次數(shù)不限?！钡倧脑绲酵磉M(jìn)進(jìn)出出1000次，但仍沒有找到兔子，問兔子究竟藏身于哪個(gè)洞里2.關(guān)鍵技術(shù)順序表一次申請(qǐng)多個(gè)空間，包括結(jié)構(gòu)體定義的。N為整數(shù)，這樣得到的就是N個(gè)連續(xù)的空間。順序表可以利用類似于數(shù)組的形式訪問，即通過下標(biāo)訪問。當(dāng)然定義的變量類型必須是指針類型的，很方便，當(dāng)然也可以通過像鏈表一樣的訪問。單鏈表只是將空間分散開了，這樣的優(yōu)點(diǎn)就是動(dòng)態(tài)申請(qǐng)，需要多少就申請(qǐng)多少，一般一次申請(qǐng)一個(gè)空間結(jié)點(diǎn)，即N=1。3 數(shù)據(jù)的組織3.1數(shù)據(jù)類型定義 數(shù)據(jù)結(jié)構(gòu)，順序表，棧，單鏈表，

3、數(shù)組。在程序設(shè)計(jì)中，為了處理方便， 把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。在C語言中， 數(shù)組屬于構(gòu)造數(shù)據(jù)類型。一個(gè)數(shù)組可以分解為多個(gè)數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類型或是構(gòu)造類型。因此按數(shù)組元素的類型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、指針數(shù)組、結(jié)構(gòu)數(shù)組等各種類別。 3.2數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)棧以順序結(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)系來體現(xiàn)主要用在線性的數(shù)據(jù)結(jié)構(gòu)4總體設(shè)計(jì)4.1 順序表系統(tǒng)模塊圖圖4.1 順序表系統(tǒng)模塊圖4.2棧的基本操作 定

4、義棧的順序存取結(jié)構(gòu)，分別定義棧的基本操作（初始化棧、判棧為空、入棧、出棧等），通過定義函數(shù)實(shí)現(xiàn)。4.3順序表的基本操作在順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)基本操作：初始化、創(chuàng)建、插入、刪除、查找等運(yùn)算。5 詳細(xì)設(shè)計(jì)5.1順序存儲(chǔ)的線性表（1）程序中包括哪些函數(shù)？畫出函數(shù)之間的調(diào)用關(guān)系。答：程序中包含12個(gè)成員函數(shù)和1個(gè)主函數(shù)。12個(gè)成員函數(shù)。如下，:SqList,SqList,CreateList,Insert,Delete,GetElem,Locate,Clear,Eepty,Full,Length,ListDisp（2）程序中數(shù)據(jù)采用了什么樣的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)？答：邏輯結(jié)構(gòu)為依次存放線性表中的數(shù)據(jù)；物理結(jié)

5、構(gòu)為一組地址連續(xù)的儲(chǔ)存單元。（3）程序中那個(gè)函數(shù)實(shí)現(xiàn)順序表的創(chuàng)建？其中包括順序表的初始化嗎？答：函數(shù)SqList用于實(shí)現(xiàn)順序表的創(chuàng)建，不包括表的初始化。（4）程序中哪個(gè)函數(shù)實(shí)現(xiàn)結(jié)點(diǎn)的插入？畫出流程圖。答： 函數(shù)Insert實(shí)現(xiàn)結(jié)點(diǎn)的插入。圖5.1實(shí)現(xiàn)結(jié)點(diǎn)插入（5）程序中哪個(gè)函數(shù)實(shí)現(xiàn)結(jié)點(diǎn)的刪除？畫出流程圖。答：函數(shù)Delete實(shí)現(xiàn)了結(jié)點(diǎn)的刪除。圖5.2實(shí)現(xiàn)結(jié)點(diǎn)刪除（6）程序中提供了幾種元素查找方法？分別在哪個(gè)函數(shù)中實(shí)現(xiàn)？ 答：一種是按位置查找，在GetElem中實(shí)現(xiàn)；另一種是按元素查找在Locate 中實(shí)現(xiàn)。（7）程序退出時(shí)，調(diào)用了哪個(gè)函數(shù)？該函數(shù)主要操作有哪些？ 答：調(diào)用SqList函數(shù)，該函

6、數(shù)主要操作是：刪除順序表元素，使表長和表容量為0.開始輸入initstack()構(gòu)造堆棧來記!L.baseL.top=L.base;棧頂?shù)扔跅５?L.stacksize_curren=0;當(dāng)前棧的長度為0結(jié)束exit(0)構(gòu)造失敗否是6 測(cè)試結(jié)果及分析運(yùn)行程序，程序主界面如圖6.1所示。 圖6.1 程序的主界面運(yùn)行結(jié)果如圖6.2圖6.2 程序的運(yùn)行結(jié)果7心得體會(huì)本次課程設(shè)計(jì)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入的理解。數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。我的課程設(shè)計(jì)題目關(guān)于順序表和棧。剛開始做這個(gè)程序的時(shí)候，感到完全無從下手，甚至讓我覺得完成這

7、次程序設(shè)計(jì)根本就是不可能的，于是開始查 閱各種資料以及參考文獻(xiàn)，之后便開始著手寫程序，寫完運(yùn)行時(shí)有很多問題。特別是實(shí)現(xiàn)線索二叉樹的刪除運(yùn)算時(shí)很多情況沒有考慮周全，經(jīng)常運(yùn)行出現(xiàn)錯(cuò)誤，但通 過同學(xué)間的幫助最終基本解決問題。在本課程設(shè)計(jì)中，我明白了理論與實(shí)際應(yīng)用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能以及合 作能力。這次課程設(shè)計(jì)同樣提高了我的綜合運(yùn)用所學(xué)知識(shí)的能力。并對(duì)C有了更深入的了解。數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性很強(qiáng)的課程，上機(jī)實(shí)習(xí)是對(duì)學(xué)生全面綜合 素質(zhì)進(jìn)行訓(xùn)練的一種最基本的方法，是與課堂聽講、自學(xué)和練習(xí)相輔相成的、必不可少的一個(gè)教學(xué)環(huán)節(jié)。上機(jī)實(shí)習(xí)一方面

8、能使書本上的知識(shí)變“活”，起到深化理解 和靈活掌握教學(xué)內(nèi)容的目的;另一方面，上機(jī)實(shí)習(xí)是對(duì)學(xué)生軟件設(shè)計(jì)的綜合能力的訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧的訓(xùn)練。此外，還 有更重要的一點(diǎn)是：機(jī)器是比任何更嚴(yán)厲的檢查者。因此，在“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)過程中，必須嚴(yán)格按照老師的要求，主動(dòng)地、積極地、認(rèn)真地做好每一個(gè)實(shí)驗(yàn)，以不斷提高自己的編程能力與專業(yè)素質(zhì)。通過這段時(shí)間的課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程。需要多花時(shí)間上機(jī)練習(xí)。這次的程序訓(xùn)練培養(yǎng)了我實(shí)際分析問題、編程和動(dòng)手能力，使我掌握了程序設(shè)計(jì)的基本技能，提高了我適應(yīng)實(shí)際，實(shí)踐編程的能力?？偟膩碚f，這次課程設(shè)計(jì)讓我獲益匪淺，對(duì)

9、數(shù)據(jù)結(jié)構(gòu)也有了進(jìn)一步的理解和認(rèn)識(shí)。 附錄：程序代碼#include#include#include #define StackSize 100typedef int DataType;typedef struct DataType stackStackSize; int top;SeqStack;#define MAXSIZE 1100typedef struct DataType listMAXSIZE; int last;SeqList;void InitList(SeqList *L)/*順序表的初始化*/L-last=-1;int ListEmpty(SeqList L)/*判斷順序表

10、是否為空*/ if(L.last=-1)/*判斷最后一個(gè)元素的序號(hào)是否為-1*/ return 1;/*當(dāng)順序表為空時(shí)返回1；否則返回0*/ else return 0;/*否則返回0*/int ListLength(SeqList L)/*求線性表的長度*/return L.last+1;int GetElem(SeqList L,int i,DataType *e)/*按序號(hào)順序查找元素。查找成功將該值返回給e，并返回1表示成功；否則返回-1表示失敗*/ if(iL.last+1)/*在查找第i個(gè)元素之前，先判斷該序號(hào)是否合法*/ return -1; *e=L.listi-1;/*將第i

11、個(gè)元素值賦值給e*/ return 1;int LocateElem(SeqList *L,DataType x)/*按內(nèi)容查找，查找成功，將對(duì)應(yīng)元素的序號(hào)返回；否則返回-1*/ int i=0; while(ilast&L-listi!=x) i+; if(iL-last) return -1; else return i+1;int InsertList(SeqList *L,int i,DataType x) int j; if(L-last=MAXSIZE-1)/*表空間已滿，不能插入*/ printf(表滿，不能插入); return -1; if(iL-last+2)/*檢查插入位

12、置是否合法*/ printf(插入位置非法); return 0; for(j=L-last;j=i-1;j-) L-listj+1=L-listj;/*結(jié)點(diǎn)移動(dòng)*/ L-listi-1=x;/*新元素插入*/ L-last+;/*last仍指向最后一個(gè)元素*/ return 1;/*插入成功，返回*/int DeleteList(SeqList *L,int i,DataType *e)int j;if(L-last0) printf(順序表已空,不能插入進(jìn)行操作!n); return 0;else if(iL-last+1) printf(插入位置不合法!n); return -1;els

13、e *e=L-listi-1; for(j=i;jlast;j+)L-listj-1=L-listj; L-last-; return 1;void InitStack(SeqStack *S)/*棧的初始化*/ S-top=-1;/*把棧頂指針置為-1*/int StackEmpty(SeqStack S)/*判斷棧是否為空*/ if(S.top=-1)/*判斷棧頂指針top是否為-1*/ return 1;/*當(dāng)棧為空時(shí)，返回1；否則返回0*/ else return 0;int GetTop(SeqStack S,DataType *e)/*取棧頂元素*/ if(S.toptop=Sta

14、ckSize)/*在元素進(jìn)棧前，判斷棧是否已滿*/ printf(棧已滿,不能進(jìn)棧！n); return 0; else S-top+;/*修改棧頂指針*/ S-stackS-top=x;/*元素x進(jìn)棧*/ return 1; int PopStack(SeqStack *S,DataType *e)/*出棧操作，出棧成功返回1，否則返回0*/ if(S-top=-1)/*元素出棧前，判斷棧是否為空*/ printf(棧已經(jīng)沒有元素,不能出棧!n); return 0; else *e=S-stackS-top;/*將出棧元素賦值給e*/ S-top-;/*修改棧頂指針，即出棧*/ retur

15、n 1; void main() SeqList a; InitList(&a); int b10=0,0,0,0,0,0,0,0,0,0; int i=0;/表示第n-1次 int f_n_1=0;/表示f(n-1); int f_n=0;/表示f(n) a.list0=1; a.last+; for(i=1;i10) f_n=(f_n%10); InsertList(&a,i+1,f_n);/將第n次的結(jié)果輸入到數(shù)組a for(i=0;i1000;i+) switch(a.listi) case 1:b0+;break; case 2:b1+;break; case 3:b2+;break; case 4:b3+;break; case 5:b4+;break; case 6:b5+;break; case 7:b6+;break; case 8:b7+;break; case 9:b8+;break; case 10:case 0:b9+;break; printf(n); printf( n); printf( 狼追兔子 n); printf( 狼追蹤的次數(shù)為1000次 n); printf( 狼找的洞的號(hào)數(shù)f(n)=f(n-1)+n n); printf( 求狼追兔子的洞的號(hào)數(shù) n); printf(n); printf(請(qǐng)稍等