数据结构-图的邻接表表示（C语言）

数据结构-图的邻接表表示（C语言）

// grap_theory.cpp : 定义控制台应用程序的入口点.//
//#include "stdafx.h" //VS2010头文件#include<stdio.h>#define NTOTAL (26*4) //最大路径数目#define MAX_DISTANCE  10000.0struct 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++){//判断fromfor(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++;}//判断endfor(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);
}