數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告公園導(dǎo)游圖

1、課 程 設(shè) 計(jì) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 公園導(dǎo)游圖 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級 計(jì)算機(jī)0702 學(xué) 號 姓 名 指導(dǎo)教師 2009年 10月 26日湖南工程學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 公園導(dǎo)游圖 專業(yè)班級 計(jì)算機(jī)0702 學(xué)生姓名 學(xué) 號 指導(dǎo)老師 審 批 任務(wù)書下達(dá)日期 2009 年 10 月 8 日任務(wù)完成日期 2009 年 11 月 8 日1設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1.1設(shè)計(jì)內(nèi)容1.1.1 算術(shù)24游戲演示由系統(tǒng)隨機(jī)生成4張撲克牌，用戶利用撲克牌的數(shù)字及運(yùn)算符號“+”、“”、“*”、“/”及括號“（”和“）”從鍵盤上輸入一個計(jì)算表達(dá)式，系統(tǒng)運(yùn)行后

2、得出計(jì)算結(jié)果，如果結(jié)果等于24，則顯示“congratulation!”，否則顯示“incorrect!”設(shè)計(jì)思路：從鍵盤輸入中綴表達(dá)式，然后將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，利用后綴表達(dá)式求值。1.1.2 迷宮探索隨機(jī)生成一個迷宮圖，迷宮大小為n*n，n預(yù)定義為常數(shù)，修改n的值可以改變迷宮的大小。用白色表示可走的路，藍(lán)色表示墻壁不可以通過。系統(tǒng)設(shè)計(jì)兩種運(yùn)行方式：一種是系統(tǒng)自動探索（用遞歸方法實(shí)現(xiàn)）；另一種是由人工操作探索通路。設(shè)計(jì)思路：程序首先要考慮迷宮的表示，這是一個二維關(guān)系圖，所以可選擇二維數(shù)組來存儲。數(shù)組元素只有兩種值0和1，分別代表通路和墻壁。圖形的顯示可以根據(jù)數(shù)組元素的值來確定。如果是

3、人工探索，則依據(jù)按鍵來確定探索物的位置坐標(biāo)，利用循環(huán)語句實(shí)現(xiàn)。如果是系統(tǒng)自動探索，可采用遞歸算法實(shí)現(xiàn)。1.1.3 二叉樹遍歷演示演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計(jì)兩種生成樹的方式：一種是系統(tǒng)隨機(jī)生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二叉樹不超過5層，最多26個字符，輸入字符小數(shù)點(diǎn)“.”代表null。初始樹為某種顏色的結(jié)點(diǎn)，三種情況的遍歷采用填充另外一種醒目的顏色，來表示當(dāng)前遍歷的結(jié)點(diǎn)，同時顯示該結(jié)點(diǎn)的訪問序號。同時在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。1.1.4 數(shù)組應(yīng)用按照行優(yōu)先順序?qū)⒂脩綦S機(jī)輸入

4、的數(shù)據(jù)建成2維數(shù)組并以圖形方式逐步顯示出來，然后再按照列優(yōu)先順序以圖形方式逐步輸出相應(yīng)數(shù)組。1.1.5 拓?fù)渑判蜓菔狙菔就負(fù)渑判虻倪^程。按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。要求每輸出一個頂點(diǎn)后就演示從圖中刪去此頂點(diǎn)以及所有以它為尾的弧。1.1.6 圖的遍歷演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點(diǎn)數(shù)不能少于6個?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動輸入圖。報(bào)告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。1.1.7 八皇后問題演示在8*8的棋盤上擺放8

5、個皇后，使他們不在同一條對角線上和不在一行和列上。 解決8皇后時，在安放第i行皇后時，需要在列的方向從1到n試探(j =1, n)：首先在第j列安放一個皇后，如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動，遞歸安放第i+1行皇后。 該課題要求求解可能的方案及方案數(shù)并逐步演示擺放皇后的過程。1.1.8 雙鏈表創(chuàng)建演示建立一個遞增有序的雙鏈表。功能是隨機(jī)生成8個結(jié)點(diǎn)數(shù)據(jù)，每生成一個結(jié)點(diǎn)則申請空間得到一個指針，將數(shù)據(jù)存放到指針?biāo)傅臄?shù)據(jù)域中，然后將結(jié)點(diǎn)插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點(diǎn)的插入位置，第二不演示

