醫(yī)院選址問題(數(shù)據(jù)結(jié)構(gòu))大作業(yè)

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