數(shù)據(jù)結(jié)構(gòu)A第三次實(shí)驗(yàn)報(bào)告

1、實(shí) 驗(yàn) 報(bào) 告（2014 / 2015 學(xué)年 第 二 學(xué)期）課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)A實(shí)驗(yàn)名稱(chēng)圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問(wèn)題實(shí)驗(yàn)時(shí)間年月日指導(dǎo)單位計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系指導(dǎo)教師學(xué)生姓名班級(jí)學(xué)號(hào)學(xué)院(系)管理學(xué)院專(zhuān) 業(yè) 信息管理與信息系統(tǒng)實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱(chēng)圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問(wèn)題指導(dǎo)教師陳蕾實(shí)驗(yàn)類(lèi)型設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2一、 實(shí)驗(yàn)?zāi)康暮鸵螅?）圖的基本運(yùn)算驗(yàn)證教材中關(guān)于在鄰接矩陣和鄰接表兩種不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本運(yùn)算的算法。在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的深度和廣度優(yōu)先遍歷算法。設(shè)計(jì)主函數(shù)，測(cè)試上述運(yùn)算。提示：擴(kuò)充MGraph類(lèi)，在擴(kuò)充類(lèi)上增加DFS和BFS函數(shù)。（2）飛機(jī)最

2、少換乘次數(shù)問(wèn)題 設(shè)有n個(gè)城市，編號(hào)為0n-1，m條航線的起點(diǎn)和終點(diǎn)由用戶(hù)輸入提供。尋找一條換乘次數(shù)最少的線路方案。 提示：可以使用有向圖表示城市間的航線。只要兩城市間有航班，則圖中這兩點(diǎn)間存在一條權(quán)為1的邊?？梢允褂肈ijkstra算法實(shí)現(xiàn)。思考：如果是城市公交車(chē)的最少換乘問(wèn)題，將如何解決？假如希望使用類(lèi)似的算法，則圖中的邊如何設(shè)置？要求：（1）掌握在圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)圖的基本運(yùn)算的算法。（2）學(xué)習(xí)使用圖算法解決應(yīng)用問(wèn)題的方法。二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)中文五號(hào)宋體，英文五號(hào)Times new roman字體，1.25倍行距硬件：微型計(jì)算機(jī)軟件：Windows 操作系統(tǒng)、Micro

3、soft Visual C+6.0 三、實(shí)驗(yàn)原理及內(nèi)容1、類(lèi)和類(lèi)的層次結(jié)構(gòu)Queueabstrat+ virtual void EnQueue( T &x)=0; + virtual void DeQueue()=0+ virtual bool IsEmpty() const=0 + virtual bool IsFull() const=0+ virtual T Front()=0 SeqQueue-int front,rear;-int MaxSize;-T *q;+ SeqQueue()+SeqQueue()+ void EnQueue( T &x)+ void DeQu

4、eue()+ T Front()+ bool IsEmpty() const+ bool IsFull() constT GraphQueue 父類(lèi)： 父類(lèi)： LGraphSeqQueue 子類(lèi)： 子類(lèi):繼承關(guān)系 繼承關(guān)系Graphabstract#int n#int e+virtual Graph()+virtual ResultCode Insert(int u, int v, T& w)=0+virtual ResultCode Remove(int u, int v)=0+virtual bool Exist(int u, int v)const=0LGraph#ENode&l

5、t;T>* a+LGraph(int mSize)+LGraph()+ResultCode Insert(int u, int v, T& w)+ResultCode Change(int u,int v,T& w)+ResultCode Remove(int u, int v)+bool Exist(int u, int v)const+int Vertices()+void Output()ExtLGraph+ExtLGraph(int mSize):LGraph<T>(mSize)+void DFS(); +void BFS();+void CallIn

6、Degree(int* InDegree);+void TopoSort(int* order);+int Choose(int *d,bool* s);+void Dijkstra(int v,T* d,int* path);+void BetweenMinPath(int a,int b);-void DFS(int v, bool* visited);-void BFS(int v, bool* visited);實(shí) 驗(yàn) 報(bào) 告2、算法及數(shù)據(jù)結(jié)構(gòu)(1)圖的寬度優(yōu)先遍歷所使用的隊(duì)列結(jié)構(gòu) 0 1 2 3 4 5 6 7=maxSize-1 f r 隊(duì)列結(jié)構(gòu)示意圖(2)圖的結(jié)構(gòu)示意 70 10