6、插入過程中指針的變化，第三步顯示插入后的鏈表結(jié)果。1.1.9 公園導(dǎo)游圖給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點(diǎn)到另一景點(diǎn)的最短路徑。游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點(diǎn)，最后回到出口（出口就在入口旁邊）。要求用圖示展示最佳路徑。1.2 選題方案：所選題目根據(jù)學(xué)號確定，學(xué)號模9加1，即（學(xué)號%9+1）。如你的學(xué)號為12，則所選題目號為：12%9+1（題目4）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。有興趣的同學(xué)可以自己針對數(shù)據(jù)結(jié)構(gòu)課程中所講算法來設(shè)計(jì)一個演示過程的算法，但要預(yù)先告知老師，經(jīng)過審批，方可確定課題。1.3設(shè)計(jì)要求：1.3.1 課程

7、設(shè)計(jì)報(bào)告規(guī)范（1）需求分析a. 程序的功能。b. 輸入輸出的要求。（2）概要設(shè)計(jì)a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。（3）詳細(xì)設(shè)計(jì)a. 采用c語言定義相關(guān)的數(shù)據(jù)類型。b. 寫出各模塊的類c碼算法。c. 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。（4）調(diào)試分析以及設(shè)計(jì)體會a. 測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。b. 程序調(diào)試中遇到的問題以及解決問題的方法。c. 課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會。

8、（5）使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。 （6）書寫格式a. 設(shè)計(jì)報(bào)告要求用a4紙打印成冊：b. 一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為22。（7）附錄a. 源程序清單（帶注釋）1.3.2 考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計(jì)成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分：（1）平時出勤 （占10%）（2）系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否（占10%）（3）程序能否完整、準(zhǔn)確地

9、運(yùn)行，個人能否獨(dú)立、熟練地調(diào)試程序（占40%）（4）設(shè)計(jì)報(bào)告（占30%）注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴?。?）獨(dú)立完成情況（占10%）。1.3.3 課程驗(yàn)收要求（1）運(yùn)行所設(shè)計(jì)的系統(tǒng)。（2）回答有關(guān)問題。（3）提交課程設(shè)計(jì)報(bào)告。（4）提交軟盤（源程序、設(shè)計(jì)報(bào)告文檔）。（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。2 進(jìn)度安排2.1 計(jì)算機(jī)0701/0702班：第 7 周：星期一 8：0012：00 上課 星期一 14：0016：00 上課 星期五 18：0022：00 上機(jī)第 8 周：星期六 14：0018：00 上機(jī) 星期日 8：0012：00 上

10、機(jī) 星期日 18：0022：00 上課第 9 周：星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī)2.2 計(jì)算機(jī)0703班： 第 7 周：星期一 8：0012：00 上課 星期一 14：0016：00 上課 星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī)第 8 周：星期六 8：0012：00 上機(jī) 星期日 14：0018：00 上機(jī)第 9 周：星期六 14：0018：00 上機(jī) 星期日 18：0022：00 上機(jī)。 目 錄1需求分析11.1課程設(shè)計(jì)內(nèi)容和要求11.2 輸入輸出的要求12概要設(shè)計(jì)22.1 主要程序功能模22.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫

11、結(jié)構(gòu)23詳細(xì)設(shè)計(jì)43.1 c語言定義的相關(guān)數(shù)據(jù)類型43.2 各模塊的類c碼算法43.3 各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖74調(diào)試分析以及設(shè)計(jì)體會114.1測試數(shù)據(jù)114.2程序調(diào)試中遇到的問題以及解決問題的方法154.3經(jīng)驗(yàn)教訓(xùn)、心得體會155使用說明166附錄171 需求分析1.1課程設(shè)計(jì)內(nèi)容和要求。程序要能夠顯示出地圖，要能夠查找出地圖中任意兩點(diǎn)間的最短距離，以及不重復(fù)遍歷全圖的最短路徑，并且在查找及遍歷的每個過程都在圖中顯示出暫時的結(jié)果，以便演示整過過程。1.2輸入輸出的要求。程序執(zhí)行要求有描述地圖的兩個文件，并放到相應(yīng)位置。其中一個文件存放有描述地圖各個景點(diǎn)之間距離的矩陣，另一個文

