剑痴乎

  • 首页
  • 文章分类
    • 音视频
    • WebRTC
    • 编程之美
    • Linux
    • Windows
    • 生活点滴
    • 校园生活
  • 参考
    • API参考
    • 实用工具
    • 测试音视频
    • 文档
  • 留言板
  • 关于
剑痴乎
代码为剑,如痴如醉
  1. 首页
  2. 编程之美
  3. 正文

中南大学数据结构课程设计--医院选址问题

2013年11月20日 349点热度 0人点赞 0条评论

医院选址问题--这是中南大学计算机系数据结构课程设计里面的一道题

1. 问题描述
n个村庄之间的交通图可以用有向网图来表示,图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院,问这所医院应建在哪个村庄,才能使所有的村庄离医院都比较近?

2. 基本要求
(1) 建立模型,设计存储结构
(2) 设计算法完成问题求解
(3) 分析算法的时间复杂度

3.实现代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>
#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;//邻接矩阵初始化为最大值
}
 
    printf("请输入村庄个数★不多于10个★:\n");
    scanf("%d",&n);
    printf("\n请依次输入各个村庄的名称(用数字表示):\n");
    for(int i=0;i<n;i++)//依次输入顶点,插入图中
    {
        scanf("%d",&name);
        InsertVertex(name);
    vNum++;
    }
    printf("\n请输入边数:\n");
    scanf("%d",&e);
    printf("\n以下输入边信息:\n");
    for(int i=0;i<e;i++)
    {
        printf("请输入第%d边头顶点:\n",i+1);
        scanf("%d",&head);
        printf("请输入该边尾顶点:\n");
        scanf("%d",&tail);
        printf("请输入该边权值:\n");
        scanf("%d",&weight);
        if(!InsertEdge(head,tail,weight))
        {
            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 &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为机器内最大整数。
    printf("********************************************\n");
    //以下为求各村离医院最近的医院选址
    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
    printf("要建医院的村庄号为:%d\n",k+1); //输出要建医院的村庄号
    //输出要建医院的村庄号及离医院最远的村庄到医院的距离
    for(j=0;j<vNum;j++)
        if(j!=k)
            printf("该村庄离%d村庄最短距离为:%d\n",j+1,Edge[k][j]);
}//算法结束
int main()
{  
       printf(" \t                     中  南  大  学           \n");
       printf(" \t             ---------------------------------  \n");
       printf(" \t            |        医  院  选  址          |  \n");
       printf(" \t             ---------------------------------  \n");
       printf(" \t                   班级:物联网***班           \n");
       printf(" \t             --------------------------------- \n");
       printf(" \t              姓名: ** 学号: ***               \n");
       printf(" \t             ---------------------------------  \n");
    system("color 3E");
    Graph Town(MaxNumVertices);
    Town.Hospital();
    return 0;
}

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2013年12月20日

Jeff Young

代码为剑,如痴如醉

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复

我的其它小窝

公众号:码上Play(基本不更新,回答问题用)

近期评论
  • Jeff on Windows平台WebRTC编译(持续更新)M79是2019年发布的版本,不适用这篇文章。编译…
  • haige on Windows平台WebRTC编译(持续更新)我编译的m79版本,用VS2019打开会报错, F…
  • 菜菜 on libcef编译使用--使用VS2015是真的鸟
  • Jeff on WebRTC研究:应用受限区域探测器-AlrDetector不知道你怎么得出`让gcc发送更频繁`这个结论
  • vtron on 音视频开发入门:视频基础赞一个
版权声明

为支持原创,创作更好的文章,未经许可,禁止任何形式的转载与抄袭,如需转载请邮件私信!本人保留所有法定权利。违者必究!

COPYRIGHT © 2021 剑痴乎. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS