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

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

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

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

4、短路徑(5). Floyd算法(核心)3.詳細設計3.1 數(shù)據類型的定義typedef struct char name100;/名字char info10000;/介紹VertexType; /頂點結構typedef struct VertexType vexs10;int arcs100100; /鄰接矩陣int vexnum,arcnum;/頂點個數(shù)，邊的個數(shù) MGraph;/圖結構校園道路是雙向通行的，可設校園平面圖是一個帶權的無向圖，用鄰接矩陣表示此無向網。鄰接矩陣的數(shù)據類型定義如下：3.2 功能模塊的設計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相當于無窮大/輸入距離for (int i = 0; i < mg.arcnum; i+) char from100;/開始結點名char to100;/結束結點名/f表示開始結點編號，t表示目的結點編號，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);/改變輸入流校園平面圖可以表示成為一個無向網，用一個MGraph 類型的變量 mg表示這張無向網。網中包含了景點的名字和信息，以及表示各景點之間是否有路可達鄰接矩陣，同時還保存了景點個數(shù)和邊數(shù)。其俱體定義如下：Graph.txt8 15 校門江西理工大學

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

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

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

11、并同時作出反應，向用戶展示景點的具體信息。作為算法的健壯性，這一模塊在用戶輸入查詢指令后，判斷用戶輸入的指令的合法性，防止出現(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ù)據有誤！n");具體實現(xiàn)代碼如下：3.2.4 查找兩景點的最短路徑查找兩景點的最短路徑模塊，同景點信息查詢處理模塊相似。只不過是所處理的事情不一樣。查找兩景點的最短路徑模塊要求用戶輸入要查詢的兩景點的編號a , b（a表示開始結點， b表示終止結點）。然后程序會對用戶輸入的查詢指令進行判斷合法性，如果用戶輸入的指令合法，則告訴用戶所查詢到的最短路徑。如

13、果輸入指令不合法，則提醒用戶輸入的數(shù)據有誤。/兩景點最短路徑的查詢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算法又稱為插點法，是一種用于尋找給定的加權圖中多源點之間最短路徑的算法。該算法名稱以創(chuàng)始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。路徑矩陣：通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權鄰接矩陣A=a(i,j) n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩

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

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

18、，假如D(5,1)=3則說明從V5到V1經過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)建圖信息，然后展示用戶可選擇的菜單，用戶根據菜單提示進行操作。用戶輸入指令后，系統(tǒng)根據用戶的輸入指令進行 1、景點信息查詢 2、最短路徑的查詢。如果是用戶要求查詢景點信息，輸入了相應的指令，則系統(tǒng)調用景點信息查詢模塊outInfo() 。如果用戶要求查詢景點信息，并輸入了相應的指令，則系統(tǒng)調用最短路徑查詢模塊 mindistance() 結束退出具體操作流程如下圖：結束退出指令是否合法用戶輸入指令輸出可選操作菜單開始創(chuàng)建圖信息圖退出指令查詢景點信息指令

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

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

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

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

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

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

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

27、空，依次進行如下操作：（1）中序遍歷左子樹（2）訪問根結點（3）中序遍歷右子樹3.1.3后序遍歷二叉樹若二叉樹非空，依次進行如下操作： （1）后序遍歷左子樹 （2）后序遍歷右子樹（3）訪問根結點3.2程序數(shù)據類型 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ù)關系：圖3.4.1 函數(shù)間的關系4.詳細設計4.1二叉樹

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

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

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

33、航空航天大學出版社，20113徐德民.最新C語言程序設計M電子工業(yè)出版社1992年4唐策善，黃劉生.數(shù)據結構M中國科學技術出版社.1992年5仲萃豪，馮玉琳.程序設計方法學M北京科學技術出版社1985年6 寧正元，王秀麗，算法與數(shù)據結構 清華大學出版社，2006 7 譚浩強， 數(shù)據結構教程上級實驗指導 清華大學出版社，2008. 8 朱站立，數(shù)據結構-使用C語言西安：西安交通大學出版社，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; /頂點結構typedef structVertexType vexs10;int arcs100100;/鄰接矩陣int vexnum, arcnum;/頂點個數(shù)，邊的個數(shù) MGraph; /圖結構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ù)據有誤！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;| 輸入對應編號執(zhí)行相應操作，輸入 -1 結束操作 |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; /*為左結點*/break;case ')':top-;break;case ',':k = 2; /*為右結點*/break;default: p = (BTree *)malloc(sizeof(BTree);p->data = ch; p->left = p->right = NULL; p->isOut = 0;if (*BT = NULL) /*根結點*/*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; /*根結點入棧*/leveltop0 = width;while (top>0)p = stacktop; /*退棧并凹入顯示該結點值*/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) /*將右子樹根結點入棧*/top+;stacktop = p->right;leveltop0 = n + width; /*顯示場寬增width*/leveltop1 = 2;if (p->left != NULL) /*將左子樹根結點入棧*/top+;stacktop =