AHelianthuss 于 2014.07.05 13:30 提问

#include
#include
#include
#include
#include
#include
#define STATUS int
#define OK 1
#define ERROR 0
#define INFINITY INT_MAX
#define VERTEX_NUM 13
char a[VERTEX_NUM][20]={"信息楼","网络中心","图书馆","理学院","国际交流学院","体育馆","采矿馆","冶金馆","大成教学馆","综合楼","逸夫楼","何世礼教学馆","汉卿会堂"};
//建筑数组
typedef struct ArcCell
{
int distance;
bool pushe;//是否铺设的bool型变量
}ArcCell,DisMatrix[VERTEX_NUM][VERTEX_NUM];

typedef struct
{
char* name;
}VertexType;

typedef struct
{
VertexType vexs[VERTEX_NUM];
DisMatrix dist;
int vexnum;
}MGraph;//图结构

typedef struct
{

}NODE;//堆排序数组

NODE Heap[25];
typedef struct UFSet
{
int x;
int y;
}UFSet;//并查集结构体

typedef struct
{
string name;
double x,y;
}Building;

UFSet set[25];
int rank[VERTEX_NUM];
int father[VERTEX_NUM];
STATUS ShowAllGraph(MGraph &G);//显示所有线路分布
STATUS CreateGraph(MGraph &G);//创建校园节点图
STATUS MiniSpanTree_KRUSCAL2(MGraph &G);//最小生成树KR2
void heapsort(int n);//排序
void MakeSet(int x);//初始化并查集
int Find_set(int x);//查找父节点
void Uion_set(int x, int y);
void showMap(MGraph &G);
STATUS ShowDist(int a,int b,MGraph &G)
{
printf("%s--%s(%d)\n",G.vexs[a],G.vexs[b],G.dist[a][b].distance);
return OK;
}
STATUS ShowAllGraph(MGraph &G)//显示所有节点及线路
{
int i,j;
for(i=0;i {
for (j=i+1;j {
if (G.dist[i][j].distance!=INFINITY) ShowDist(i,j,G);
}
}
return OK;
}
void heapsort(int n)//排序
{
int i,e;
for(i=(n-1)/2;i>=0;--i)
{
}

for(i=n-1;i>=1;--i)
{
}
}
{
int j;
for(j=2*s;j<=m;j*=2)
{
if(j ++j;
break;
s=j;
}
}
void MakeSet(int x)//初始化并查集
{
father[x]=x;
rank[x]=0;
}
int Find_set(int x)//查找父节点
{
if (x != father[x])
{
father[x] = Find_set(father[x]);
}
return father[x];
}
void Uion_set(int x, int y)
{

if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}

STATUS CreateGraph(MGraph &G)//创建一个图
{
int i,j,k;
G.vexnum =VERTEX_NUM;
for( i=0;i<VERTEX_NUM;i++)
{
G.vexs[i].name=a[i];
}

for(i=0;i<VERTEX_NUM;i++)
{
for (j=0;j<VERTEX_NUM;j++)
{
G.dist[i][j].distance=INFINITY;
G.dist[i][j].pushe=false;
}
}
G.dist[0][1].distance=103;
G.dist[0][2].distance=113;
G.dist[0][4].distance=170;
G.dist[1][2].distance=115;
G.dist[1][3].distance=128;
G.dist[2][3].distance=105;
G.dist[2][4].distance=154;
G.dist[2][6].distance=165;
G.dist[2][7].distance=288;
G.dist[2][9].distance=271;
G.dist[3][9].distance=240;
G.dist[3][11].distance=247;
G.dist[3][12].distance=229;
G.dist[4][5].distance=159;
G.dist[4][6].distance=97;
G.dist[5][6].distance=182;
G.dist[6][7].distance=151;
G.dist[7][8].distance=156;
G.dist[7][9].distance=173;
G.dist[8][9].distance=170;
G.dist[8][10].distance=354;
G.dist[9][10].distance=224;
G.dist[9][11].distance=153;
G.dist[10][11].distance=73;
G.dist[11][12].distance=267;
for(i=0;i<VERTEX_NUM;i++)
{
for (j=i+1;j<VERTEX_NUM;j++)
{
if (G.dist[i][j].distance!=INFINITY) G.dist[j][i].distance=G.dist[i][j].distance;
}
}
return OK;
}
STATUS MiniSpanTree_KRUSCAL2(MGraph &G)//最小生成树KR2
{
int i,j,k,m,n,x,y,z,a,b,c,d;
k=0;
m=0;
z=0;
for(i=0;i<G.vexnum;i++)
{
for(j=i;j<G.vexnum;j++)
{
if(G.dist[i][j].distance!=INFINITY)
{
k++;
}
}
}
for(i=0;i<G.vexnum;i++)
{
for(j=i;j<G.vexnum;j++)
{
if(G.dist[i][j].distance!=INFINITY)
{
set[z].x=i;
set[z].y=j;
z++;
}
}
}
for(a=0;a<G.vexnum;a++)
{
MakeSet(a);
}
heapsort(k);
while(m<25)
{
for(i=0;i<G.vexnum;i++)
{
for(j=i;j<G.vexnum;j++)
{
{
x=i;
y=j;
d=0;
while(d<25)

{
if(set[d].x==x&&set[d].y==y)
{
b=Find_set(set[d].x);
c=Find_set(set[d].y);
if(b==c)
{
}
else
{
Uion_set(b, c);
}
}
d++;
}
m++;
}
}
}
}
heapsort(k);
return 0;
}

void showMap(MGraph &G)
{

int i,j,k,x,y;
k=0;

{
k++;
}
while(k<25)
{
for(i=0;i<G.vexnum;i++)
{
for(j=i;j<G.vexnum;j++)
{
{
x=i;
y=j;
printf("\n");
k++;
}
}
}
}
}

{
char i;
printf(" ***************************************************************\n");
printf(" ***************************************************************\n");
printf(" 1.显示东大楼距 \n");
printf(" 2.克鲁斯卡尔二 \n");
printf(" 3.退出 \n");
printf(" ***************************************************************\n");
printf(" ***************************************************************\n");

return 0;

}
int main()
{
MGraph G;
int i;
CreateGraph(G);
while(1)
{
scanf_s("%d",&i);
switch(i)
{
case 1:
ShowAllGraph(G);
break;
case 2:
MiniSpanTree_KRUSCAL2(G);
showMap(G);
break;
case 3:
return 0;
}
}
}