通信网络(数据结构)-中国石油大学远程教育考核

1需求分析

在 n 个城市建设通信网络， 只需架设 n-1 条线路即可。 设计算法， 求出如果以最低的经

济代价建设这个通信网络。 要求如下： （1 ） 至少包含 1 0 个城市； （2） 城市数 n 由键盘录入；

（3） 城市坐标由随机函数产生小于 1 00 的整数； （4） 输出生成树中各条边以及它们的权值；

2概要设计

typedef struct point //声明点结构体 { int number; //序号 int x; //点的横坐标 int y; //点的纵坐标 }point; typedef struct citys { int city_nums; //城市的个数 point * p; //所有城市的坐标 }citys; typedef struct edge //声明边结构体 { point begin; //起点的坐标 point end; //终点的坐标 double distance; //距离,在这里就是权值 }edge; typedef struct edges { int edge_nums; //边的数目 edge ** p; //所有边的坐标 }edges; // 邻接矩阵 typedef struct Graph { citys ct; //点的集合 edges eg; //边的集合 }Graph, *PGraph;

系统主要函数及功能如下： double get_distance(point a, point b); //得到两个坐标点之间的距离 citys generate_citys(int n); //根据城市的个数，随机生成城市的坐标，每一个城市的坐标都不能相同 void print_citys(citys ct); //打印城市坐标信息 edges generate_edges(citys ct); //根据城市坐标信息，得到所有的边信息 void print_edges(edges eg); //打印图中所有边的长度信息 void print_column(edges eg); //按列打印边信息 void prim(Graph G, int start); //生成最小生成树信息 void free_citys(citys ct); //释放citys void free_edges(edges eg); //释放edges

3详细设计

/*主函数*/ int main() { srand((unsigned int)time(NULL)); int n; char ch = 0; printf(\请输入城市数: \); scanf(\, &n); while ((ch = getchar()) != '\\n' && ch != EOF); citys ct = generate_citys(n); printf(\城市的坐标信息如下:\\n\); print_citys(ct); edges eg = generate_edges(ct); printf(\城市之间的距离信息如下:\\n\); print_edges(eg); printf(\按列打印边的信息如下:\\n\); print_column(eg); printf(\最小生成树如下:\\n\); Graph gra; gra.ct = ct; gra.eg = eg; prim(gra, 1); free_citys(ct); free_edges(eg); system(\); return 0; } /*各个子函数*/ double get_distance(point a, point b); //得到两个坐标点之间的距离 citys generate_citys(int n); //根据城市的个数，随机生成城市的坐标，每一个城市的坐标都不能相同 void print_citys(citys ct); //打印城市坐标信息 edges generate_edges(citys ct); //根据城市坐标信息，得到所有的边信息 void print_edges(edges eg); //打印图中所有边的长度信息 void print_column(edges eg); //按列打印边信息 void prim(Graph G, int start); //生成最小生成树信息 void free_citys(citys ct); //释放citys void free_edges(edges eg); //释放edges double get_distance(point a, point b) { int x_diff = abs(a.x - b.x); int y_diff = abs(a.y - b.y); return sqrt((double)(x_diff*x_diff + y_diff*y_diff)); } citys generate_citys(int n) { citys ct; ct.city_nums = n; ct.p = (point*)calloc(ct.city_nums, sizeof(point)); int i = 0, j = 0; for (i = 0; i < ct.city_nums;) { ct.p[i].number = i + 1; ct.p[i].x = rand() % 100; ct.p[i].y = rand() % 100; j = 0; for (j = 0; j < i; j++) { if (ct.p[j].number == ct.p[i].number) break; } if (j == i) i++; } return ct; } void print_citys(citys ct) { int i = 0; for (; i < ct.city_nums; i++) { printf(\, ct.p[i].number, ct.p[i].x, ct.p[i].y); if (i == ct.city_nums) printf(\); else printf(\); } } edges generate_edges(citys ct) { int i = 0, j = 0; edges eg; eg.edge_nums = ct.city_nums; eg.p = (edge**)calloc(eg.edge_nums, sizeof(edge*)); for (i = 0; i < eg.edge_nums; i++) { eg.p[i] = (edge*)calloc(eg.edge_nums, sizeof(edge)); } for (i = 0; i < ct.city_nums; i++) { for (j = 0; j < ct.city_nums; j++) { eg.p[i][j].begin = ct.p[i]; eg.p[i][j].end = ct.p[j]; eg.p[i][j].distance = get_distance(eg.p[i][j].begin, eg.p[i][j].end); } } return eg; } void print_edges(edges eg) { int i = 0, j = 0, k = 0; for (i = 0; i < eg.edge_nums; i++) { if (i == 0) { printf(\, ' '); for (j = 0; j < eg.edge_nums; j++) { printf(\, j + 1); if (j != eg.edge_nums - 1) printf(\); else printf(\); } } for (j = 0; j < eg.edge_nums; j++) { if (j == 0) { printf(\, i + 1); printf(\); } printf(\, eg.p[i][j].distance); if (j != eg.edge_nums - 1) printf(\); else printf(\); k++; } } } void print_column(edges eg) { int i = 0, j = 0; printf(\, \城市\, \城市\, \距离\); char szTemp1[256] = { 0 }; char szTemp2[256] = { 0 }; for (i = 0; i < eg.edge_nums; i++) { for (j = 0; j < eg.edge_nums; j++) { sprintf(szTemp1, \, eg.p[i][j].begin.number, eg.p[i][j].begin.x, eg.p[i][j].begin.y); sprintf(szTemp2, \, eg.p[i][j].end.number, eg.p[i][j].end.x, eg.p[i][j].end.y); printf(\, szTemp1, szTemp2, eg.p[i][j].distance); } } } void prim(Graph gra, int start) { int i, j, k, m, n; double min, sum; int index = 0; //prim最小树的索引，即prims数组的索引 int size = gra.ct.city_nums; point * prims = (point*)calloc(size, sizeof(point)); //prim最小树的结果数组 double * weights = (double*)calloc(size, sizeof(double)); //顶点间边的权值 prims[index++] = gra.ct.p[start];// prim最小生成树中第一个数是\图中第start个顶点\，因为是从start开始的。