12、件存有地圖中各景點(diǎn)在顯示器上顯示的位置。兩個地圖文件不允許有錯誤。執(zhí)行相應(yīng)功能前要求先選擇。查找任意兩點(diǎn)間的最短距離，要求輸入要查找最短路徑的兩點(diǎn)。在運(yùn)行各個小過程后要求輸出暫時結(jié)果。2 概要設(shè)計(jì)2.1 程序模塊程序共有主模塊、查找兩點(diǎn)最短路徑并輸出具體過程、尋找不重復(fù)遍歷全圖圖路徑并輸出遍歷過程、三個模塊。主模塊包含、載入地圖、顯示地圖、功能選擇與調(diào)用三部分。查找兩點(diǎn)最短路徑并輸出具體過程模塊中的輸出具體過程為顯示地圖模塊模塊結(jié)構(gòu)如圖：功能調(diào)用輸出圖形查找兩點(diǎn)最短路徑并輸出具體過程尋找不重復(fù)遍歷全圖路徑并輸出遍歷過程載入圖形主模塊圖2.12.2 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)程序主要用了圖和

13、棧兩種數(shù)據(jù)結(jié)構(gòu)，采用矩陣來保存圖形結(jié)構(gòu)的地圖，用棧保存遍歷時經(jīng)過的結(jié)點(diǎn)用以遍歷的回溯，以及存儲最終路徑。圖的抽象數(shù)據(jù)類型：adt graph數(shù)據(jù)對象:d=a1|1in，n0數(shù)據(jù)關(guān)系:r=|ai,ajd,1jn,1jn,其中每個元素可以有零個或多個前驅(qū)，可以有零個或多個后繼基本運(yùn)算：loadimg(*g)：從相應(yīng)文件中載入圖數(shù)據(jù)初始化圖g。outputimg(*g)把圖輸出到屏幕。bestpath（）不重復(fù)遍歷圖。floyed（）計(jì)算圖中所有點(diǎn)的兩兩最短路徑。 棧的抽象數(shù)據(jù)類型：adt list數(shù)據(jù)對象：d=ai|1in，n0，數(shù)據(jù)關(guān)系：r=|ai,ai+1d，i=1，n-1基本運(yùn)算：push（

14、*s，e）：進(jìn)棧：將元素e查到棧s中作為棧頂元素。 pop（*s，*e）：出棧：從棧s中退出棧頂元素，并將其值賦予e。copsta(*s1, *s)：把棧s中的內(nèi)容復(fù)制到棧s1。3 詳細(xì)設(shè)計(jì)3.1采用c語言定義相關(guān)的數(shù)據(jù)類型。圖的定義：typedef struct int edgesmaxmax; int n; /* n 頂點(diǎn)數(shù)*/int e; /* e 邊數(shù) */mgraph;棧的定義：typedef struct int bodymax; int top;stack;3.2寫出各模塊的類c碼算法。3.2.1讀取地圖：把保存在文件中的地圖數(shù)據(jù)載入到程序中相應(yīng)的數(shù)據(jù)結(jié)構(gòu),圖結(jié)構(gòu)體g及頂點(diǎn)位置數(shù)

15、組vl2中。void loadimg(int vl2,mgraph *g) fp=fopen(g.g2,r); fscanf(fp, %d,&(g-n); for(i=0;in; i+) fscanf(fp, %d%d,&vli0,&vli1); fclose(fp); fp=fopen(g.g1,r); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) fscanf(fp, %d,&(g-edgesij);fclose(fp);3.2.2 顯示地圖：把地圖以圖形方式輸出到顯示器。void outputimg(int vl2,mgraph *g) for(i=0,

16、g-e=0; in; i+) for(j=0; jn; j+) if(g-edgesij!=inf & ie+;畫兩點(diǎn)間路徑; for(i=0;in; i+) 畫景點(diǎn)；3.2.3 不重復(fù)遍歷全圖的最短路徑：尋找從起點(diǎn)開始不重復(fù)走完所有景點(diǎn)的路徑，如果該路徑不存在，將提示。如果存在將會最終找出符合要求的最短路徑。step1： if（沒遍歷完）if（向前有一景點(diǎn)沒訪問過）往下走；else 回溯到上一景點(diǎn)點(diǎn)（原景點(diǎn)之后景點(diǎn)變?yōu)闆]訪問過）；if（ 遍歷到起點(diǎn) 且 訪問其以后景點(diǎn)必然與以前的試探路徑相同） /說明 路徑不再存在；若 以前找到過遍歷路徑則輸出最佳結(jié)果 結(jié)束；else 到step1 開始下一

