數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-最短路徑算法-二叉樹的三種遍歷

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告班 級： 計算機科學(xué)與技術(shù)132班 姓 名： 賴恒財 指導(dǎo)教師： 董躍華 成 績： 32 信息工程學(xué)院 2015 年 7月 8日目錄圖的最短路徑算法實現(xiàn)1.需求分析11.1 程序設(shè)計內(nèi)容11.2 設(shè)計要求12.概要設(shè)計23.詳細設(shè)計23.1 數(shù)據(jù)類型的定義23.2 功能模塊的設(shè)計23.3 主程序流程94.調(diào)試分析104.1 問題回顧和分析104.2.經(jīng)驗和體會115.測試結(jié)果12二叉樹的遍歷1.設(shè)計目的132.需求分析142.1課程設(shè)計的內(nèi)容和要求142.2選題的意義及背景143.概要設(shè)計143.1設(shè)計思想143.2程序數(shù)據(jù)類型163.3程序模塊分析163.3.1置空棧16

2、3.3.2入棧173.3.3出棧173.3.4取棧頂操作173.3.5判空棧173.4函數(shù)關(guān)系：184.詳細設(shè)計184.1二叉樹算法程序截圖和結(jié)果185.程序測試結(jié)果及問題分析196.總結(jié)20參考文獻21附錄122附錄22630圖的最短路徑算法實現(xiàn) -基于floyd最短路徑算法1. 需求分析設(shè)計校園平面圖，所含景點不少于8個。以圖中頂點表示學(xué)校內(nèi)各景點，存放景點的名稱、景點介紹信息等；以邊表示路徑，存放路徑長度信息。要求將這些信息保存在文件graph.txt中，系統(tǒng)執(zhí)行時所處理的數(shù)據(jù)要對此文件分別進行讀寫操作。1.1 程序設(shè)計內(nèi)容1從文件graph.txt中讀取相應(yīng)數(shù)據(jù), 創(chuàng)建一個圖,使用鄰接

3、矩陣表示圖 ；2景點信息查詢：為來訪客人提供校園任意景點相關(guān)信息的介紹；3問路查詢：為來訪客人提供校園任意兩個景點之間的一條最短路徑 。1.2 設(shè)計要求(1) 程序要具在一定的健壯性，即當(dāng)輸入數(shù)據(jù)非法時，程序也能適當(dāng)?shù)刈龀龇磻?yīng)。(2) 程序要添加適當(dāng)?shù)淖⑨?，程序的書寫要采用縮進格式。(3) 根據(jù)實驗報告模板詳細書寫實驗報告，在實驗報告中給出校園平面圖。(4) 校園平面圖中的校園景點信息保存在文件graph.txt中。2.概要設(shè)計此程序主要實現(xiàn)以下幾個模塊, 基于下面幾個模塊完全可以實現(xiàn)此題要求.(1). 圖的創(chuàng)建(2). 輸出提供可選查詢景點(3). 景點介紹查詢處理(4). 查找兩景點間的最

