C++数据结构课程设计,医院选址
发布网友
发布时间：2022-05-10 13:14
共2个回答
热心网友
时间：2023-10-10 01:01
using namespace std;
#define MaxInt 10000//最大数
const int MaxNumEdges=50;
const int MaxNumVertices=10; //最大顶点数
class Graph{
private:
int vNum;//当前顶点数
int eNum;//当前边数
int Vertex[MaxNumVertices];//顶点数组
int Edge[MaxNumVertices][MaxNumVertices];//边数组
bool GetVertexPos(const int &vertex,int &i);//给出顶点vertex在图中的位置
public:
Graph(const int sz= MaxNumEdges);//构造函数
bool FindVertex(const int &vertex);
bool InsertVertex(const int & vertex);//插入一个顶点vertex
bool InsertEdge(const int v1,const int v2,const int weight);//插入一条边(v1,v2),该边上的权值为weight
void Hospital();//医院选址函数
};
Graph::Graph(const int sz): vNum(0), eNum(0)//构造函数
{
int n,e;
int name,tail,head;
int weight;
for(int i=0;i<sz;i++)
for(int j=0;j<sz;j++)
{
if(i==j)
Edge[i][j]=0;//顶点到自身权值为0
else
Edge[i][j]=10000;//邻接矩阵初始化为最大值
}
cout<<"请输入顶点数,注意本程序最多为10个。\n";
cin>>n;
cout<<"请依次输入顶点名称:\n";
for(i=0;i<n;i++)//依次输入顶点，插入图中
{
cin>>name;
InsertVertex(name);
vNum++;
}
cout<<"请输入边数:\n";
cin>>e;
cout<<"以下输入边信息。\n";
for(i=0;i<e;i++){
cout<<"请输入第"<<i+1<<"边头顶点：\n";
cin>>head;
cout<<"请输入该边尾顶点：\n";
cin>>tail;
cout<<"请输入该边权值：\n";
cin>>weight;
if(!InsertEdge(head,tail,weight)){
cout<<"不存在该边，请重输！\n";
continue;
}
}
}
bool Graph::FindVertex(const int& vertex){//给出顶点vertex在图中的位置
for (int i = 0; i < vNum; i++)
if (vertex == Vertex[i])
return true;
return false;
}
bool Graph:: GetVertexPos(const int &vertex,int &i){//给出顶点vertex在图中的位置
for (i = 0; i < vNum; i++)
if (vertex == Vertex[i])
return true;
return false;
}
bool Graph::InsertVertex(const int & vertex){//插入一个顶点vertex
if (FindVertex(vertex))
return false;
Vertex[vNum] = vertex;
return true;
}
bool Graph::InsertEdge(const int v1,const int v2,const int weight){
//插入一条边(v1,v2),该边上的权值为weight
int k=0,j=0;
if(GetVertexPos(v1,k) && GetVertexPos(v2,j)){
Edge[k][j]=weight; eNum++;
Edge[j][k]=weight; eNum++;
return true;
}
else
return false;
}
void Graph::Hospital()
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{
int k,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];
int m=MaxInt; //设定m为机器内最大整数。
cout<<"********************************************"<<endl;
//以下为求各村离医院最近的医院选址
int min=MaxInt ; //设定机器最大数作村庄间距离之和的初值。
k=0; //k设医院位置。
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;} //取顶点间的距离之和的最小值。
}//for
cout<<"各村离医院最近的医院选址,要建医院的村庄号:"<<k+1<<'\n'; //输出要建医院的村庄号
//输出要建医院的村庄号及离医院最远的村庄到医院的距离
for(j=0;j<vNum;j++)
if(j!=k)
cout<<"该村庄离"<<j+1<<"村庄最短距离为:"<<Edge[k][j]<<'\n';
}//算法结束
int main(int argc, char* argv[])
{
Graph Town(MaxNumVertices);
Town.Hospital();
return 0;
}
热心网友
时间：2023-10-10 01:02
