xy3.cpp

这是一个用来求最短路径的程序,用的是迪杰斯特拉算法

#include "stdio.h"
#include"STDLIB.H"
#define SIZE_view 20
#define SIZE_way 300
struct view_info    /*景点信息结构*/
{
        char name[20];
        char info[100];
      } views[SIZE_view];
struct way_info    /*路径信息结构*/
       {
       int start_id;
       int end_id;
       int dist;
       } ways[SIZE_way];
struct path_info   /*路径查询结构*/
       {
       int count;
       int path[SIZE_view];
       };
int view_count, way_count;

ReadViewsFile() //VIEWS文件
{
int i;
FILE *fp;
view_count = 0;
if ((fp = fopen("VIEWS", "rb")) == NULL)   /*读取VIEWS文件 rb 只读打开一个二进制文件，只允许读数据*/
       {
       printf("  Open file VIEWS failed.\n");
       exit(0);
       return;
       }
for (i = 0; i < SIZE_view; i++)
       {
       if (fread(&views[i], sizeof (struct view_info), 1, fp) == 1) /*1就是那个sizeof(struct view_info)的个数,fp是当前文件指针  */           
 view_count = view_count + 1;
       else
              break;
       }
fclose(fp);
}
ReadWaysFile()
{
int i;
FILE *fp;
way_count = 0;
if ((fp = fopen("WAYS", "rb")) == NULL)  /*读取WAYS文件 rb只读打开一个二进制文件，只允许读数据 */
       {
       return;
       }
for (i = 0; i < SIZE_way; i++)
       {
       if (fread(&ways[i], sizeof (struct way_info), 1, fp) == 1)
              way_count = way_count + 1;
       else
              break;
       }
fclose(fp);
}
AddView()
{
int i;
int count;
FILE *fp;
struct view_info new_view;
printf("Adding a view...\n");
if ((fp = fopen("VIEWS", "ab")) == NULL)  /*读取WAYS文件 rb只读打开一个二进制文件，只允许读数据 */

       {
       printf("  Open file VIEWS failed.\n");
       exit(0);
       }
printf("  The name of new view: ");
scanf("%s", new_view.name);  
printf("  The info of new view: ");
scanf("%s", new_view.info);
if (fwrite(&new_view, sizeof (struct view_info), 1, fp) == 1)
       {
       views[view_count] = new_view;
       view_count = view_count + 1;
       printf("Add a view successfully.");
       }
else
       printf("  Write error.\n");
fclose(fp);
printf("\n\n");
return;
}
/*删除景点的同时，遍历路径表，将大于所删序号的编号减小1*/
DelView()
{
int i, select_id;
FILE *fp;
printf("Deleting a view...\n");
select_id = 1;
while (select_id != 0)
       {
       if (view_count == 0)
              {
              printf("  There is not any view. You can't delete any view.\n\n\n");
              return;
              }
       printf("  All views in the school:\n");
       for (i = 0; i < view_count; i++)
              printf("    %d: %s\n", i + 1, views[i].name);
       printf("  Press 1-%d to delete a view, or press 0 to cancel: ", view_count);
       scanf("%d", &select_id);
       if (select_id > 0 && select_id <= view_count)
              {
              view_count = view_count - 1;
              for (i = select_id - 1; i < view_count; i++)
                     views[i] = views[i+1];
              fp = fopen("VIEWS", "wb+");/* wb+读写打开或建立一个文本文件，允许读写*/
              for (i = 0; i < view_count; i++)
              fwrite(&views[i], sizeof (struct view_info), 1, fp);
              fclose(fp);
              }
       }
printf("\n");
return;
}
ShowView()
{
int i, select_id;
FILE *fp;
printf("Showing the info of views...\n");
if (view_count == 0)
       {
       printf("  There is not any view.\n\n\n");
       return;
       }
printf("  All views in the school:\n");
for (i = 0; i < view_count; i++)
       printf("    %d: %s\n", i+1, views[i].name);
select_id = 1;
while (select_id != 0)
       {
       printf("  Press 1-%d to show the info of view, or press 0 to cancel: ", view_count);
       scanf("%d", &select_id);
       if (select_id > 0 && select_id <= view_count)
              printf("    %s: %s\n", views[select_id-1].name, views[select_id-1].info);
       }
printf("\n\n");
return;
}
AddWay()
{
int i;
int tmp_num;
FILE *fp;
struct way_info new_way;
printf("Adding a way...\n");
if (view_count == 0)
       {
       printf("  There is not any view. You can't add a way.\n\n\n");
       return;
       }
printf("  All views in the school:\n");
for (i = 0; i < view_count; i++)
       printf("    %d: %s\n", i+1, views[i].name);
if (view_count == 1)
       {
       printf("  There is only one view. You can't add a way.\n\n\n");
       return;
       }
if ((fp = fopen("WAYS", "ab")) == NULL)
       {
       printf("  Open file WAYS failed.\n");
       exit(0);
       }
tmp_num = 0;
while (1)
{
       printf("  ID of 1st view: ");
       scanf("%d", &tmp_num);
       if (tmp_num == 0)
              {
              printf("\n\n");
              return;
              }
       if (tmp_num > 0 && tmp_num <= view_count)
              {
              new_way.start_id = tmp_num - 1;
              break;
              }
       else
              printf("  Wrong ID! Please input 1-%d, or 0 to cancel.\n", view_count);
}
while (1)
{
       printf("  ID of 2nd view: ");
       scanf("%d", &tmp_num);
       if (tmp_num == 0)
              {
              printf("\n\n");
              return;
              }
       if (tmp_num > 0 && tmp_num <= view_count)
              {
              new_way.end_id = tmp_num - 1;
              break;
              }
       else
              printf("  Wrong ID! Please input 1-%d, or 0 to cancel.\n", view_count);
}
while (1)
{
       printf("  Distance: ");
       scanf("%d", &tmp_num);
       if (tmp_num == 0)
              {
              printf("\n\n");
              return;
              }
       if (tmp_num > 0)
              {
              new_way.dist = tmp_num;
              break;
              }
       else
              printf("  Error! Please input positive whole number, or 0 to cancel.\n");
}
if (fwrite(&new_way, sizeof (struct way_info), 1, fp) == 1)
       {
       ways[way_count] = new_way;
       way_count = way_count + 1;
       printf("Add a view successfully.");
       }
else
       printf("  Write error.\n");
fclose(fp);
printf("\n\n");
return;
}
DelWay()
{
int i, select_id;
FILE *fp;
printf("Deleting a way...\n");
select_id = 1;
while (select_id != 0)
       {
       if (way_count == 0)
              {
              printf("  There is not any way. You can't delete any way.\n\n\n");
              return;
              }
       printf("  All ways in the school:\n");
       for (i = 0; i < way_count; i++)
              printf("    %d: from %s to %s, distance is %d\n", i+1, views[ways[i].start_id].name,
                     views[ways[i].end_id].name, ways[i].dist);
       printf("  Press 1-%d to delete a way, or press 0 to cancel: ", way_count);
       scanf("%d", &select_id);
       if (select_id > 0 && select_id <= way_count)
              {
              way_count = way_count - 1;
              for (i = select_id - 1; i < way_count; i++)
                     ways[i] = ways[i+1];
              fp = fopen("WAYS", "wb+");
              for (i = 0; i < way_count; i++)
                     fwrite(&ways[i], sizeof (struct way_info), 1, fp);
              fclose(fp);
              }
       }
printf("\n\n");
return;
}
ShowWay()
{
int i;
printf("Showing the info of ways...\n");
if (way_count == 0)
       {
       printf("  There is not any way.\n\n\n");
       return;
       }
printf("  All ways in the school:\n");
for (i = 0; i < way_count; i++)
       printf("    %d: from %s to %s, distance is %d\n", i+1, views[ways[i].start_id].name,
              views[ways[i].end_id].name, ways[i].dist);
}

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 and end number: ");
scanf("%d%d", &start_num, &end_num);
start_num = start_num - 1;
end_num = end_num - 1;
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");
}
}
SearchWay()
{
int select_id;
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(" 用弗洛伊德（Floyed）算法求取最佳路径\n");
Floyed();
}
main()
{  int com_menu;
   int i;
   for(i=1;i<5;i++)
          printf("\n");
   
printf("           ***********************************************************\n");
printf("           **                      Wellcome校园导航                 **\n");
printf("           ***********************************************************\n");
printf("\n");     printf("\n");
ReadViewsFile();
ReadWaysFile();
com_menu = 1;//Welcome菜单--------
while (com_menu != 0)
       {
       
       printf("                   Welcome! You can do:\n");
	   printf("\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("\n");
       printf("                   What will you do: ");
       scanf("%d", &com_menu);
       switch(com_menu)
             {
                case 1:
				for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     ShowView();
                     break;
              case 2:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     AddView();
                     break;
              case 3:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     DelView();
                     break;
              case 4:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     ShowWay();
                     break;
              case 5:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     AddWay();
                     break;
              case 6:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     DelWay();
                     break;
              case 7:
				  for(i=1;i<30;i++)//代替清屏函数
                     printf("\n");
                     SearchWay();
                     break;     
              }
       }
printf("\n\n");
printf("Quiting...\n");
return;
}