7、 35 20 30 (3)圖的鄰接表表示 (4)圖的鄰接矩陣表示 0 1 2 3 4 50 0 0 0 0 0 01 1 0 1 0 0 12 0 1 0 0 1 13 1 0 0 0 1 04 0 1 0 0 1 15 1 1 0 0 0 03、函數(shù)流程示意圖開(kāi)始對(duì)象調(diào)用函數(shù)BFS（）判斷對(duì)象是否為空 是 否將圖的頂點(diǎn)存入隊(duì)列判斷隊(duì)列是否為空 是 否按照FIFO原則，輸出頂點(diǎn)值后出隊(duì)判斷出隊(duì)頂點(diǎn)是否有未訪問(wèn)頂點(diǎn) 否 是未訪問(wèn)頂點(diǎn)入隊(duì)結(jié)束實(shí)現(xiàn)按層次遍歷函數(shù)BFS()流程示意圖實(shí) 驗(yàn) 報(bào) 告4、核心算法代碼（1）圖的寬度優(yōu)先遍歷，使用鄰接矩陣實(shí)現(xiàn)void MGraph<T>:BFS(

8、) bool* visited =new booln; for(int i= 0; i <n; i+) visitedi =false; for(int i= 0; i <n; i+) if(!visitedi) BFS(i, visited); delete visited;void MGraph<T>:BFS(int v, bool* visited)SeqQueue<int> q(20);visitedv =true; cout << " " << v;q.EnQueue(v);while(!q.IsEmpt

9、y()q.Front(v);q.DeQueue();for(int i=0;i<n;i+)if(!visitedi)&&(avi!=INFTY) /當(dāng)頂點(diǎn)未被訪問(wèn)以及兩頂點(diǎn)間存在路徑才訪問(wèn)visitedi=true;cout<<" "<<i;q.EnQueue(i);（2）圖的深度優(yōu)先遍歷，使用鄰接矩陣實(shí)現(xiàn)void MGraph<T>:DFS() bool* visited =new booln; for(int i= 0; i <n; i+) visitedi =false; for(int i= 0; i

10、<n; i+) if(!visitedi) DFS(i, visited); delete visited;template<class T>void MGraph<T>:DFS(int v, bool* visited) visitedv =true; cout << " " <<v; for(int i=0;i<n;i+) if(!visitedi)&&(avi!=INFTY) DFS(i,visited); （3）Djikstra算法void ExtLGraph<T>:Dijkst

11、ra(int v,T* d,int* path)int i,k,w1;ENode<T>* p=av;if(v<0|v>n-1) cout<<"OutOfBounds!"<<endl;bool* s=new booln;for(i=0;i<n;i+)si=false;if(i=v) di=0;else di=INFTY;pathi=-1;while(p)i=p->adjVex;di=p->w;pathi=v;p=p->nextArc;p=NULL;sv=true;dv=0;for(i=1;i<n;i

12、+)k=Choose(d,s);sk=true;p=ak;for(;p;p=p->nextArc)w1=p->adjVex;if(!sw1&&dk+p->w<dw1)dw1=dk+p->w;pathw1=k;（4）求圖的任意兩點(diǎn)之間的最短路徑算法void ExtLGraph<T>:BetweenMinPath(int a, int b)int x=this->n;int y=b;if(a<0|a>x|b<0|b>x) /對(duì)輸入數(shù)據(jù)進(jìn)行越界判斷cout<<"OutofBounds!&qu

13、ot;<<endl;int* d=new intx;int* path=new intx;this->Dijkstra(a,d,path);if(pathb=-1)cout<<"The path is NotPresent!"<<endl;return;elseint n=0;int* pathmin=new int; /申請(qǐng)動(dòng)態(tài)一維數(shù)組由于存儲(chǔ)路徑while(pathy!=-1)pathminn=pathy;n+;y=pathy;n=n-2;cout<<"the path is: ("<<

14、;a;for(;n>=0;n-) /倒序輸出路徑數(shù)組，結(jié)果為頂點(diǎn)a到b的路徑cout<<" "<<pathminn; cout<<" "<<b<<")"<<endl;cout<<"the distance is:"<<db<<endl;（5）主函數(shù)程序int main(void)int b=10;cout<<"請(qǐng)輸入將要建立圖的頂點(diǎn)數(shù)："<<endl;cin&

15、gt;>b;ExtLGraph<int> lg(b);enum ResultCode status=Failure;int u=0,v=0,w=0,a=0;int* order=new intb;system("color 70");menu(); while (a!=7) cin>>a;switch(a) case 1:cout<<"請(qǐng)輸入始點(diǎn)u和終點(diǎn)v以及權(quán)值w:"<<endl;while(!(u<0|v<0|w<0)cin>>u>>v>>w;

16、status=lg.Insert(u,v,w);if(status=Success)/cout<<"Success!"<<endl;else if(status=Duplicate)cout<<"the path is exist!"<<endl<<"Please input again!"<<endl;cin>>u>>v>>w;else if(status=Failure&&!(u<0|v<0|w&

17、lt;0)cout<<"Input Error!"<<endl;cin>>u>>v>>w;system("pause");system("cls");menu(); break; case 2:cout<<"請(qǐng)輸入始點(diǎn)u和終點(diǎn)v以及要改變的權(quán)值w:"<<endl;cin>>u>>v>>w;status=lg.Change(u,v,w);if(status=Success)/*cout<<

18、;"Success!"<<endl;*/else cout<<"The path is NotPresent!"<<endl;system("pause");system("cls");menu();break;case 3: cout<<"請(qǐng)輸入要?jiǎng)h除的始點(diǎn)u和終點(diǎn)v:"<<endl;cin>>u>>v;status=lg.Remove(u,v);if(status=Success)cout<<&q

19、uot;Success!"<<endl;else cout<<"The path is NotPresent!"<<endl<<"Remove Failure!"<<endl;system("pause"); system("cls");menu(); break; case 4:cout<<"BFS :"<<endl; lg.BFS();cout<<endl<<"DF

20、S :"<<endl;lg.DFS();cout<<endl;system("pause");system("cls");menu(); break;case 5:cout<<"the TopoSort is: "lg.TopoSort(order);cout<<endl;system("pause");system("cls");menu(); break;case 6: cout<<"請(qǐng)輸入要查詢(xún)最短路徑的始點(diǎn)u和終點(diǎn)v:"<<endl;cin>>u>>v;lg.BetweenMinPath(u,v);system("pause");system("cls");menu();