guide.c

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

#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dos.h>
/* 说明keydef.h为按键编码*/
#include "keydef.h"
#include "conio.h"
#define NUM 10
#define OK 1

/*背景色*/
#define BACKGROUND BLACK
/*菜单选择点颜色*/
#define MENUCOLOR YELLOW
/*地图背景色*/
#define MAPBACKGROUND BLUE

/*新增地点*/
typedef struct Place
{
   char Name[10];
   int x;
   int y;
   struct Place *next;
} Place, *PlaceList;

void *savedot,*savewelcome,*saveblank,*saveDraw;
char str[5],path[NUM][NUM];
char depart='0',destin='0',choice;
int NewNum = 5;
int dis[NUM][NUM],sign[NUM];
int mapFlag;
int AddFlag=0;   /*是否有新增操作标志*/
int NewX[10],NewY[10],NewDis[10];   /*新加地点信息数组*/
int Relation[3][10];  /*新加节点关系数组*/
char name[10][20];    /*新加地点名称*/
int Count = 0;/*关系级记录数量*/

/*-----------空图变量设置*/
int NewCount=0;

void goto_xy(int x,int y)  /* 使光标跳转 */
 {  union REGS r;
    r.h.ah=2;  r.h.dl=y;
    r.h.dh=x;  r.h.bh=0;
    int86(0x10,&r,&r);
 } /* goto_xy */

/*将指定区域填充为指定颜色*/
void FillColor(int left,int top,int right,int bottom,int color)
{
    setcolor(color);
    rectangle(left,top,right,bottom);        /* 画黄色实边框 */
}

void Init(void)          /* 初始化图形系统 */
{
   int gd=DETECT,gm;
   registerbgidriver(EGAVGA_driver);

   /*设置地图初始为false*/
   mapFlag= 0;
   initgraph(&gd,&gm,"");
   cleardevice();
}/* Init */

void Save(void)       /* 设置并保存welcome和绿点 */
{
    int size;
    setbkcolor(BACKGROUND);             /* 设置背景为淡绿色（Turk） */
    setfillstyle(SOLID_FILL,GREEN);  /* 绿色实填充 */
    fillellipse(200,200,1,1);           /* 画一点 fillellipse画椭圆函数*/
    size=imagesize(200,200,200,200);    /* 保存点 imagesize() 图像存储大小函数*/
    savedot=malloc(size);               /* 分配位图空间 */
    getimage(200,200,200,200,savedot);  /* 保存位图 getimage() 保存图像函数*/
    cleardevice();

    setcolor(WHITE);               /* 设置前景色为白色 setcolor() 设置颜色函数*/
    settextstyle(0,0,2);           /* 设置二倍字体 */
    outtextxy(250,200,"Welcome!");
    size=imagesize(249,199,390,250);
    savewelcome=malloc(size);
    getimage(249,199,390,250,savewelcome);  /* 保存welcome */
}/* Save */

void Welcome(void)          /* 欢迎界面 */
{
    int i,j;float k;
    settextstyle(0,0,1);
    setcolor(YELLOW);
    outtextxy(100,340,"Powered by : Wang Ziyan");

    setcolor(GREEN);
    outtextxy(400,365,"number : ");

    setcolor(LIGHTRED);
    outtextxy(250,400,"Major : Maths And Applied Mathematics");

    setcolor(CYAN);
    outtextxy(130,440,"Finished On Dec. 17th , 2007   v1.01");
    while(!kbhit())                    /* 设置颜色闪动 */
        for(i=100;i<250;i++)
            {setcolor(i/100);
             outtextxy(210,250,"Press Any Key To Continue");}
    cleardevice();

    for(i=249,j=199;j>=20;i--,j--)       /* 使welcome运动 */
        putimage(i,j,savewelcome,COPY_PUT);
    for(i=69,j=20;i>=25;i--)
        putimage(i,j,savewelcome,COPY_PUT);
        if(kbhit())
        {
            putimage(25,20,savewelcome,COPY_PUT);
        }
    for (k=0;k<700;k+=0.05)                  /* 使绿点运动成线 */
        putimage(25+k/2,50,savedot,COPY_PUT);
    setcolor(WHITE);
    outtextxy(200,25,"v1.01");
    settextstyle(0,0,2);setcolor(LIGHTGREEN);  /* JNU GUIDE */
    outtextxy(430,20,"JNU Guide!");
    getch();
}/* Welcome */

void DrawChoice(int x,int y,int radius,int color)  /* 画实心圆 */
{
   setcolor(color);        /* 设置前景色 */
   circle(x,y,radius);       /* 画圆周 */
   setfillstyle(SOLID_FILL,color);     /* 设置用前景色实填充 */
   floodfill(x,y,color);         /* 填充圆区域 */
}/* DrawChoice */



