數(shù)據(jù)結(jié)構(gòu)實驗六：簡單路徑

1、HUNAN UNIVERSITY課程實驗報告題 目： 簡單路徑 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 李 曉 鴻 完 成 日 期 2 0 1 5年 12 月 12日 一、需求分析1程序的功能 該程序可以通過構(gòu)建一個圖用來表示各個城市之間是否有高速公路連通的關(guān)系，可以實現(xiàn)查詢兩城市間所有路徑的功能,如果存在路徑則輸出。2.輸入的形式 本程序要求用戶首先輸入一個結(jié)點總數(shù)，然后輸入結(jié)點的城市編號，最后輸入要查詢所有簡單路徑的兩座城市的名稱。當(dāng)用戶輸入不合法時，提示用戶輸入有誤，并重新輸入。輸入具體格式如下：請輸入城市總數(shù)：n（大于零的整數(shù)）請輸入輸入城市1名稱：請輸入輸入城市2名稱：請輸入輸入城市

2、3名稱：.請輸入輸入城市n名稱：請輸入城市間的高速公路：請輸入兩所城市的名稱：3. 輸出的形式 若有路徑從城市A到城市B的所有路徑如下：/路徑1/路徑2若無路徑兩城市不連通4 測試數(shù)據(jù)正常的輸入：請輸入城市總數(shù)：4請輸入輸入城市1名稱：0001請輸入輸入城市2名稱：0002請輸入輸入城市3名稱：0003請輸入輸入城市4名稱：0004請輸入城市間的高速公路：0001 0002請輸入城市間的高速公路：0002 0003請輸入城市間的高速公路：0003 0004請輸入城市間的高速公路：0001 0004請輸入城市間的高速公路：0 0請輸入兩所城市的名稱：0001 0004輸出：兩城市間的路徑為：00

3、01 0002 0003 0004兩城市間的路徑為：0001 0004正常的輸入：請輸入城市總數(shù)：5請輸入輸入城市1名稱：c1請輸入輸入城市2名稱：c2請輸入輸入城市3名稱：c3請輸入輸入城市4名稱：c4請輸入輸入城市5名稱：c5請輸入城市間的高速公路：c1 c2請輸入城市間的高速公路：c1 c5請輸入城市間的高速公路：c5 c4請輸入城市間的高速公路：c4 c3請輸入城市間的高速公路：0 0請輸入兩所城市的名稱：c2 c4輸出：兩城市間的路徑為：c2 c1 c5 c4無路徑情況：請輸入城市總數(shù)：3請輸入輸入城市1名稱：a請輸入輸入城市2名稱：b請輸入輸入城市3名稱：c 請輸入城市間的高速公路

4、：a b請輸入城市間的高速公路：0 0請輸入兩所城市的名稱：a c輸出：兩城市不連通錯誤的城市個數(shù)請輸入城市總數(shù)：-1輸入錯誤重新輸入（大于零的整數(shù)）請輸入城市總數(shù) 2請輸入輸入城市1名稱：1請輸入輸入城市2名稱：2 請輸入城市間的高速公路：1 2請輸入城市間的高速公路：0 0請輸入兩所城市的名稱：1 2輸出：兩城市的路徑為 1 2存在自返路徑請輸入城市總數(shù)：2請輸入輸入城市1名稱：上海請輸入輸入城市2名稱：長沙 請輸入城市間的高速公路：上海 上海請輸入城市間的高速公路：上海 長沙請輸入兩所城市的名稱：長沙 上海輸出：長沙 上海二、概要設(shè)計1.抽象數(shù)據(jù)類型 因為各個結(jié)點之間是網(wǎng)狀結(jié)構(gòu)，那么一個

5、結(jié)點會和多個結(jié)點連接，因此我們使用圖來存儲各個結(jié)點的信息。同時我們需要一個數(shù)據(jù)結(jié)構(gòu)來搜索圖，該數(shù)據(jù)結(jié)構(gòu)滿足先進后出，所以使用棧來實現(xiàn)。2. ADTADT Stack數(shù)據(jù)對象：D ai | ai binNode, i=1,2,.,n, n0數(shù)據(jù)關(guān)系：R1 <ai-1, ai >| ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 若棧中沒有元素，則為空棧。基本操作：bool push（const BinNode&item）；bool pop（BinNode&it）；bool topValue（BinNode&it）；int lengt

6、h()；const；ADT Graph 數(shù)據(jù)對象：V,R（圖是由一個頂點集 V 和一個弧集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)） 數(shù)據(jù)關(guān)系：Graph = (V,R) VR<v,w>|v,wV且P(v,w) 基本操作：int n() =0; / 返回圖節(jié)點數(shù) int e() =0; /返回圖邊數(shù) int first(int)=0;/返回該節(jié)點的第一條鄰邊 void setEdge(int v1, int v2)/加邊 int next(int, int) =0; /返回下一條鄰邊 int getMark(int) =0;/有標記嗎 void setMark(int, int) =0;/設(shè)置標記3.

