《應(yīng)用程序的設(shè)計(jì)》課程設(shè)計(jì)指導(dǎo)書

./《應(yīng)用程序綜合》課程設(shè)計(jì)指導(dǎo)書信息與計(jì)算機(jī)學(xué)院二○一九年目錄TOC\o"1-2"\h\z\u一前言11應(yīng)用程序綜合課程設(shè)計(jì)目的及任務(wù)12應(yīng)用程序綜合課程設(shè)計(jì)培養(yǎng)目標(biāo)13應(yīng)用程序綜合課程設(shè)計(jì)選用教材及主要參考書24應(yīng)用程序綜合課程設(shè)計(jì)實(shí)驗(yàn)環(huán)境2二應(yīng)用程序綜合課程設(shè)計(jì)要求31采用項(xiàng)目小組開發(fā)模式32課程設(shè)計(jì)報(bào)告要求4三課程設(shè)計(jì)備選題目61數(shù)據(jù)結(jié)構(gòu)CAI系統(tǒng)62理工大學(xué)計(jì)算機(jī)學(xué)院學(xué)生獎(jiǎng)學(xué)金評(píng)定系統(tǒng)7四參考樣例9五課程設(shè)計(jì)考核261成績?cè)u(píng)定標(biāo)準(zhǔn)262項(xiàng)目組成績考核273項(xiàng)目組成員個(gè)人成績考核27.一前言1應(yīng)用程序綜合課程設(shè)計(jì)目的及任務(wù)《應(yīng)用程序綜合課程設(shè)計(jì)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的重要實(shí)踐性課程。此課程目的目的在于培養(yǎng)學(xué)生具備需求分析、設(shè)計(jì)、開發(fā)、測(cè)試和應(yīng)用的職業(yè)技能,具備綜合運(yùn)用計(jì)算機(jī)軟硬件理論和技術(shù),分析和解決計(jì)算機(jī)領(lǐng)域相關(guān)工程問題的能力。課程將理論知識(shí)和實(shí)際應(yīng)用問題進(jìn)行有機(jī)結(jié)合,提高學(xué)生程序設(shè)計(jì)、程序調(diào)試及項(xiàng)目開發(fā)能力,為后續(xù)課程：操作系統(tǒng)、軟件工程,編譯原理等課程的學(xué)習(xí)奠定必要的實(shí)踐基礎(chǔ)?！稇?yīng)用程序綜合課程設(shè)計(jì)》是利用數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、語言理論和實(shí)驗(yàn)課中學(xué)到的編程知識(shí)和編程技巧,通過布置具有一定難度、一定編程量的綜合課程設(shè)計(jì)題目,利用C語言作為開發(fā)工具,使學(xué)生通過課程設(shè)計(jì)掌握高級(jí)編程語言的知識(shí)和編程技術(shù),掌握程序設(shè)計(jì)的思想和方法,初步具備利用計(jì)算機(jī)求解實(shí)際問題的能力。給定兩個(gè)題目：1數(shù)據(jù)結(jié)構(gòu)CAI系統(tǒng)2理工大學(xué)信息與計(jì)算機(jī)學(xué)院學(xué)生獎(jiǎng)學(xué)金評(píng)定系統(tǒng)。學(xué)生可根據(jù)自身情況完成部分或全部題目；如有自備題目,必須經(jīng)指導(dǎo)教師審查通過方可實(shí)施,否則不計(jì)入成績。通過《應(yīng)用程序綜合課程設(shè)計(jì)》課程的學(xué)習(xí),能夠幫助學(xué)生加深理解數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、C語言基本概念,達(dá)到培養(yǎng)學(xué)生良好程序設(shè)計(jì)的習(xí)慣和運(yùn)用C語言編寫程序解決實(shí)際問題的能力,使學(xué)生學(xué)會(huì)把書本知識(shí)用于解決實(shí)際問題,起到深化理解和靈活掌握教學(xué)容的目的。課程同時(shí)使學(xué)生在程序設(shè)計(jì)方法及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2應(yīng)用程序綜合課程設(shè)計(jì)培養(yǎng)目標(biāo)1基本要求掌握C語言程序設(shè)計(jì)的方法、數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學(xué)理論知識(shí),熟悉C程序的開發(fā)環(huán)境及C程序的調(diào)試過程,鞏固和加深對(duì)理論課中知識(shí)的理解,提高學(xué)生對(duì)所學(xué)知識(shí)的綜合運(yùn)用能力。2具有下列基本技能=1\*GB3①具備查閱參考資料、手冊(cè)的自學(xué)能力,通過獨(dú)立思考深入鉆研問題,學(xué)會(huì)自己分析、解決問題。=2\*GB3②通過對(duì)所選題目方案分析比較,確立方案,編制程序與調(diào)試程序。=3\*GB3③能熟練調(diào)試程序,在教師的指導(dǎo)下,完成課題任務(wù)。=4\*GB3④根據(jù)個(gè)人的設(shè)計(jì)調(diào)試過程,按課程設(shè)計(jì)報(bào)告的要求撰寫設(shè)計(jì)報(bào)告。3應(yīng)用程序綜合課程設(shè)計(jì)選用教材及主要參考書教材：《應(yīng)用程序綜合課程設(shè)計(jì)》指導(dǎo)書參考書：[1]譚浩強(qiáng).C程序設(shè)計(jì)〔第四版.清華大學(xué),20XX6月1日[2]譚浩強(qiáng).C程序設(shè)計(jì)〔第四版學(xué)習(xí)輔導(dǎo).清華大學(xué),20XX6月1日[3]丁亞濤.C語言程序設(shè)計(jì)實(shí)訓(xùn)與考試指導(dǎo)〔第2版〔附光盤.高等教育,20XX8月1日[4]丁亞濤.C語言程序設(shè)計(jì)〔第2版.高等教育,20XX8月1日[5]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)<C語言版>清華大學(xué),1997年4月1日[6]盤林.離散數(shù)學(xué).人民郵電,20XX4月1日4應(yīng)用程序綜合課程設(shè)計(jì)實(shí)驗(yàn)環(huán)境PC機(jī)、Windows操作系統(tǒng)。VisualC++6.0或WIN-TC或TURBOC等編譯系統(tǒng)。二應(yīng)用程序綜合課程設(shè)計(jì)要求1采用項(xiàng)目小組開發(fā)模式要求學(xué)生采用"項(xiàng)目小組"的形式,結(jié)合具體的開發(fā)項(xiàng)目進(jìn)行設(shè)計(jì)。分析設(shè)計(jì)過程可以采用面向?qū)ο蠡蛎嫦蜻^程分析設(shè)計(jì)。具體要求如下：1.班級(jí)按項(xiàng)目小組進(jìn)行分組,每組2-5人?？梢匀我膺x擇兩種分組模式：一按"主程序員"組織軟件開發(fā)小組,程序員小組的人數(shù)應(yīng)視任務(wù)的大小和完成任務(wù)的時(shí)間機(jī)時(shí)定,一般是２～人。為降低系統(tǒng)開發(fā)過程的復(fù)雜性,小組程序員之間的任務(wù)界面必須清楚并盡量簡化。"主程序員"應(yīng)該是"超級(jí)程序員"。其他成員,包括程序員、后備工程師等,是主程序員的助手。主程序員負(fù)責(zé)規(guī)劃、協(xié)調(diào)和審查小組的全部技術(shù)活動(dòng)。程序員負(fù)責(zé)軟件的分析和開發(fā)。后備工程師是主程序員的助手,必要時(shí)能代替主程序員領(lǐng)導(dǎo)小組的工作并保持工作的連續(xù)性。二按"無我程序設(shè)計(jì)"建立軟件開發(fā)小組。程序員小組的人數(shù)應(yīng)視任務(wù)的大小和完成任務(wù)的時(shí)間機(jī)時(shí)定,一般是２～5人。組織形式強(qiáng)調(diào)組成員人人平等,組問題均由集體討論決定。這種組織形式有利于集思廣益、互相取長補(bǔ)短,但工作效率比較低。軟件開發(fā)各個(gè)階段所需要的技術(shù)人員類型、層次和數(shù)量是不同的。軟件項(xiàng)目的計(jì)劃與分析階段只需要少數(shù)人,主要是系統(tǒng)分析員、從事軟件系統(tǒng)論證和概要設(shè)計(jì)的軟件高級(jí)工程師和項(xiàng)目高級(jí)管理人員。概要設(shè)計(jì)時(shí)要增加一部分高級(jí)程序員,詳細(xì)設(shè)計(jì)時(shí),要增加軟件工程師和程序員,在編碼和測(cè)試階段還要增加程序員、軟件測(cè)試員。在此過程中軟件開發(fā)管理人員和各類專門人員逐漸增加,到測(cè)試階段結(jié)束時(shí),軟件項(xiàng)目開發(fā)人員的數(shù)量達(dá)到頂峰。秘書負(fù)責(zé)維護(hù)和軟件配置中的文檔、源代碼、數(shù)據(jù)及所依附的各種磁介質(zhì)；規(guī)并收集軟件開發(fā)過程中的數(shù)據(jù)；規(guī)并收集可重用軟件,對(duì)它們分類并提供檢索機(jī)制；協(xié)助軟件開發(fā)小組準(zhǔn)備文檔,對(duì)項(xiàng)目中的各種參數(shù),如代碼行、成本、工作進(jìn)度等,進(jìn)行估算；參與小組的管理、協(xié)調(diào)和軟件配置的評(píng)估。2.每個(gè)項(xiàng)目小組選出一名項(xiàng)目組長,由項(xiàng)目組長召集項(xiàng)目組成員討論、選定開發(fā)項(xiàng)目,同一項(xiàng)目小組同學(xué)采用同一個(gè)課程設(shè)計(jì)題目。項(xiàng)目組長的課程設(shè)計(jì)成績有加分。項(xiàng)目開發(fā)的每項(xiàng)任務(wù)要落實(shí)到人且規(guī)定該任務(wù)的起止日期和時(shí)間。3.需求分析,完成需求技術(shù)報(bào)告,全體成員參加需求討論,修訂并評(píng)審需求分析人員的需求分析報(bào)告,確定系統(tǒng)的需求分析模型。4.項(xiàng)目組每位人員均需要參加系統(tǒng)總體設(shè)計(jì)。5.每一位同學(xué)均需按照需求分析任務(wù)書和概要設(shè)計(jì)說明的要求,獨(dú)立該項(xiàng)目2個(gè)以上模塊的詳細(xì)設(shè)計(jì)、編碼、測(cè)試工作。項(xiàng)目小組應(yīng)共同進(jìn)行各模塊詳細(xì)設(shè)計(jì)的評(píng)審工作。6.編程語言、數(shù)據(jù)庫平臺(tái)可以由項(xiàng)目小組根據(jù)項(xiàng)目性質(zhì)選擇,同一個(gè)項(xiàng)目的編程語言與數(shù)據(jù)庫平臺(tái)應(yīng)一致。項(xiàng)目提交時(shí),應(yīng)將所有模塊集成在一起。不能集成在一起運(yùn)行的,酌情扣分。7.每一位同學(xué)完成自己所負(fù)責(zé)模塊的測(cè)試工作,并完成測(cè)試報(bào)告。8.每個(gè)項(xiàng)目小組必須提交一份完整的項(xiàng)目技術(shù)文檔,文檔容包含《需求分析說明書》、《概要設(shè)計(jì)說明書》、《詳細(xì)設(shè)計(jì)說明書》、《測(cè)試報(bào)告>與《項(xiàng)目開發(fā)日志》等部分,《項(xiàng)目可行性研究報(bào)告》可以選作。所有文檔必須符合《計(jì)算機(jī)開發(fā)規(guī)》。9.每一位同學(xué)應(yīng)提交一份開發(fā)日志,詳細(xì)記錄課程設(shè)計(jì)過程中出現(xiàn)的問題、解決方案及課程設(shè)計(jì)心得,務(wù)必真實(shí)詳盡。2課程設(shè)計(jì)報(bào)告要求應(yīng)用程序綜合課程設(shè)計(jì)最后以小組為單位提交一份紙質(zhì)版報(bào)告,報(bào)告提交時(shí)間咨詢各自指導(dǎo)教師為準(zhǔn)。應(yīng)用程序綜合課程設(shè)計(jì)報(bào)告格式參考報(bào)告模板,要求有統(tǒng)一的報(bào)告封面、任務(wù)書、日志、目錄、正文以及最后的設(shè)計(jì)心得體會(huì)等容,正文部分排版基本要求為五號(hào)宋體,對(duì)于每一個(gè)所選定的題目報(bào)告需要包含以下容：[需求分析]簡要說明程序設(shè)計(jì)的任務(wù),程序要做什么。明確規(guī)定以下容：=1\*GB3①輸入的形式和輸入值的圍；=2\*GB3②輸出的形式；=3\*GB3③程序所能達(dá)到的功能；=4\*GB3④測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。[概要設(shè)計(jì)]說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次〔調(diào)用關(guān)系。[詳細(xì)設(shè)計(jì)]實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型,對(duì)每個(gè)操作寫出偽碼算法；對(duì)主程序和其他模塊也寫出偽碼算法〔偽碼算法的詳細(xì)程度為按照偽碼算法可以在計(jì)算機(jī)鍵盤直接輸入高級(jí)程序設(shè)計(jì)語言程序；畫出函數(shù)的調(diào)用關(guān)系圖。[測(cè)試分析]容包括：=1\*GB3①測(cè)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論與分析；此部分詳細(xì)給出說明=2\*GB3②算法的時(shí)空分析和改進(jìn)設(shè)想；=3\*GB3③經(jīng)驗(yàn)和體會(huì)。[使用說明]說明如何使用程序,列出每一步的操作步驟。[測(cè)試結(jié)果]列出測(cè)試結(jié)果,包括輸入和輸出。測(cè)試數(shù)據(jù)應(yīng)該完整和嚴(yán)格。[附錄]列出程序文件名的清單以及帶注釋的源程序。三課程設(shè)計(jì)備選題目1數(shù)據(jù)結(jié)構(gòu)CAI系統(tǒng)問題描述隨著多媒體計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展,應(yīng)用多媒體CAI技術(shù)已經(jīng)成為廣大教育工作者改革教學(xué)方法,提高教學(xué)質(zhì)量的首選途徑。多媒體演示課件是多媒體教育發(fā)展到一定階段的產(chǎn)物,也是目前多媒體教育改革的一個(gè)標(biāo)志。利用多媒體演示課件,可以代替?zhèn)鹘y(tǒng)的黑板板書,而且還能把各種與教材有關(guān)的多媒體素材融合在演示課件中,在增加知識(shí)信息的同時(shí),大大提高了課堂效率?；疽笤跀?shù)據(jù)結(jié)構(gòu)這門課程中,最難理解的就是其中的各類算法,為了加深用戶對(duì)算法的理解,多媒體CAI加入大量的算法演示。這樣有助于學(xué)生更加方便得學(xué)好這門課程。以數(shù)據(jù)結(jié)構(gòu)教材中的容為例,設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的CAI〔計(jì)算機(jī)輔助教學(xué)系統(tǒng),用菜單的形式選擇各項(xiàng)功能?；疽笠娤卤恚焊呒?jí)功能可設(shè)計(jì)圖形化界面的形式顯示算法的執(zhí)行過程；可擴(kuò)充更多教學(xué)容以及算法。1線性表的操作算法分別用數(shù)組和鏈表作為存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)線性表的插入、刪除、查找、排序、合并等操作2棧的應(yīng)用使用棧實(shí)現(xiàn)算術(shù)表達(dá)式求值的算符優(yōu)先算法3字符串的查找替換編寫字符串的模式匹配程序,實(shí)現(xiàn)字符串的查找替換功能4二叉樹的操作算法實(shí)現(xiàn)二叉樹的常用操作算法：包括二叉樹的建立、遍歷、求高度、線索化等操作5Huffman編碼與譯碼輸入若干個(gè)權(quán),建立Huffman樹,并進(jìn)行Huffman編碼與譯碼6圖的操作算法實(shí)現(xiàn)圖的常用操作算法：包括建立圖的存儲(chǔ)結(jié)構(gòu)、深度優(yōu)先搜索和廣度優(yōu)先搜索,求圖的最小生成樹、拓?fù)渑判?、最短路徑?查找算法的實(shí)現(xiàn)實(shí)現(xiàn)二分查找、二叉排序樹的操作算法8排序算法的實(shí)現(xiàn)多種排序算法的實(shí)現(xiàn)2理工大學(xué)計(jì)算機(jī)學(xué)院學(xué)生獎(jiǎng)學(xué)金評(píng)定系統(tǒng)問題描述為貫徹黨和國家的教育方針,激勵(lì)廣大學(xué)生樹立專業(yè)志向、培養(yǎng)學(xué)科興趣、激發(fā)探究熱忱、發(fā)揚(yáng)創(chuàng)新精神,培育全面發(fā)展的卓越人才,樹立新時(shí)代人才典,引領(lǐng)廣大學(xué)生健康成才,理工大學(xué)結(jié)合學(xué)校實(shí)際情況,面向?qū)W生有多種獎(jiǎng)學(xué)金發(fā)放和評(píng)比制度。獎(jiǎng)學(xué)金的評(píng)定應(yīng)堅(jiān)持公開、公平、公正的原則。實(shí)際評(píng)定中因?yàn)榉N類繁多,評(píng)定條件多變,因此需要有一個(gè)更規(guī)化、科學(xué)化的評(píng)定系統(tǒng)為學(xué)生和管理人員服務(wù)?；疽笳鎸?shí)了解理工大學(xué)信息與計(jì)算機(jī)學(xué)院學(xué)生本科學(xué)生可以參與的獎(jiǎng)學(xué)金種類以及評(píng)比條件,選擇合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)和處理,分級(jí)管理數(shù)據(jù)。系統(tǒng)可以按照要求自動(dòng)篩選獲得獎(jiǎng)學(xué)金的學(xué)生。測(cè)試數(shù)據(jù)不少于10人。高級(jí)功能考慮系統(tǒng)的可擴(kuò)展性,例如此系統(tǒng)是否可以方便的為其他學(xué)院用戶使用；是否為研究生獎(jiǎng)學(xué)金預(yù)留了空間；如有弄虛作假者,系統(tǒng)是否做相關(guān)處理等。四參考樣例[課程設(shè)計(jì)報(bào)告示例：迷宮問題]題目：編制一個(gè)求解迷宮通路的程序。一．需求分析〔1以二維數(shù)組迷宮[M+2][N+2]表示迷宮,其中：迷宮[0][J]和迷宮[M+1][J]〔0≤J≤N+1及迷宮[我][0]和迷宮[我][N+1]〔第一0≤≤M+1為添加的一圈障礙。數(shù)組中以元素值為0表示通路,1表示障礙。限定迷宮的大小M,N≤10?！?用戶以文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)M和列數(shù)N；從第2行至第M+1行〔每行N個(gè)數(shù)為迷宮值,同一行中的兩個(gè)數(shù)字之間用空白字符相隔?！?迷宮的入口位置和出口位置可由用戶隨時(shí)設(shè)定?！?若設(shè)定的迷宮存在通路,則以長方陣形式將迷宮及其通路輸出到標(biāo)準(zhǔn)輸出文件〔即終端上,其中,字符"#"表示障礙,字符"*"表示路徑上的位置,字符""表示"死胡同",即曾途經(jīng)然而不能到達(dá)出口的位置,余者用空格符印出。若設(shè)定的迷宮不存在通路,則報(bào)告相應(yīng)信息?！?本程序只求出一條成功的通路。然而,只需要對(duì)迷宮求解的函數(shù)作小量修改,便可求得全部路徑?！?測(cè)試數(shù)據(jù)見原題,當(dāng)入口位置為〔1,1,出口位置為〔9,8時(shí),輸出數(shù)據(jù)應(yīng)為：表3-1輸出數(shù)據(jù)表**##*##**###*####***#***#***#*#####*####*###**〔7程序執(zhí)行的命令為：1創(chuàng)建迷宮；2求解迷宮；3輸出迷宮的解。二．概要設(shè)計(jì)1．設(shè)定棧的抽象數(shù)據(jù)類型定義為：ADTstack{數(shù)據(jù)對(duì)象：D={ai|ai∈charset,i=1,2,……,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2……,n}基本操作：InitStack<&S>操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack<&S>初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack<&S>初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength<&S>初始條件：棧S已存在。操作結(jié)果：返回棧S的長度。StackEmpty<&S>初始條件：棧S已存在。操作結(jié)果：若S為空棧,則返回TRUE,否則返回FALSE。GetTop<S,&e>初始條件：棧S已存在。操作結(jié)果：若棧S不空,則以e返回棧頂元素。Push<&S,e>初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop<&S,&e>初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素,并以e返回其值。StackTraverse<S,visit<>>初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit<>.}ADTstack2．設(shè)定迷宮的抽象數(shù)據(jù)類型為：ADTmaze{數(shù)據(jù)對(duì)象：D={ai,j|ai,j∈{‘’、‘#’、‘’、‘*’},0≤i≤m+1,0≤j≤n+1,m,n≤10}數(shù)據(jù)關(guān)系：R={ROW,COL}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,……,m+1,j=0,……,n+1}COL={<ai,j-1,ai,j>|ai,j-1,ai,j∈D,i=0,……,m+1,j=1,……,n+1}基本操作：InitMaze<&M,a,row,col>初始條件：二維數(shù)組a[row+2][col+2]已存在,其中自第1行至第row+1行、每行中自第1列至第col+1列的元素已有值,并且以值0表示通路,以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組,以空白字符表示通路,以字符‘#’表示障礙,并在迷宮四周加上一圈障礙。MazePath<&M>初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路,則按如下規(guī)定改變迷宮M的狀態(tài)：以字符"*"表示路徑上的位置,字符""表示"死胡同"；否則迷宮的狀態(tài)不變。PrintMaze<M>初始條件：迷宮M已存在。操作結(jié)果：以字符形式輸出迷宮。}ADTmaze;3.本程序包含三個(gè)模塊1主程序模塊voidmain<>{初始化do{接受命令；處理命令；}while<命令！="退出">；}2棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型3迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型各模塊之間的調(diào)用關(guān)系如下：主程序模塊迷宮模塊棧模塊4．求解迷宮中一條通路的偽碼算法：設(shè)定當(dāng)前位置的初值為入口位置；do{若當(dāng)前位置可通,則{將當(dāng)前位置插入棧頂；//納入路徑若該位置是出口位置,則結(jié)束；//求得路徑存放在棧中否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則{若棧不空且棧位置尚有其他方向未被探索,則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通,則{刪去棧頂位置；//后退一步,從路徑中刪去該通道塊,若棧不空,則重新測(cè)試新的棧頂位置,直到找到一個(gè)可通的相鄰塊或出棧至棧空；}}}while<棧不空>,{?？照f明沒有路徑存在}三．詳細(xì)設(shè)計(jì)1．坐標(biāo)位置類型typedefstruct{intr,c;//迷宮中行、列的圍}postype;2．迷宮類型typedefstruct{intm,n;chararr[RANGE][RANGE];//各位置取值‘’,‘#’,‘’或‘*’}mazetype;voidinitmaze<mazetype&maze,inta[][],introw,intcol>//按照用戶輸入的row行和col列的二維數(shù)組〔元素值為0或1//設(shè)置迷宮的初值,包括加上邊緣一圈的值boolmazepath<mazetype&maze,postypestart,postypeend>//求解迷宮maze中,從入口start到出口end的一條路徑//若存在,則返回TRUE；否則返回FALSEvoidprintmaze<mazetypemaze>//將迷宮以字符型方陣的形式輸出到標(biāo)準(zhǔn)輸出文件上3．棧類型typedefstruct{intstep;//當(dāng)前位置在路徑上的"序號(hào)"postypeseat;//當(dāng)前的坐標(biāo)位置directivetypedi;//往下一坐標(biāo)位置的方向}Elemtype;//棧的元素類型typedefstructnodetype{elemtypedata;nodetype*next;}nodetype,*linktype;//結(jié)點(diǎn)類型,指針類型typedefstruct{linktypetop;intsize;}stack;//棧類型棧的基本操作設(shè)置如下：voidinitstack<stack&S>//初始化,設(shè)S為空?！睸.top=NULLvoiddestroystack<stack&S>//銷毀棧S,并釋放所占空間voidclearstack<stack&S>//將S清為空棧intstacklength<stackS>//返回棧S的長度S.sizestatusstackempty<stackS>//若S為空棧〔S.top==NULL,則返回TRUE;否則返回FALSEstatusgettop<stacks,Elemtypee>//若棧S不空,則以e帶回棧頂元素并返回TRUE,否則返回FALSE;statuspush<stack&S,Elemtypee>//若分配空間成功,則在S的棧頂插入新的棧頂元素e,并返回TRUE,//否則棧不變,并返回FALSEstatuspop<stack&S,Elemtype&e>//若棧不空,則刪除S的棧頂元素并以e帶回其值,且返回TRUE//否則返回FALSEvoidstacktraverse<stacks,status<*visit><Elemtypee>>//從棧底到棧頂依次對(duì)S中的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit其中部分操作的算法：statuspush<stack&S,Elemtypee>{//若分配空間成功,則在S的棧頂插入新的棧頂元素e,并返回TRUE；//否則棧不變,并返回FALSEif<Makenode<p,e>>{p^.next=s.top;s.top=p;s.size++;returnTRUE;}elsereturnFALSE;}statuspop<stack&S,Elemtype&e>{//若棧不空,則刪除S的棧頂元素并以e帶回其值,且返回TRUE,//否則返回FALSE,且e無意義if<stackempty<s>returnFALSE>;else{p=S.top;S.top->next;e=p->date;S.size--;returnTRUE;}}4.求迷宮路徑的偽碼算法：statusmazepath<mazetypemaze,postypestart,postypeend>{//若迷宮中存在從入口start到出口end的通道,則求得一條存入在棧中//〔從棧底到棧頂為從入口到出口的路徑,并返回TRUE；否則返回FALSEinitstack<S>;curpos=start;//設(shè)定"當(dāng)前位置"為"入口位置"curstep=1;found=FALSE;//探索第一步do{if<pass<maze,curpos>>{//當(dāng)前位置可以通過,即是未曾走到過的通道塊footprint<maze,curpos>;//留下足跡e=<curstep,curpos,1>;push<S,e>;//加入路徑if<same<curpos,end>>found=TRUE;//到達(dá)終點(diǎn)〔出口else{curpos=nextpos<curpos,1>;//下一位置是當(dāng)前位置的東鄰curstep++;//探索下一步}//else}//ifelse//當(dāng)前位置不能通過if<!stackempty<S>>{pop<S,e>;while<e.di==4&&!stackempty<S>>{markprint<maze,e,seat>;pop<S,e>;curstep--;//留下不能通過的標(biāo)記,并退回一步}//whileif<e.di<4>{e.di++;push<S.e>//換下一個(gè)方向探索curpos=nextpos<e.seat,e.di>;//設(shè)定當(dāng)前位置是該新方向上的相鄰塊}//if}//if}while<!stackempty<S>&&!found>;returnfound;}//mazepath5．主函數(shù)和其他函數(shù)的偽碼算法voidmain<>{//主程序initialization<>;//初始化do{readcommand<cmd>;//讀入一個(gè)操作命令符interpret<cmd>;//解釋執(zhí)行操作命令符}while<cmd!=‘q’&&cmd!=‘Q’>;}//mainvoidinitialization<>{//系統(tǒng)初始化clrscr<>;//清屏在屏幕上方顯示操作命令清單：creatmaze—cmazepath—mprintmaze—pQuit—q;在屏幕下方顯示操作命令提示框：}//initializationvoidreadcommand<char&cmd>{//讀入操作命令符顯示鍵入操作命令符的提示信息；do{cmd=getche<>}while<cmd[‘c’,‘C’,‘m’,‘M’,‘p’,‘P’,‘q’,‘Q’]>；}//readcommandvoidinterpret<charcmd>{//解釋執(zhí)行操作命令switch<cmd>{case‘c’,’C’:提示用戶輸入"迷宮數(shù)據(jù)的文件名filename"；從文件讀入數(shù)據(jù)分別存儲(chǔ)在rnum,cnum和二維數(shù)組a2中；initmaze<ma,a2,rnum,cnum>;//創(chuàng)建迷宮輸出迷宮建立完畢的信息break;case‘m’,‘M’:提示用戶輸入迷宮的入口from和出口term的坐標(biāo)位置；if<mazepath<ma,from,term>>//存在路徑提示用戶察看迷宮；else輸出該迷宮沒有從給定的入口到出口的路徑的信息；break；case‘p’,‘P’:printmaze<ma>://將標(biāo)記路徑信息的迷宮輸出到終端}//switch}//interpret6．函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：initmazemazepathprintmaze函數(shù)的調(diào)用關(guān)系圖四．調(diào)試分析1．本次作業(yè)比較簡單,只有一個(gè)核心算法,即求迷宮的路徑,所以總的調(diào)試比較順利,只在調(diào)試mazepath算法時(shí),遇到兩個(gè)問題：其一是,起初輸出的迷宮中沒有加上‘’的記號(hào),后發(fā)現(xiàn)是因?yàn)樵趍arkprint函數(shù)中的迷宮參數(shù)丟失"變參"的原因；其二是,由于回退時(shí)沒有將curpos隨之減一,致使棧中路徑上的序號(hào)有錯(cuò)。2．棧的元素中的step域沒有太多用處,可以省略。3．Stacktraverse在調(diào)試過程中很有用,它可以插入在mazepath算法中多處,以察看解迷宮過程中走的路徑是否正確,但對(duì)最后的執(zhí)行版本沒有用。4．本題中三個(gè)主要算法：initmaze,mazepath和printmaze的時(shí)間復(fù)雜度均為0〔m*n,本題的空間復(fù)雜度亦為0〔m*n〔棧所占最大空間5．經(jīng)驗(yàn)體會(huì)：借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口,可以加快找到程序中疵點(diǎn)。五．用戶手冊(cè)〔1本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng),執(zhí)行文件為：testmaze.exe〔2進(jìn)入演示程序后,即顯示文本方式的用戶界面：〔3進(jìn)入"產(chǎn)生迷宮〔creatmaze"的命令后,即提示鍵入迷宮數(shù)據(jù)的文件名,結(jié)束符為"回車符",該命令執(zhí)行之后輸出"迷宮已建成"?！?進(jìn)入"求迷宮路徑〔mazepath"的命令后,即提示鍵入入口位置〔行號(hào)和列號(hào),中間用空格分開,結(jié)束符為"回車符"和出口位置〔行號(hào)和列號(hào),中間用空格分開,結(jié)束符為"回車符",該命令執(zhí)行之后輸出相應(yīng)信息。若迷宮中存在路徑,則執(zhí)行此命令后,迷宮狀態(tài)已改變,若要重復(fù)執(zhí)行此命令,無論是否改變出口和入口的位置,均需重新輸入迷宮數(shù)據(jù)?！?輸入"顯示迷宮"的命令后,隨即輸出當(dāng)前的迷宮,即迷宮的初始狀態(tài)或求出路徑之后的狀態(tài)。**********************************************************************creatmaze-cmazepath-mprintmaze-pquit-q***********************************************************************creatmaze-cmazepath-mprintmaze-pquit-q********************************operation:-*********************************************************************enteraoperationcode:c,m,pORq**********************************************************************鍵入操作命令符鍵入操作命令符操作命令清單操作命令清單操作提示信息操作提示信息圖3-2操作界面六．測(cè)試結(jié)果三組測(cè)試數(shù)據(jù)和輸出結(jié)果分別如下：1．輸入文件名為：m1.dat,其中迷宮數(shù)據(jù)為：32000