公园导游.txt

公园导游图 数据结构课程设计作业 需要的人下 功能：给出一张某公园的导游图

  

  

void Dijkstra()   /*狄克斯特拉（Dijkstra）算法*/ 

{ 

int j, k, w, m, start_num; 

int used_list[SIZE_view], dist_list[SIZE_view]; 

int GA[SIZE_view][SIZE_view]; 

struct path_info path_list[SIZE_view]; 

printf("  All views in the school:\n"); 

for (j = 0; j < view_count; j++) 

       printf("    %d: %s\n", j+1, views[j].name); 

printf("  Please input the number of start view: "); 

scanf("%d", &start_num); 

start_num = start_num - 1; 

  

for (j = 0; j < view_count; j++) 

       for (k = 0; k < view_count; k++) 

              if (j == k) 

                     GA[j][k] = 0; 

              else 

                     GA[j][k] = -1; 

for (j = 0; j< way_count; j++) 

       { 

       w = ways[j].start_id; 

       m = ways[j].end_id; 

       GA[w][m] = ways[j].dist; 

       } 

  

for (j = 0; j< view_count; j++) 

       { 

       if (j != start_num) 

              used_list[j] = 0; 

       else 

              used_list[j] = 1; 

       dist_list[j] = GA[start_num][j]; 

       if (dist_list[j] > 0) 

              { 

              path_list[j].count = 2; 

              path_list[j].path[0] = start_num; 

              path_list[j].path[1] = j; 

              continue; 

              } 

       if (dist_list[j] == 0) 

              { 

              path_list[j].count = 1; 

              path_list[j].path[0] = j; 

              continue; 

              } 

       path_list[j].count = 0; 

       } 

for (k = 0; k< view_count - 2; k++) 

       { 

       w = -1; 

       m = start_num; 

       for (j = 0; j< view_count; j++) 

              if (used_list[j] == 0) 

                     { 

                     if (dist_list[j] == -1) 

                            continue; 

                     if ((w == -1) || (w != -1 && dist_list[j] < w)) 

                            { 

                            m = j; 

                            w = dist_list[j]; 

                            } 

                     } 

       if (m != start_num) 

              used_list[m] = 1; 

       else 

              break; 

       for (j = 0; j< view_count; j++) 

              { 

              if (used_list[j] == 0) 

                     { 

                     if ((dist_list[m] == -1 || GA[m][j] == -1)) 

                            continue; 

                     if ((dist_list[j] == -1) || (dist_list[j] != -1 && dist_list[m] + GA[m][j] < dist_list[j])) 

                            { 

                            dist_list[j] = dist_list[m] + GA[m][j]; 

                            path_list[j].count = path_list[m].count + 1; 

                            for (w = 0; w < path_list[m].count; w++) 

                                   path_list[j].path[w] = path_list[m].path[w]; 

                            path_list[j].path[path_list[j].count-1] = j; 

                            } 

                     } 

              } 

       } 

/*printf("  Dijkstra table:\n"); 

for (j = 0; j< view_count; j++) 

       printf("t%d", used_list[j]); 

printf("\n"); 

for (j = 0; j< view_count; j++) 

       printf("t%d", dist_list[j]); 

printf("\n"); 

for (j = 0; j< view_count; j++) 

       { 

       printf("t"); 

       for (k = 0; k< path_list[j].count; k++) 

              printf("%d", path_list[j].path[k] + 1); 

       }*/ 

printf("\n"); 

for (j = 0; j< view_count; j++) 

       { 

       printf("  From %s to %s: ", views[start_num].name, views[j].name); 

       if (path_list[j].count == 0) 

              printf("no way.\n"); 

       else 

              { 

              printf("distance is %d, and path is ", dist_list[j]); 

              printf("%s", views[start_num].name); 

              for (k = 1; k< path_list[j].count; k++) 

                     printf(" -> %s", views[path_list[j].path[k]].name); 

              printf("\n"); 

              } 

       } 

printf("\n\n"); 

} 

  

  

void Floyed()    /*弗洛伊德（Floyed）算法*/ 