/*获取键盘值*/
int testcode()
{
    int code;
    /*if (bioskey(0))*/
         code =bioskey(0)/0x100;
    return code;
}


/*初始化地图*/
void InitMap()
{
     NewNum = 5;
     Count = 0;
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(30,205,255,400);
}

/*新增地点信息输入*/
void InputPlaceInfo(int x,int y)
{
     PlaceList p;
     int selP;
     int Dis;
     int i;


     settextjustify(LEFT_TEXT,CENTER_TEXT);

     NewNum = NewNum + 1;


     setfillstyle(SOLID_FILL,BACKGROUND);   /*清空当前区域*/
     bar(20,210,255,260);


     /*--输入地点名称-----------------------*/
     setcolor(WHITE);
     outtextxy(35,220,"Input new place name:");
     goto_xy(15,4);
     printf("Input:");
     scanf("%s",name[NewNum]);
     outtextxy(x+3,y,name[NewNum]);
     /*selP=getche();*/
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(35,220,"Input new place name:");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*------------------------------------*/

     List();  /*显示列表*/

     /*--选择列表中的地点------------------*/
     setcolor(WHITE); 
     outtextxy(35,220,"Select the related place");
     goto_xy(15,4);
     printf("Input:");
     scanf("%d",&selP);

     while(selP>NewNum-1)
     {
        setcolor(BACKGROUND);
        for (i=1;i<=200;i++)
        {
            setcolor(WHITE);
            outtextxy(35,210,"Error! Choose again!");
        }; /* 显示错误 */
        setcolor(BACKGROUND);
        outtextxy(35,210,"Error! Choose again!");   /* 消除显示 */
        goto_xy(15,4);
        printf("Input:");
        scanf("%d",&selP);
     }

     DrawChoice(Zbx(selP),Zby(selP),2,RED);        /*显示选择节点*/
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(35,220,"Select the related place");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*-----------------------------------*/


     /*--输入两点之间距离------------------*/
     setcolor(WHITE);
     outtextxy(35,220,"Input the distance:");
     goto_xy(15,4);
     printf("Input:");
     scanf("%d",&Dis);
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(35,220,"Input the distance:");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*-----------------------------------*/



     dis[NewNum][selP]=Dis;
     dis[selP][NewNum]=Dis;

     NewX[NewNum]=x;            /*保存新加地点X坐标*/
     NewY[NewNum]=y;            /*保存新加地点Y坐标*/
     NewDis[NewNum]=Dis;

     Relation[Count][0]=NewNum;     /*起始地点*/
     Relation[Count][1]=selP;       /*中止地点*/
     Relation[Count][2]=Dis;        /*两点距离*/
     Count = Count + 1;             /*数组位移*/

     setcolor(WHITE);              /* 设置前景色为白色 */
     setlinestyle(DOTTED_LINE,0,1);    /* 设置线条为细点线 */
     line(x,y,Zbx(selP),Zby(selP));   /* 连线 */
     sprintf(str,"%d",dis[NewNum][selP]);
     settextjustify(CENTER_TEXT,CENTER_TEXT);
     outtextxy((x+Zbx(selP))/2,(y+Zby(selP))/2,str);
     DrawChoice(x,y,2,MAPBACKGROUND); /*清除坐标点*/



     DrawChoice(Zbx(selP),Zby(selP),2,MAPBACKGROUND);   /*清除选择节点*/

}


