村村通 c语言实现

村村通设计系统

1. 设计目的
   在计算机科学中，数据结构是一般程序设计的基础。通过综合设计，使学生学会分析研究数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，掌握算法的时间复杂度分析技术。另一方面，综合设计也是复杂程序设计的训练过程，要求学生编写的程序结构符合软件工程规范，培养他们的数据抽象能力、建模能力和算法设计能力，提高复杂问题的解决能力，为后续课程的学习和应用奠定基础。
2. 任务与要求
   要求学生以3人一组，自由结合，从给定的综合设计题目中进行选择。本次设计题目是设计内容不固定的题目，这就要求学生自己先确定本组设计题目，然后确定具体内容和设计目标，从而为数据结构设计、数据建模和算法设计奠定基础。提交的资料包含综合设计纸质版、电子版及源程序电子版。
3. 村通建设模拟系统
   3.1 系统（问题）描述
   “村村通”是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。 2004年1月16日，信息产业部下发了《关于在部分省区开展村通工程试点工作的通知》(以下简称《通知》)，同时出台了《农村通信普遍服务——村通工程实施方案》（以下简称村通工程方案），作为一个过渡时期的解决方案。
   本系统旨在已知村庄及村庄之间的路径关系及长度，求出总路径最短的网使所有村庄相连通，以及计算给定的两村庄之间最短路径及其长度。

4代码

#include 
#include 
#include 
#include 
#include 

#define MAX_VERTEX_NUM 20                      //最大顶点数
#define maxnumber 1000000
int adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //联通的顶点值为距离，不连通的顶点值为1000000，adjMatrix[x][y]表示第x-1个与第y-1个顶点间距离
char name[MAX_VERTEX_NUM][100];                // name[i][]存储第i-1个村庄的名称，以字符数组形式存储
int number = 0;                                //当前村庄数
struct node
{
    int start;  //边的终点
    int end;    //边的起点
    int weight; //边的权重
} close_edge[MAX_VERTEX_NUM];
void menu();
void init();
void zuixiaoshengchengshu();
void print();
void chazhao();
void gotoxy(int x, int y);

int main()
{
    for (int i = 0; i < MAX_VERTEX_NUM; i++)
    {
        for (int j = 0; j < MAX_VERTEX_NUM; j++)
        {
            adjMatrix[i][j] = 1000000;
        }
    }
    system("title 村村通");
    system("mode con cols=92 lines=33");
    char choose;
    for (;;)
    {
        system("cls");
        menu();
        choose = getch();
        switch (choose)
        {
        case '1':
            init();
            break;
        case '2':
            print();
            break;
        case '3':
            zuixiaoshengchengshu();
            break;
        case '4':
            chazhao();
            break;
        case '5':
            int message = MessageBox(NULL, "是否退出？", "友情提示", MB_OKCANCEL);
            if (IDOK == message)
                return 0;
        }
    }
}

void gotoxy(int x, int y)
{
    HANDLE handle;
    COORD coord;
    coord.X = x;
    coord.Y = y;
    handle = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(handle, coord);
}

void menu()
{
    int k;
    system("cls"); //清屏
    for (k = 2; k <= 16; k += 2)
    {
        gotoxy(5, k);
        printf("|------------------------|");
    }

    gotoxy(5, 3);
    printf("|       村  村  通       |");

    gotoxy(5, 5);
    printf("|        菜   单         |");

    gotoxy(5, 7);
    printf("|  1.输   入   村   庄   |");

    gotoxy(5, 9);
    printf("|  2.输出各村庄关系矩阵  |");

    gotoxy(5, 11);
    printf("|  3.  生成最小生成树    |");

    gotoxy(5, 13);
    printf("|  4.查找两村子最短路径  |");

    gotoxy(5, 15);
    printf("|  5.    退出系统        |");

    gotoxy(5, 18);
    printf("温馨提示:输入菜单对应序号进行操作");

    gotoxy(5, 18);
    printf("祝您使用愉快！");

    gotoxy(13, 20);
}

