計算機科學與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)大作業(yè)PAGEPAGE2實驗內(nèi)容概述n個村莊之間的交通圖用有向加權(quán)圖表示，圖中的有向邊<vi，vj>表示第i個村莊和第j個村莊之間有道路，邊上的權(quán)表示這條道路的長度?，F(xiàn)在要從這n個村莊中選擇一個村莊建一所醫(yī)院，問這所醫(yī)院應建在哪個村莊，才能使離醫(yī)院最遠的村莊到醫(yī)院最近。圖1醫(yī)院選址加權(quán)有向圖測試數(shù)據(jù)：針對圖1，輸入以下數(shù)據(jù)：輸入頂點數(shù)：5輸入頂點對和弧的權(quán)值：121232342354421433545000實驗目的概述“數(shù)據(jù)結(jié)構(gòu)”是計算機科學與技術(shù)專業(yè)一門十分重要的專業(yè)技術(shù)基礎(chǔ)課，計算機科學各領(lǐng)域及有關(guān)的應用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)。在我國，“數(shù)據(jù)結(jié)構(gòu)與算法”已經(jīng)作為理工科非計算機專業(yè)必修的信息技術(shù)基礎(chǔ)課程之一。世界上許多科技人員對學習、研究數(shù)據(jù)結(jié)構(gòu)和算法都非常重視，對于從是計算機科學及其應用的科技工作者來說，數(shù)據(jù)結(jié)構(gòu)與算法更是必須透徹的掌握的重要基礎(chǔ)。學習數(shù)據(jù)結(jié)構(gòu)與算法的最終目的是解決實際的應用問題，特別是非數(shù)值計算類型的應用問題，課程設計是加強學生實踐能力的一個強有力的手段。作為一名計算機專業(yè)的學生，通過對計算機課程兩年的學習，掌握C++和數(shù)據(jù)結(jié)構(gòu)，在完成課程設計和變成過程中，要深化對數(shù)據(jù)結(jié)構(gòu)與算法課程中的基本概念、理論和方法的理解，訓練綜合運用所學知識處理實際問題的能力，強化面向?qū)ο蟮某绦蛟O計理念，在老師的指導下完成最少換車次數(shù)問題，把自己所學的理論用具體的問題來解決，更加直接，易懂。提高程序設計與調(diào)試水平。在通過學習數(shù)據(jù)結(jié)構(gòu)，我們要掌握數(shù)據(jù)結(jié)構(gòu)的各個算法，運用學過的算法去解決實際中的問題，將數(shù)據(jù)結(jié)構(gòu)用用武之地，也能提高我們的運用能力和編寫程序的能力，對我們的技能也有進一步的提高，對我們的未來之路鋪路搭橋。在這個實驗中，我主要是類的成員函數(shù)去解決問題，除了學習到C語言的知識外，同樣還學習到C++的知識，對我的知識也有很大擴展，將C和C++相結(jié)合，達到共同解決問題的目的。在這個運用中，主要是學會類的定義以及使用，還有類的成員函數(shù)的定義和使用，通過用類的對象去調(diào)用類的成員函數(shù)，最后達到目的，這能夠體現(xiàn)出面向?qū)ο蟮木幊谭椒?，與以往的面向過程的編程方法有很大的層次性的提高，達到提高思維能力。數(shù)據(jù)結(jié)構(gòu)和算法的設計該實驗是通過計算得出在幾個村莊中的其中一個村莊建立一個距離合適醫(yī)院，使得附近各個村莊到這個醫(yī)院的距離最短，很容易讓我們想到用Floyd或者Dijkstra算法去解決問題。但是用C++同樣也可以實現(xiàn)，在C++中的類類似于C語言中的結(jié)構(gòu)體，我們正好可以用C++中的類去解決問題，因此我們需要知道類中的一些基本成員，包括私有成員和公有成員，私有成員在類外是不允許訪問的，只能通過類中的函數(shù)去訪問，因此我們需要設置類內(nèi)成員，然后通過類內(nèi)函數(shù)去訪問類中的私有成員。除了要明白類內(nèi)的私有成員和公有成員外，同意還是要明白類內(nèi)函數(shù)怎樣在類外編寫，這也是極其重要的，通過把類內(nèi)函數(shù)在類外編寫可以使類內(nèi)代碼大大的簡短，更有利于讀寫。最后還要明白構(gòu)造函數(shù)的定義和用法，構(gòu)造函數(shù)的函數(shù)名必須和類名一樣。本程序主要采用帶權(quán)圖來實現(xiàn)醫(yī)院選址實現(xiàn)總體最優(yōu)的一些功能。首先在main函數(shù)之前定義了一個類，然后在main函數(shù)運行時，根據(jù)相關(guān)的信息提示，分別輸入村莊的個數(shù)，村莊名稱，邊數(shù)(各個村莊間是否有通路)，各個道路的起點和終點，以及各個點間的距離。在main()函數(shù)中，通過調(diào)用類的構(gòu)造函數(shù)和類中的成員函數(shù)，使成員函數(shù)和構(gòu)造函數(shù)相配合，最后算出相對的最短距離從而確定超市的最優(yōu)地址，得出各個村莊到醫(yī)院的距離。 首先，構(gòu)造一個類的對象，然后再調(diào)用類的構(gòu)造函數(shù)將數(shù)據(jù)初始化，其中包括將鄰接矩陣初始化為最大值，輸入頂點名稱，再調(diào)用InsertVertex()函數(shù)插入頂點，邊數(shù)、頭頂點、尾頂點以及權(quán)值，再調(diào)用InsertEdge()插入權(quán)值。 再就是通過類對象調(diào)用類的Hospital()函數(shù)(醫(yī)院選址函數(shù))，就是在以鄰接帶權(quán)矩陣表示n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠的村莊到醫(yī)院最近。在這個函數(shù)中，首先求出任意兩頂點間的最短路徑，求各村莊離醫(yī)院最近的醫(yī)院選址，輸出要建醫(yī)院的村莊號及離醫(yī)院最遠的村莊到醫(yī)院的距離，最后結(jié)束算法，完成醫(yī)院選址問題，使離醫(yī)院最遠的村莊到醫(yī)院最近。源程序清單#include<stdio.h>#defineMaxInt10000//最大數(shù)constintMaxNumEdges=50;constintMaxNumVertices=10;//最大頂點數(shù)classGraph{private:intvNum;//當前頂點數(shù)inteNum;//當前邊數(shù)intVertex[MaxNumVertices];//頂點數(shù)組intEdge[MaxNumVertices][MaxNumVertices];//邊數(shù)組boolGetVertexPos(constint&vertex,int&i);//給出頂點vertex在圖中的位置public:Graph(constintsz=MaxNumEdges);//構(gòu)造函數(shù)boolFindVertex(constint&vertex);boolInsertVertex(constint&vertex);//插入一個頂點vertexboolInsertEdge(constintv1,constintv2,constintweight);//插入一條邊(v1,v2),該邊上的權(quán)值為weightvoidHospital();//醫(yī)院選址函數(shù)};Graph::Graph(constintsz):vNum(0),eNum(0)//構(gòu)造函數(shù){intn,e;intname,tail,head;intweight;for(inti=0;i<sz;i++)for(intj=0;j<sz;j++){if(i==j)Edge[i][j]=0;//頂點到自身權(quán)值為0elseEdge[i][j]=10000;//鄰接矩陣初始化為最大值}printf("請輸入頂點數(shù),注意本程序最多為10個!\n");scanf("%d",&n);printf("請依次輸入頂點名稱:\n");for(inti=0;i<n;i++)//依次輸入頂點，插入圖中{scanf("%d",&name);InsertVertex(name);vNum++;}printf("請輸入邊數(shù):\n");scanf("%d",&e);printf("以下輸入邊信息:\n");for(inti=0;i<e;i++){printf("請輸入第%d邊頭頂點:\n",i+1);scanf("%d",&head);printf("請輸入該邊尾頂點：\n");scanf("%d",&tail);printf("請輸入該邊權(quán)值：\n");scanf("%d",&weight);if(!InsertEdge(head,tail,weight)){printf("不存在該邊，請重輸！\n");continue;}}}boolGraph::FindVertex(constint&vertex)//給出頂點vertex在圖中的位置{for(inti=0;i<vNum;i++)if(vertex==Vertex[i])returntrue;returnfalse;}boolGraph::GetVertexPos(constint&vertex,int&i)//給出頂點vertex在圖中的位置{for(i=0;i<vNum;i++)if(vertex==Vertex[i])returntrue;returnfalse;}boolGraph::InsertVertex(constint&vertex)//插入一個頂點vertex{if(FindVertex(vertex))returnfalse;Vertex[vNum]=vertex;returntrue;}boolGraph::InsertEdge(constintv1,constintv2,constintweight)//插入一條邊(v1,v2),該邊上的權(quán)值為weight{intk=0,j=0;if(GetVertexPos(v1,k)&&GetVertexPos(v2,j)){Edge[k][j]=weight;eNum++;Edge[j][k]=weight;eNum++;returntrue;}elsereturnfalse;}voidGraph::Hospital()//在以鄰接帶權(quán)矩陣表示的n個村莊中，求醫(yī)院建在何處，使離醫(yī)院最遠的村莊到醫(yī)院的路徑最短。{intk,i,j,s;for(k=0;k<vNum;k++)//求任意兩頂點間的最短路徑for(i=0;i<vNum;i++)for(j=0;j<vNum;j++)if(Edge[i][k]+Edge[k][j]<Edge[i][j])Edge[i][j]=Edge[i][k]+Edge[k][j];intm=MaxInt;//設定m為機器內(nèi)最大整數(shù)。printf("********************************************\n");//以下為求各村離醫(yī)院最近的醫(yī)院選址intmin=MaxInt;//設定機器最大數(shù)作村莊間距離之和的初值。k=0;//k設醫(yī)院位置。for(j=0;j<vNum;j++){m=0;for(i=0;i<vNum;i++)m=m+Edge[i][j];//頂點到其它頂點最短距離的距離之和if(min>m){min=m;k=j;}//取頂點間的距離之和的最小值。}//forprintf("各村離醫(yī)院最近的醫(yī)院選址,要建醫(yī)院的村莊號:%d\n",k+1);//輸出要建醫(yī)院的村莊號//輸出要建醫(yī)院的村莊號及離醫(yī)院最遠的村莊到醫(yī)院的距離for(j=0;j<vNum;j++)if(j!=k)printf("該村莊離%d村莊最短距離為:%d\n",j+1,Edge[k][j]);}//算法結(jié)束intmain(){GraphTown.Hospital();return0;}程序調(diào)試及測試結(jié)果請輸入頂點數(shù)，注意本程序最多為10個！5請輸入頂點名稱：1 2 3 4 5以下輸入邊信息：7請輸入第1邊頂點：1請輸入該邊尾頂點：2請輸入該邊權(quán)值：1請輸入第2邊頭頂點：2請輸入該邊尾頂點：3請輸入該邊權(quán)值：1請輸入第3邊頂點：3請輸入該邊尾頂點：4請輸入該邊權(quán)值：2請輸入第邊4邊頂點：4請輸入該邊尾頂點：3請輸入該邊權(quán)值：3請輸入第邊5邊頂點：4請輸入該邊尾頂點：2請輸入該邊權(quán)值：1請輸入第邊6邊頂點：3請輸入該邊尾頂點：5請輸入該邊權(quán)值：4 請輸入第邊7邊頂點：5請輸入該邊尾頂點：5請輸入該邊權(quán)值：4****************************各村離醫(yī)院最近的醫(yī)院選址，要建醫(yī)院的村莊號：2該村莊離1村莊最短距離為：1該村莊離3村莊最短距離是：2該村莊離4村莊最短距離是：1該村莊離5村莊最短距離是：6結(jié)論計算機科學是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學。數(shù)據(jù)是計算機化的信息，它是計算機可以直接處理的最基本和最重要的對象。無論是進行科學計算或數(shù)據(jù)處理、過程控制以及對文件的存儲和檢索及數(shù)據(jù)庫技術(shù)等計算機應用領(lǐng)域中，都是對數(shù)據(jù)進行加工處理的過程。因此，要設計出一個結(jié)構(gòu)好效率高的程序，必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應的存儲表示，并利用這些特性和關(guān)系設計出相應的算法和程序。數(shù)據(jù)結(jié)構(gòu)是計算機科學與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課，是十分重要的核心課程。所有的計算機系統(tǒng)軟件和應用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設計語言是難以應付眾多復雜的課題的。要想有效地使用計算機、充分發(fā)揮計算機的性能，還必須學習和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實基礎(chǔ)。通過大型作業(yè)，讓我們可以運用結(jié)合以前學過的知識去解決現(xiàn)實中的問題，該實驗不僅是運用到C語言的知識，還運用了C++的只是，把C語言和C++相結(jié)合，很大的提高了我們的編程能力，同時也讓我們學會互相結(jié)合各種編程語言去解決問題，還能夠?qū)嶒炋岣呶覀兊膶嵺`能力，對我們個人能力的培養(yǎng)也具有很大的作用。計算機對我們的現(xiàn)實世界、現(xiàn)實生活具有很大的作用，人們能夠通過計算機去解決現(xiàn)實的問題，我們正好通過編程去解決，對現(xiàn)在來說也是很大的幫助。在數(shù)據(jù)結(jié)構(gòu)的學習過程中，我們的能力有很大的提高，對我們的未來是一個很大的幫助，對我們的編程積累很大的經(jīng)驗。我感受最深的一點是：以前用C編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單純的意識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀，只要能完成任務就行。但現(xiàn)在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合