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

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