void init()
{
    system("cls");
    if (number >= MAX_VERTEX_NUM)
    {
        MessageBox(NULL, "输入超过上限！", "村村通", MB_OK);
        return;
    }

    if (number)
        printf("please input the name of the NO.%d village:n", number + 1);
    else
        printf("please input the name of the first village:n");

    scanf("%s", name[number]);
    number++;
    int key = 0;
    int num = 0;
    for (int i = 0; i < number - 1; i++)
    {
        int length;
        printf("Please input the length of the road between this village with %s:n", name[i]);
        printf("(if the road is not exist, please input -1)n");
        scanf("%d", &num);
        if (num == -1)
        {
            adjMatrix[i][number - 1] = adjMatrix[number - 1][i] = 1000000;
        }
        else
        {
            adjMatrix[number - 1][i] = num;
            adjMatrix[i][number - 1] = adjMatrix[number - 1][i];
        }
    }

    system("cls");

    printf("1. Continue typingn");
    printf("2. Ending typingn");

    scanf("%d", &key);
    if (key == 2)
    {
        return;
    }
    init();
}

void chazhao()
{
    system("cls");
    char s1[MAX_VERTEX_NUM], s2[MAX_VERTEX_NUM];
    printf("输入村庄名:");
    scanf("%s", s1);
    printf("t");
    scanf("%s", s2);
    int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //记录对应点的最小路径的前驱点，例如p(1,3) = 2 说明顶点1到顶点3的最小路径要经过2
    int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //记录顶点间的最小路径值
    int v, k, w, m;
    for (v = 0; v < number; v++) //初始化floyd算法的两个矩阵
    {
        for (w = 0; w < number; w++)
        {
            D[v][w] = adjMatrix[v][w];
            p[v][w] = w;
        }
    }
    //这里是弗洛伊德算法的核心部分
    // k为中间点
    for (k = 0; k < number; k++)
    {
        // v为起点
        for (v = 0; v < number; v++)
        {
            // w为终点
            for (w = 0; w < number; w++)
            {
                if (D[v][w] > (D[v][k] + D[k][w]))
                {
                    D[v][w] = D[v][k] + D[k][w]; //更新最小路径
                    p[v][w] = p[v][k];           //更新最小路径中间顶点
                }
            }
        }
    }
    for (m = 0; m < number; m++)
    {
        if (strcmp(name[m], s1) == 0)
            v = m;
        else if (strcmp(name[m], s2) == 0)
            w = m;
    }
    //求V到W的最短路径
    printf("n%s->%s的最短路径为：%dn", s1, s2, D[v][w]);
    k = p[v][w];
    printf("path: %s", name[v]); //打印起点
    while (k != w)
    {
        printf("-> %s", name[k]); //打印中间点
        k = p[k][w];
    }
    printf("-> %sn", name[w]);
    system("pause");
}

void zuixiaoshengchengshu()
{
    system("cls");
    int begin = 1;
    int j;
    for (j = 0; j < number; j++)
    {
        if (j != begin - 1)
        {
            close_edge[j].start = begin - 1;
            close_edge[j].end = j;
            close_edge[j].weight = adjMatrix[begin - 1][j];
        }
    }
    close_edge[begin - 1].weight = -1;
    for (j = 1; j < number; j++)
    {

        int min = maxnumber;
        int k;
        int index;
        for (k = 0; k < number; k++)
        {
            if (close_edge[k].weight != -1)
            {
                if (close_edge[k].weight < min)
                {
                    min = close_edge[k].weight;
                    index = k;
                }
            }
        }
        close_edge[index].weight = -1;
        printf("%s----%s-----%dn", name[close_edge[index].start], name[close_edge[index].end], adjMatrix[close_edge[index].start][close_edge[index].end]);
        for (k = 0; k < number; k++)
        {
            if (adjMatrix[close_edge[index].end][k] < close_edge[k].weight && close_edge[k].weight != -1)
            {
                close_edge[k].weight = adjMatrix[close_edge[index].end][k];
                close_edge[k].start = close_edge[index].end;
                close_edge[k].end = k;
            }
        }
    }
    system("pause");
}

void print()
{
    system("cls");
    for (int i = 0; i < number; i++)
    {
        for (int j = 0; j < number; j++)
        {
            if (adjMatrix[i][j] == maxnumber)
                printf("    -");
            else
                printf("%5d", adjMatrix[i][j]);
        }
        printf("n");
    }

    system("pause");

}