数据结构课设报告(3)

7、源程序

#include #include #include #include #define Len 44

#define N 100000 //定义两个公交站之间的最大距离，单位m typedef struct xl {

int adj; /*相邻接的公交站的距离*/ }xl;

typedef struct VertexType {

char *site ;

/*公交站名称*/ int route[8];

/*经过该站的路线*/ }VertexType;

/*定义顶点的类型*/

typedef struct MGraph //定义无向图的结构体 {

VertexType vex[Len];

/*图中的顶点，即为站点*/ xl arcs[Len][Len];

/*图中的边，即为两个站点间的距离*/ int vexnum,arcnum ; /*顶点数，边数*/ }MGraph;

MGraph G;

typedef struct Bus {

int num; //车辆的路线号

int stopnum; //每辆车经过的车站的总数 int pass[13]; //每一路车经过的站点的信息 }Bus; //车辆信息

int P[Len][Len]; long int D[Len];

10

void CreateUDN(int v) //构建站点信息以及站点间的无向图 {

int i,j ;

G.vexnum=v;

G.vex[0].site=\长沙火车站\ G.vex[1].site=\窑岭南\ G.vex[2].site=\东塘北\ G.vex[3].site=\中附一院\ G.vex[4].site=\橘园桥北\ G.vex[5].site=\铁道学院\ G.vex[6].site=\林科大\ G.vex[7].site=\井湾子南\ G.vex[8].site=\湖南女大\ G.vex[9].site=\植物园\ G.vex[10].site=\汽车南站\ G.vex[11].site=\人民路北\ G.vex[12].site=\公交新村\ G.vex[13].site=\王家冲\ G.vex[14].site=\高叶塘\ G.vex[15].site=\桃子湖\ G.vex[16].site=\湖大\ G.vex[17].site=\靳江路口\ G.vex[18].site=\南郊公园\ G.vex[19].site=\汽车西站\ G.vex[20].site=\湖南财专\ G.vex[21].site=\丁家垅\ G.vex[22].site=\潇湘晨报\ G.vex[23].site=\香樟路\ G.vex[24].site=\雨花区北\ G.vex[25].site=\火车南站\ G.vex[26].site=\柑子园\ G.vex[27].site=\修业学校\ G.vex[28].site=\义茶亭\ G.vex[29].site=\雨花区西\ G.vex[30].site=\贾谊故居\ G.vex[31].site=\燕子岭\ G.vex[32].site=\东塘西\ G.vex[33].site=\韶山路口\ G.vex[34].site=\新韶路口\ G.vex[35].site=\五菱电力\ G.vex[36].site=\汽车东站\ G.vex[37].site=\血液中心\ G.vex[38].site=\长沙海关\ G.vex[39].site=\橘园桥东\

11

G.vex[40].site=\汽车西站\ G.vex[41].site=\瓜瓢山\ G.vex[42].site=\王家湾\ G.vex[43].site=\阳光一百\ for(i=0;i

12

G.vex[9].route[1]=107; G.vex[9].route[2]=152; G.vex[9].route[3]=502; G.vex[9].route[4]=17; G.vex[10].route[0]=7; G.vex[10].route[1]=107; G.vex[10].route[2]=152; G.vex[10].route[3]=502; G.vex[10].route[4]=17; G.vex[11].route[0]=107; G.vex[12].route[0]=107; G.vex[13].route[0]=107; G.vex[14].route[0]=152; G.vex[14].route[1]=63; G.vex[15].route[0]=152; G.vex[15].route[1]=63; G.vex[16].route[0]=152; G.vex[16].route[1]=63; G.vex[17].route[0]=152; G.vex[17].route[1]=63; G.vex[18].route[0]=152; G.vex[18].route[1]=63; G.vex[18].route[2]=17; G.vex[19].route[0]=63; G.vex[20].route[0]=63; G.vex[21].route[0]=63; G.vex[22].route[0]=63; G.vex[22].route[1]=124; G.vex[23].route[0]=63; G.vex[23].route[1]=124; G.vex[24].route[0]=63; G.vex[24].route[1]=124; G.vex[25].route[0]=63; G.vex[25].route[1]=124; G.vex[26].route[0]=124; G.vex[27].route[0]=124; G.vex[27].route[1]=145; G.vex[28].route[0]=124; G.vex[29].route[0]=124; G.vex[30].route[0]=145; G.vex[31].route[0]=145; G.vex[32].route[0]=145; G.vex[33].route[0]=145; G.vex[34].route[0]=145;

13

G.vex[35].route[0]=145; G.vex[36].route[0]=502; G.vex[37].route[0]=502; G.vex[38].route[0]=502; G.vex[39].route[0]=502; G.vex[40].route[0]=17; G.vex[41].route[0]=17; G.vex[42].route[0]=17; G.vex[43].route[0]=17;

/*这里把所有的边假定为N，含义是站点之间不可到达*/ for(i=0;i

/*下边是可直接到达的站点的距离，由于两个站点间距离是互相的， 所以要对图中对称的边同时赋值。*/ G.arcs[0][1].adj=G.arcs[1][0].adj=2700; G.arcs[0][11].adj=G.arcs[11][0].adj=1400; G.arcs[1][2].adj=G.arcs[2][1].adj=1300; G.arcs[2][3].adj=G.arcs[3][2].adj=1000; G.arcs[2][28].adj=G.arcs[28][2].adj=2000; G.arcs[3][4].adj=G.arcs[4][3].adj=1400; G.arcs[3][32].adj=G.arcs[32][3].adj=750; G.arcs[4][5].adj=G.arcs[5][4].adj=900; G.arcs[4][13].adj=G.arcs[13][4].adj=700; G.arcs[5][6].adj=G.arcs[6][5].adj=1250; G.arcs[5][39].adj=G.arcs[39][5].adj=500; G.arcs[5][18].adj=G.arcs[18][5].adj=3000; G.arcs[5][21].adj=G.arcs[21][5].adj=1850; G.arcs[5][22].adj=G.arcs[22][5].adj=900; G.arcs[6][7].adj=G.arcs[7][6].adj=1400; G.arcs[6][33].adj=G.arcs[33][6].adj=1500; G.arcs[7][8].adj=G.arcs[8][7].adj=1200; G.arcs[8][9].adj=G.arcs[9][8].adj=1000; G.arcs[9][10].adj=G.arcs[10][9].adj=1000; G.arcs[11][12].adj=G.arcs[12][11].adj=2500; G.arcs[12][13].adj=G.arcs[13][12].adj=1500; G.arcs[14][15].adj=G.arcs[15][14].adj=1900; G.arcs[14][20].adj=G.arcs[20][14].adj=2300; G.arcs[15][16].adj=G.arcs[16][15].adj=600; G.arcs[16][17].adj=G.arcs[17][16].adj=3300; G.arcs[17][18].adj=G.arcs[18][17].adj=3400; G.arcs[18][21].adj=G.arcs[21][18].adj=1100; G.arcs[18][43].adj=G.arcs[43][18].adj=3000; G.arcs[19][20].adj=G.arcs[20][19].adj=1400;

14