4、短路徑(5). Floyd算法(核心)3.詳細設(shè)計3.1 數(shù)據(jù)類型的定義typedef struct char name100;/名字char info10000;/介紹VertexType; /頂點結(jié)構(gòu)typedef struct VertexType vexs10;int arcs100100; /鄰接矩陣int vexnum,arcnum;/頂點個數(shù)，邊的個數(shù) MGraph;/圖結(jié)構(gòu)校園道路是雙向通行的，可設(shè)校園平面圖是一個帶權(quán)的無向圖，用鄰接矩陣表示此無向網(wǎng)。鄰接矩陣的數(shù)據(jù)類型定義如下：3.2 功能模塊的設(shè)計3.2.1 圖的創(chuàng)建void initGraph() freopen(&quo

5、t;graph.txt", "r", stdin);/打開文件scanf("%d %d", &mg.vexnum, &mg.arcnum);/讀取頂點數(shù)、邊數(shù)/循環(huán)輸入景點、景點介紹for (int i = 0; i < mg.vexnum; i+) scanf("%s %s", &, &);/初始化矩陣，任意兩點之間沒有路for (int i = 0; i < 100; i+) for (int j = 0; j < 10

6、0; j+) mg.arcsij = 999999;/999999相當(dāng)于無窮大/輸入距離for (int i = 0; i < mg.arcnum; i+) char from100;/開始結(jié)點名char to100;/結(jié)束結(jié)點名/f表示開始結(jié)點編號，t表示目的結(jié)點編號，dis表示兩點間的距離int f, t, dis;scanf("%s %s %d", &from, &to, &dis);/把景點名字換成編號for (int j = 0; j < mg.vexnum; j+) if (strcmp(, from

7、) = 0) f = j;if (strcmp(, to) = 0) t = j;/創(chuàng)建鄰接矩陣mg.arcsft = dis;mg.arcstf = dis;floyd();/floyd算法計算各兩點之間的最短路徑，后文定義freopen("CON", "r", stdin);/改變輸入流校園平面圖可以表示成為一個無向網(wǎng)，用一個MGraph 類型的變量 mg表示這張無向網(wǎng)。網(wǎng)中包含了景點的名字和信息，以及表示各景點之間是否有路可達鄰接矩陣，同時還保存了景點個數(shù)和邊數(shù)。其俱體定義如下：Graph.txt8 15 校門江西理工大學(xué)

8、校門主教學(xué)校教學(xué)主樓，有11層二教學(xué)校二號教學(xué)樓圖書館 供學(xué)生自習(xí)或借書體育場一個大的田徑場，包括足球場，女生宿舍 生女生住宿的地方南門?學(xué)校通向外面的一個小門蕙莘園食堂 學(xué)校有三個食堂，其中一個就是蕙莘園食堂，靠近男生宿舍。校門 圖書館 110校門 主教 30校門 體育場 70校門 南門 90校門 女生宿舍 110主教 圖書館 50主教 二教 10二教 蕙莘園食堂 50二教 體育場 30圖書館 體育場 70圖書館 蕙莘園食堂 60體育場 蕙莘園食堂 40體育場 南門 40南門 女生宿舍 20蕙莘園食堂 女生宿舍 130程序中用到的關(guān)于學(xué)校各景點及信息的的數(shù)據(jù)保存在graph.txt文件中，文

9、件的具體信息如下：graph.txt 文件中的格式是，第一行包括兩個整數(shù)，第一個整數(shù)是景點的個數(shù)n, 也就是圖中的結(jié)點個數(shù)，第二個整數(shù)是邊的數(shù)量m。接著n行數(shù)據(jù)分別是學(xué)校的每個景點（結(jié)點），每個景點后的是對景點的介紹。再接著的m行是路徑信息，每條路徑信息有三部分數(shù)據(jù)組成，分別是起始結(jié)點，終止結(jié)點，和它們之間的路徑長度。3.2.2 提供可選景點提供可選景點信息這一模塊，是向用戶展示從graph.txt文件中讀取到的學(xué)校的各大景點，告訴用戶提供的可查看的景點有哪些。景點信息用一個for循環(huán)輸出。此外為了方便對景點的各項操作，我們在輸出所有可選景點的同時還為它們進行了數(shù)字編號，在后面的查詢或找路過程

10、中還需要輸入煩瑣的景點名稱，只需要輸入想要查詢的景點的對應(yīng)編號即可進行操作。簡單方便，實用，用戶體驗性好。/輸出可選景點，并進行編號void outPlace() printf("本校景點有：n");for (int i = 0; i < mg.vexnum; i+) printf("ttt%d、%sn",i, );printf("n");輸出提供的可選景點的代碼如下：3.2.3 景點信息查詢處理景點信息查詢處理這一模塊，要求用戶輸入要查詢的景點的編號，根據(jù)用戶輸入的查詢景點信息指令，判斷要查詢的景點，

