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

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

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

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

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

5、結(jié)點(diǎn)會(huì)和多個(gè)結(jié)點(diǎn)連接，因此我們使用圖來存儲(chǔ)各個(gè)結(jié)點(diǎn)的信息。同時(shí)我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來搜索圖，該數(shù)據(jù)結(jié)構(gòu)滿足先進(jìn)后出，所以使用棧來實(shí)現(xiàn)。2. ADTADT Stack數(shù)據(jù)對(duì)象：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 端為棧底。 若棧中沒有元素，則為空棧?；静僮鳎篵ool push（const BinNode&item）；bool pop（BinNode&it）；bool topValue（BinNode&it）；int lengt

6、h()；const；ADT Graph 數(shù)據(jù)對(duì)象：V,R（圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 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é)點(diǎn)數(shù) int e() =0; /返回圖邊數(shù) int first(int)=0;/返回該節(jié)點(diǎn)的第一條鄰邊 void setEdge(int v1, int v2)/加邊 int next(int, int) =0; /返回下一條鄰邊 int getMark(int) =0;/有標(biāo)記嗎 void setMark(int, int) =0;/設(shè)置標(biāo)記3.

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

8、細(xì)設(shè)計(jì)1.物理數(shù)據(jù)類型 由于邊數(shù)目未知，所以對(duì)于遍歷圖的時(shí)間效率并不清楚，所以可以用鄰接表或者鄰接矩陣來實(shí)現(xiàn)，本實(shí)驗(yàn)中使用鄰接矩陣。 棧元素未知，用鏈表來實(shí)現(xiàn)棧。用string保存輸入的城市名信息。2. 算法的具體步驟圖的構(gòu)建路徑的存儲(chǔ)深度優(yōu)先搜索棧元素的打印圖的構(gòu)建：創(chuàng)建一個(gè)城市數(shù)n*城市數(shù)n的二階矩陣，并且給每一個(gè)元素賦值為零。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;路徑的存儲(chǔ)：將城市v1到城市v2在矩陣中對(duì)應(yīng)的坐標(biāo)(v1,v2)賦值為1。void setEdge(int v1,

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

11、出棧，重復(fù)對(duì)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);/將路徑進(jìn)棧cout << "兩城間的路徑為："b.print();cout << endl;b.pop(Ch);/即城市v2出棧G->setMark(v2, -1);/將v2標(biāo)記為未被訪問count+;/路線多一條return;for (int w = G->first(v1); w<G->n(); w = G->next(v1, w)/訪問v1所有頂點(diǎn)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);棧所有元素的打?。盒陆ㄒ粋€(gè)和需要打印棧a長(zhǎng)度相同的棧b，棧a中每一個(gè)元素依次出棧進(jìn)入棧b，直到棧a為空，棧b依次出棧，并且輸出每一個(gè)元素的值，同時(shí)將這些元素進(jìn)棧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í)空分析及改進(jìn)設(shè)想因?yàn)閳D的鄰接矩陣是一個(gè)|V|×|V|矩陣，所以鄰接矩陣的空間代價(jià)為(|V|2)，對(duì)于有n個(gè)頂點(diǎn)的和E條弧的無向圖而言，DFS對(duì)每條邊分別沿兩個(gè)方向進(jìn)行處理，且每個(gè)頂點(diǎn)必須被訪問一次，所以總的時(shí)間代價(jià)為(|V|+|E|) 。綜上可知，該程序的時(shí)間復(fù)雜度為Max（(|V|2)，(|V|+|E|)）。4. 輸入和輸出的格式.條件的輸入請(qǐng)輸入城市總數(shù)：n（大于零的整數(shù)）請(qǐng)輸入輸入城市1名稱：請(qǐng)輸入輸入城市2名稱：請(qǐng)輸入輸入城市3名稱：.請(qǐng)輸入輸入城市n名稱：請(qǐng)輸入城市間的高速公路：請(qǐng)輸入兩所城市的名稱：cout << "請(qǐng)輸入城市總數(shù)："

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

16、入城市之間的高速公路(輸入兩個(gè)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 << "請(qǐng)輸入城市之間的公路："cin >> Ch1;cin >> Ch2;輸入要查找的城市cout << "請(qǐng)輸入要查找的兩個(gè)城市："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);不連通時(shí)的輸出if (count = 0)cout << "兩個(gè)城市不連通" << endl;4 測(cè)試結(jié)果正常的輸入：正常的輸入：無路徑情況：錯(cuò)誤的城市個(gè)數(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/獲取棧的長(zhǎng)度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<<"此時(shí)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 << "路徑錯(cuò)誤"

26、; << endl;return;void DFS(Graph* G, int v1, int v2, AStack& b, int& count)string Ch;b.push(G->getVal(v1);/將v1邊進(jìn)棧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標(biāo)記為未被訪問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對(duì)應(yīng)的邊G->setMark(v, -1);/設(shè)置為未訪問int m