17、步搜索；else 若比以前有的結(jié)果更好，則輸出結(jié)果并繼續(xù)試探更好的遍歷方法； 3.2.4 兩點(diǎn)間最短路徑：采用弗洛伊德算法，求出每點(diǎn)間的最短路徑，并在計(jì)算過程中輸出用戶所求兩點(diǎn)間的暫時計(jì)算出的最短路徑。void floyed(mgraph *g, int amax, int pathmax,int vl2) for (i=0;in;i+) /*置初值*/ for (j=0;jn;j+) aij=g-edgesij; pathij=-1; 輸入兩景點(diǎn)； for (k=0;kn;k+) for (i=0;in;i+) for (j=0;jn;j+) if(aik!=inf & akj!=inf &

18、 aij(aik+akj) aij=aik+akj; pathij=k; 輸出0到k號頂點(diǎn)被考慮作為中間節(jié)點(diǎn)時兩景點(diǎn)的最短路徑圖；3.3各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。3.3.1函數(shù)調(diào)用關(guān)系圖： 顯示地圖outputimg從文件中載入地圖數(shù)據(jù)loadimg不重復(fù)遍歷景點(diǎn)bestpath查找兩點(diǎn)最短路徑floyed主函數(shù)main查詢最短路徑的中間節(jié)點(diǎn)ppath顯示兩點(diǎn)間最短路徑fdispath顯示遍歷路徑disbestpath圖3.1 函數(shù)調(diào)用關(guān)系圖3.3.2主函數(shù)流程圖：否否否是是是開始輸出地圖完成遍歷圖功能提示用戶選擇相應(yīng)功能輸入選擇的功能號aa=0？結(jié)束a=1？a=2？完成查找兩點(diǎn)間

19、最短路徑功能從文件中載入地圖圖3.2 主函數(shù)流程圖3.3.3查找兩點(diǎn)最短路徑函數(shù)floyed（）流程圖：否否是把所有景點(diǎn)的兩兩最短路徑初始值設(shè)為其直接距離，中途景點(diǎn)設(shè)為空開始輸入要查找最短路徑的兩點(diǎn)i1、j1k=0k景點(diǎn)數(shù)？k+顯示兩點(diǎn)間最短路徑結(jié)束更新最短路徑長度為lmk+lkn，更新中途景點(diǎn)為k考慮k號景點(diǎn)可以作為路徑的中途景點(diǎn)時，對每兩個景點(diǎn)m、n計(jì)算距離lm,k+lk,jn并與原距離l0mnlmk+lkn寫成了減號-以及字符忘加引號等。輸入錯誤在編譯時一般可以排除，編譯時還沒排除的錯誤以及邏輯錯誤一般要在調(diào)試運(yùn)行時排除。排除錯誤主要是通過在程序中加入大量輸出函數(shù)，輸出運(yùn)行狀態(tài)，然后根據(jù)

20、輸出結(jié)果定位出錯位置，找出出錯原因并解決問題。但在中途還遇到過一些奇怪的問題，如函數(shù)執(zhí)行完畢之后不能正常跳出。我實(shí)在是找不到錯在哪里，后來我改變了函數(shù)的結(jié)構(gòu)，及程序的組織方式，問題終于沒有了。我自己覺得應(yīng)該是對語言或編譯環(huán)境的細(xì)節(jié)還了解得不夠造成了這類問題不能解決。4.3經(jīng)驗(yàn)教訓(xùn)、心得體會。兩周的課程設(shè)計(jì)中，碰到過許多問題。首先，上課時聽的理論知識，各種算法似乎很容易理解，但是在真正的運(yùn)用過程中，并不能把理論知道很好的和實(shí)踐結(jié)合起來。在平時做實(shí)驗(yàn)時，尤其是這次課程設(shè)計(jì)，總感到有些無從下手。因此，在學(xué)知識的過程中，一定要多動手、動腦，將所學(xué)的知識熟練掌握，自如運(yùn)用。其次，通過這次課程設(shè)計(jì)，對自己

21、的邏輯思維能力是一個很大的鍛煉，加強(qiáng)了我們的系統(tǒng)思考問題的能力，在編程方面，我們開始從整體的角度來考慮問題了，而不再像以前一樣的，沒有一個總體的概念。也就是因?yàn)檫@種習(xí)慣，使自己在課程設(shè)計(jì)過程中浪費(fèi)了不少的時間。 程序設(shè)計(jì)是一個毅力的考驗(yàn)過程。有時候往往只是一個小小的錯誤，卻要費(fèi)很多的時間來解決。在這個過程不能過于急躁，并且要很有耐心才行程序需要反復(fù)調(diào)試，其過程很可能相當(dāng)令人頭疼，有時花很長時間設(shè)計(jì)出來還是需要重做，那時心中未免有點(diǎn)灰心，有時還特別想放棄，此時更加需要靜下心，查找原因。在課程設(shè)計(jì)中，感謝老師的耐心指導(dǎo)，讓我能能能夠順利寫出程序并把程序更快的調(diào)試正確，我從中也學(xué)到了許多新的方法和知

