數(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ì)算機(jī)0702 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2009年 10月 26日湖南工程學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 公園導(dǎo)游圖 專業(yè)班級(jí) 計(jì)算機(jī)0702 學(xué)生姓名 學(xué) 號(hào) 指導(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)算符號(hào)“+”、“”、“*”、“/”及括號(hào)“（”和“）”從鍵盤上輸入一個(gè)計(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ī)生成一個(gè)迷宮圖，迷宮大小為n*n，n預(yù)定義為常數(shù)，修改n的值可以改變迷宮的大小。用白色表示可走的路，藍(lán)色表示墻壁不可以通過。系統(tǒng)設(shè)計(jì)兩種運(yùn)行方式：一種是系統(tǒng)自動(dòng)探索（用遞歸方法實(shí)現(xiàn)）；另一種是由人工操作探索通路。設(shè)計(jì)思路：程序首先要考慮迷宮的表示，這是一個(gè)二維關(guān)系圖，所以可選擇二維數(shù)組來存儲(chǔ)。數(shù)組元素只有兩種值0和1，分別代表通路和墻壁。圖形的顯示可以根據(jù)數(shù)組元素的值來確定。如果是

3、人工探索，則依據(jù)按鍵來確定探索物的位置坐標(biāo)，利用循環(huán)語句實(shí)現(xiàn)。如果是系統(tǒng)自動(dòng)探索，可采用遞歸算法實(shí)現(xiàn)。1.1.3 二叉樹遍歷演示演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計(jì)兩種生成樹的方式：一種是系統(tǒng)隨機(jī)生成，另一種是人工輸入。考慮到屏幕界面的有限性，限定二叉樹不超過5層，最多26個(gè)字符，輸入字符小數(shù)點(diǎn)“.”代表null。初始樹為某種顏色的結(jié)點(diǎn)，三種情況的遍歷采用填充另外一種醒目的顏色，來表示當(dāng)前遍歷的結(jié)點(diǎn)，同時(shí)顯示該結(jié)點(diǎn)的訪問序號(hào)。同時(shí)在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。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)排成一個(gè)線性序列，對(duì)于有向圖中沒有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。要求每輸出一個(gè)頂點(diǎn)后就演示從圖中刪去此頂點(diǎn)以及所有以它為尾的弧。1.1.6 圖的遍歷演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點(diǎn)數(shù)不能少于6個(gè)?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動(dòng)輸入圖。報(bào)告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。1.1.7 八皇后問題演示在8*8的棋盤上擺放8

5、個(gè)皇后，使他們不在同一條對(duì)角線上和不在一行和列上。 解決8皇后時(shí)，在安放第i行皇后時(shí)，需要在列的方向從1到n試探(j =1, n)：首先在第j列安放一個(gè)皇后，如果在列、主對(duì)角線、次對(duì)角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。 該課題要求求解可能的方案及方案數(shù)并逐步演示擺放皇后的過程。1.1.8 雙鏈表創(chuàng)建演示建立一個(gè)遞增有序的雙鏈表。功能是隨機(jī)生成8個(gè)結(jié)點(diǎn)數(shù)據(jù)，每生成一個(gè)結(jié)點(diǎn)則申請(qǐng)空間得到一個(gè)指針，將數(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é)號(hào)確定，學(xué)號(hào)模9加1，即（學(xué)號(hào)%9+1）。如你的學(xué)號(hào)為12，則所選題目號(hào)為：12%9+1（題目4）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。有興趣的同學(xué)可以自己針對(duì)數(shù)據(jù)結(jié)構(gòu)課程中所講算法來設(shè)計(jì)一個(gè)演示過程的算法，但要預(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)系；每個(gè)模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲(chǔ)什么數(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ì)體會(huì)a. 測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及輸出結(jié)果。b. 程序調(diào)試中遇到的問題以及解決問題的方法。c. 課程設(shè)計(jì)過程經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)。

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

9、運(yùn)行，個(gè)人能否獨(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)新程度，完善程序情況及對(duì)程序講解情況打分。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ì)體會(huì)114.1測試數(shù)據(jù)114.2程序調(diào)試中遇到的問題以及解決問題的方法154.3經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)155使用說明166附錄171 需求分析1.1課程設(shè)計(jì)內(nèi)容和要求。程序要能夠顯示出地圖，要能夠查找出地圖中任意兩點(diǎn)間的最短距離，以及不重復(fù)遍歷全圖的最短路徑，并且在查找及遍歷的每個(gè)過程都在圖中顯示出暫時(shí)的結(jié)果，以便演示整過過程。1.2輸入輸出的要求。程序執(zhí)行要求有描述地圖的兩個(gè)文件，并放到相應(yīng)位置。其中一個(gè)文件存放有描述地圖各個(gè)景點(diǎn)之間距離的矩陣，另一個(gè)文