11、并同時作出反應(yīng)，向用戶展示景點的具體信息。作為算法的健壯性，這一模塊在用戶輸入查詢指令后，判斷用戶輸入的指令的合法性，防止出現(xiàn)異常。/景點信息查詢處理void outInfo() int n;printf(" -n");printf("| 您選擇了 1.查詢景點信息 |n");printf(" -n");printf(">>>>>>請選擇您要查詢的景點（0 - %d） :n", mg.vexnum);scanf("%d", &n);if (n >

12、= 0 && n < mg.vexnum) printf("t%s:ntt%snn", , );else printf("您輸入的數(shù)據(jù)有誤！n");具體實現(xiàn)代碼如下：3.2.4 查找兩景點的最短路徑查找兩景點的最短路徑模塊，同景點信息查詢處理模塊相似。只不過是所處理的事情不一樣。查找兩景點的最短路徑模塊要求用戶輸入要查詢的兩景點的編號a , b（a表示開始結(jié)點， b表示終止結(jié)點）。然后程序會對用戶輸入的查詢指令進行判斷合法性，如果用戶輸入的指令合法，則告訴用戶所查詢到的最短路徑。如

13、果輸入指令不合法，則提醒用戶輸入的數(shù)據(jù)有誤。/兩景點最短路徑的查詢void mindistance() int a, b;printf(" -n");printf("| 您選擇了 2.查找最短路徑 |n");printf(" -n");printf(">>>>>>請輸入要查詢的兩景點 a b（a b表示景點編號）:n");scanf("%d %d", &a, &b);if (a >= 0 && a < mg.vexn

14、um && b >= 0 && b < mg.vexnum) printf("n -n");printf("| 起始地 | 目的地 | 最短路徑 |n");printf(" -n");printf("| %s | %s | %4d |n", , , mg.arcsab);printf(" -nn");elseprintf("輸入有誤！n");具體實現(xiàn)代碼如下：3.2.5 Floyd

15、算法計算任意兩點間的最短路徑（重點）在這個問題中需要用到floyd算法，這是此問題中的核心重點，也是難點,下面也將重點介紹。Floyd算法又稱為插點法，是一種用于尋找給定的加權(quán)圖中多源點之間最短路徑的算法。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學(xué)計算機科學(xué)系教授羅伯特·弗洛伊德命名。路徑矩陣：通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=a(i,j) n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩

16、陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。采用松弛技術(shù)（松弛操作），對在i和j之間的所有其他點進行一次松弛。所以時間復(fù)雜度為O(n3)。狀態(tài)轉(zhuǎn)移方程：其狀態(tài)轉(zhuǎn)移方程如下： mapi,j:=minmapi,k+mapk,j,mapi,jmapi,j表示i到j(luò)的最短距離，K是窮舉i,j的斷點，mapn,n初值應(yīng)該為0，或者按照題目意思來做。當(dāng)然，如果這條路沒有通的話，還必須特殊處理，比如沒有mapi,k這條路。算法過程：1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊

17、相連，則權(quán)為無窮大。2，對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則Gi,j=d，d表示該路的長度；否則Gi,j=無窮大。定義一個矩陣D用來記錄所插入點的信息，Di,j表示從Vi到Vj需要經(jīng)過的點，初始化Di,j=j。把各個頂點插入圖中，比較插點后的距離與原來的距離，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值變小，則Di,j=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D

