数据结构大作业—医院选址问题—报告 程序

n个村庄之间的交通图用有向加权图表示，图中的有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

#include
#define MaxInt 10000//最大数 
using namespace std;
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 &vertexint &i）;//给出顶点vertex在图中的位置
    public:
        Graph（const int sz= MaxNumEdges）;//构造函数
        bool FindVertex（const int &vertex）;
        bool InsertVertex（const int & vertex）;//插入一个顶点vertex
        bool InsertEdge（const int v1const int v2const int weight）;//插入一条边（v1v2）该边上的权值为weight
        void Hospital（）;//医院选址函数
}; 
Graph::Graph（const int sz）: vNum（0） eNum（0）
//构造函数
{ 
    int ne;
    int nametailhead;
    int weight;
    for（int i=0;i    for（int j=0;j    {
        if（i==j）
            Edge[i][j]=0;//顶点到自身权值为0
        else
            Edge[i][j]=10000;//邻接矩阵初始化为最大值
    }
    printf（“请输入顶点数注意本程序最多为10个!\n“）;
    scanf（“%d“&n）;
    printf（“请依次输入顶点名称:\n“）;
    for（int i=0;i    {
        scanf（“%d“&name）;
        InsertVertex（name）;
    vNum++;
    }
    printf（“请输入边数:\n“）;
    scanf（“%d“&e）;
    printf（“以下输入边信息:\n“）;
    for（int i=0;i    {
        printf（“请输入第%d边头顶点:“i+1）;
        scanf（“%d“&head）;
        printf（“请输入该边尾顶点：“）;
        scanf（“%d“&tail）;
        printf（“请输入该边权值：“）;
        scanf（“%d“&weight）;
        if（!InsertEdge（headtailweight））
        {
            printf（“不存在该边，请重输！\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 &vertexint &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 v1const int v2const int weight）
//插入一条边（v1v2）该边上的权值为weight
{ 
    int k=0j=0;
    if（GetVertexPos（v1k） && GetVertexPos（v2j））
    {
        Edge[k][j]=weight;
        eNum++;
        Edge[j][k]=weight;
        eNum++;
        return true;
    }
    else
        return false;
} 
void Graph::Hospital（） 
//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 
{
    int kijs;
    for （k=0;k        for （i=0;i            for （j=0;j                if （Edge[i][k]+Edge[k][j]                    Edge[i][j]=Edge[i][k]+Edge[k][j];
    int m=MaxInt; //设定m为机器内最大整数。
    printf（“********************************************\n“）;
    //以下为求各村离医院最近的医院选址
    int min=MaxInt ; //设定机器最大数作村庄间距离之和的初值。
    k=0; //k设医院位置。
    for （j=0;j


 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     124928  2009-06-08 17:24  大型作业_医院选址问题.doc

     文件       3927  2009-05-18 15:20  大型作业_医院选址问题.c

----------- ---------  ---------- -----  ----

               128855                    2