7、算法的基本思想 使用深度優(yōu)先搜索DFS對圖進行遍歷，在搜索過程中，每當(dāng)訪問一個頂點V后，DFS就會遞歸的訪問它的所有未被訪問的相鄰頂點。即先訪問點v，把所有與v相關(guān)聯(lián)的邊存入棧，彈出棧頂元素，棧頂元素代表的邊所關(guān)聯(lián)的另一個頂點就是就是要訪問的下一個元素，重復(fù)對v的操作；依次類推直到所有元素都被處理完畢。4程序流程程序主要由四個步驟組成： （1） 輸入城市總數(shù) （2） 輸入正確的城市編號列表 （3） 輸入所有的有高速公路直接連接的城市對編號 （4） 循環(huán)輸入需要尋找路徑的城市對的編號尋找它們之間的所有簡單路徑。 三詳

8、細設(shè)計1.物理數(shù)據(jù)類型 由于邊數(shù)目未知，所以對于遍歷圖的時間效率并不清楚，所以可以用鄰接表或者鄰接矩陣來實現(xiàn)，本實驗中使用鄰接矩陣。 棧元素未知，用鏈表來實現(xiàn)棧。用string保存輸入的城市名信息。2. 算法的具體步驟圖的構(gòu)建路徑的存儲深度優(yōu)先搜索棧元素的打印圖的構(gòu)建：創(chuàng)建一個城市數(shù)n*城市數(shù)n的二階矩陣，并且給每一個元素賦值為零。Graph(int numVert)int i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i<numVertex

9、; i+)marki.ViMark = -1;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; i<numVertex; i+)matrixi = new intnumVertex;for (i = 0; i< numVertex; i+)/Edges start w/0 weightfor (int j = 0; j<numVertex; j+) matrixij = 0;路徑的存儲：將城市v1到城市v2在矩陣中對應(yīng)的坐標(v1,v2)賦值為1。void setEdge(int v1,

10、 int v2)  if (matrixv1v2 = 0) numEdge+; matrixv1v2 = 1;   深度優(yōu)先搜索：在搜索過程中，每當(dāng)訪問一個頂點V后，DFS就會遞歸的訪問它的所有未被訪問的相鄰頂點。即先訪問點v，把所有與v相關(guān)聯(lián)的邊存入棧，彈出棧頂元素，棧頂元素代表的邊所關(guān)聯(lián)的另一個頂點就是就是要訪問的下一個元素，重復(fù)對v的操作；當(dāng)彈出棧的元素就是我們需要到達的城市v2時，輸出整個棧的元素，再將v2的值設(shè)置為-1，表示為未訪問狀態(tài)，將v2彈

11、出棧，重復(fù)對v的操作；依次類推直到所有元素都被處理完畢。void DFS(Graph* G, int v1, int origin, int v2, AStack& b, int M100100, int D100, int& count)string Ch;b.push(G->getVal(v1);int v;G->setMark(v1, 1);if (G->getVal(v1) = G->getVal(v2)for (int i = 0; i<G->n(); i+)for (int j = 0; j<G->n(); j+)G-

12、>setEdge(i, j, Mij);/將路徑進棧cout << "兩城間的路徑為："b.print();cout << endl;b.pop(Ch);/即城市v2出棧G->setMark(v2, -1);/將v2標記為未被訪問count+;/路線多一條return;for (int w = G->first(v1); w<G->n(); w = G->next(v1, w)/訪問v1所有頂點G->setEdge(w, v1, 0);if (G->getMark(w) = -1 | w = 5)DFS

13、(G, w, origin, v2, b, M, D, count);b.pop(Ch);G->Find(Ch, v);G->setMark(v, -1);棧所有元素的打印：新建一個和需要打印棧a長度相同的棧b，棧a中每一個元素依次出棧進入棧b，直到棧a為空，棧b依次出棧，并且輸出每一個元素的值，同時將這些元素進棧a，直到棧b為空。void print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)cout<<Ch<< " "push(Ch);3

14、算法的時空分析及改進設(shè)想因為圖的鄰接矩陣是一個|V|×|V|矩陣，所以鄰接矩陣的空間代價為(|V|2)，對于有n個頂點的和E條弧的無向圖而言，DFS對每條邊分別沿兩個方向進行處理，且每個頂點必須被訪問一次，所以總的時間代價為(|V|+|E|) 。綜上可知，該程序的時間復(fù)雜度為Max（(|V|2)，(|V|+|E|)）。4. 輸入和輸出的格式.條件的輸入請輸入城市總數(shù)：n（大于零的整數(shù)）請輸入輸入城市1名稱：請輸入輸入城市2名稱：請輸入輸入城市3名稱：.請輸入輸入城市n名稱：請輸入城市間的高速公路：請輸入兩所城市的名稱：cout << "請輸入城市總數(shù)："

15、;cin >> n;if (n <= 0 )cout << "輸入錯誤重新輸入(大于零的整數(shù))" << endl;cout << "請輸入城市總數(shù)："cin >> n;Graph a(n);for (int i = 0; i<n; i+)cout << "請輸入城市" << i + 1 << "編號:"cin >> Ch;a.setVal(i, Ch);cout << "請輸

16、入城市之間的高速公路(輸入兩個0結(jié)束輸入)："cin >> Ch1;cin >> Ch2;while (Ch1 != "0")a.Find(Ch1, v1);a.Find(Ch2, v2);a.setEdge(v1, v2, 10);a.setEdge(v2, v1, 10);cout << "請輸入城市之間的公路："cin >> Ch1;cin >> Ch2;輸入要查找的城市cout << "請輸入要查找的兩個城市："cin >> Ch1

17、>> Ch2;連通情況路徑的輸出（即上述算法中的棧元素的打?。﹙oid print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)cout<<Ch<< " "push(Ch);不連通時的輸出if (count = 0)cout << "兩個城市不連通" << endl;4 測試結(jié)果正常的輸入：正常的輸入：無路徑情況：錯誤的城市個數(shù)存在自返路徑#include<iostream>#includ

18、e<fstream>#include<string>#include<iomanip>using namespace std;class AStackprivate:int size;/棧的大小int top;/棧中元素的多少string *listArray;public:AStack(int sz = 0)/構(gòu)建棧size = sz;top = 0;listArray = new stringsz;AStack()/銷毀棧deletelistArray;bool push(const string&item)/壓棧if (top = size)

19、return false;/如果棧已滿則return falseelselistArraytop+ = item;return true;bool pop(string& it)/出棧if (top = 0) return false;/如果棧為空棧，則return falseelseit = listArray-top;return true;int length()const/獲取棧的長度return top;void print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)cout&l