18、，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為V5,V3,V1，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。/Floyd 算法計算任兩點間的最短路徑void floyd() int i, j, k;for (i = 0; i < mg.vexnum; i+) for (j = 0; j < mg.vexnum; j+) for (k = 0; k < mg.vexnum; k+) if (mg.arcsjk >= (mg.arcsik + mg.arcsij) mg.arcsjk = mg.arcsik + mg

19、.arcsij;在符合本問題時的Floyd算法的具體實現(xiàn)代碼如下：3.3 主程序流程在主程序中，首先通過 initGraph() 讀取圖文件并創(chuàng)建圖信息，然后展示用戶可選擇的菜單，用戶根據(jù)菜單提示進行操作。用戶輸入指令后，系統(tǒng)根據(jù)用戶的輸入指令進行 1、景點信息查詢 2、最短路徑的查詢。如果是用戶要求查詢景點信息，輸入了相應(yīng)的指令，則系統(tǒng)調(diào)用景點信息查詢模塊outInfo() 。如果用戶要求查詢景點信息，并輸入了相應(yīng)的指令，則系統(tǒng)調(diào)用最短路徑查詢模塊 mindistance() 結(jié)束退出具體操作流程如下圖：結(jié)束退出指令是否合法用戶輸入指令輸出可選操作菜單開始創(chuàng)建圖信息圖退出指令查詢景點信息指令

20、最短路徑指令是否outInfo()mindistance() .314.調(diào)試分析4.1 問題回顧和分析在程序設(shè)計中的遇到的問題有;1、 文件讀取和操作。2、 輸入文件的字符編碼的選擇。3、 求最短路徑算法的選擇。問題1、文件的讀取操作。起初用了好多種文件操作的方法，不知道用哪種方式讀取文件，最后看見同學(xué)用了一種文件讀取方式可以正確讀取文件，于是就把那個方法給引用過來了。問題2、輸入文件的字符編碼的選擇。由于不同的編譯器對字符編碼的要求不一，所以要選擇正確的字符編碼，程序可以正確地讀取文件并顯示。問題3、求最短路徑算法的選擇。最初對于最短路徑算法，我首先想到的是Dijkstra算法,但后來發(fā)現(xiàn)D

21、ijkstra算法每次只能計算兩點之間的最短路徑，在這個問題中用起來比較煩瑣，最后發(fā)現(xiàn)Floyd算法可以很好地解決這個問題，于是毫不猶豫地選擇了Floyd算法。4.2.經(jīng)驗和體會通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計我覺得要設(shè)計一個程序不簡單，尤其是要設(shè)計出一個很好的程序，那更是難上加難，在今后的學(xué)習(xí)中還要不斷加強自己設(shè)計程序的能力，進行更多的程序設(shè)計實踐，提高設(shè)計程序和寫程序的水平。5.測試結(jié)果二叉樹的三種遍歷 -基于棧的非遞歸遍歷1.設(shè)計目的數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法

22、）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。在當(dāng)今信息時代，信息技術(shù)己成為當(dāng)代知識經(jīng)濟的核心技術(shù)。我們時刻都在和數(shù)據(jù)打交道。比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠程教育報名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機上所處理的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)

23、學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：1、 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2、 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3、 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；四訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)

24、一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)2.需求分析2.1課程設(shè)計的內(nèi)容和要求二叉樹的遍歷: 對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。2.2選題的意義及背景二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用指針建立二叉樹中結(jié)點之間的關(guān)系。二叉鏈存儲結(jié)構(gòu)的每個結(jié)點包含三個域，分別是數(shù)據(jù)域，左孩子指針域，右孩子指針域。因此每個結(jié)點為leftchild data rightchild 由二叉樹的定義知可把其遍歷設(shè)計成遞歸算法。共有前序遍歷、中序遍歷、后序遍歷。可

25、先用這三種遍歷輸出二叉樹的結(jié)點。采用遞歸算法設(shè)計，以前序遍歷為例，它要求首先要訪問根節(jié)點，然后前序遍歷左子樹和前序遍歷右子樹。特點在于所有未被訪問的節(jié)點中，最后訪問結(jié)點的左子樹的根結(jié)點將最先被訪問，這與堆棧的特點相吻合。因此可借助堆棧實現(xiàn)二叉樹的遞歸遍歷。將輸出結(jié)果與遞歸結(jié)果比較來檢驗正確性，因此程序結(jié)果可做成菜單方便這兩種算法的結(jié)果查看。3.概要設(shè)計3.1設(shè)計思想所謂遍歷二叉樹，就是遵從某種次序，訪問二叉樹中的所有結(jié)點，使得每個結(jié)點僅被訪問一次。這里提到的“訪問”是指對結(jié)點施行某種操作，操作可以是輸出結(jié)點信息，修改結(jié)點的數(shù)據(jù)值等，但要求這種訪問不破壞它原來的數(shù)據(jù)結(jié)構(gòu)。我們訪問是輸出結(jié)點信息d

