中国石油大学北京 远程教育学院 《数据结构》课程设计报告

题目要求：建立通信网络 在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。要求如下： （1）至少包含10个城市； （2）城市数n由键盘录入； （3）城市坐标由随机函数产生小于100的整数； （4）输出生成树中各条边以及它们的权值

#include 
using namespace std;
const int MAX=1000; 
int M=0x3f3f3f;     //代表无穷大 
int n;
int ans[MAX][MAX];    //能建立MAX个城市的通信网络 
struct node{
	int xy;      //城市坐标 
}v[MAX];
void init（）{                   //初始化及其界面 
    printf（“\t\t\t欢迎使用建立通信网络系统\n“）;
    printf（“请输入城市个数（>=10）:“）;
    scanf（“%d“ &n）;
    while（n<10）{
        printf（“输入出错，请重新输入城市个数（>=10）:“）;
        scanf（“%d“ &n）;
    }
}
void city（）{    //随机生成城市坐标 
	printf（“\n\n“）;
	printf（“正在随机生成城市坐标...\n“）;
	
	srand（time（NULL））;    //设置随机种子 
	
	for（int i=0;i		v[i].x=rand（）%100;
		v[i].y=rand（）%100;
	}
	
	printf（“\n\n“）;
	
	printf（“城市坐标生成完毕！\n“）;
	printf（“\n\n城市编号   城市x坐标    城市y坐标\n“）;
	for（int i=0;i	printf（“%-12d%-12d%-12d\n“iv[i].xv[i].y）;
	
}
void count（）{   //计算任意两个城市间的距离
				//生成无向图的邻接矩阵 
	for（int i=0;i		for（int j=0;j			if（i!=j）{
				ans[i][j]=sqrt（（v[i].x-v[j].x）*（v[i].x-v[j].x）+（v[i].y-v[j].y）*（v[i].y-v[j].y））;
			} 
		}
	} 
	
} 
void prim（int ans[MAX][MAX]int n）{
	printf（“\n\n“）;
	printf（“使用prim算法计算最小生成树\n“）;
	int ijkminlow[MAX]close[MAX];
	for（int i=1;i		low[i]=ans[0][i];
		close[i]=0;
	}
	close[0]=-1;
	printf（“打印最小生成树\n“）;
	printf（“------------------------------------------------\n“）;
	printf（“起点--->终点\t起点坐标   \t终点坐标\t权值\n“） ;
	for（int i=1;i		min=M;
		k=i;
		for（int j=0;j			if（low[j]				min=low[j];
				k=j;
			}
		}
		
		printf（“%-3d--->%-3d \t（%-3d%-3d）\t（%-3d%-3d）\t权值%-3d \n“close[k]kv[close[k]].xv[close[k]].yv[k].xv[k].ylow[k]）;
		close[k]=-1;
		for（int j=1;j			if（close[j]!=-1&&ans[k][j]				low[j]=ans[k][j];
				close[j]=k;
			}
		}
	}
	
	
	
}
int main（）{
    init（）;
	city（）;
	count（）;
	prim（ansn）;
    return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        1998  2019-04-26 20:14  prim.cpp
     文件      107857  2019-04-26 20:28  《数据结构课程设计报告》.docx
     文件        1996  2019-04-26 20:35  新建文本文档 （3）.txt