20、t;<Ch<< " "push(Ch);class Pointpublic:string LessonName;int ViMark;class Graph/Implement adjacency matrixprivate:int numVertex, numEdge;/Store number of vertices edgesint *matrix; / Pointer to adjacency matrixPoint *mark; / Pointer to mark arraypublic:Graph(int numVert)/ Make grap

21、h w/ numVert verticesint i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i<numVertex; i+)marki.ViMark = -1;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; i<numVertex; i+)matrixi = new intnumVertex;for (i = 0; i< numVertex; i+)/Ed

22、ges start w/0 weightfor (int j = 0; j<numVertex; j+) matrixij = 0;Graph()delete mark;for (int i = 0; i<numVertex; i+)delete matrixi;delete matrix;int n()return numVertex;int e()return numEdge;int first(int v)/ Return v's first neighborint i;for (i = 0; i<numVertex; i+)if (matrixvi != 0

23、&& marki.ViMark = -1) return i;return i; / Return n if noneint next(int v1, int v2)/ Get v1's neighbor after v2int i;for (i = v2 + 1; i<numVertex; i+)if (matrixv1i != 0 && marki.ViMark = -1)/cout<<"此時next的i值是:"<<v1+1<<" "<<i+1<<

24、;endl; return i;return i;/ Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt)if (matrixv1v2 = 0) numEdge+;matrixv1v2 = wgt;void delEdge(int v1, int v2) / Delete edge (v1, v2)if (matrixv1v2 != 0)numEdge-;matrixv1v2 = 0;int weight(int v1, int v2)return matrixv1v2;string getVal(int v)return

25、markv.LessonName;int getMark(int v)return markv.ViMark;void setVal(int v, string val)markv.LessonName = val;void setMark(int v, int Mark)markv.ViMark = Mark;void Find(string search, int& v)for (int i = 0; i<numVertex; i+)if (marki.LessonName = search)v = i;return;cout << "路徑錯誤"

26、; << endl;return;void DFS(Graph* G, int v1, int v2, AStack& b, int& count)string Ch;b.push(G->getVal(v1);/將v1邊進棧int v;G->setMark(v1, 1);if (G->getVal(v1) = G->getVal(v2)/已經(jīng)連通的情況cout << "兩城間的路徑為："b.print();cout << endl;b.pop(Ch);/即城市v2出棧G->setMark(v2, -1);/將v2標記為未被訪問count+;/路線多一條return;for (int w = G->first(v1); w<G->n(); w = G->next(v1, w)/訪問v1所有邊G->setEdge(w, v1, 0);/訪問后G圖中此條路徑變?yōu)?if (G->getMark(w) = -1 )DFS(G, w, v2, b, count);/訪問v1的下一條路徑b.pop(Ch);/出棧并且將v1邊的值給chG->Find(Ch, v);/找到v對應(yīng)的邊G->setMark(v, -1);/設(shè)置為未訪問int m