26、ata，且以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點可能有一個以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹，最后得到二叉樹所有結(jié)點的一個線性序列。令L,R,D分別代表二叉樹的左子樹、右子樹、根結(jié)點，則遍歷二叉樹有6中規(guī)則：DLR、DRL、LDR、LRD、RDL、RKD。若規(guī)定二叉樹中必須先左后右（左右順序不能顛倒），則只有DLR、LDR、LRD三種遍歷規(guī)則。稱DLR先序遍歷，LDR中序遍歷，LRD后序遍歷。3.1.1先序遍歷二叉樹若二叉樹非空，依次進行如下操作：（） 訪問根結(jié)點（） 先序遍歷左子樹（） 先序遍歷右子樹3.1.2中序遍歷二叉樹若二叉樹非

27、空，依次進行如下操作：（1）中序遍歷左子樹（2）訪問根結(jié)點（3）中序遍歷右子樹3.1.3后序遍歷二叉樹若二叉樹非空，依次進行如下操作： （1）后序遍歷左子樹 （2）后序遍歷右子樹（3）訪問根結(jié)點3.2程序數(shù)據(jù)類型 typedef struct BiTNodechar data;struct BiTNode *LChild; struct BiTNode *RChild; BiTNode,*BiTree;typedef struct snodeBiTNode pp;struct snode *next; linkstacknode,*linkstack;3.3程序模塊分析3.3.1置空棧link

28、stack InitBiTree()Linkstack top;top=(linkstack)malloc(sizeof(struct snode);if(!top) printf(“EROORn”);top=NULL;return top;3.3.2入棧void Push(linkstack top,BiTNode x)linkstack temp;temp=(linkstack)malloc(sizeof(struct snode);temp->pp=x;temp->next=top->next;top->next=temp;3.3.3出棧BiTNode Pop(l

29、inkstack top)BiTNode ss;linkstacknode *temp;temp=top->next;top->next=temp->next;ss=temp->pp;return ss;3.3.4取棧頂操作int getTop(BiTree T,char &e)if(!T)return 0;e=T->data;return 1;3.3.5判空棧int linkstackempty(linkstack top)if（！top） return 1;else return 0; 3.4函數(shù)關(guān)系：圖3.4.1 函數(shù)間的關(guān)系4.詳細設(shè)計4.1二叉樹

30、算法程序截圖和結(jié)果例如：輸入二叉樹為：A(B(,D(E,F),C(G(,H(I,J),K)。 它的前序遍歷為：ABDEFCGHIJK 它的中序遍歷為：BEDFAGIHJCK 它的后序遍歷為：EFDBIJHGKCA AB C D 當(dāng)輸入數(shù)據(jù)為 A(B(,D(E,F),C(G(,H(I,J),K) 顯示結(jié)果如下：圖4.1.15.程序測試結(jié)果及問題分析 通過與遞歸的遍歷結(jié)果相比較之后，用堆棧實現(xiàn)的非遞歸遍歷算法得出了正確的遍歷結(jié)果，可以對二叉樹進行遍歷操作。但是程序中樹的結(jié)點已經(jīng)建立好不能隨意改動這確實是一個缺點因此可以進行改進，可以用遞歸的方法建立一棵二叉樹，先建立左子樹，在建立右子樹這樣用戶輸入

31、的字符可以直接用來建樹程序的靈活性會更強。6.總結(jié) 通過一周的數(shù)據(jù)結(jié)構(gòu)實訓(xùn)，進一步加深了對數(shù)據(jù)結(jié)構(gòu)整體的理解，明白了鏈表的各種操作的實質(zhì)，并且對老師課上講的各種算法進行了實際的運用，更加掌握了各種算法的使用方法，例如鏈表的創(chuàng)建，查找，插入，二叉樹的遍歷等算法。 而且，通過這一次的實訓(xùn)，不僅加深了對數(shù)據(jù)結(jié)構(gòu)知識的了解，更復(fù)習(xí)了以前學(xué)習(xí)過的C語言，重新復(fù)習(xí)了棧等經(jīng)典算法，而且對于以前不懂得地方，例如主函數(shù)與子函數(shù)之間的實參，形參之間的傳遞，并且在二叉樹的遍歷部分復(fù)習(xí)了遞歸算法的使用。這一周的實訓(xùn)，我深刻的領(lǐng)悟到，遇到困難，一定不要畏懼，自己多動腦思考思考，所聯(lián)系自己以前學(xué)過的知識，便會有很大的進展

32、，還有就是，往往一些錯誤都不是編寫的邏輯錯誤，而是一些小錯誤點，例如忘記另外一部分的大括號，忘記分號等等，這提醒自己以后要細心，不要錯在一些小問題上。 在這次課程設(shè)計中在，雖然不會成功的編寫一個完整的程序，但是在看程序的過程中，不斷的上網(wǎng)查資料以及翻閱相關(guān)書籍，通過不斷的模索，測試，發(fā)現(xiàn)問題，解決問題和在老師的幫助下一步一步慢慢的正確運行程序決問題，終于完成了這次課程設(shè)計，雖然這次課程設(shè)計結(jié)束了但是總覺得自已懂得的知識很是不足，學(xué)無止境，以后還會更加的努力深入的學(xué)習(xí)。參考文獻1嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版），北京：清華大學(xué)出版社，2009.2顧澤元，劉文強，數(shù)據(jù)結(jié)構(gòu)（C語言版），北京：北京

33、航空航天大學(xué)出版社，20113徐德民.最新C語言程序設(shè)計M電子工業(yè)出版社1992年4唐策善，黃劉生.數(shù)據(jù)結(jié)構(gòu)M中國科學(xué)技術(shù)出版社.1992年5仲萃豪，馮玉琳.程序設(shè)計方法學(xué)M北京科學(xué)技術(shù)出版社1985年6 寧正元，王秀麗，算法與數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社，2006 7 譚浩強， 數(shù)據(jù)結(jié)構(gòu)教程上級實驗指導(dǎo) 清華大學(xué)出版社，2008. 8 朱站立，數(shù)據(jù)結(jié)構(gòu)-使用C語言西安：西安交通大學(xué)出版社，2004. 附錄1最短路徑源代碼:#include <iostream>#include <stdio.h>#include <string>#include <alg

34、orithm>using namespace std;const int MAXPLACE = 100;typedef structchar name100;char info10000;VertexType; /頂點結(jié)構(gòu)typedef structVertexType vexs10;int arcs100100;/鄰接矩陣int vexnum, arcnum;/頂點個數(shù)，邊的個數(shù) MGraph; /圖結(jié)構(gòu)MGraph mg;void floyd() int i, j, k;for (i = 0; i<mg.vexnum; i+)for (j = 0; j<mg.vexnum

35、; j+)for (k = 0; k<mg.vexnum; k+)mg.arcsij = min(mg.arcsij, mg.arcsik + mg.arcskj);void initGraph() freopen("graph.txt", "r", stdin);scanf("%d %d", &mg.vexnum, &mg.arcnum);/輸入景點信息for (int i = 0; i < mg.vexnum; i+) scanf("%s %s", &mg.vexsi.nam

36、e, &);/初始化矩陣for (int i = 0; i < 100; i+) for (int j = 0; j < 100; j+) mg.arcsij = 999999;/輸入距離for (int i = 0; i < mg.arcnum; i+) char from100;char to100;int f, t, dis;scanf("%s %s %d", &from, &to, &dis);/把景點換成編號for (int j = 0; j < mg.vexnum; j+) if

37、(strcmp(, from) = 0) f = j;if (strcmp(, to) = 0) t = j;/創(chuàng)建鄰接矩陣mg.arcsft = dis;mg.arcstf = dis;floyd();/算出各兩點之間的最短路徑freopen("CON", "r", stdin);void outPlace() printf("本校景點有：n");for (int i = 0; i < mg.vexnum; i+) printf("ttt%d、%sn",i

38、, );printf("n");void outInfo() int n;printf(" -n");printf("| 您選擇了 1.查詢景點信息 |n");printf(" -n");printf(">>>>>>請選擇您要查詢的景點（0 - %d） :n", mg.vexnum);scanf("%d", &n);if (n >= 0 && n < mg.vexnum) pri

39、ntf("t%s:ntt%snn", , );else printf("您輸入的數(shù)據(jù)有誤！n");void mindistance() int a, b;printf(" -n");printf("| 您選擇了 2.查找最短路徑 |n");printf(" -n");printf(">>>>>>請輸入要查詢的兩景點 a b（a b表示景點編號）:n");scanf("%d %d&

40、quot;, &a, &b);if (a >= 0 && a < mg.vexnum && b >= 0 && b < mg.vexnum) printf("n -n");printf("| 起始地 | 目的地 | 最短路徑 |n");printf(" -n");printf("| %s | %s | %4d |n", , , mg.arcsab);printf("

41、-nn");elseprintf("輸入有誤！n");int main() int a;initGraph();outPlace();while (1) printf(" -n");printf("| 您有以下選擇： |n");printf(" -n");printf("| |n");printf("| 1.查詢景點t 2.查找最短路徑 |n");printf("| |n");printf(" -n");printf(&quo

42、t;| 輸入對應(yīng)編號執(zhí)行相應(yīng)操作，輸入 -1 結(jié)束操作 |n");printf(" -n");scanf("%d", &a);if (a = -1) break;if (a = 1) outInfo();if (a = 2) mindistance();return 0;附錄2二叉樹遍歷源代碼:#include <stdio.h>#include <iostream>#include <stack>using namespace std;#define MaxSize 100#define MaxWi

43、dth 40typedef char ElemType;typedef struct nodeElemType data;struct node *left, *right;int isOut = 0; /訪問次數(shù)(后序遍歷會用到) BTree;void creatree(BTree *BT, char *str)BTree *stackMaxSize, *p;int top = -1, k, j = 0;/*top為棧指針,k指定是左還是右孩子,j為str指針*/char ch;*BT = NULL;ch = strj;while (ch != '0')switch (ch)

44、case '(':top+; stacktop = p; k = 1; /*為左結(jié)點*/break;case ')':top-;break;case ',':k = 2; /*為右結(jié)點*/break;default: p = (BTree *)malloc(sizeof(BTree);p->data = ch; p->left = p->right = NULL; p->isOut = 0;if (*BT = NULL) /*根結(jié)點*/*BT = p;elseswitch (k)case 1:stacktop->le

45、ft = p;break;case 2:stacktop->right = p;j+;ch = strj;void disptree(BTree *BT) BTree *stackMaxSize, *p;int levelMaxSize2, top, n, i, width = 4;if (BT != NULL)printf("n凹入表示法:n");top = 1;stacktop = BT; /*根結(jié)點入棧*/leveltop0 = width;while (top>0)p = stacktop; /*退棧并凹入顯示該結(jié)點值*/n = leveltop0;fo

46、r (i = 1; i <= n; i+) /*其中n為顯示場寬,字符以右對齊顯示*/printf(" ");printf("%c", p->data);for (i = n + 1; i <= MaxWidth; i += 2)printf("");printf("n");top-;if (p->right != NULL) /*將右子樹根結(jié)點入棧*/top+;stacktop = p->right;leveltop0 = n + width; /*顯示場寬增width*/leveltop1 = 2;if (p->left != NULL) /*將左子樹根結(jié)點入棧*/top+;stacktop =