《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)_第1頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)_第2頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)_第3頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)_第4頁(yè)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)_第5頁(yè)
已閱讀5頁(yè),還剩449頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1第一篇課程設(shè)計(jì)教學(xué)指導(dǎo) 3第一章《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱 3第二章數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書(shū) 5第二篇案例課題 8第一章鏈表的應(yīng)用 8一、通信錄管理(★★★) 8二、約瑟夫生死者游戲(★★) 三、鏈表的綜合應(yīng)用設(shè)計(jì)要求(★★) 四、哲學(xué)家就餐問(wèn)題(★★) 第二章棧和隊(duì)列的應(yīng)用 一、八皇后問(wèn)題(★★★★) 二、表達(dá)式求值問(wèn)題(★★) 三、馬踏棋盤(pán)(★★★) 40四、漢諾塔問(wèn)題(★★★) 44五、舞伴問(wèn)題(★★) 六、臺(tái)階問(wèn)題(★) 七、鍵盤(pán)緩沖區(qū)(★★) 八、背包問(wèn)題(★) 九、劃分子集問(wèn)題(★★★) 十、迷宮問(wèn)題(★★★) 十一、學(xué)生就餐問(wèn)題(★★★★) 第三章文本文件的檢索 一、串模式匹配算法(★★) 二、文本文件單詞的檢索與計(jì)數(shù)(★★★) 80第四章數(shù)組和廣義表 一、稀疏矩陣(★) 二、矩陣運(yùn)算(★★) 三、統(tǒng)計(jì)成績(jī)(★) 四、廣義表運(yùn)算(★★) 五、十字鏈表運(yùn)算(★★★★) 第五章樹(shù) 一、求二叉樹(shù)上結(jié)點(diǎn)的路徑(★★) 二、二叉樹(shù)的綜合操作(★★) 三、赫夫曼編碼(★★) 一、渡河問(wèn)題(★★★) 二、工程可行性分析(★★) 三、關(guān)鍵路徑(★★★) 四、交通咨詢系統(tǒng)設(shè)計(jì)(★★★★) 第七章查找 2一、散列表的應(yīng)用——通信錄管理(★★★) 二、查找綜合練習(xí)(★★★★) 三、二叉排序樹(shù)(★★★) 四、散列文件(★★★★) 第八章排序 一、最優(yōu)裝載問(wèn)題(★) 二、排序綜合練習(xí)(★★) 第九章提高題 二、圖書(shū)管理系統(tǒng) 三、停車場(chǎng)管理 五、大眾匹薩問(wèn)題 219六、王伯買(mǎi)魚(yú) 2243第一篇課程設(shè)計(jì)教學(xué)指導(dǎo)第一章《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)教學(xué)大綱本課程設(shè)計(jì)是《數(shù)據(jù)結(jié)構(gòu)》課程的具體應(yīng)用和實(shí)踐,是軟件技術(shù)、電子商務(wù)的專業(yè)課知識(shí)的綜合應(yīng)用,其重點(diǎn)在于將理論知識(shí)應(yīng)用于一個(gè)具體的軟件項(xiàng)目開(kāi)發(fā)。通過(guò)查閱相關(guān)資料、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法,具備初步的獨(dú)立分析和設(shè)計(jì)能力;初步掌握系統(tǒng)需求分析、系統(tǒng)總體和詳細(xì)設(shè)計(jì)、系統(tǒng)實(shí)現(xiàn)和運(yùn)行、系統(tǒng)測(cè)試和維護(hù)等過(guò)程復(fù)習(xí)和鞏固該課程相關(guān)的理論專業(yè)知識(shí),鍛煉和提高學(xué)生綜合應(yīng)用和動(dòng)手實(shí)踐能力。1.復(fù)習(xí)鞏固數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法等基本知識(shí);2.掌握數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的基本思路和方法;4.鍛煉提高動(dòng)手實(shí)踐和綜合分析、解決實(shí)際問(wèn)題的能力。1、指導(dǎo)教師要熟悉課程設(shè)計(jì)的理論知識(shí),清楚本課程設(shè)計(jì)在實(shí)踐教學(xué)環(huán)節(jié)中的地位和作用。并于課程設(shè)計(jì)開(kāi)始時(shí)向?qū)W生公布。做好課程設(shè)計(jì)的各項(xiàng)準(zhǔn)備工作。4、培養(yǎng)和幫助學(xué)生建立正確的設(shè)計(jì)思想、嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng),使學(xué)生分析問(wèn)題和解決問(wèn)題的能力得到提高??己耍荒芊湃巫粤鳌2檎n程設(shè)計(jì)的進(jìn)度和質(zhì)量。7、認(rèn)真評(píng)閱和審核學(xué)生課程設(shè)計(jì)的全部?jī)?nèi)容,評(píng)定成績(jī),做好總結(jié)。8、按規(guī)定保管或上交文檔資料。9、一位指導(dǎo)教師指導(dǎo)的學(xué)生人數(shù)不宜超過(guò)20人。會(huì)設(shè)計(jì)的基本方法與步驟,積極認(rèn)真地做好準(zhǔn)備工作。3、課程設(shè)計(jì)中,學(xué)會(huì)如何運(yùn)用先修課程的知識(shí)與收集、歸納相關(guān)資料解決具體問(wèn)題的方法.4課程設(shè)計(jì)報(bào)告是課程設(shè)計(jì)工作的總結(jié)和提高,課程設(shè)計(jì)報(bào)告應(yīng)該反映出學(xué)生在課程設(shè)計(jì)過(guò)程中所做的主要工作和取得的主要成果,以及心得體會(huì)。要求學(xué)生以積極認(rèn)真、嚴(yán)謹(jǐn)求實(shí)的態(tài)度完成課程設(shè)計(jì)報(bào)告的撰寫(xiě)。課程設(shè)計(jì)報(bào)告編寫(xiě)基本要求:2、課程設(shè)計(jì)報(bào)告應(yīng)書(shū)寫(xiě)規(guī)范、文字通順、圖表清晰、數(shù)據(jù)完整、結(jié)論明確;課程設(shè)計(jì)報(bào)告要求統(tǒng)一使用A4紙打印。5、課程設(shè)計(jì)報(bào)告不少于3000字,源程序代碼不少于300行,要附有必要的結(jié)構(gòu)圖、流程圖及程序運(yùn)行的結(jié)果等項(xiàng)內(nèi)容。報(bào)告內(nèi)容要求包括:?jiǎn)栴}的概述、分析及研究意義;數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)和物理存儲(chǔ)設(shè)計(jì);重要算法的設(shè)計(jì)、流程描述或偽代碼描述;數(shù)據(jù)結(jié)構(gòu)的時(shí)空復(fù)雜性分析以及重要算法的復(fù)雜性分析;程序最終實(shí)現(xiàn)結(jié)果(包括重點(diǎn)結(jié)果界面的抓取,能過(guò)說(shuō)明問(wèn)題的重要實(shí)驗(yàn)結(jié)果數(shù)據(jù)的打印或其課程設(shè)計(jì)地點(diǎn):實(shí)驗(yàn)室設(shè)計(jì)內(nèi)容與學(xué)時(shí)分配:1)查閱相關(guān)資料2)復(fù)習(xí)鞏固數(shù)據(jù)結(jié)構(gòu)基本知識(shí)3)明確系統(tǒng)需求分析4)系統(tǒng)總體和詳細(xì)設(shè)計(jì)5)系統(tǒng)實(shí)現(xiàn)、運(yùn)行和測(cè)試6)課程設(shè)計(jì)總結(jié)報(bào)告撰寫(xiě)《數(shù)據(jù)結(jié)構(gòu)》蔣文蓉編著,高等教育出版社考核方法:日常考勤、系統(tǒng)實(shí)現(xiàn)運(yùn)行檢查、總結(jié)報(bào)告撰寫(xiě)評(píng)閱、設(shè)計(jì)答辯。:(1.問(wèn)題描述:描述要求編程解決的問(wèn)題。53.測(cè)試數(shù)據(jù):設(shè)計(jì)測(cè)試數(shù)據(jù),或具體給出測(cè)試數(shù)據(jù)。要求測(cè)試數(shù)據(jù)能全面地測(cè)試所設(shè)計(jì)程序的4.算法思想:描述解決相應(yīng)問(wèn)題算法的設(shè)計(jì)思想。5.模塊劃分:描述所設(shè)計(jì)程序的各個(gè)模塊(即函數(shù))功能。7.源程序:給出所有源程序清單,要求程序有充分的注釋語(yǔ)句,至少要注釋每個(gè)函數(shù)參數(shù)的含8.測(cè)試情況:給出程序的測(cè)試情況,并分析運(yùn)行結(jié)果。成績(jī)?cè)u(píng)定:日??记?0%、系統(tǒng)實(shí)現(xiàn)運(yùn)行檢查30%、總結(jié)報(bào)告撰寫(xiě)評(píng)閱30%、設(shè)計(jì)答辯30%。學(xué)生課程設(shè)計(jì)成績(jī)按優(yōu)秀、良好、中等、及格、不及格五級(jí)進(jìn)行評(píng)定。課程設(shè)計(jì)成績(jī)低于60分者不得畢業(yè)。要適當(dāng)控制成績(jī)優(yōu)秀的人數(shù)比例,一般應(yīng)不高于35%。優(yōu)秀:能獨(dú)立完成設(shè)計(jì)要求所規(guī)定的全部?jī)?nèi)容,設(shè)計(jì)方案正確、基本概念清楚,有獨(dú)到的見(jiàn)解或創(chuàng)造性。中等:能完成設(shè)計(jì)要求規(guī)定的全部?jī)?nèi)容,設(shè)計(jì)方案基本正確,基本概念清楚。及格:基本完成設(shè)計(jì)要求規(guī)定的內(nèi)容,設(shè)計(jì)方案基本合理,基本概念較清楚。不及格:未完成設(shè)計(jì)要求規(guī)定的內(nèi)容,設(shè)計(jì)方案不合理,或有較嚴(yán)重缺陷,基本概念不清楚。六、設(shè)計(jì)最終需提交的內(nèi)容包括:1、完整的程序系統(tǒng)(電子方式提交)(1).能夠?qū)斎氘a(chǎn)生相應(yīng)的輸出,并在輸入輸出做必要的提示.(2).該部分包括源代碼和可執(zhí)行文件兩個(gè)部分.(3).所有以電子方式提交的文件全部存在一個(gè)目錄中,并對(duì)其進(jìn)行壓縮(用Winrar或Winzip均可),壓縮后的文件按規(guī)定格式進(jìn)行命名,命名格式為:班級(jí)+學(xué)號(hào)+姓名.rar(如z04043120張文.rar).(4)將提交作品發(fā)送給各自的指導(dǎo)教師2、課程設(shè)計(jì)報(bào)告七、說(shuō)明課程設(shè)計(jì)報(bào)告封面:青島大學(xué)軟件技術(shù)學(xué)院課程設(shè)計(jì)見(jiàn)附件一;課程設(shè)計(jì)報(bào)告封二:課程設(shè)計(jì)式規(guī)范要求見(jiàn)附件四。評(píng)語(yǔ)表第二章數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書(shū)(一)設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練,包括問(wèn)題分析,總體結(jié)構(gòu)設(shè)計(jì),用戶界面設(shè)計(jì),程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力,培養(yǎng)科學(xué)的軟件工作方法。學(xué)生通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)在下述各方面得61、能根據(jù)實(shí)際問(wèn)題的具體情況,結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法,正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu),合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu),并能設(shè)計(jì)出解決問(wèn)題的有效算法。2、提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過(guò)上機(jī)實(shí)習(xí),驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法,迅速找出程序代碼中的錯(cuò)誤并且修改。(二)設(shè)計(jì)要求1、分析問(wèn)題,給出數(shù)學(xué)模型,設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。1)分析問(wèn)題的特點(diǎn),用數(shù)學(xué)表達(dá)式或其它形式描述其數(shù)學(xué)模型。2)選擇能夠體現(xiàn)問(wèn)題本身特點(diǎn)的邏輯結(jié)構(gòu)。3)在邏輯結(jié)構(gòu)確定的情況下,為算法的設(shè)計(jì)選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)的不同存儲(chǔ)方式,其對(duì)應(yīng)的算法也不相同。2、算法設(shè)計(jì)在已經(jīng)選擇好數(shù)據(jù)結(jié)構(gòu)的前提下,為解決問(wèn)題設(shè)計(jì)算法。1)確定所需模塊對(duì)于稍復(fù)雜的程序設(shè)計(jì),要充分利用模塊化程序設(shè)計(jì)方法,自頂向下,逐步細(xì)化,在整體思路確定的情況下,考慮所需模塊數(shù),各模塊完成功能以及模塊之間的數(shù)據(jù)聯(lián)系和調(diào)用關(guān)系。2)各子模塊功能描述給出主要模塊的算法描述,用流程圖或偽代碼表示。3)模塊之間的調(diào)用關(guān)系給出算法各模塊之間的關(guān)系圖示。3、源程序清單為了提高工作效率,充分利用上機(jī)調(diào)試程序的時(shí)間,要求學(xué)生在上機(jī)之前給出源程序清單。4、用測(cè)試數(shù)據(jù)去驗(yàn)證算法及程序的正確性按《軟件工程》的原理給出與題目相符的測(cè)試數(shù)據(jù)。經(jīng)過(guò)上機(jī)調(diào)試,源程序運(yùn)行正確,并且實(shí)現(xiàn)算法要求的功能,解決課程設(shè)計(jì)題目中給出的問(wèn)題后,分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度。6、編寫(xiě)設(shè)計(jì)報(bào)告2)設(shè)計(jì)內(nèi)容3)概要設(shè)計(jì):確定所需模塊及模塊間調(diào)用關(guān)系4)算法描述:給出各模塊流程圖及代碼5)測(cè)試結(jié)果及分析6)心得體會(huì)和參考資料注:學(xué)生完成課程設(shè)計(jì)后提交課程設(shè)計(jì)報(bào)告,要求將前述全部?jī)?nèi)容依先后順序?qū)懗稍O(shè)計(jì)報(bào)告一份,要求文字通暢,字跡工整,裝訂成冊(cè)。說(shuō)明書(shū)封面為A4紙,由計(jì)算機(jī)打印。上交報(bào)告以及源程序(刻光盤(pán))源程序中包括庫(kù)文件和程序代碼以及數(shù)據(jù)源連接方法。光盤(pán)上標(biāo)明姓名和學(xué)號(hào)(若幾個(gè)人的程序存放于一張光盤(pán)上則需要做目錄清單,按照學(xué)號(hào)先后順序存放)。7課程設(shè)計(jì)完成后提交的課程設(shè)計(jì)報(bào)告應(yīng)有指導(dǎo)教師的簽名。無(wú)指導(dǎo)教師簽字的設(shè)計(jì),沒(méi)有課程課程設(shè)計(jì)成績(jī)根據(jù)學(xué)生平時(shí)工作情況,上機(jī)調(diào)試程序的能力,算法的效率,課程設(shè)計(jì)報(bào)告質(zhì)量綜合衡量,由指導(dǎo)教師評(píng)定。課程設(shè)計(jì)成績(jī)=考勤20%+系統(tǒng)總體設(shè)計(jì)10%+調(diào)試程序能力30%+設(shè)計(jì)報(bào)告30%+論文答辯10%8第二篇案例課題第一章鏈表的應(yīng)用一、通信錄管理(★★★)利用鏈表結(jié)構(gòu)解決通訊錄的使用問(wèn)題,通過(guò)菜單實(shí)現(xiàn)其常用的幾種功能:程序運(yùn)行后,給出6個(gè)菜單項(xiàng)的內(nèi)容和輸入1、通訊錄鏈表的建立2、通訊錄結(jié)點(diǎn)的插入3、通訊錄結(jié)點(diǎn)的查詢4、通訊錄結(jié)點(diǎn)的刪除5、通訊錄結(jié)點(diǎn)的輸出0、退出管理系統(tǒng)請(qǐng)選擇0—5:使用數(shù)字0—5來(lái)選擇菜單項(xiàng),執(zhí)行相應(yīng)的操作,其他輸入則不起作用。按照單鏈表的結(jié)構(gòu),設(shè)計(jì)單鏈表的建立、結(jié)點(diǎn)的插入、結(jié)點(diǎn)的查找、結(jié)點(diǎn)的刪除和鏈表的輸出等相應(yīng)的子函數(shù)。為實(shí)現(xiàn)菜單的調(diào)用功能,應(yīng)該設(shè)計(jì)一個(gè)函數(shù)用于輸出提示信息和處理輸入,并將返回值提供給主函數(shù)實(shí)現(xiàn)相應(yīng)的子函數(shù)調(diào)用。/*****************//*通訊錄管理程序*//****************/#include<stdio.h>#include<string.h>#include<stdlib.h>charnum[5];/*編號(hào)*/charname[5];/*姓名*/charsex[3];/*性別*/charphone[13];/*電話*/charaddr[31];/*地址*/}DataType;typedefstructnode9DataTypedata;/*結(jié)點(diǎn)數(shù)據(jù)域*/structnode*next;/*結(jié)點(diǎn)指針域*/}ListNode;typedefListNode*LinkList;ListNode*p;/*定義一個(gè)指向結(jié)點(diǎn)的指針變量*/LinkListhead;/*定義指向單鏈表的頭指針*//*函數(shù)說(shuō)明*/intmenu_select();LinkListcreateList(void);LinkListInsertNode(LinkListhead,ListNode*p);ListNode*ListFind(LinkListhead);LinkListDelNode(LinkListhead);voidPrintList(LinkListhead);/*主函數(shù)*/voidmain(){{printf("*****************\n");printf("*通訊錄鏈表的建立*\n");printf("*****************\n");head=createList();break;printf("*****************\n");printf("*通訊錄鏈表的添加*\n");printf("*****************\n");p=(ListNode*)malloc(sizeof(ListNode));printf("編號(hào)(4)姓名(8)性別(2)電話(11)地址(31)\n");scanf("%s%s%s%s%s",p->data.num,p->,p->data.sex,p->data.phone,p->data.addr);head=InsertNode(head,p);break;printf("*****************************\n");printf("***通訊錄信息的刪除****\n");printf("*****************************\n");head=DelNode(head);break;printf("*****************\n");printf("通訊錄信息的查詢\n");printf("*****************\n");p=ListFind(head);{printf("編號(hào)姓名性別聯(lián)系電話地址\n");printf("----------------------------------------------\n");printf("%s,%s,%s,%s,%s\n",p->data.num,p->,p->data.sex,p->data.phone,p->data.aprintf("-------------------------------------------------\n");}{printf("沒(méi)查到要查詢的通訊者\(yùn)n");}break;printf("*****************************\n");printf("***通訊錄鏈表的輸出****\n");printf("*****************************\n");PrintList(head);break;return;}}}/********************//**菜單選擇函數(shù)程序**//********************/intmenu_select(){printf("通訊錄管理系統(tǒng)\n");printf("========================\n");printf("1、通訊錄鏈表的建立\n");printf("2、通訊者結(jié)點(diǎn)的插入\n");printf("3、通訊者結(jié)點(diǎn)的刪除\n");printf("4、通訊者結(jié)點(diǎn)的查詢\n");printf("5、通訊者結(jié)點(diǎn)的輸出\n");printf("0、退出管理系統(tǒng)\n");printf("=======================\n");printf("請(qǐng)選擇0-5\n");for(;;){scanf("%d",&sn);if(sn<0||sn>5)printf("\n\t輸入錯(cuò)誤,重選0-5");break;}}/***************************************//*用頭插法建立通訊錄鏈表函數(shù)/***************************************/LinkListcreateList(void){/*頭插法建立無(wú)頭結(jié)點(diǎn)的通訊錄鏈表算法*/ListNode*p;charflag='y';/*設(shè)置重復(fù)添加的標(biāo)記*/head=NULL;while((flag=='y')||(flag=='Y')){p=(ListNode*)malloc(sizeof(ListNode));/*申請(qǐng)新結(jié)點(diǎn)*/printf("編號(hào)(4)姓名(8)性別(2)電話(11)地址(31)\n");scanf("%s%s%s%s%s",p->data.num,p->,p->data.sex,p->data.phone,p->data.addr);p->next=head;head=p;scanf("%s",&flag);}returnhead;/*返回鏈表頭指針*/}/***************************//*在鏈表head中插入結(jié)點(diǎn)*//**************************/LinkListInsertNode(LinkListhead,ListNode*p)p->next=head;head=p;while((flag=='y')||(flag=='Y')){printf("繼續(xù)添加嗎?(y/n):\n");scanf("%s",&flag);if((flag=='y')||(flag=='Y')){p=(ListNode*)malloc(sizeof(ListNode));printf("編號(hào)(4)姓名(8)性別(2)電話(11)地址(31)\n");scanf("%s%s%s%s%s",p->data.num,p->,p->data.sex,p->data.phone,p->data.addr);p->next=head;head=p;}}returnhead;}/***********************//*通訊錄鏈表的查找函數(shù)*//***********************/ListNode*ListFind(LinkListhead){ListNode*p;charnum[5];charname[9];printf("1.按編號(hào)查詢\n");printf("2.按姓名查詢\n");p=head;scanf("%d",&xz);scanf("%s",num);while(p&&strcmp(p->data.num,num)!=0)p=p->next;p=NULL;}scanf("%s",name);while(p&&strcmp(p->,name)!=0)p=p->next;}returnp;}/********************//*通訊錄鏈表上結(jié)點(diǎn)的刪除*//********************/LinkListDelNode(LinkListhead){ListNode*p,*q;p=ListFind(head);printf("沒(méi)有查到要?jiǎng)h除的通訊者\(yùn)n");return;}{head=head->next;free(p);printf("該記錄已刪除!\n");returnhead;}q=head;while(q!=NULL&&q->next!=p)q=q->next;q->next=p->next;free(p);printf("通訊者已被刪除!\n");returnhead;}/***********************//*通訊錄鏈表的輸出函數(shù)/***********************/voidPrintList(LinkListhead){ListNode*p;p=head;printf("編號(hào)姓名性別聯(lián)系電話地址\n");printf("-----------------------------\n");while(p!=NULL){printf("%s,%s,%s,%s,%s\n",p->data.num,p->,p->data.sex,p->data.phone,p->data.aprintf("------------------------------\n");p=p->next;}}二、約瑟夫生死者游戲(★★)約瑟夫游戲的大意是:每30個(gè)旅客同乘一條船,因?yàn)閲?yán)重超載,加上風(fēng)高浪大,危險(xiǎn)萬(wàn)分;因此船長(zhǎng)告訴乘客,只有將全船一半的旅客投入海中,其余人才能幸免于難。無(wú)奈,大家只能同意這種辦法,并議定30個(gè)人圍成一圈,由第一個(gè)人數(shù)起,依次報(bào)數(shù),數(shù)到第9個(gè)人,便把他投入海中,然后再?gòu)乃南乱粋€(gè)數(shù)起,數(shù)到第9人,再將他投入海中,如此循環(huán)進(jìn)行,直到剩下15人為止。要求采用單循環(huán)鏈表實(shí)現(xiàn),利用結(jié)點(diǎn)的數(shù)據(jù)域存放位置。采用單循環(huán)鏈表解決這一問(wèn)題。將鏈表結(jié)點(diǎn)的數(shù)據(jù)域存放位置,然后將它們組成一個(gè)單循環(huán)鏈表。為了不失一般性,將人數(shù)用n表示,報(bào)數(shù)上限用k表示。算法描述如下:while(i<=n/2)輸出其位置q->data;}#include<stdio.h>#include<stdlib.h>typedefstructnode{structnode*next;}ListNode;typedefListNode*LinkList;voidmain(){LinkListR;LinkListInitRing(intn,LinkListR);LinkListDeleteDeath(intn,intk,LinkListvoidOutRing(intn,LinkListR);printf("n.k=");scanf("%d%d",&n,&k);R=InitRing(n,R);R=DeleteDeath(n,k,R);OutRing(n,R);}/***************************//*建立單循環(huán)鏈表函數(shù)*//**************************/LinkListInitRing(intn,LinkListR){ListNode*p,*q;R=q=(ListNode*)malloc(sizeof(ListNode));p=(ListNode*)malloc(sizeof(ListNode));q->data=i;q->next=p;}p->data=n;p->next=R;R=p;returnR;}/***************************//*生者與死者選擇函數(shù)*//**************************/LinkListDeleteDeath(intn,intk,LinkList{ListNode*p,*q;p=R;for(i=1;i<=n-1;i++)/*刪除一半的結(jié)點(diǎn)*/{for(j=1;j<=k-1;j++)/*沿鏈前進(jìn)k-1步*/p=p->next;q=p->next;/*q為被刪除結(jié)點(diǎn)*/p->next=q->next;/*刪除q指向的結(jié)點(diǎn)*/printf("%4d",q->data);if(i%10==0)printf("\n");free(q);}printf("\n");R=p;returnR;}/***************************//*輸出所有生者函數(shù)/**************************/voidOutRing(intn,LinkListR){ListNode*p;p=R;for(i=1;i<=1;i++,p=p->next){printf("%4d",p->data);}printf("\n");}三、鏈表的綜合應(yīng)用設(shè)計(jì)要求(★★)););設(shè)計(jì)一個(gè)菜單,通過(guò)菜單項(xiàng)的調(diào)用,實(shí)現(xiàn)題目要求的各項(xiàng)功能。#include<stdio.h>#include<malloc.h>#defineDATATYPE2chartypedefstructnode{DATATYPE2data;structnode*next;}LINKLIST;intlocate(LINKLIST*a,charx)if(la->data==x)return1;return0;}insert(LINKLIST*a,charx)p=(LINKLIST*)malloc(sizeof(LINKLIST));p->data=x;p->next=a->next;a->next=p;}voidunionn(LINKLIST*a1,LINKLIST*b1){/*兩有序表交集*/LINKLIST*lb;/*如果b1表中的一個(gè)元素不在a1表中*/insert(a1,lb->data);/*則將b1表中的該元素加入a1表中*/}voidunite(LINKLIST*a,LINKLIST*b,LINKLIST*c){/*a,b為兩有序鏈表,合并到c表,并保持有序*/LINKLIST*la,*lb,*lc,*p;{p=(LINKLIST*)map->data=la->data;p->next=NULL;}{p=(LINKLIST*)map->data=lb->data;p->next=NULL;}}{p=(LINKLIST*)mallp->data=la->data;p->next=NULL;}{p=(LINKLIST*)mallp->data=lb->data;p->next=NULL;}}voiddelete1(LINKLIST*a){/*無(wú)序鏈表中刪除重復(fù)元素,重復(fù)元素保留一個(gè)*/LINKLIST*la,*p,*q;}}}voiddelete(LINKLIST*a){/*有序鏈表中刪除重復(fù)元素,重復(fù)元素保留一個(gè)*/LINKLIST*la;la->next=la->next->next;}inser_order(DATATYPE2x,LINKLIST*head){/*有序表中插入元素x,并保持表有序*/LINKLIST*pr,*pn,*pp;pr=head;pn=head->next;while(pn!=NULL&&pn->datapn=pn->next;}pp=(LINKLIST*)malloc(sizeof(LINKLIST));pp->data=x;pp->next=pr->next;pr->next=pp;}LINKLIST*invertlink(LINKLIST*head){/*單鏈表元素逆置*/LINKLIST*p,*q,*r;q=NULL;p=head;p=p->next;q->next=r;}}intcount_nohead(LINKLIST*head){/*不帶頭結(jié)點(diǎn)的單鏈表:輸出單鏈表元素值并計(jì)數(shù)*/LINKLIST*p;printf("輸出單鏈表元素值:");{printf("%c",p->datap=p->next;}printf("\n");}intcount_head(LINKLIST*head){/*帶頭結(jié)點(diǎn)的單鏈表:輸出單鏈表元素值并計(jì)數(shù)*/LINKLIST*p;p=head->next;printf("輸出單鏈表元素值:");{printf("%c",p->datap=p->next;}printf("\n");}LINKLIST*creatlink_nohead_head(LINKLIST*head){/*用頭插入法建立不帶頭結(jié)點(diǎn)的單鏈表*/LINKLIST*t;while((ch=getchar())!=’$’)t->next=head;return(head);}LINKLIST*creatlink_head_head(LINKLIST*head){/*用頭插入法建立帶頭結(jié)點(diǎn)的單鏈表*/LINKLIST*t;t=(LINKLIST*)malloc(sizeof(LINKLIST));t->next=NULL;while((ch=getchar())!=’$’){t=(LINKLIST*)mat->next=head->next;head->next=t;}return(head);}LINKLIST*creatlink_nohead_rail(LINKLIST*head){/*用尾插入法建立不帶頭結(jié)點(diǎn)的單鏈表*/LINKLIST*last,*t;t->next=NULL;}}LINKLIST*creatlink_head_rail(LINKLIST*head){/*用尾插入法建立帶頭結(jié)點(diǎn)的單鏈表*/LINKLIST*last,*t;t=(LINKLIST*)malloc(sizeof(LINKLIST));t->next=NULL;t->next=NULL;}LINKLIST*creatlink_order_head(LINKLIST*head)/*建立帶頭結(jié)點(diǎn)的有序單鏈表*/t=(LINKLIST*)malloc(sizeof(LINKLIST));head=t;t->next=NULL;q=head;p=head->next;q->next=t;t->next=}return(head);}main()printf("\n\n");printf("printf("printf("printf("printf("5--逆置單鏈表\n");printf("6--有序鏈表插入\n");printf("7--有序鏈表刪除重復(fù)元素\n");printf("8--無(wú)序鏈表刪除重復(fù)元素\n");printf("9--兩鏈表合并并排序\n");printf("10--兩鏈表并集\n\n");printf("請(qǐng)選擇項(xiàng)號(hào):");scanf("%d",&j);fflush(stdin);printf("\n\n");case1:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_nohead_head(head);fflush(stdin);num=count_nohead(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);break;case2:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_head_head(head);fflush(stdin);num=count_head(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);break;case3:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_nohead_rail(head);fflush(stdin);num=count_nohead(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);break;case4:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_head_rail(head);fflush(stdin);num=count_head(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);break;case5:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_nohead_head(head);fflush(stdin);num=count_nohead(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);printf("\n逆置單鏈表\n\n");head=invertlink(head);num=count_nohead(head);break;case6:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_order_head(head);fflush(stdin);num=count_head(head);printf("單鏈表元素個(gè)數(shù)=%d\n",num);printf("\n輸入插入元素值:");ch=getchar();inser_order(ch,head);printf("\n元素插入后\n\n");num=count_head(head);printf("插入后單鏈表元素個(gè)數(shù)=%d\n",num);break;case7:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_order_head(head);fflush(stdin);num=count_head(head);printf("\n刪除重復(fù)元素后\n\n");delete(head);num=count_head(head);break;case8:printf("\n建立單鏈表\n\n");head=NULL;head=creatlink_head_rail(head);fflush(stdin);num=count_head(head);printf("\n刪除重復(fù)元素后\n\n");delete1(head);num=count_head(head);break;case9:printf("\n建立單鏈表a1\n\n");a1=NULL;a1=creatlink_order_head(a1);fflush(stdin);num=count_head(a1);printf("單鏈表a1元素個(gè)數(shù)=%d\n",num);printf("\n建立單鏈表a2\n\n");a2=NULL;a2=creatlink_order_head(a2);fflush(stdin);num=count_head(a2);printf("單鏈表a2元素個(gè)數(shù)=%d\n",num);c=(LINKLIST*)malloc(sizeof(LINKLIST));c->next=NULL;unite(a1,a2,c);num=count_head(c);printf("合并到單鏈表c中,元素個(gè)數(shù)=%d\n",num);break;case10:printf("\n建立單鏈表a1\n\n");a1=NULL;a1=creatlink_head_rail(a1);fflush(stdin);num=count_head(a1);printf("\n建立單鏈表a2\n\n");a2=NULL;a2=creatlink_head_rail(a2);fflush(stdin);num=count_head(a2);printf("\n\n兩鏈表交集運(yùn)算,結(jié)果保留在a1中\(zhòng)n\n");unionn(a1,a2);num=count_head(a1);}scanf("%d",&loop);printf("\n");}}四、哲學(xué)家就餐問(wèn)題(★★)可用循環(huán)鏈表實(shí)現(xiàn),鏈表數(shù)據(jù)類型為結(jié)構(gòu)體,記錄編號(hào)和相應(yīng)密碼,另外設(shè)標(biāo)志哲學(xué)家報(bào)數(shù)的前取他的密碼交給m,同時(shí)將他的編號(hào)放另一單鏈表numbsave保存。注意編號(hào)要從numbsave的最后節(jié)點(diǎn)插入。當(dāng)循環(huán)鏈表指向自身時(shí)停止比較,這個(gè)哲學(xué)家即是最后離開(kāi)的一個(gè)。依次打印出numbsave中的數(shù)即為按編號(hào)哲學(xué)家離開(kāi)的先后順序。#include"stdio.h"#include"conio.h"#include"stdlib.h"structphilosopher/*哲學(xué)家就餐結(jié)構(gòu)體*/number;/*編號(hào)*/intpassword;intmouth;/*嘴上報(bào)的數(shù)*/structphilosopher*next;philosopher*phead,*pend,*pp;numbsave/*存放離開(kāi)順序*/structnumbsave*next;structnumbsave*top=NULL,*numbnew,*numbthis;voidmain(void)intb=1,k,n,m,mouthm=1;clrscr();gotoxy(9,8);/*在文本窗口中設(shè)置光標(biāo)*/printf("pleaseinputnm:");phead=(structphilosopher*)malloc(sizeof(structphilosopher));pend=phead;phead->mouth=1;for(b=1;b<=n-1;b++)/*給哲學(xué)家分配隨機(jī)密碼*/k=random(20);/*k為0<k<20之間的數(shù)*/while(k<=0)k=random(20);pend->password=k;pp=(structphilosopher*)malloc(sizeof(structphilosopher));pend->next=pp;pend=pp;}pend->number=b;/*最后一位哲學(xué)家*/k=random(20);while(k<=0)k=random(20);pend->password=k;pend->next=phead;/*形成循環(huán)鏈表*/printf("\n\tphilosophernumbercorrespondencepasswordasfollowed:\n\t");pp=phead;for(b=1;b<=n;b++){printf("%d:%d\t",pp->number,pp->password);pp=pp->next;}while(pend->next!=pend){if(phead->mouth==m)/*如果嘴上報(bào)數(shù)和m相等,意味著一個(gè)人要走了*/phead->next->mouth=1;mouthm=1;/*下一位哲學(xué)家從一開(kāi)始報(bào)*/phead=pend->next=phead->next;/*兩個(gè)指針一定要相鄰*/numbnew=(structnumbsave*)malloc(sizeof(structnumbsave));m=pp->password;/*修改m的值為離開(kāi)哲學(xué)家numbnew->numsave=pp->number;if(top==NULL){top=numbnew;top->next=NULL;}/*離開(kāi)的哲學(xué)家的編號(hào)存入numbsave的最后節(jié)點(diǎn)*/while(numbthis->next!=NULL)numbthis=numbthis->next;numbthis->next=numbnew;numbnew->next=NULL;}free(pp);}phead=phead->next;/*讓phead指向下一個(gè)*/mouthm++;phead->mouth=mouthm;/*嘴巴說(shuō)我該報(bào)mouthm*/}}/*打印離桌順序*/printf("\n\tphilosopherawayfromcookdeskinthefollowqueue:\n\t");while(top!=NULL)top=top->next;}printf("%d",pend->number);/*這個(gè)千萬(wàn)別忘了,他是運(yùn)氣最好的一位*/printf("\n\tpressanykeytogoback......");while(!kbhit());/*檢查當(dāng)前按下的鍵*/}第二章棧和隊(duì)列的應(yīng)用一、八皇后問(wèn)題(★★★★)八皇后問(wèn)題是在8*8的國(guó)際象棋棋盤(pán)上,安放8個(gè)皇后,要求沒(méi)有一個(gè)皇后能夠吃掉任何其他一個(gè),即沒(méi)有兩個(gè)或兩個(gè)以上的皇后占據(jù)棋盤(pán)上的同一行、同一列或同一對(duì)角線。盡可能取小的列數(shù)。若當(dāng)前試探的列位置是安全的,即不與已放置的其它皇后沖突,則將該行的列位置保存在棧中,然后繼續(xù)在下一行上尋找安全位置;若當(dāng)前試探的列位置不安全,則用下一列進(jìn)行試探,當(dāng)8列位置試探完畢都未找到安全位置時(shí),就退?;厮莸缴弦恍?,修改棧頂保存的皇后位(1)置當(dāng)前行當(dāng)前列均為1;(2)while(當(dāng)前行號(hào)〈=8〉(5)放置皇后,將列號(hào)記入棧中,并將下一行置成當(dāng)前行,第一列置為當(dāng)前列;(7)退?;厮莸缴弦恍?,移去該行已放置的皇后,以該皇后所在列的下一列作為當(dāng)前列;enumboolean{false,true};enumbooleana[9],b[17],c[17];#include<stdio.h>voidmain(){voidprint(),movequeen(),eightqueen();eightqueen();}voideightqueen()for(i=2;i<=16;i++){if(i>=2&&i<=9)a[i-1]=true;b[i]=true;c[i]=true;}while(i>=1){/*當(dāng)i=0時(shí)終止循環(huán)*/while(j<=8){/*在當(dāng)前行i上尋找安全位置*/if(a[j]&&b[i+j]&&c[i-j+9])break;}if(j<=8){/*找到安全位置(i,j)*/a[j]=false;b[i+j]=false;c[i-j+9]=false;s[i]=j;/*皇后位置j入棧if(i==8){/*找到一個(gè)解,輸出一個(gè)解*/print();/*打印輸出一個(gè)解*/movequeen(i,j);/*移去位置(i,j)上的皇后*/i=i-1;j=s[i];/*退棧,回溯到上一個(gè)皇后*/movequeen(i,j);/*移去位置(i,j)上的皇后*/j++;/*修改棧頂皇后的位置*/}{i++;j=1;}/*準(zhǔn)備放置下一個(gè)皇后*/}i--;/*退棧*/movequeen(i,j);}}}}/***************************//*打印輸出一個(gè)解的函數(shù)*//**************************/voidprint(){for(k=1;k<=8;k++)printf("%4d",s[k]);printf("\n\n");}/***************************//*移去位置(i,j)上的皇后函數(shù)*//**************************/voidmovequeen(inti,intj){a[j]=true;b[i+j]=true;c[i-j+9]=true;}二、表達(dá)式求值問(wèn)題(★★)表達(dá)式求值是編譯系統(tǒng)中的一個(gè)基本問(wèn)題,目的是把人們平時(shí)書(shū)寫(xiě)的算術(shù)表達(dá)式變成計(jì)算機(jī)能夠理解并能正確求值的表達(dá)方法。表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一,也是棧和隊(duì)列應(yīng)用的一個(gè)典型例子。具體要求是:以字符序列的形式從終端輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式,利用給定的運(yùn)算符優(yōu)先關(guān)系,實(shí)現(xiàn)對(duì)算術(shù)四則運(yùn)算表達(dá)式的求值。為實(shí)現(xiàn)表達(dá)式求值,需要完成兩個(gè)步驟:2、利用隊(duì)列,將后綴表達(dá)式求值并輸出。#include<stdio.h>#defineStackSize100#defineQueueSize100/*隊(duì)列的相關(guān)操作*/typedefcharDataType;chardata[100];intfront,rear;}SeqQueue;/*定義隊(duì)列類型*/voidInitQueue(SeqQueue*Q)/*初始化隊(duì)列*/{Q->front=0;Q->rear=0;}intQueueEmpty(SeqQueue*Q)/*判空隊(duì)列*/{returnQ->rear==Q->front;}voidEnQueue(SeqQueue*Q,DataTypex)/*入隊(duì)列*/{if((Q->rear+1)%QueueSize==Q->front)printf("Queueoverflow");{Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}DataTypeDeQueue(SeqQueue*Q)/*出隊(duì)列*/{DataTypex;if(!QueueEmpty(Q))Q->front=(Q->front+1)%QueueSize;returnx;}}voidPrintQueue(SeqQueue*Q)/*打印隊(duì)列*/{intnum=Q->front;for(i=Q->front;i<=Q->rear;i++)printf("%c",Q->data[Q->front++]);Q->front=num;}/*棧的相關(guān)操作*/DataTypedata[100];}SeqStack;/*棧類型的定義*/voidInitStack(SeqStack*S)/*初始化棧*/{S->top=-1;}voidPush(SeqStack*S,DataTypex)/*入棧*/{if(S->top==StackSize-1)printf("stackoverflow");{S->top=S->top+1;S->data[S->top]=x;}}DataTypePop(SeqStack*S)/*出棧*/{if(S->top==-1)printf("stackunderflow");returnS->data[S->top--];}DataTypeGetTop(SeqStack*S)/*取棧頂元素*/{if(S->top==-1)printf("stackempty");returnS->data[S->top];}DataTypeCPostExp(SeqQueue*Q)/*后綴表達(dá)式求值*/{SeqStackVS,*S;S=&VS;InitStack(S);while(!QueueEmpty(Q)){ch=DeQueue(Q);if(ch>='0'&&ch<='9')Push(S,ch-'0');{y=Pop(S);x=Pop(S);switch(ch){case'+':Push(S,x+y);break;case'-':Push(S,x-y);break;case'*':Push(S,x*y);break;case'/':Push(S,x/y);break;}}}returnGetTop(S);}voidCTPostExp(SeqQueue*Q)/*中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換*/{SeqStackOS;/*運(yùn)算符棧*/SeqStack*S;S=&OS;InitStack(S);/*初始化棧*/Push(S,'#');do/*掃描中綴表達(dá)式*/{c=getchar();{case'':break;/*去除空格符*/EnQueue(Q,c);break;case'(':Push(S,c);break;t=Pop(S);if(t!='('&&t!='#')EnQueue(Q,t);}while(t!='('&&S->top!=-1);break;while(Priority(c)<=Priority(GetTop(S))){t=Pop(S);EnQueue(Q,t);}Push(S,c);break;}/*EndSwitch*/}while(c!='#');}intPriority(DataTypeop){switch(op){case'#':return(0);case'+':return(1);case'/':return(2);}}voidmain(){SeqQueue*Q;SeqQueuePostQ;/*定義隊(duì)列,存放后綴表達(dá)式*/Q=&PostQ;InitQueue(Q);/*初始化隊(duì)列*/printf("請(qǐng)輸入表達(dá)式,并以#鍵結(jié)束!");CTPostExp(Q);/*調(diào)用轉(zhuǎn)換函數(shù)將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式*/PrintQueue(Q);/*輸出后綴表達(dá)式*/s=CPostExp(Q);printf("表達(dá)式結(jié)果為");printf("s=%d",s);}三、馬踏棋盤(pán)(★★★)“馬踏棋盤(pán)”又叫“馬的遍歷”、“騎士巡游”或者“騎士游歷”,它是由上世紀(jì)中葉被歐洲的幾位數(shù)學(xué)家提出的,后來(lái)由著名大數(shù)學(xué)家歐拉將各種解法歸納總結(jié),系統(tǒng)的解決了這個(gè)問(wèn)題。遍歷棋盤(pán),即達(dá)到棋盤(pán)上的每一格,并且每格只能到達(dá)一次。1.貪婪算法(請(qǐng)同學(xué)自己實(shí)現(xiàn))貪婪算法就是一步一個(gè)最優(yōu)解,每步都是有去無(wú)回的架勢(shì),做出這些最優(yōu)解的策略號(hào)稱貪婪準(zhǔn)在設(shè)計(jì)程序解決“騎士游歷”問(wèn)題時(shí),可以發(fā)現(xiàn),外層格子比在棋盤(pán)中心附近的格子更難棋盤(pán)上所有的格都置為零。以后,馬跳到哪個(gè)格,就將馬跳躍的步數(shù)記錄在相應(yīng)的空格里。我們?cè)O(shè)置一組坐標(biāo)增量來(lái)描述這八個(gè)條約方向:①(1,2)②(2,1)③(2,-1)④(1,-2)⑤(-1,-2)⑥(-2,-1)⑦(-2,1)⑧(-1,2)(3)馬的跳躍方向的表示一個(gè)方向,在不出界的情況下,如果A(NI,NJ)=0,則表示該方向的前方有通路,可以繼續(xù)向前跳躍。如果A(NI,NJ)>0,則表示該格已經(jīng)走過(guò)了,不能再走。放棄該方向,并轉(zhuǎn)向下一個(gè)方向#include"stdio.h"#include"conio.h"}ma[N*N+1]={{0,0,0}};voidpush(inta[][N],inti,intj,intm)ma[top].y=j;ma[top].step=m;a[i][j]=++top;}intpop(inta[][N])a[ma[top].x][ma[top].y]=0;ma[top].x=0;ma[top].y=0;temp=ma[top].step+1;ma[top].step=0;returntemp;}introw[]={-1,-2,-2,-1,1,2,2,1};intt,ti=i,tj=j,count=0;for(t=0;t<8;t++){ti+=row[t];tj+=col[t];if(judge(ti,tj,a))count++;/*Howmanywaysforthehorsecanjumpforsecondtime.*/ti-=row[t];tj-=col[t];}returncount;}intjudge(inti,intj,inta[][N]){if(i>=0&&j>=0&&i<N&&j<N&&a[ireturn0;}sort(inta[8],intb[8])for(i=1;i<8;i++){if(min>a[i]&&a[i]>-1&&a[i]<8){min=a[i];/*FindtheMin-}}returnt;}voiddisp(inta[][N])for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%4d",a[i][j]);printf("\n");}}voidhorse(intx,inty){inti=x,j=y,min,ti,tj,t,temp=0,flag=0,temp1=0;intcount[8],num[8]={0};intcol[]={2,1,-1,-2,-2,-1,1,2};introw[]={-1,-2,-2,-1,1,2,2,1};inta[N][N]={{0}};for(x=0;x<8;x++)count[x]=8;push(a,i,j,0);while(top<N*N)for(x=0;x<8;x++)count[x]=8;for(t=temp;t<8;t++,temp1++){ti+=row[t];tj+=col[t];if(judge(ti,tj,a)){count[temp1]=jump(ti,tj,a);num[temp1]=t;}ti-=row[t];tj-=col[t];}min=sort(count,num);ti+=row[min];tj+=col[min];/*Howmanywaysforthehorsecanpush(a,ti,tj,min);}temp=pop(a);/*Returnthestack*/j=ma[top-1].y;}}printf("\n\n");disp(a);}main()printf("PleaseentertheX-position:");scanf("%d",&x);printf("PleaseentertheY-position:");scanf("%d",&y);if(x>N||y>N||x<1||y<1)printf("Error!Tryitagain,X(1~%d),Y(1~%d)\n",N,N);}while(x>N||y>N||x<1||y<1);horse(x-1,y-1);getch();}四、漢諾塔問(wèn)題(★★★)傳說(shuō)所羅門(mén)廟里有一個(gè)塔臺(tái),臺(tái)上有3根用鉆石做成的標(biāo)號(hào)為A、B、C的柱子,在A柱上放著64個(gè)金盤(pán),每一個(gè)金盤(pán)都比下面的略小一點(diǎn)。把A柱上的金盤(pán)全部移到C柱上的那一天就是世界末日。移動(dòng)的條件是,一次只能移動(dòng)一個(gè)金盤(pán),移動(dòng)過(guò)程中大金盤(pán)不能放在小金盤(pán)上面。廟里的僧人一直在移個(gè)不停。因?yàn)槿恳苿?dòng)次數(shù)是264-1,如果每秒移動(dòng)一次的話,需要500億年。漢諾塔盤(pán)子之間的移動(dòng)過(guò)程很復(fù)雜與煩瑣,但規(guī)律性卻很強(qiáng)。使用遞歸調(diào)用技術(shù)來(lái)解決這個(gè)移動(dòng)過(guò)程,先得找到一個(gè)遞歸調(diào)用模型。想要得到漢諾塔問(wèn)題的簡(jiǎn)單解法,著眼點(diǎn)應(yīng)該是移動(dòng)A桿最底部的大盤(pán),而不是其頂部的小盤(pán)。不考慮64個(gè)盤(pán)而考慮N個(gè)盤(pán)的一般情況。要想將A桿上的N個(gè)各桿的作用有所不同。這樣,原問(wèn)題被轉(zhuǎn)換為與原問(wèn)題相同性質(zhì)的、規(guī)模小一些的新問(wèn)題。即:HANOI(N,A,B,C)可轉(zhuǎn)化為HANOI(N-1,A,C,B)與HANOI(N-1,B,A,C)盤(pán)數(shù)為0為止,因?yàn)檫@時(shí)已無(wú)盤(pán)可移了。這就是需要找的遞歸調(diào)用模型。采用非遞歸算法可以用棧實(shí)現(xiàn)。采用遞歸算法實(shí)現(xiàn),其流程為:#include<stdlib.h>#include<string.h>#include<stdio.h>/*#defineERROR_DEBUG*/#ifdefERROR_DEBUG#defineerror(x)error_debug(x)#definereport()report_debug()#defineiniterror()initerror_debug()char*err[10];voidiniterror_debug(){for(i=0;i<10;i++)err[i]=NULL;}voiderror_debug(char*a){return;err[errs]=(char*)malloc(strlen(a)+1);strcpy(err[errs],a);printf(a);}voidreport_debug(){return;for(i=0;i<errs;i++){printf(err[i]);free(err[i]);}}#else#defineerror(x)#definereport()#defineiniterror()#endif/*************************************/#defineSTACK_SIZE31{intdata[STACK_SIZE];intclear(stack*a);intcreate(stack**a);intpush(stack*a,intdata);intpop(stack*a,int*data);intgettop(stack*a,int*data);intdispose(stack*a);intpop(stack*a,int*data){{*data=a->data[--a->top];}{error("pop(stack*,int*):stackempty!\n");return0;}}intpush(stack*a,intdata){if(a->top<STACK_SIZE){a->data[a->top++]=data;}{error("push(stack*,int):stackfull!\n");return0;}}intcreate(stack**a){*a=(stack*)malloc(sizeof(stack));returnclear(*a);{error("create(stack**):createerror!Notenoughmomery!\n");return0;}}intclear(stack*a){{a->top=0;}{error("clear(stack*):stacknotexist!\n");return0;}}intgettop(stack*a,int*data){{*data=a->data[a->top-1];}{error("gettop(stack*,int*):stackempty!\n");return0;}}intdispose(stack*a){{free(a);}{error("dispose(stack*):stacknotexist!\n");return0;}}/**************************************/#include<graphics.h>#include<dos.h>#defineMAX_LEVELSTACK_SIZEintposition[MAX_LEVEL+1];stack*theStack[3];{{intgdriver=DETECT,gmode,errorcode;/*initializegraphicsmode*/initgraph(&gdriver,&gmode,"");setfillstyle(1,7);}for(i=0;i<3;i++)if(!create(&theStack[i]))break;{for(;i>=0;i--)dispose(theStack[i]);error("initgame(int):cannotinitstack!\n");return0;}depth=d;for(i=d;i;i--){push(theStack[0],i);{y=200+100-theStack[0]->top*(h+1);w=i*10;x=150-w/2;setcolor(i);setfillstyle(1,i);bar(x,y,x+w,y+h);}position[i]=0;}{setcolor(15);for(i=0;i<3;i++)rectangle(150+i*150-1,120,150+i*150+1,300);line(50,300,500,300);}}{for(;i>=0;i--)dispose(theStack[i]);printf("report:");report();closegraph();}voidshow(intp,intfrom,intto){x,y;newx,newy;h=5;w=p*10;y=200+100-(theStack[from]->top+1)*(h+1);x=from*150+150-w/2;newx=to*150+150-w/2;newy=200+100-theStack[to]->top*(h+1);while(y>100){setcolor(0);setfillstyle(1,0);bar(x,y,x+w,y+h);y-=(h+1);setcolor(15);rectangle(150+from*150-1,120,150+from*150+1,300);setcolor(p);setfillstyle(1,p);bar(x,y,x+w,y+h);delay(10);}w

溫馨提示

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

評(píng)論

0/150

提交評(píng)論