guide.c

C语言实现数据结构中最短路径的算法代码

     outtextxy(60,190,"Exit");

     keyx=40;keyy=90;     /* 初始默认选中第一项 */
     DrawChoice(keyx,keyy,r,YELLOW);

     while(yes)
     {
       key=testcode();          /* 从键盘获取按键 */
       switch(key)
       {    case UP:    DrawChoice(keyx,keyy,r,BACKGROUND);
                        if (keyy==90)
                            keyy=190; else keyy-=20;
                        DrawChoice(keyx,keyy,r,MENUCOLOR); /* 选项上移 */
                        break;
            case DOWN:  DrawChoice(keyx,keyy,r,BACKGROUND);
                        if (keyy==190)
                        keyy=90; else keyy+=20;
                        DrawChoice(keyx,keyy,r,MENUCOLOR); /* 选项下移 */
                        break;
            case ENTER: switch(keyy)
                        {
                          case 90: InitMap();DrawMap();break;  /* 画地图 */
                          case 110: Depa();break;     /* 出发地 */
                          case 130: Dest();break;     /* 目的地 */
                          case 150: DrawChoice(keyx,keyy,r,RED);
                                    if (AddPlace()==1) DrawChoice(keyx,keyy,r,YELLOW);
                                    break;            /* 添加地点 */
                          case 170:CreateRelation();break;
                          case 190: yes=0;break;      /* 退出循环 */
                        }/* switch keyy */
                        break;
       }/* switch key */
     }/* while yes */
}/* Menu */

int Zbx(int dot)        /* 设置每个结点的横坐标 */
{  switch (dot)
    {
      case 1:return 425;
      case 2:return 330;
      case 3:return 425;
      case 4:return 325;
      case 5:return 530;

      default :
          return Nbx(dot);   /*获取新加地点X坐标*/
    }/* switch */
}/* Zbx */

int Zby(int dot)        /* 设置每个结点的纵坐标 */
{  switch (dot)
    {
      case 1:return 420;
      case 2:return 380;
      case 3:return 340;
      case 4:return 110;
      case 5:return 120;

      default :
          return Nby(dot);   /*获取新加地点Y坐标*/
    }/* switch */
}/* Zby */

int Nbx(int dot)  /*获取新加点X坐标*/
{
    int i;
    for (i=6;i<20;i++)
    {
        if (dot == i)
        {
            return NewX[i];
        }
    }
    
}

int Nby(int dot)  /*获取新加点Y坐标*/
{
    int i;
    for (i=6;i<20;i++)
    {
        if (dot == i)
        {
            return NewY[i];
        }
    }
}


/*键盘输入ASCII转换*/
int Convert(int v)
{
     switch (v)
     {
        case 49:return 1;
        case 50:return 2;
        case 51:return 3;
        case 52:return 4;
        case 53:return 5;
        case 54:return 6;
        case 55:return 7;
        case 56:return 8;
        case 57:return 9;
     }
}

int NEbx(int dot)  /*获取新加点X坐标*/
{
    int i;
    for (i=1;i<10;i++)
    {
        if (dot == i)
        {
            return NewX[i];
        }
    }
    
}

int NEby(int dot)  /*获取新加点Y坐标*/
{
    int i;
    for (i=1;i<10;i++)
    {
        if (dot == i)
        {
            return NewY[i];
        }
    }
}



int DrawMap(void)          /* 画地图 */
{
    int i,j;
    int m;
    int x,y;
    setcolor(YELLOW);
    setlinestyle(SOLID_LINE,0,3);

    /*设定地图大小－－－－－－－－－－－－－－*/
    rectangle(260,75,635,475);        /* 画黄色实边框 600,440 */
    setfillstyle(SOLID_FILL,MAPBACKGROUND);
    bar(262,77,633,473);            /* 填充该边框内的区域 598,438 */
    /*设定地图大小－－－－－－－－－－－－－－*/

    for(i=1;i<=NUM-1;i++)
    for(j=1;j<=NUM-1;j++)
     dis[i][j]=20000;             /* 初始置任两点距离为无穷大 */


     dis[1][2]=140;dis[2][1]=140;
     dis[3][2]=150;dis[2][3]=150;
     dis[4][5]=500;dis[5][4]=500;
     dis[2][4]=820;dis[4][2]=820;
     dis[3][5]=700;dis[5][3]=700;
     dis[1][3]=230;dis[3][1]=230;


    for(m=0;m<Count;m++)                  /*建立新加节点关系*/
    {
       dis[Relation[m][0]][Relation[m][1]]=Relation[m][2];
       dis[Relation[m][1]][Relation[m][0]]=Relation[m][2];
    }


     setcolor(WHITE);              /* 设置前景色为白色 */
     setlinestyle(DOTTED_LINE,0,1);    /* 设置线条为细点线 */
        for(i=1;i<=NUM-1;i++)
        for(j=i+1;j<=NUM-1;j++)
         if (dis[i][j]<20000)
         {
            line(Zbx(i),Zby(i),Zbx(j),Zby(j));   /* 连线 */
            sprintf(str,"%d",dis[i][j]);
            settextjustify(CENTER_TEXT,CENTER_TEXT);
            outtextxy((Zbx(i)+Zbx(j))/2,(Zby(i)+Zby(j))/2,str); /* 显示距离 */
         }/* if */





     setcolor(YELLOW);
     settextjustify(CENTER_TEXT,CENTER_TEXT);
     outtextxy(425,420,"South Gate");
     outtextxy(425,340,"Library");
     outtextxy(325,110,"West Gate");
     outtextxy(530,120,"North Gate");
     outtextxy(330,380,"Nanhai");    /* 显示名点名称 */



     for(i=6;i<=NewNum;i++)    /*标注新地点名称*/
     {
        outtextxy(Zbx(i)+5,Zby(i),name[i]);
     }

     mapFlag = 1;
}/* DrawMap */




