數(shù)據(jù)結(jié)構(gòu)第二次試驗(yàn).地鐵換乘

-/數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（二）學(xué)院自動(dòng)化學(xué)院學(xué)號(hào)姓名徐璐峰日期2017-12-18-/實(shí)驗(yàn)?zāi)康氖炀氄莆請(qǐng)D的存儲(chǔ)方式；了解圖的特性，學(xué)習(xí)在實(shí)際問題背景下靈活運(yùn)用圖；掌握?qǐng)D的兩種最短路徑算法。實(shí)驗(yàn)內(nèi)容為簡(jiǎn)化問題，假設(shè)南京現(xiàn)有三條地鐵線：1號(hào)線、2號(hào)線和3號(hào)線，線路都是雙向的。3條地鐵線的站點(diǎn)名分別如下，地鐵線交叉的換乘點(diǎn)用T1、T2等表示。請(qǐng)根據(jù)3條地鐵線的站點(diǎn)和換乘點(diǎn)構(gòu)造圖。編寫程序，任意輸入兩個(gè)站名名稱，輸出乘坐地鐵最少需要經(jīng)過的車站數(shù)量（含輸入的起點(diǎn)和終點(diǎn)，換乘站點(diǎn)只計(jì)算一次）。謝謝閱讀地鐵1號(hào)線（直線）經(jīng)過車站：A1A2A3T1A4A5A6A7A8T2A9A10A11A12T3A13A14A15T4A16謝謝閱讀地鐵2號(hào)線（直線）經(jīng)過車站：B1T5B2B3B4B5T2B6B7B8B9B10B11T3B12B13T6B14B15精品文檔放心下載地鐵3號(hào)線（環(huán)線）經(jīng)過車站：C1C2C3C4C5T1C6C7C8C9C10T5C11C12C13T6C14C15T4C16C17C18精品文檔放心下載實(shí)驗(yàn)要求用戶從鍵盤輸入兩個(gè)不同的站名，程序輸出最少需要經(jīng)過的車站數(shù)量（含輸入的起點(diǎn)和終點(diǎn)，換乘站點(diǎn)只計(jì)算一次）；精品文檔放心下載分別基于迪杰斯特拉算法和弗洛里德算法實(shí)現(xiàn)上述地鐵換乘問題；精品文檔放心下載程序功能模塊的劃分要適當(dāng)，多使用流程圖來描述算法結(jié)構(gòu)。感謝閱讀-/需求分析1）輸入的形式和輸入值的范圍。輸入的形式需要是地鐵站的名稱，如“A1”、“B7”、“C14”。所輸入的的站點(diǎn)名不能是所要求的站點(diǎn)名之外的名稱。精品文檔放心下載2）輸出的形式。所輸出的是基于弗洛里德算法與迪杰斯特拉算法進(jìn)行的最短路徑長(zhǎng)度求解的結(jié)果，以及最短路徑的車站路徑編號(hào)，并在輸入錯(cuò)誤的時(shí)候允許重復(fù)輸入。精品文檔放心下載3）程序所能達(dá)到的功能。用戶輸入車站起點(diǎn)與車站終點(diǎn)之后，通過迪杰斯特拉算法與弗洛伊德算法，輸出從起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度，以及最短路徑所經(jīng)過的車站編號(hào)。精品文檔放心下載4）測(cè)試數(shù)據(jù)。在程序運(yùn)行的開始，會(huì)提示用戶輸入起點(diǎn)與終點(diǎn)，在用戶輸入起點(diǎn)與終點(diǎn)之后，程序會(huì)輸出根據(jù)弗洛伊德算法所得到的最短路徑所經(jīng)過的車站數(shù)量，及經(jīng)過的車站路徑的編號(hào)。之后會(huì)再輸出根據(jù)迪杰斯特拉算法所得的最短路徑所經(jīng)過的車站數(shù)量，及所經(jīng)過的車站路徑的編號(hào)。如果所輸入起點(diǎn)或終點(diǎn)不存在，則會(huì)提示“起點(diǎn)/終點(diǎn)輸入錯(cuò)誤，請(qǐng)確認(rèn)后重新輸入?！敝髸?huì)繼續(xù)出現(xiàn)“請(qǐng)輸入起點(diǎn)/終點(diǎn)：”之后，用戶就可以重新輸入原來輸入錯(cuò)誤的起點(diǎn)或終點(diǎn)車站名。在確認(rèn)起點(diǎn)與終點(diǎn)都輸入正確之后，程序就會(huì)輸出最短路徑與路徑編號(hào)。在一次程序執(zhí)行完畢后，支持用戶重復(fù)輸入。感謝閱讀概要設(shè)計(jì)在程序中之定義了一種抽象數(shù)據(jù)類型，structGraph，它包含三個(gè)元素，intarrAcc[56][56];//鄰接矩陣intverCount;//點(diǎn)數(shù)intarcCount;//邊數(shù)。并且在程序開始的時(shí)候，還定義了長(zhǎng)度為56的string型數(shù)組，用于存儲(chǔ)所有的地鐵站點(diǎn)。在程序運(yùn)行開始的時(shí)候，會(huì)先調(diào)用change_train函數(shù)，在change_train函數(shù)中，會(huì)先對(duì)g.arrAcc[56][56]鄰接矩陣進(jìn)行初始化。之后調(diào)用floyd函數(shù)，及printres函數(shù)，輸出起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度及路徑車站編號(hào)。之后，會(huì)繼續(xù)調(diào)用Dijkstra函數(shù)及searchPath函數(shù)，輸出起點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度及路徑車站編號(hào)。感謝閱讀詳細(xì)設(shè)計(jì)類視圖整個(gè)程序中所寫的函數(shù)有：floyd函數(shù)，transform函數(shù)，printres函數(shù)，Dijkstra函數(shù)，searchPath函數(shù)，change_train函數(shù)。謝謝閱讀Floyd函數(shù)(圖g,鄰接矩陣dis[][],用來存儲(chǔ)路徑的矩陣path[][])感謝閱讀{//初始化path矩陣For(row0to總的站點(diǎn)數(shù))For(col0to總的站點(diǎn)數(shù))path[row][col]←row;-/For(k 0to總的站點(diǎn)數(shù))For（i 0to總的站點(diǎn)數(shù))For(j 0to總的站點(diǎn)數(shù)){//存在更近的路徑，更新If(dis[i][j]>dis[i][k]+dis[k][j]){感謝閱讀dis[i][j]←dis[i][k]+dis[k][j];謝謝閱讀path[i][j]←path[k][j];}}}Transform函數(shù)(字符c){For(i 0to站點(diǎn)數(shù))If(存儲(chǔ)所有站點(diǎn)的數(shù)組s[i]==c)返回i;}Printres函數(shù)(圖Graph*p,經(jīng)floyd函數(shù)轉(zhuǎn)化后的鄰接矩陣dis[56][56],存儲(chǔ)路徑的矩陣感謝閱讀path[56][56],起點(diǎn)start,終點(diǎn)end)謝謝閱讀{起點(diǎn)數(shù)碼st=transform(起點(diǎn)字符start);感謝閱讀終點(diǎn)數(shù)碼en=transform(終點(diǎn)字符end);//將起點(diǎn)與終點(diǎn)轉(zhuǎn)化為存儲(chǔ)站點(diǎn)的數(shù)組中對(duì)應(yīng)的下標(biāo)輸出<<”起點(diǎn)->終點(diǎn)”<<endl;感謝閱讀輸出<<"根據(jù)弗洛伊德算法得，最少經(jīng)過的車站數(shù)量:"<<dis[st][en]+1<<endl;謝謝閱讀輸出<<"經(jīng)過的車站路徑編號(hào):";For(i 0to站點(diǎn)數(shù))For(j 0to站點(diǎn)數(shù)){If(i==起點(diǎn)數(shù)碼st并且j==終點(diǎn)數(shù)碼en)//輸出路徑精品文檔放心下載{stack<int>pathrout; //壓棧k←j;do{k←path[i][k];k入pathrout的棧}當(dāng)(k不等于i);輸出<<存儲(chǔ)站點(diǎn)的數(shù)組s[pathrout的棧頂元素];精品文檔放心下載彈出pathrout的棧頂元素；length←棧pathrout的大小;For(t 0tolength){-/輸出<<"->"<<存儲(chǔ)站點(diǎn)的數(shù)組s[pathrout的棧頂元素];精品文檔放心下載彈出pathrout的棧頂元素;}輸出<<"->"<<用戶輸入的終點(diǎn);跳出循環(huán);}}}Dijkstra函數(shù)(總的站點(diǎn)數(shù)n,起點(diǎn)v,當(dāng)前點(diǎn)到起點(diǎn)的最短路徑長(zhǎng)度distence,記錄當(dāng)前節(jié)點(diǎn)的掐一個(gè)節(jié)點(diǎn)prev,記錄圖兩點(diǎn)間的路徑長(zhǎng)度c[56][56]){謝謝閱讀bools[56]; //判斷是否已存入該點(diǎn)到S集合中精品文檔放心下載For（i 0to總的站點(diǎn)數(shù)n){distence[i]←c[v][i];s[i]=0; //初始都未用過該點(diǎn)If(起點(diǎn)到第i個(gè)點(diǎn)的距離為1000)第i個(gè)點(diǎn)的前一個(gè)點(diǎn)為0；否則第i個(gè)點(diǎn)的前一個(gè)點(diǎn)為起點(diǎn)；}//依次將未放入S集合的結(jié)點(diǎn)中，取distence[]最小值的結(jié)點(diǎn)，放入結(jié)合S中謝謝閱讀//一旦S包含了所有V中頂點(diǎn)，distence就記錄了從源點(diǎn)到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度感謝閱讀For(i 1ton){u←v;//找出當(dāng)前未使用的點(diǎn)j的distence[j]最小值感謝閱讀For(j 0ton)if(s[j]等于0 并且起點(diǎn)到第j個(gè)點(diǎn)的距離（temp）小于1000)謝謝閱讀{u←j; //u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的號(hào)碼精品文檔放心下載tmp←distence[j];}s[u]←1; //表示u點(diǎn)已存入S集合中//更新distenceFor(j 0ton)If(s[j]為0 并且點(diǎn)j到點(diǎn)u的距離c[u][j]小于1000)謝謝閱讀{newdist←distence[u]+c[u][j];精品文檔放心下載If(newdist<distence[j])感謝閱讀{distence[j]←newdist;//更新起點(diǎn)到第j個(gè)點(diǎn)的最短路徑感謝閱讀prev[j]←u;//更新第j個(gè)點(diǎn)的前一個(gè)點(diǎn)-/}}}}searchPath函數(shù)(用于表示當(dāng)前點(diǎn)的前一個(gè)點(diǎn)的數(shù)組prev,起點(diǎn)v,intu)謝謝閱讀{intque[56];tot←1;que[tot]←u;tot自增;tmp←prev[u];當(dāng)(tmp不等于v){que[tot]←tmp;tot自增;tmp←prev[tmp];}que[tot]←v;For(i tot to1)If(i不等于1)輸出<<s[que[i]]<<"->";否則輸出<<s[que[i]]<<endl;換行；}change_train函數(shù)(){distence[56];記錄起點(diǎn)到當(dāng)前點(diǎn)的最短路徑感謝閱讀prev[56]; 記錄當(dāng)前點(diǎn)的前一個(gè)結(jié)點(diǎn)path[56][56];記錄路徑matrix[56][56];用于備份的矩陣arrAcc[56][56];鄰接矩陣g.verCount=56;//定義總的站點(diǎn)的數(shù)目+1感謝閱讀For(i 0to56)distence[i]←max;//初始化鄰接矩陣For(i 0tog.verCount(56)){感謝閱讀For(k 0tog.verCount(56))感謝閱讀{If(i與k相同)g.arrAcc[i][k]=0;否則-/g.arrAcc[i][k]=max;}}//輸入A環(huán)線各點(diǎn)連接情況，每個(gè)邊權(quán)重都為1a[20]={0,1,2,49,3,4,5,6,7,50,8,9,10,11,51,12,13,14,52,15};精品文檔放心下載For（i 0to19){g.arrAcc[a[i]][a[i+1]]←1;謝謝閱讀g.arrAcc[a[i+1]][a[i]]←1;感謝閱讀}//輸入B線各點(diǎn)連接情況，每個(gè)權(quán)重都為1b[19]={16,53,17,18,19,20,50,21,22,23,24,25,26,51,27,28,54,29,30};//19個(gè)點(diǎn)精品文檔放心下載For(i 0to18){g.arrAcc[b[i]][b[i+1]]←1;精品文檔放心下載g.arrAcc[b[i+1]][b[i]]←1;謝謝閱讀}//輸入C線各點(diǎn)連接情況，每個(gè)權(quán)重都為1c[23]={31,32,33,34,35,49,36,37,38,39,40,53,41,42,43,54,44,45,52,46,47,48,31};//23個(gè)點(diǎn)(因?yàn)槭黔h(huán)線，所以點(diǎn)數(shù)加一）精品文檔放心下載For(i 0to22){g.arrAcc[c[i]][c[i+1]]←1;精品文檔放心下載g.arrAcc[c[i+1]][c[i]]←1;精品文檔放心下載}For(i 0to56){For(j 0to56){arrAcc[i][j]←g.arrAcc[i][j];感謝閱讀}}//因?yàn)槭褂猛旮ヂ逡恋滤惴ㄖ?，g.arrAcc的返回值已經(jīng)變化了，//故在此將g.arrAcc中的值都賦值給matrix二維數(shù)組中，進(jìn)行備份For(i0to56){謝謝閱讀For(j 0to56){matrix[i][j]←g.arrAcc[i][j];感謝閱讀}}For(i 0to56){matrix[i][i]←max;}while(true){//利用這個(gè)死循環(huán)來實(shí)現(xiàn)用戶的重復(fù)輸入精品文檔放心下載調(diào)用floyd函數(shù)(&g,arrAcc,path);謝謝閱讀-/定義judge1=0,judge2=0;輸出<<"請(qǐng)輸入起點(diǎn)與終點(diǎn)：";輸入>>start>>end;當(dāng)(judge1==0或者judge2==0){精品文檔放心下載For(i 0to56){If(s[i]==start){judge1←1;跳出循環(huán);}謝謝閱讀否則judge1←0;}If(judge1==0){輸出<<"起點(diǎn)輸入錯(cuò)誤，請(qǐng)確認(rèn)后重新輸入！"<<換行;謝謝閱讀輸出<<"請(qǐng)輸入起點(diǎn)：";輸入>>start;}For(i 0to56){If(s[i]==end){judge2←1;跳出循環(huán);}精品文檔放心下載否則judge2←0;}If(judge2==0){輸出<<"終點(diǎn)輸入錯(cuò)誤，請(qǐng)確認(rèn)后重新輸入！"<<換行;精品文檔放心下載輸出<<"請(qǐng)輸入終點(diǎn)：";輸入>>end;}}n=transform(end);v=transform(start);調(diào)用printres(&g,arrAcc,path,start,end);謝謝閱讀輸出<<換行;For(i 0to56){//使用完弗洛伊德算法之后，g.arrAcc已經(jīng)變了，所以需要鄰接矩陣謝謝閱讀進(jìn)行重置For(j 0to56){arrAcc[i][j]←matrix[i][j];謝謝閱讀}}調(diào)用Dijkstra(56,v,distence,prev,matrix);謝謝閱讀//最短路徑長(zhǎng)度輸出<<"根據(jù)迪杰斯特拉算法得，最少經(jīng)過的車站數(shù)量:"<<distence[n]+1<<換行;謝謝閱讀//路徑輸出<<"經(jīng)過的車站路徑編號(hào):";調(diào)用searchPath(prev,v,n);}}函數(shù)調(diào)用關(guān)系圖-/調(diào)試分析1）調(diào)試過程中遇到的問題及其解決辦法，以及對(duì)整個(gè)設(shè)計(jì)和實(shí)現(xiàn)過程的回顧討論與分析；謝謝閱讀問題一：在進(jìn)行完floyd算法之后，鄰接矩陣arrAcc[56][56]的值已經(jīng)變化了，此時(shí)再利用這個(gè)矩陣進(jìn)行接下來的Dijkstra算法，以及在用戶九子那個(gè)重復(fù)輸入，重復(fù)調(diào)用floyd與Dijkstra函數(shù)，都是不能得出正確的結(jié)果的。在對(duì)這個(gè)點(diǎn)進(jìn)行調(diào)試的時(shí)候，就頗費(fèi)了些功夫，最后不得不先將arrAcc數(shù)組儲(chǔ)存起來，每次在調(diào)用floyd之前，都新建一個(gè)matrix[56][56]數(shù)組，將arrAcc[56][56]數(shù)組中的值都復(fù)制進(jìn)來，之后讓floyd函數(shù)調(diào)用matrix數(shù)組，而不再調(diào)用arrAcc數(shù)組。問題二：在借用網(wǎng)上的代碼的時(shí)候，網(wǎng)上的算法中，無論矩陣還是數(shù)組，下標(biāo)都是從1開始的，但我自己所建的數(shù)組，為了節(jié)省內(nèi)存，都是從0開始的，所以在將從1開始的數(shù)組以及矩陣轉(zhuǎn)化為從0開始的數(shù)組與矩陣的時(shí)候，廢了很多麻煩。但無論是從0開始，還是從1開始，只是表達(dá)數(shù)組與矩陣的思想不同，效果都是一樣的。感謝閱讀問題三:在設(shè)計(jì)實(shí)現(xiàn)用戶的重復(fù)輸入的過程中，一直找不到如果用戶輸入錯(cuò)誤之謝謝閱讀-/后，重新輸入時(shí)，輸入正確之后，結(jié)束循環(huán)的條件，就一直陷入死循環(huán)中。最后，就設(shè)置了judge1和judge2兩個(gè)數(shù)來記錄是否能夠在已有的站點(diǎn)中找到所輸入的站點(diǎn)。在依據(jù)用戶輸入的站點(diǎn)對(duì)已有的站點(diǎn)數(shù)組進(jìn)行遍歷的時(shí)候，在數(shù)組中的站點(diǎn)與輸入的站點(diǎn)不相同的時(shí)候，用0對(duì)judge1/judge2進(jìn)行重復(fù)賦值，一旦找到站點(diǎn)數(shù)組中的某個(gè)站點(diǎn)與用戶所輸入的站點(diǎn)相同的時(shí)候，用1對(duì)judge1/judge2進(jìn)行賦值，并且break。判斷循環(huán)的條件就是judge1/judge2==0。問題四：在整個(gè)程序中涉及到很多對(duì)矩陣進(jìn)行的操作，包括很多對(duì)于矩陣中的值的修改，在很多情況下，在代碼運(yùn)行錯(cuò)誤，以及出現(xiàn)意想不到的結(jié)果的時(shí)候，通過輸出中間變量矩陣來判斷程序那里出現(xiàn)了問題是非常方便的。所以在整個(gè)程序編寫的過程中，也寫了很多的將程序運(yùn)行過程中生成的矩陣輸出的代碼，以便弄清楚代碼哪里出現(xiàn)了問題。精品文檔放心下載2）算法的時(shí)空分析?？臻g復(fù)雜度：在整個(gè)程序運(yùn)行的過程中，定義的變量有arrAcc[56][56],s[56],queue[56][56],distance[56][56],prev[56][56],path[56][56],matrix[56][56],以精品文檔放心下載及三個(gè)，大小總共為64的用于記錄站點(diǎn)編號(hào)的數(shù)組。所以程序的空間復(fù)雜度為O(6608).謝謝閱讀時(shí)間復(fù)雜度：程序中所有的循環(huán)都是以56為單位的。在整個(gè)程序運(yùn)行的過程中，共進(jìn)行了以56為單位的單重循環(huán)5次，雙重循環(huán)8次，三重循環(huán)1次。所以整個(gè)程序的時(shí)間復(fù)雜度為O(200984).謝謝閱讀測(cè)試結(jié)果當(dāng)輸入的車站名滿足要求時(shí)：所設(shè)計(jì)的程序能夠?qū)崿F(xiàn)重復(fù)輸入，更大程度的滿足用戶需求。精品文檔放心下載當(dāng)輸入的車站名不存在時(shí)：起點(diǎn)終點(diǎn)均不存在：-/起點(diǎn)存在，終點(diǎn)不存在：終點(diǎn)存在，起點(diǎn)不存在：當(dāng)用戶重復(fù)輸入錯(cuò)誤的時(shí)候：-/在設(shè)計(jì)程序的過程中，考慮了用戶輸入錯(cuò)誤的情況。在用戶輸入錯(cuò)誤的情況下，提示用戶是起點(diǎn)，還是終點(diǎn)輸入錯(cuò)誤，之后提示用戶確認(rèn)后重新輸入。并且支持程序的重復(fù)運(yùn)行，直到用戶不再需要查詢路徑的時(shí)候，退出程序。精品文檔放心下載實(shí)驗(yàn)總結(jié)本次實(shí)驗(yàn)主要就是基于弗洛里德與迪杰斯特拉算法進(jìn)行最短路徑的求解，兩種算法雖然原理不同，但總的來說，都是對(duì)矩陣進(jìn)行操作，從而得到自己想要的結(jié)果。網(wǎng)上也有很多有關(guān)弗洛伊德算法與迪杰斯特拉算法的代碼，但將網(wǎng)上的代碼改編為自己想要的基于地鐵換乘的代碼還是有很大難度的。首先需要考慮的就是在定義儲(chǔ)存所有站點(diǎn)的數(shù)組的時(shí)候，地鐵線路的交叉點(diǎn)應(yīng)處在數(shù)組的什么位置，處于所有站點(diǎn)的末尾與處在站點(diǎn)的中間會(huì)是兩種不同的處理方法。并且網(wǎng)上的很多代碼都是數(shù)字作為整個(gè)圖的節(jié)點(diǎn)，但地鐵換乘的節(jié)點(diǎn)是站點(diǎn)名字，是string類型的量。在將代碼從基于數(shù)字到基于string也是破費(fèi)了寫功夫。謝謝閱讀創(chuàng)新之處：1.在初始化鄰接矩陣的時(shí)候，依據(jù)每個(gè)站點(diǎn)在總的存儲(chǔ)站點(diǎn)的數(shù)組里的順序，定義了分別表示三條地鐵線路的int型數(shù)組。用int型數(shù)組中的值來表示每個(gè)站點(diǎn)的下標(biāo)，這樣在初始化鄰接矩陣的時(shí)候，只用寫三個(gè)循環(huán)，就還能搞定，大大減少了代碼的工作量。精品文檔放心下載2.剛開始在看書上的關(guān)于floyd算法的時(shí)候，floyd算法的輸出結(jié)果只有矩陣，本來以為基于floyd算法只能得到最短路徑的長(zhǎng)度，無法得出最短路徑的車站編號(hào)。但