void CreateRelation()
{
    int start,end;    /*初始地点，终止地点*/
    int selP;
    int Dis;
    int i;

     DrawMap();     /*加载地图*/
     List();        /*加载地点选择列表*/


     /*--选择初始地点-----------------*/
     setcolor(WHITE); 
     outtextxy(30,220,"Select the start place");
     goto_xy(15,4);
     printf("Input:");
     scanf("%d",&selP);

     while(selP>NewNum)
     {
        setcolor(BACKGROUND);
        for (i=1;i<=200;i++)
        {
            setcolor(WHITE);
            outtextxy(35,210,"Error! Choose again!");
        }; /* 显示错误 */
        setcolor(BACKGROUND);
        outtextxy(35,210,"Error! Choose again!");   /* 消除显示 */
        goto_xy(15,4);
        printf("Input:");
        scanf("%d",&selP);
     }

     start = selP;

     DrawChoice(Zbx(selP),Zby(selP),2,RED);        /*显示选择节点*/
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(30,220,"Select the start place");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*-----------------------------------*/


     /*--选择终止的地点------------------*/
     setcolor(WHITE); 
     outtextxy(30,220,"Select the end place");
     goto_xy(15,4);
     printf("Input:");
     scanf("%d",&selP);

     while(selP>NewNum)
     {
        setcolor(BACKGROUND);
        for (i=1;i<=200;i++)
        {
            setcolor(WHITE);
            outtextxy(35,220,"Error! Choose again!");
        }; /* 显示错误 */
        setcolor(BACKGROUND);
        outtextxy(35,220,"Error! Choose again!");   /* 消除显示 */
        goto_xy(15,4);
        printf("Input:");
        scanf("%d",&selP);
     }

     end = selP;

     DrawChoice(Zbx(selP),Zby(selP),2,RED);        /*显示选择节点*/
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(30,220,"Select the end place");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*-----------------------------------*/


     /*-判断是否已存在关系--*/

     if (dis[start][end]!=20000)
     {
        setcolor(BACKGROUND);
        for (i=1;i<=200;i++)
        {
            setcolor(WHITE);
            outtextxy(30,220,"Error!The relation is existed!");

        }; /* 显示错误 */
        setcolor(BACKGROUND);
        outtextxy(30,220,"Error!The relation is existed!");   /* 消除显示 */
        return;
     }

     /*************************/


     /*--输入两点之间距离------------------*/
     setcolor(WHITE);
     outtextxy(35,220,"Input the distance:");
     goto_xy(15,4);
     printf("Input:");
     scanf("%d",&Dis);
     setcolor(BACKGROUND); /* 消除显示 */
     outtextxy(35,220,"Input the distance:");
     setfillstyle(SOLID_FILL,BACKGROUND);
     bar(20,210,255,260);
     /*-----------------------------------*/

     dis[start][end]=Dis;    /*建立有向图关系*/
     dis[end][start]=Dis;

     Relation[Count][0]=start;     /*起始地点*/
     Relation[Count][1]=end;       /*中止地点*/
     Relation[Count][2]=Dis;        /*两点距离*/
     Count = Count + 1;             /*数组位移*/

     setcolor(WHITE);              /* 设置前景色为白色 */
     setlinestyle(DOTTED_LINE,0,1);    /* 设置线条为细点线 */
     line(Zbx(start),Zby(start),Zbx(end),Zby(end));   /* 连线 */
     sprintf(str,"%d",dis[start][end]);
     settextjustify(CENTER_TEXT,CENTER_TEXT);
     outtextxy((Zbx(start)+Zbx(end))/2,(Zby(start)+Zby(end))/2,str);

    
}


/*添加新的地点*/
int AddPlace()
{
    int key,keyx,keyy,r,yes=1;
    int size;
    int i;

    DrawMap();

    setfillstyle(SOLID_FILL,BACKGROUND);
    bar(30,205,255,270);

    keyx=265;keyy=85;
    r=2;

    DrawChoice(keyx,keyy,r,YELLOW);


    while(yes)
     {
       key=testcode();
       switch(key)
       {
            case UP:    DrawChoice(keyx,keyy,r,MAPBACKGROUND);
                        if (keyy<=84)
                            keyy=84; else keyy-=2;
                        DrawChoice(keyx,keyy,r,YELLOW);
                        break;
            case DOWN:  DrawChoice(keyx,keyy,r,MAPBACKGROUND);
                        if (keyy>=436)
                        keyy=436; else keyy+=2;
                        DrawChoice(keyx,keyy,r,YELLOW);
                        break;
            case LEFT:  DrawChoice(keyx,keyy,r,MAPBACKGROUND);
                        if (keyx<=264)
                        keyy=264; else keyx-=2;
                        DrawChoice(keyx,keyy,r,YELLOW);
                        break;
            case RIGHT: DrawChoice(keyx,keyy,r,MAPBACKGROUND);
                        if (keyx>=596)
                        keyx=596; else keyx+=2;
                        DrawChoice(keyx,keyy,r,YELLOW);
                        break;
            case ENTER: AddFlag = 1;

                        InputPlaceInfo(keyx,keyy);
                        return 1;
            case ESC:   DrawChoice(keyx,keyy,r,MAPBACKGROUND);
                        return 1;

       }
     }
}

void Menu(void)                /* 菜单 */
{
     int key,keyx,keyy,r=2,yes=1;
     int oper;
     setcolor(LIGHTGRAY);
     settextstyle(0,0,1);
     settextjustify(LEFT_TEXT,CENTER_TEXT);  /* 水平居左，垂直居中 */
     outtextxy(60,90,"Show the map");
     outtextxy(60,110,"Choose the departure");
     outtextxy(60,130,"Choose the destination");
     outtextxy(60,150,"Add the place");
     outtextxy(60,170,"Create the relation");