int List(void)
{
     int i,H;
     setcolor(WHITE);
     settextjustify(LEFT_TEXT,CENTER_TEXT);

     outtextxy(35,300,"1 - South Gate");
     outtextxy(35,315,"2 - Nanhai Building");
     outtextxy(35,330,"3 - Library");
     outtextxy(35,345,"4 - West Gate");
     outtextxy(35,360,"5 - North Gate");

     H=360;
     for(i=6;i<=NewNum;i++)
     {
        H=H+15;
        sprintf(str,"%d",i);
        outtextxy(35,H,str);
        outtextxy(41,H," - ");
        outtextxy(65,H,name[i]);
     }
     outtextxy(35,435,"    (Adult Edu. Building)");    /* 显示图例 */
}

int Depa(void)         /* 出发地 */
{
     int i,H;
     char sel[10];
     char c[20];
     DrawMap();           /* 重绘地图 */
     setcolor(WHITE);
     settextjustify(LEFT_TEXT,CENTER_TEXT);

     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,280);


     outtextxy(35,300,"1 - South Gate");
     outtextxy(35,315,"2 - Nanhai Building");
     outtextxy(35,330,"3 - Library");
     outtextxy(35,345,"4 - West Gate");
     outtextxy(35,360,"5 - North Gate");


     H=360;
     for(i=6;i<=NewNum;i++)     /*新增地点列表*/
     {
        H=H+15;
        sprintf(str,"%d",i);
        outtextxy(35,H,str);
        outtextxy(41,H," - ");
        outtextxy(65,H,name[i]);
     }

     outtextxy(35,435,"    (Adult Edu. Building)");    /* 显示图例 */

     setcolor(WHITE);
     outtextxy(35,210,"Input the number directly");    /* 输入提示 */
     depart=getche();

                               /* 获取键值 */
       switch (depart)
        {
            case '1': DrawChoice(425,420,5,RED);break;
            case '2': DrawChoice(330,380,5,RED);break;
            case '3': DrawChoice(425,340,5,RED);break;
            case '4': DrawChoice(325,110,5,RED);break;
            case '5': DrawChoice(530,120,5,RED);break;

            default :
                    if (Convert((int)depart) <= NewNum)
                    {
                        DrawChoice(Nbx(Convert((int)depart)),Nby(Convert((int)depart)),5,RED);
                    }
                    else
                    {
                        setcolor(BACKGROUND);
                        outtextxy(35,210,"Input the number directly"); /* 消除提示 */
                        for (i=1;i<=200;i++)
                        {
                            setcolor(WHITE);
                            outtextxy(35,210,"Error! Choose again!");
                        }; /* 显示错误 */
                        setcolor(BACKGROUND);
                        outtextxy(35,210,"Error! Choose again!");   /* 消除显示 */
                        return;
                    }

        }/* switch c */
    setcolor(BACKGROUND);
    outtextxy(35,210,"Input the number directly");  /* 消除提示 */
}/* Depa */



