数据结构-图的邻接表表示（C语言）
// grap_theory.cpp : 定义控制台应用程序的入口点。
//
//#include "stdafx.h" //VS2010头文件
#include<stdio.h>
#define NTOTAL (26*4) //最大路径数目
#define MAX_DISTANCE 10000.0
struct piont{
int line_adjacency_list;
int num_piont;
int test_num[2];
char from[NTOTAL];
char to[NTOTAL];
char all_piont[NTOTAL];
int all_piont_num[NTOTAL];
float distance[NTOTAL];
float distance_all[NTOTAL][NTOTAL];
};//结构体定义
void read(piont *test){
int i;
char temp[100];
scanf("%d"敏带,&test->line_adjacency_list);//读取行数
gets(temp);//读取回车字符
for(i=0;i<test->line_adjacency_list;i++){//读取列表
scanf("%c %c %f",&test->from[i],&test->to[i],&test->distance[i]);
gets(temp);//读取回车字符
}
scanf("%c %c",&test->from[i],&test->to[i]);//读取短短路径名称
}
void cal_num_piont(piont *test){
int i,j;
int from_num,to_num;
test->num_piont=0;
for(i=0;i<NTOTAL;i++){
test->all_piont_num[i]=0;//点的度数清零
test->distance_all[i][i]=0.0;
for(j=i+1;j<NTOTAL;j++){
test->distance_all[i][j]=MAX_DISTANCE;
test->distance_all[j][i]=MAX_DISTANCE;
}
}
for(i=0;i<test->line_adjacency_list;i++){
//判断from
for(j=0;j<test->num_piont;j++){
if(test->from[i]==test->all_piont[j]){
from_num=j;
test->all_piont_num[j]++;
break;
}
}
if(j==test->num_piont){
test->碰物all_piont[j]=test->from[i];
from_num=j;
test->all_piont_num[j]++;
test->num_piont++;
}
//判断end
for(j=0;j<test->num_piont;j++){
if(test->to[i]==test->all_piont[j]){
to_num=j;
test->all_piont_num[j]++;
break;
}
}
if(j==test->num_piont){
test->all_piont[j]=test->to[i];
to_num=j;
test->all_piont_num[j]++;
test->num_piont++;
}
test->distance_all[from_num][to_num]=test->distance[i];
test->distance_all[to_num][from_num]=test->distance[i];
}
//判断所求点的位置
for(i=0;i<test->num_piont;i++){
if(test->from[test->line_adjacency_list]==test->all_piont[i])
test->test_num[0]=i;
if(test->to[test->line_adjacency_list]==test->all_piont[i])
test->test_num[1]=i;
}
}
float 笑拿液min_distance(piont *test){
int i,j,k,n;
float min_dis;
float dis_i_k_add_k_j;
n=test->num_piont;
//Floyd-Warshall算法
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);
if(test->distance_all[i][j]>dis_i_k_add_k_j)
test->distance_all[i][j]=dis_i_k_add_k_j;
}
}
}
min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];
return min_dis;
}
void test_printf(piont *test,float min_dis){
int i;
printf("%d\n",test->num_piont);
for(i=0;i<test->num_piont;i++){
printf("%d\n",test->all_piont_num[i]);
}
printf("%-8.0f\n",min_dis);
}
void main()
{
float min_dis;
piont test1;//结构体声明
read(&test1);
cal_num_piont(&test1);
min_dis=min_distance(&test1);
test_printf(&test1,min_dis);
}