12、件存有地圖中各景點(diǎn)在顯示器上顯示的位置。兩個(gè)地圖文件不允許有錯(cuò)誤。執(zhí)行相應(yīng)功能前要求先選擇。查找任意兩點(diǎn)間的最短距離，要求輸入要查找最短路徑的兩點(diǎn)。在運(yùn)行各個(gè)小過程后要求輸出暫時(shí)結(jié)果。2 概要設(shè)計(jì)2.1 程序模塊程序共有主模塊、查找兩點(diǎn)最短路徑并輸出具體過程、尋找不重復(fù)遍歷全圖圖路徑并輸出遍歷過程、三個(gè)模塊。主模塊包含、載入地圖、顯示地圖、功能選擇與調(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)的地圖，用棧保存遍歷時(shí)經(jīng)過的結(jié)點(diǎn)用以遍歷的回溯，以及存儲(chǔ)最終路徑。圖的抽象數(shù)據(jù)類型：adt graph數(shù)據(jù)對(duì)象:d=a1|1in，n0數(shù)據(jù)關(guān)系:r=|ai,ajd,1jn,1jn,其中每個(gè)元素可以有零個(gè)或多個(gè)前驅(qū)，可以有零個(gè)或多個(gè)后繼基本運(yùn)算：loadimg(*g)：從相應(yīng)文件中載入圖數(shù)據(jù)初始化圖g。outputimg(*g)把圖輸出到屏幕。bestpath（）不重復(fù)遍歷圖。floyed（）計(jì)算圖中所有點(diǎn)的兩兩最短路徑。 棧的抽象數(shù)據(jù)類型：adt list數(shù)據(jù)對(duì)象：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)的路徑，如果該路徑不存在，將提示。如果存在將會(huì)最終找出符合要求的最短路徑。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)間的暫時(shí)計(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號(hào)頂點(diǎn)被考慮作為中間節(jié)點(diǎn)時(shí)兩景點(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)功能輸入選擇的功能號(hào)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號(hào)景點(diǎn)可以作為路徑的中途景點(diǎn)時(shí)，對(duì)每兩個(gè)景點(diǎn)m、n計(jì)算距離lm,k+lk,jn并與原距離l0mnlmk+lkn寫成了減號(hào)-以及字符忘加引號(hào)等。輸入錯(cuò)誤在編譯時(shí)一般可以排除，編譯時(shí)還沒排除的錯(cuò)誤以及邏輯錯(cuò)誤一般要在調(diào)試運(yùn)行時(shí)排除。排除錯(cuò)誤主要是通過在程序中加入大量輸出函數(shù)，輸出運(yùn)行狀態(tài)，然后根據(jù)

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

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

22、識(shí)。感謝在做課程設(shè)計(jì)幫助自己的一些同學(xué)，是他們給我的意見和建議，讓我的程序能夠更加完善。5.使用說明把地圖文件放到與程序文件相同的目錄，然后運(yùn)行程序，程序會(huì)提供地圖的圖形顯示，以及兩個(gè)供選擇的功能，選擇相應(yīng)編號(hào)或即可完成對(duì)應(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)在顯示器中顯示時(shí)的坐標(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); /* 遍歷 */*/ /*顯示整個(gè)路徑*/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)編號(hào)*/ int i,n, length2=0,inf,k1; /* n為 已訪問頂點(diǎn)數(shù)*/ int verstflagmax=0; /* 該頂點(diǎn)下一條可訪問邊對(duì)應(yīng)的另一頂點(diǎn)號(hào)*/ int verflagmax=0;

30、/* 頂點(diǎn)數(shù)被訪問標(biāo)志*/ stack sta3;/*保存路徑的棧sta0隨時(shí)更新、sta1保存前一條最短路徑、sta2直接用于顯示（顯示是棧會(huì)清空）*/ int count; int radius=10; int starmax=0; /*star1指示起點(diǎn)與第i個(gè)頂點(diǎn)間的路徑是否可以作為起點(diǎn)路徑初始為（可以作為起點(diǎn)路徑） 當(dāng)試探過一次或作過遍歷路徑最后一段時(shí)將為（不可再作為起點(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