22、識。感謝在做課程設(shè)計(jì)幫助自己的一些同學(xué)，是他們給我的意見和建議，讓我的程序能夠更加完善。5.使用說明把地圖文件放到與程序文件相同的目錄，然后運(yùn)行程序，程序會提供地圖的圖形顯示，以及兩個供選擇的功能，選擇相應(yīng)編號或即可完成對應(yīng)功能，并在圖上看到其完成過程。6.附錄#include stdio.h#include conio.h#include graphics.h#include dos.h#define closegr closegraph#define max 12#define inf 32767/*定義圖結(jié)構(gòu)*/typedef struct int edgesmaxmax; int n,

23、e; /* n 頂點(diǎn)數(shù) e 邊數(shù)*/mgraph;/*定義棧結(jié)構(gòu)*/typedef struct int bodymax; int top;stack;int push(stack *s,int n) if(s-top=max-1)return 0; s-top+; s-bodys-top=n; return 1;int pop(stack *s,int *n) if(s-top=-1) return 0; *n=s-bodys-top; s-top-; return 1;void copsta(stack *s1, stack *s) int i; s1-top=s-top; for(i=0

24、;itop;i+) s1-bodyi = s-bodyi; void initgr(void) /* bgi初始化*/ int gd = detect, gm = 0; /* 和gd = vga,gm = vgahi是同樣效果*/ registerbgidriver(egavga_driver); initgraph(&gd, &gm, ); /*從文件中讀取圖形到程序*/void loadimg(int vl2,mgraph *g) /*vl 頂點(diǎn)在顯示器中顯示時的坐標(biāo)值 */file *fp; int i,j; fp=fopen(g.g2,r); fscanf(fp, %d,&(g-n);

25、 for(i=0;in; i+) fscanf(fp, %d%d,&vli0,&vli1); fclose(fp); fp=fopen(g.g1,r); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) fscanf(fp, %d,&(g-edgesij); fclose(fp);/* 在屏幕顯示上圖形*/void outputimg(int vl2,mgraph *g) char jd1025=enter, flower garden,zoo,roller skating,teahouse,barbecue, amusement park, verandah,

26、buffet,botanical gardens,; int radius=10; int i,j; char s50=0; setlinestyle(0,0, 2); for(i=0,g-e=0; in; i+) for(j=0; jn; j+) if(g-edgesij!=inf & ie+; line(vli0,vli1,vlj0,vlj1); sprintf(s,%d,g-edgesij); setcolor(red); outtextxy( (vli0+vlj0)/2 ,(vli1+vlj1)/2+5 ,s); setcolor(white); for(i=0;in; i+) set

27、fillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), sprintf(s,%d,i), setcolor(red), outtextxy(vli0-3,vli1-3,s), setcolor(white), outtextxy(vli0+10,vli1-10,jdi); /* 遍歷 */*/ /*顯示整個路徑*/void disbestpath(stack *psta, int vl2)int i, k; char s5= ; int radius=10; outtextxy(120,300,best path i

28、s that); pop(psta,&i); setlinestyle(0,0, 3); while(pop(psta,&k) setcolor(yellow); line(vlk0, vlk1, vli0, vli1); setcolor(red); setlinestyle(0,0, 2); setfillstyle(solid_fill,green), fillellipse(vlk0,vlk1,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setlinestyl

29、e(0,0, 3); sprintf(s,%d,k), outtextxy(vlk0-3,vlk1-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s); i=k; setcolor(white); setlinestyle(0,0, 2);int bestpath(mgraph *g, int k, int vl2) /* k 起點(diǎn)編號*/ int i,n, length2=0,inf,k1; /* n為 已訪問頂點(diǎn)數(shù)*/ int verstflagmax=0; /* 該頂點(diǎn)下一條可訪問邊對應(yīng)的另一頂點(diǎn)號*/ int verflagmax=0;

30、/* 頂點(diǎn)數(shù)被訪問標(biāo)志*/ stack sta3;/*保存路徑的棧sta0隨時更新、sta1保存前一條最短路徑、sta2直接用于顯示（顯示是棧會清空）*/ int count; int radius=10; int starmax=0; /*star1指示起點(diǎn)與第i個頂點(diǎn)間的路徑是否可以作為起點(diǎn)路徑初始為（可以作為起點(diǎn)路徑） 當(dāng)試探過一次或作過遍歷路徑最后一段時將為（不可再作為起點(diǎn)路徑） */ int ns=0; /*還可以作為起點(diǎn)路徑的邊數(shù)*/char s5= ; for(i=0;in; i+) if(g-edgeski !=inf & i!=k)ns+; sta0.top=-1; sta1

31、.top=-1; verflagk=1; k1=k; push(&sta0,k1); n=1;bestpathloop1: for(i=verstflagk1; in); i+) verstflagk1+; if(g-edgesk1i!=inf & i!=k1 & verflagi=0 & verstflagk1n) if(k1=k) ns-; if(stari=1)continue; verflagi=1; length0+=g-edgesk1i; push(&sta0,i); setlinestyle(0,0, 3); setcolor(yellow); line(vlk10, vlk11

32、, vli0, vli1); setcolor(white); setlinestyle(0,0, 2); setfillstyle(solid_fill,green), fillellipse(vlk10,vlk11,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k1), outtextxy(vlk10-3,vlk11-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,

33、s), setcolor(white); for(count=0;countn & g-edgesik!=inf & verstflagk=i) ns-; stari=1; if(length0length1) copsta(&sta1, &sta0); copsta(&sta2, &sta0); push(&sta2,k); disbestpath(&sta2, vl);outtextxy(300,300,now); for(count=0;count20;count+) delay(32767); length1=length0;verstflagi=0; if(ns=0) outtext

34、xy(350,300,finally ); push(&sta1,k); disbestpath(&sta1, vl);return; setlinestyle(0,0, 3), setcolor(black), line(vlk0, vlk1, vli0, vli1), setcolor(white), setlinestyle(0,0, 2), line(vlk0, vlk1, vli0, vli1); setfillstyle(solid_fill,green), fillellipse(vlk0,vlk1,radius,radius), setfillstyle(solid_fill,

35、green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k), outtextxy(vlk0-3,vlk1-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s), setcolor(white); for(count=0;count20;count+) delay(32767); break; k1=i; i=verstflagi-1; if(pop(&sta0, &i)=0 | pop(&sta0, &k1)=0 ) if(sta1.top=-1)outt

36、extxy(100,300,path not exit); return; push(&sta1,k);outtextxy(250,300,finally); disbestpath(&sta1, vl);return; setlinestyle(0,0, 3), setcolor(black), line(vlk10, vlk11, vli0, vli1), setcolor(white), setlinestyle(0,0, 2); line(vlk10, vlk11, vli0, vli1); setfillstyle(solid_fill,green), fillellipse(vlk

37、10,vlk11,radius,radius), setfillstyle(solid_fill,green), fillellipse(vli0,vli1,radius,radius), setcolor(red), sprintf(s,%d,k1), outtextxy(vlk10-3,vlk11-3,s), sprintf(s,%d,i), outtextxy(vli0-3,vli1-3,s), setcolor(white); for(count=0;countedgesk1i; verflagi=0; verstflagi=0; push(&sta0, k1); n-; i=verstflagk1; goto bestpathloop1; /* 兩點(diǎn)最短路徑 */void ppath(int pathmax,i