第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(井字棋)（大全）
目錄
一、設(shè)計(jì)課題名????????????????? 1
二、設(shè)計(jì)目的?????????????????? 1
三、問(wèn)題描述及需求分析………………………………… 1
四、概要設(shè)計(jì)??????????????????
五、詳細(xì)設(shè)計(jì)??????????????????
六、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果…………………………………
七、課程設(shè)計(jì)小結(jié)????????????????
八、用戶手冊(cè)……………………………………………… 1 5 7 8
一、設(shè)計(jì)課題名
井字棋（人機(jī)對(duì)弈）
二、設(shè)計(jì)目的
1、課程設(shè)計(jì)是《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)必不可缺的一個(gè)重要環(huán)節(jié)；
2、通過(guò)課程設(shè)計(jì)加深課堂教學(xué)內(nèi)容的理解和鞏固；
3、將《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)內(nèi)容與解決實(shí)際問(wèn)題結(jié)合起來(lái)，培養(yǎng)理論聯(lián)系實(shí)際的學(xué)風(fēng)；
4、提高程序設(shè)計(jì)能力、培養(yǎng)自學(xué)能力 ；
5、提高分析問(wèn)題、解決問(wèn)題的能力；
6、提高收集資料、查找參考書的能力；
7、鍛煉書寫報(bào)告的能力。
三、問(wèn)題描述及需求分析
本設(shè)計(jì)的主要完成的是井字棋的人機(jī)對(duì)弈問(wèn)題，即計(jì)算機(jī)與人交替落子，當(dāng)行、列或?qū)怯羞B續(xù)三個(gè)相同一方棋時(shí)，則判定一方勝利，若無(wú)此情形則為和局。
要完成此設(shè)計(jì)則需一判定勝負(fù)函數(shù)及一計(jì)算機(jī)自行落子函數(shù)，一旦這兩個(gè)函數(shù)完成則此程序主要部分可完成。
四、概要設(shè)計(jì)
完成此程序需一合理數(shù)據(jù)結(jié)構(gòu)，因其為井字棋游戲程序則此結(jié)構(gòu)中應(yīng)包含一存儲(chǔ)當(dāng)前棋局的數(shù)組；又因計(jì)算機(jī)在判定在何位置落子最佳時(shí)，需一搜索樹因而我在設(shè)計(jì)時(shí)設(shè)置了一PARENT域和CHILD域；
除了主程序外，它還包括具有以下功能的函數(shù)：(1)棋盤初始化函數(shù)：void Init()；(2)打印棋盤函數(shù)：void PrintQP()；
(3)用戶輸入落子位置函數(shù)：void UserInput()；
(4)判斷當(dāng)前棋局是否有一方獲勝，并判斷哪一方獲勝的函數(shù)：int IsWin(State s)；(5)評(píng)估函數(shù)值計(jì)算函數(shù)：int e_fun(State s)；(6)極大極小值算法主函數(shù)：int AutoDone()。
五、詳細(xì)設(shè)計(jì)
設(shè)計(jì)步驟:
(1)選定算法；
(2)建立一個(gè)簡(jiǎn)單的應(yīng)用程序（如字符界面程序）來(lái)測(cè)試算法；
(3)選定要實(shí)現(xiàn)的其他功能（如雙人對(duì)弈、悔棋、難易級(jí)別選定、聯(lián)機(jī)對(duì)戰(zhàn)等）；
第1頁(yè)
共8頁(yè)(4)實(shí)現(xiàn)井字棋程序。
數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：
struct
State
該結(jié)構(gòu)表示棋盤的某個(gè)狀態(tài)，也可看做搜索樹中的一個(gè)節(jié)點(diǎn) { int QP[3][3];
棋盤格局
int e_fun；
當(dāng)前狀態(tài)的評(píng)估函數(shù)值
int child[9];
兒女節(jié)點(diǎn)的下標(biāo)
int parent;
雙親節(jié)點(diǎn)的下標(biāo)
int bestChild;
最優(yōu)節(jié)點(diǎn)（評(píng)估函數(shù)值最大或最小）的兒女節(jié)點(diǎn)下標(biāo) } States[MAX_NUM];用來(lái)保存搜索樹中狀態(tài)節(jié)點(diǎn)的數(shù)組
我使用了States[MAX_NUM]數(shù)組來(lái)保存生成的狀態(tài)節(jié)點(diǎn)，通過(guò)State結(jié)構(gòu)中的parent、child域構(gòu)成了一個(gè)搜索樹，并通過(guò)bestChild域保存了一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最優(yōu)解路徑。特別的，States[0]作為根節(jié)點(diǎn)保存了當(dāng)前的棋局狀態(tài)。為了保存當(dāng)前對(duì)弈過(guò)程的狀態(tài)信息，我定義了以下常量：
const int MAX_NUM=1000;
擴(kuò)展生成狀態(tài)節(jié)點(diǎn)的最大數(shù)目 const int NO_BLANK=-1001;表示沒有空格 const int TREE_DEPTH=3;
搜索樹的最大深度 const int NIL=1001;表示空
算法設(shè)計(jì)及算法分析：
本程序采用的核心算法是極大極小值算法，這種算法的思想是“考慮雙方對(duì)弈若干步之后，從可能的走法中選一步相對(duì)較好的走法來(lái)走”，并且“在有限的搜索深度范圍內(nèi)進(jìn)行求解”。整個(gè)算法在AutoDone函數(shù)中實(shí)現(xiàn)，其實(shí)現(xiàn)過(guò)程分為以下幾步：
(1)為了獲得最優(yōu)的落子位置，在算法中首先要生成搜索樹。其中，我把States[0]作為樹根節(jié)點(diǎn)，根節(jié)點(diǎn)所在的層是極大層（MAX層），然后通過(guò)向棋盤中沒有落子的空格添一個(gè)對(duì)方的棋子生成下一層（極小層，MIN層）的樹節(jié)點(diǎn)，如果當(dāng)前樹的高度大于等于TREE_DEPTH（>=1）全局變量，則停止生成節(jié)點(diǎn)，否則則繼續(xù)生成下一層節(jié)點(diǎn)（如果當(dāng)前節(jié)點(diǎn)層為MIN層，則下一層為MAX層，否則，則下一層為MIN層）。生成每一層時(shí)可為每一層的屬性（MAX或MIN）做標(biāo)記，生成每個(gè)節(jié)點(diǎn)時(shí)，應(yīng)計(jì)算這個(gè)節(jié)點(diǎn)的評(píng)估函數(shù)值，并將其保存在狀態(tài)節(jié)點(diǎn)的e_fun域中。
(2)因?yàn)閷哟伪闅v會(huì)修改非葉節(jié)點(diǎn)的極大極小值，而且非葉節(jié)點(diǎn)原來(lái)的極大極小值會(huì)對(duì)其來(lái)自其子女節(jié)點(diǎn)的極大極小值產(chǎn)生影響（比如，如果一個(gè)非葉節(jié)點(diǎn)的極大極小值大于或小于其子女節(jié)點(diǎn)中的最大者或小于其中的最小者，則導(dǎo)致其評(píng)估函數(shù)值無(wú)法更新）。所以非葉節(jié)點(diǎn)沒有必要也不能保存。這一步的源代碼如下所示：
tag=States[s_count].parent;//設(shè)置最底層標(biāo)志，以區(qū)分葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)。
第2頁(yè)
共8頁(yè) for(i=0;i<=s_count;i++){
if(i>tag)//保留葉節(jié)點(diǎn)的評(píng)估函數(shù)值
{
States[i].e_fun=e_fun(States[i]);
}
else //抹去非葉節(jié)點(diǎn)的評(píng)估函數(shù)值
States[i].e_fun=NIL;}(3)然后，通過(guò)層次遍歷獲得每個(gè)非葉節(jié)點(diǎn)的評(píng)估函數(shù)值，同時(shí)將非葉節(jié)點(diǎn)的bestChild域指向最佳子女，從而形成一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最佳解路徑。這一步的源代碼如下所示：
while(!IsOK)//尋找最佳落子的循環(huán)
{
for(int i=s_count;i>tag;i--)
{
if(max_min)//取子女節(jié)點(diǎn)的最大值
{
if(States[States[i].parent].e_fun { States[States[i].parent].e_fun=States[i].e_fun; //設(shè)置父母節(jié)點(diǎn)的最大最小值 States[States[i].parent].bestChild=i; //設(shè)置父母節(jié)點(diǎn)的最佳子女的下標(biāo) } } else//取子女節(jié)點(diǎn)的最小值 { if(States[States[i].parent].e_fun>States[i].e_fun||States[States[i].parent].e_fun==NIL) { States[States[i].parent].e_fun=States[i].e_fun; //設(shè)置父母節(jié)點(diǎn)的最大最小值 States[States[i].parent].bestChild=i; //設(shè)置父母節(jié)點(diǎn)的最佳子女的下標(biāo) } } } s_count=tag;//將遍歷的節(jié)點(diǎn)上移一層 max_min=!max_min;//如果該層都是MAX節(jié)點(diǎn)，則它的上一層都是MIN節(jié)點(diǎn)，反之亦然。 if(States[s_count].parent!=NIL)//如果當(dāng)前遍歷的層中不包含根節(jié)點(diǎn)，//則tag標(biāo)志設(shè)為上一層的最后一個(gè)節(jié)點(diǎn)的下標(biāo) 第3頁(yè) 共8頁(yè) tag=States[s_count].parent; else IsOK=true; //否則結(jié)束搜索 }(4)最后，將當(dāng)前的棋局更新為其最優(yōu)子女節(jié)點(diǎn)的棋局，并獲得落子的位置。這一步的源代碼如下所示： //取落子的位置，將x,y坐標(biāo)保存在變量pos_x和pos_y中，//并將根（當(dāng)前）節(jié)點(diǎn)中的棋局設(shè)為最佳子女節(jié)點(diǎn)的棋局 for(int x=0;x<3;x++){ for(int y=0;y<3;y++) { if(States[States[0].bestChild].QP[x][y]!=States[0].QP[x][y]) { pos_x=x;pos_y=y; } States[0].QP[x][y]=States[States[0].bestChild].QP[x][y]; } } 在我采用的算法中，可以通過(guò)增加生成樹的層數(shù)，即增加TREE_DEPTH的值來(lái)提高計(jì)算機(jī)的智商。這相當(dāng)于增加了計(jì)算機(jī)向前預(yù)測(cè)的步數(shù)。對(duì)井字棋來(lái)說(shuō)，因?yàn)榫制逵?個(gè)格，所以TREE_DEPTH的最大值可以設(shè)為9。TREE_DEPTH＝3時(shí)，計(jì)算機(jī)會(huì)綜合考慮以后3步的走法。當(dāng)TREE_DEPTH＝3時(shí)，程序生成的最大狀態(tài)節(jié)點(diǎn)數(shù)為：1＋9＋9×8＋9×8×7＝585個(gè)。 總結(jié)： 在本程序中的井字棋程序使用了極大極小值算法，這種算法的思想是“考慮雙方對(duì)弈若干步之后，從可能的走法中選一步相對(duì)較好的走法來(lái)走”，并且“在有限的搜索深度范圍內(nèi)進(jìn)行求解”。 最大最小值算法的核心是將搜索樹的層分為MAX層和MIN層，MAX層和MIN層交替相鄰（即，一個(gè)節(jié)點(diǎn)如果在MAX層，則其子女節(jié)點(diǎn)在MIN層；如果在MIN層，則其子女節(jié)點(diǎn)在MAX層），在MAX層的節(jié)點(diǎn)的評(píng)估函數(shù)值取其子女節(jié)點(diǎn)中的最大者，在MIN層的節(jié)點(diǎn)的評(píng)估函數(shù)值取其子女節(jié)點(diǎn)中的最小者。 此外，需要定義一個(gè)評(píng)估函數(shù)來(lái)計(jì)算葉節(jié)點(diǎn)的評(píng)估函數(shù)值，要注意將某方獲勝的狀態(tài)節(jié)點(diǎn)的評(píng)估函數(shù)值設(shè)為計(jì)算機(jī)能表示的最大數(shù)（無(wú)窮大）或最小數(shù)（無(wú)窮小）以表明在該狀態(tài)下有一方獲勝。 最后，還要“在有限的搜索深度范圍內(nèi)進(jìn)行求解”，如果搜索深度太大，則在狀態(tài)數(shù)較多的情況下會(huì)使時(shí)間耗費(fèi)或空間耗費(fèi)達(dá)到無(wú)法忍受的程度。 第4頁(yè) 共8頁(yè) 六、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 圖一：程序初始運(yùn)行界面 圖二：人機(jī)對(duì)弈初始界面 第5頁(yè) 共8頁(yè) 圖三：人機(jī)對(duì)弈一方勝利界面 圖四：雙人對(duì)弈界面 第6頁(yè) 共8頁(yè) 圖五：雙人對(duì)弈一方勝利界面 七、課程設(shè)計(jì)小結(jié) 心得體會(huì)： 通過(guò)本次《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)，從看到設(shè)計(jì)要求，到選擇課題再到自己構(gòu)思，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，構(gòu)造算法，編寫源代碼，再到一個(gè)星期的上機(jī)調(diào)試，我充分認(rèn)識(shí)到書本上的知識(shí)只是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)，認(rèn)識(shí)到將知識(shí)有機(jī)融合并運(yùn)用到實(shí)際生活中的重要性。 本次課程設(shè)計(jì)的主要數(shù)據(jù)結(jié)構(gòu)涉及到樹的存儲(chǔ)結(jié)構(gòu)，我選擇了用數(shù)組來(lái)存儲(chǔ)相關(guān)內(nèi)容，設(shè)計(jì)了一個(gè)parent域和child域。通過(guò)本次的課程設(shè)計(jì)、上機(jī)實(shí)驗(yàn)，原本對(duì)于樹的存儲(chǔ)結(jié)構(gòu)相對(duì)比較生疏的我，現(xiàn)在能較為熟練的掌握樹的各種存儲(chǔ)結(jié)構(gòu)，并能比較純熟的選擇適合的存儲(chǔ)結(jié)構(gòu)。在此次程序調(diào)試運(yùn)行過(guò)程中我認(rèn)識(shí)到一個(gè)可操作的好的程序必須有個(gè)良好的界面，因?yàn)橹挥羞@樣才能實(shí)現(xiàn)與用戶的互動(dòng)，便于用戶使用，才能充分發(fā)揮出一個(gè)好程序應(yīng)有的功效。而一個(gè)好的編程工作者，應(yīng)當(dāng)在編程之前充分了解用戶的需求，使用戶能方便使用此程序的各項(xiàng)功能。 當(dāng)然由于時(shí)間比較倉(cāng)促、所學(xué)比較有限，對(duì)于此課程設(shè)計(jì)的模塊尚不完全，因此功能還需完善，有較多地方有待改進(jìn)，希望通過(guò)將來(lái)的進(jìn)一步學(xué)習(xí)，我能完善此程序，將其功能設(shè)計(jì)的更加完全，能讓用戶更方便的使用。 存在問(wèn)題： （1）在游戲進(jìn)行過(guò)程中不能退出游戲界面； （2）雙人對(duì)弈時(shí)不能清楚鑒別兩人身份，落子時(shí)可能出現(xiàn)錯(cuò)誤，且在游戲進(jìn)行中不可提前判斷平局情況； 第7頁(yè) 共8頁(yè)（3）不可進(jìn)行悔棋，人機(jī)對(duì)弈難度的選擇。 改進(jìn)措施： 雙人對(duì)弈時(shí)可設(shè)一姓名判別函數(shù)，確定雙人身份； 設(shè)定判定樹提前預(yù)測(cè)平局情況； 可對(duì)樹的深度進(jìn)行設(shè)置，借以改變對(duì)弈難度； 設(shè)一數(shù)組保存前一階段棋局，在悔棋時(shí)可調(diào)出。 八、用戶手冊(cè) 按鍵說(shuō)明： 1：進(jìn)入人機(jī)對(duì)弈界面； 2：進(jìn)入雙人對(duì)弈界面； 3：退出。 具體說(shuō)明： （1）進(jìn)入具體對(duì)弈界面后會(huì)出現(xiàn)提示信息，按提示信息輸入相關(guān)內(nèi)容即可；（2）所輸入的棋子的行列號(hào)為整數(shù)，其分別為11，12，13，21，22，23，31，32，33；其中前一位數(shù)為行號(hào)，后一位數(shù)為列號(hào)； （3）盤界面上0代表所在位置為空，若為0則代表此位置可落子；在人機(jī)對(duì)弈則1代表計(jì)算機(jī)所落之子，-1代表人所落之子；在雙人對(duì)弈則1代表第二個(gè)人所落之子，-1代表第一人所落之子； （4）雙人對(duì)弈時(shí)需先自行對(duì)下棋雙方進(jìn)行編號(hào)（1和2），而后根據(jù)提示輸入誰(shuí)為先手的信息，進(jìn)而進(jìn)入游戲。 注意： （1）進(jìn)入游戲后不可中途退出游戲，需在決出勝負(fù)后按3方可退出；（2）在游戲進(jìn)行期間若發(fā)現(xiàn)所輸落子位置出錯(cuò)，可自行更改或按系統(tǒng)出錯(cuò)提示重新輸入。 第8頁(yè) 共8頁(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 散列表的應(yīng)用:插隊(duì)買票 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)（網(wǎng)絡(luò)技術(shù)） 金玲 計(jì)算機(jī)131 1310704114 張靜林 2015年1月23日 學(xué)生姓名 班學(xué)級(jí) 號(hào) 指導(dǎo)教師 完成日期 目錄概述……………………………………………………………………………………1 1.1 課程設(shè)計(jì)目的……………………………………………………………………….1 1.2 課程設(shè)計(jì)內(nèi)容……………………………………………………………………….1 2 系統(tǒng)需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統(tǒng)概要設(shè)計(jì)…………………………………………………………………………2 3.1 系統(tǒng)流程圖………………………………………………………………………….2 4 系統(tǒng)詳細(xì)設(shè)計(jì)…………………………………………………………………………3 5 測(cè)試……………………………………………………………………………………5 5.1 測(cè)試方案…………………………………………………………………………….5 5.2 測(cè)試結(jié)果…………………………………………………………………………….5 6 小結(jié)……………………………………………………………………………………5 參考文獻(xiàn)…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述 1.1 課程設(shè)計(jì)目的 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是為數(shù)據(jù)結(jié)構(gòu)課程獨(dú)立開設(shè)的實(shí)踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)對(duì)于鞏固數(shù)據(jù)結(jié)構(gòu)知識(shí)，加強(qiáng)學(xué)生的實(shí)際動(dòng)手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計(jì)的目的： 1．要求學(xué)生達(dá)到熟練掌握C語(yǔ)言的基本知識(shí)和技能。 2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力。3．提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過(guò)上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。 4．培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。 5．初步掌握軟件開發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能。 1.2課程設(shè)計(jì)內(nèi)容 本課程設(shè)計(jì)的任務(wù)是寫一個(gè)程序模擬這種情況。每個(gè)隊(duì)伍都允許插隊(duì)。如果你在排隊(duì)，有一個(gè)以上的朋友要求插隊(duì)，則你可以安排他們的次序。每次一個(gè)人入隊(duì)，并且如果這個(gè)入隊(duì)的人發(fā)現(xiàn)隊(duì)伍中有自己的朋友，則可以插入到這個(gè)朋友的后面；當(dāng)隊(duì)伍中的朋友不止一個(gè)的時(shí)候，這個(gè)人會(huì)排在最后一個(gè)朋友的后面；如果隊(duì)伍中沒有朋友，則他只能夠排在這個(gè)隊(duì)伍的最后面。每一個(gè)入隊(duì)的人都先進(jìn)行上述的判斷。當(dāng)隊(duì)伍前面的人買到車票之后，依次出隊(duì)。系統(tǒng)需求分析 2.1 主體功能 程序從“input.txt”文件讀入測(cè)試用例，一個(gè)文件可包含多個(gè)測(cè)試用例。每個(gè)用例的第一行是朋友組的數(shù)目n（1<=n<=1000)。對(duì)于一個(gè)朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個(gè)數(shù)以及他們的名字組成，一個(gè)空格后接該組朋友的名字，以空格分開，并且每個(gè)人的名字都不同。每個(gè)名字不超過(guò)四個(gè)字母，由{A，B，...，Z，a，b，...，z}組成。一個(gè)朋友組最多有1000個(gè)人，每個(gè)人只屬于一個(gè)朋友組。n=0時(shí)，測(cè)試數(shù)據(jù)結(jié)束。 下面是一些具體命令：.ENQUEUE——X入隊(duì);.DEQUEUE——排隊(duì)頭的人買票，離開隊(duì)伍，即出隊(duì)；.STOP——一個(gè)測(cè)試用例結(jié)束。 測(cè)試結(jié)果輸出到“output.txt”文件中。每個(gè)測(cè)試用例第一行輸出“Scenario#k”，k是測(cè)試用例的序號(hào)（從1開始）。對(duì)每一個(gè)出隊(duì)命令，輸出剛買票離開隊(duì)伍的人名。兩個(gè)測(cè)試試用例 之間隔一空行，最后一個(gè)用例結(jié)束不輸出空行。系統(tǒng)概要設(shè)計(jì) 3.1 系統(tǒng)流程圖 系統(tǒng)詳細(xì)設(shè)計(jì) 本題目主要解決兩個(gè)問(wèn)題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表來(lái)存放和查找數(shù)據(jù)。由于最多有1000個(gè)朋友組，每組最多有1000人，使用平方探測(cè)法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素?cái)?shù)）。同一個(gè)組內(nèi)的都是朋友，所以每個(gè)人除了記錄他的名字name，還要記錄他屬于哪個(gè)組group，另外用info來(lái)表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計(jì)算一個(gè)以64為階的多項(xiàng)式，如圖4.2所示。沖突解決方法采用平方探測(cè)法，如圖4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個(gè)朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };圖4.1數(shù)據(jù)結(jié)構(gòu)：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 圖4.2散列函數(shù) Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((單元被占用)and(單元內(nèi)的名字與查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 圖4.3用平方探測(cè)法解決沖突 第二個(gè)問(wèn)題是關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊(duì)列來(lái)模擬。由于有插隊(duì)現(xiàn)象的存在，不能單純的用一個(gè)數(shù)組來(lái)表示隊(duì)列，因?yàn)檫@樣的話，插入一個(gè)朋友，則他后面的人都要往后移一個(gè)單位，刪除一個(gè)人，則他后面的人都要前移一個(gè)，會(huì)降低效率。所以，采用一個(gè)Index標(biāo)記來(lái)表示當(dāng)前元素的后繼元素，最后一個(gè)單元的后繼元素是第0個(gè)，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖4.4所示。不用鏈表是因?yàn)殒湵泶娣胖羔樢残枰臻g，并且鏈表插入、刪除的效率沒有數(shù)組高。 typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號(hào)*/ };圖4.4數(shù)據(jù)結(jié)構(gòu)：隊(duì)列 輸入ENQUEUE命令，如果隊(duì)伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊(duì)尾。入隊(duì)時(shí)，用一個(gè)數(shù)組記錄每個(gè)朋友組的最后一位，以便下一個(gè)朋友到來(lái)時(shí)排到他后面，這個(gè)數(shù)組被稱為“插隊(duì)數(shù)組”。 輸入DEQUEUE命令，則根據(jù)“先進(jìn)先出”，按照各個(gè)元素和它后繼元素的先后順序，每次刪除隊(duì)列重的第一個(gè)。程序結(jié)構(gòu)如圖4.5所示。 While(讀測(cè)試文件){ if(輸入”ENQUEUE”) { 讀入名字； 插入散列表； 插入隊(duì)列； } else if(輸入”DEQUEUE”) { 刪除隊(duì)列第一個(gè)名字； 將該名字輸出到文件； } else stop;} 圖4.5入隊(duì)、出隊(duì)操作 測(cè)試 5.1 測(cè)試方案 按輸入要求輸入正常測(cè)試數(shù)據(jù)，測(cè)試程序是否能正確解決問(wèn)題，得到正確答案。應(yīng)注意邊界測(cè)試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時(shí)需寫程序生成測(cè)試用例。 不按輸入要求輸入數(shù)據(jù)，測(cè)試程序能否對(duì)輸入內(nèi)容進(jìn)行數(shù)據(jù)合法性檢測(cè)并進(jìn)行相應(yīng)的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過(guò)4個(gè)字母等情況下的測(cè)試用例。5.2 測(cè)試結(jié)果 小結(jié) 在前面的學(xué)習(xí)過(guò)程中我們學(xué)到了很多知識(shí)而這次課程設(shè)計(jì)又是對(duì)我們所學(xué)的 一次總結(jié)，剛開始，可以說(shuō)是沒有頭緒，于是就去圖書館找資料，找到了一些關(guān)于程序方面的，可這遠(yuǎn)遠(yuǎn)不夠，這只是小小的開始。我們必須掌握很多已學(xué)的知識(shí)才能很好的完成本次的課程設(shè)計(jì)。在這次課程設(shè)計(jì)中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經(jīng)驗(yàn)不足，有時(shí)雖然是一個(gè)很小的問(wèn)題但解決起來(lái)卻花費(fèi)了我不少的時(shí)間，值得欣慰的是，當(dāng)自己苦思冥想或者和其它同學(xué)一起探討把問(wèn)題解決的時(shí)候我還是覺得獲益非淺，這就是在摸索中尋求到的知識(shí)。在設(shè)計(jì)時(shí)也免不了存在著些不足，所以在今后的學(xué)習(xí)中我會(huì)努力取得更大的進(jìn)步。雖然對(duì)著電腦做程序，有些累，可當(dāng)看到勞動(dòng)成果時(shí)，卻有另一番滋味。 參考文獻(xiàn) [1]范策，周世平，胡曉琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》[M].北京：機(jī)械工業(yè)出版社，2004 [2]嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》.北京：清華大學(xué)出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結(jié)構(gòu)與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版）》.北京：清華大學(xué)出版社，2006 附錄 附錄1 源程序清單 #include /*散列表大小TabSize 是大于表最大空間的素?cái)?shù)*/ #define Max 1000001 /*隊(duì)列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個(gè)朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號(hào)*/ }; int hashedx=0; /*標(biāo)記元素是否已經(jīng)在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函數(shù)，計(jì)算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果當(dāng)前單元被占用：?jiǎn)卧獌?nèi)的元素與當(dāng)前操作的名字不同，使用平方探測(cè)法解決沖突；與當(dāng)前操作的名字相同，則直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探測(cè)法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize;} if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) /*元素已經(jīng)在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*隊(duì)列*/ int *grouppos; /*記錄每個(gè)朋友組的最后一位，即插隊(duì)數(shù)組*/ int n; /*測(cè)試用例數(shù)目*/ int num; /*當(dāng)前測(cè)試用例序號(hào)*/ long int i,ii,j,key,temp;long int head,last; /*隊(duì)列的頭和尾*/ char c[8],tempc[8]; /*名字*/ FILE *fpin,*fpout; /*輸入、輸出文件指針*/ if(!(fpin=fopen(“input.txt”,“r”))) /*打開測(cè)試文件*/ { printf(“fopen error!”); /*文件打開錯(cuò)誤*/ return-1;} if(!(fpout=fopen(“output.txt”,“w”))) /*打開輸出文件*/ { printf(“fopen error!”); return-1;} hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*為散列表申請(qǐng)空間*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*為隊(duì)列申請(qǐng)空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請(qǐng)空間記錄每個(gè)朋友組的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一個(gè)單元的后繼單元是第0個(gè)，形成環(huán)*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當(dāng)前測(cè)試用例的朋友組數(shù)*/ { if(n<1||n>1000) /*處理異常輸入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*兩個(gè)測(cè)試用例間輸入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表，標(biāo)記位置0*/ for(i=0;i /*對(duì)每一組朋友*/ { fscanf(fpin,“%d”,&j); /*當(dāng)前組里的人數(shù)*/ if(j<1||j>1000) /*處理異常輸入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*輸入名字*/ for(ii=0;ii tempc[ii]='
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告