{ 

int i, j, k, m, start_num, end_num; 

int dist_list[SIZE_view][SIZE_view]; 

struct path_info path_list[SIZE_view][SIZE_view]; 

  

printf("  Floyed table:\n"); 

for (i = 0; i< view_count; i++) 

       for (j = 0; j< view_count; j++) 

              { 

              if (i == j) 

                     { 

                     dist_list[i][j] = 0; 

                     continue; 

                     } 

              dist_list[i][j] = -1; 

              path_list[i][j].count = 0; 

              for  (k = 0; k< way_count; k++) 

                     { 

                     if (ways[k].start_id == i && ways[k].end_id == j) 

                            { 

                            dist_list[i][j] = ways[k].dist; 

                            path_list[i][j].count = 2; 

                            path_list[i][j].path[0] = i; 

                            path_list[i][j].path[1] = j; 

                            break; 

                            } 

                     } 

              } 

for (k = 0; k< view_count; k++) 

       for (i = 0; i < view_count; i++) 

              for (j = 0; j< view_count; j++) 

                     { 

                     if (i == k || j == k || i == j) 

                            continue; 

                     if (dist_list[i][k] == -1 || dist_list[k][j] == -1) 

                            continue; 

                     if ((dist_list[i][j] == -1) || ((dist_list[i][j] != -1) && 

                            (dist_list[i][k] + dist_list[k][j] < dist_list[i][j]))) 

                            { 

                            dist_list[i][j] = dist_list[i][k] + dist_list[k][j]; 

                            path_list[i][j].count = path_list[i][k].count + path_list[k][j].count - 1; 

                            for (m = 0; m < path_list[i][k].count; m++) 

                                   path_list[i][j].path[m] = path_list[i][k].path[m]; 

                            for (m = 0; m < path_list[k][j].count; m++) 

                                   path_list[i][j].path[m+path_list[i][k].count] = path_list[k][j].path[m+1]; 

                            } 

                     } 

/*for (i = 0; i< view_count; i++) 

       { 

       for (j = 0; j< view_count; j++) 

              { 

              printf("t%d", dist_list[i][j]); 

              } 

       printf("\n"); 

       }*/ 

  

printf("  All views in the school:\n"); 

for (i = 0; i < view_count; i++) 

       printf("    %d: %s\n", i+1, views[i].name); 

printf("  Please input the start number: "); 

scanf(" %d", &start_num); 

printf("  Please input the end number: "); 

scanf(" %d", &end_num); 

start_num = start_num - 1; 

end_num = end_num - 1; 

printf("\n"); 

printf("  From %s to %s: ", views[start_num].name, views[end_num].name); 

if (dist_list[start_num][end_num] == -1) 

       printf("no way.\n"); 

else 

       { 

       printf("distance is %d, and path is ", dist_list[start_num][end_num]); 

       k = path_list[start_num][end_num].path[0]; 

       printf("%s", views[k].name); 

       for (m = 1; m < path_list[start_num][end_num].count; m++) 

              { 

              k = path_list[start_num][end_num].path[m]; 

              printf(" -> %s", views[k].name); 

              } 

       } 

printf("\n\n"); 

//return; 

} 


void SearchWay() 

{ 

int select_id,i; 

printf("Searching the best way...\n"); 

if (view_count == 0) 

       { 

       printf("  There is not any view.\n\n\n"); 

       //return; 

       } 

if (way_count == 0) 

       { 

       printf("  There is not any way.\n\n\n"); 

       //return; 

       } 


printf("  Algorithms:\n");
printf("    1: Dijkstra\n");   /*用狄克斯特拉（Dijkstra）算法求取最佳路径*/ 

printf("    2: Floyed\n");   /*用弗洛伊德（Floyed）算法求取最佳路径*/ 

printf("    0: Cancel\n");   /*退出求取最佳路径*/ 

select_id = 1; 

if(select_id = 1) 

       { 

       printf("  You will do:");
    scanf("%d", &i); 

       switch (i) 

              { 

              case 0:
       select_id = 2;
   
                     //return;
                     break; 

              case 1: 

                     Dijkstra(); 

                     //return; 

                     break; 

              case 2: 

                     Floyed(); 

                     //return; 

                     break; 

              } 

       } 

} 

  

void main() 

{ 

int com_menu; 

//clrscr(); 

  

printf("***********************************************************\n"); 

printf("**                      Wellcome                         **\n"); 

printf("***********************************************************\n"); 

printf("\n"); 

printf("\n"); 

  

ReadViewsFile(); 

ReadWaysFile(); 

  

com_menu = 1; 

while (com_menu != 0) 

       { 

       printf("\n"); 

       printf("Welcome! You can do:\n"); 

       printf("  1 -------- Show the info of views.\n");  /*显示景点信息*/ 

       printf("  2 -------- Add a view.\n");   /*增加景点方便系统后台管理*/ 

       printf("  3 -------- Delete a view.\n");  /*删除景点方便系统后台管理*/ 

       printf("  4 -------- Show the info of ways.\n"); /*显示路径信息*/ 

       printf("  5 -------- Add a way.\n");  /*增加路径 方便系统后台管理*/ 

       printf("  6 -------- Delete a way.\n"); /*删除路径方便系统后台管理*/ 

       printf("  7 -------- Search the best way.\n"); /*寻找最佳路径*/ 

       printf("  0 -------- Quit\n");/*退出系统查询系统*/ 

       printf("  What will you do: "); 

       scanf("%d", &com_menu); 

       switch(com_menu) 

             { 

             case 1: 

                     ShowView(); 

                     break; 

              case 2: 

                     AddView(); 

                     break; 

              case 3: 

                     DelView(); 

                     break; 

              case 4: 

                     ShowWay(); 

                     break; 

              case 5: 

                     AddWay(); 

                     break; 

              case 6: 

                     DelWay(); 

                     break; 

              case 7: 

                     SearchWay(); 

                     break;     

              } 

       } 

printf("\n\n"); 

printf("Quiting...\n"); 

////return; 

}