int Dest(void)
{
   int i;

   setfillstyle(SOLID_FILL,BACKGROUND);
   bar(20,210,255,280);

   if (depart<=48||depart>=57)
   {
        for (i=1;i<=700;i++)
        {
            setcolor(WHITE);
            outtextxy(35,210,"Incorrect Departure!");
        }  /* 显示错误，缺出发地 */
        setcolor(BACKGROUND);
        outtextxy(35,210,"Incorrect Departure!");  /* 消除显示 */
        return ;
   }/* if */

    setcolor(WHITE);
    outtextxy(35,210,"Input the number directly");
    destin=getche();
    switch (destin)
        {
            case '1': DrawChoice(425,420,5,RED);break;
            case '2': DrawChoice(330,380,5,RED);break;
            case '3': DrawChoice(425,340,5,RED);break;
            case '4': DrawChoice(325,110,5,RED);break;
            case '5': DrawChoice(530,120,5,RED);break;

            default :

                   if (Convert((int)destin) <= NewNum)
                   {
                        DrawChoice(Nbx(Convert((int)destin)),Nby(Convert((int)destin)),5,RED);
                   }
                   else
                   {
                        setcolor(BACKGROUND);
                        outtextxy(35,210,"Input the number directly");
                        for (i=1;i<=200;i++)
                            {setcolor(WHITE);
                            outtextxy(35,210,"Error! Choose again!");};
                        setcolor(BACKGROUND);
                        outtextxy(35,210,"Error! Choose again!");
                        return;
                   }

   }/* switch c */

    setcolor(BACKGROUND);
    outtextxy(35,210,"Input the number directly");

    goto_xy(15,4);
    printf("You are going from place %c",depart);
    goto_xy(16,4);
    printf("                         ");
    goto_xy(16,4);
    printf("to place %c\t(y/n)?",destin);        /* 显示输入情况 */

    choice=getche();
    switch(choice)
     {case 'y': Shortest();   /* 开始求最短路径 */
                depart='0';destin='0';break;
      default:  setfillstyle(SOLID_FILL,BACKGROUND);
                bar(20,220,255,290);         /* 用矩形将显示字的地方覆盖 */
                depart='0';destin='0';break;
     }/* switch choice */
}/* Dest */

void Initshoulujing(int node)      /* 初始化所求点到任意点的路径*/
{
    char ch[3],i;
    for(i=1;i<=NUM-1;i++)
       {path[i][0]='\0';           /* 初始为空串 */
        if(dis[node][i]<20000)
            {ch[0]=node+'0';
             ch[1]=i+'0';
             ch[2]='\0';
             strcat(path[i],ch);     /* 初始路径为所求点直接到任意点 */
            }/* if */
        sign[i]=0;         /* 设置每一点为未标记 */
       }/* for */
    sign[node]=1;          /* 设置所求点为已标记 */
}/* Initshoulujing */

void Find(int node)              /* 找所求点到任意点的最短路径 */
{
    int i,k,min=node,z,t=0;
    char ch[3];
    for(z=2;z<=NUM-1;z++)
        {for(k=1;k<=NUM-1;k++)
            if(!sign[k])                 /* 如果某点未被标记 */
                if(dis[node][min]>dis[node][k])
                    min=k;                    /* 找出到所求点距离最小的点 */
         for(i=1;i<=NUM-1;i++)
            if(dis[min][i]<20000&&dis[node][i]>dis[node][min]+dis[min][i]&&i!=node)
                {dis[node][i]=dis[node][min]+dis[min][i];
                 ch[0]=i+'0';
                 ch[1]='\0';
                 strcat(path[min],ch);
                 strcpy(path[i],path[min]); /* 通过该点找其他点的最短路径 */
                 t=0;
                 while (path[min][t++]!='\0');
                    path[min][t-2]='\0';      /* 重置该点的最短路径 */
                }/* if */
         sign[min]=1; /* 设置该点为已标记 */
         min=node;
        } /* for */
}/* Find */

int Shortest(void)           /* 显示最短路径 */
{
     int m=depart-48,n=destin-48,i,j,t;
     Initshoulujing(m);         /* 初始化路径 */
     Find(m);                   /* 找最短路径 */
     goto_xy(15,4);
     printf("%d to %d | about %d metres  ",m,n,dis[m][n]);
     goto_xy(16,4);
     printf("                         ");
     goto_xy(16,4);
     printf("The route is ");
     t=0;
     while (path[n][t+1]!='\0')           /* 输出路径结果 */
          {setlinestyle(SOLID_LINE,0,3);
           setcolor(GREEN);
            i=path[n][t]-48;
            j=path[n][t+1]-48;
            line(Zbx(i),Zby(i),Zbx(j),Zby(j));    /* 画线 */
            printf("%c\-",path[n][t++]);      /* 写结点 */
          }/* while */
     printf("%c",path[n][t]);       /* 补上最后一个结点 */
}/* Shortest */

void End(void)
{
    settextstyle(0,0,3);
    settextjustify(CENTER_TEXT,CENTER_TEXT);
    setcolor(LIGHTRED);
    while(!kbhit())
        outtextxy(319,239,"Thank You For Using!");
}/* End */

main()
{
    Init();
    Save();
    Welcome();
    Menu();
    End();
}