数据结构课程设计论文(手机通讯录管理系统,最佳旅游路线规划问题,图书租借管理问题)

附录

源程序清单 //3.h

#include #include #include

#define INFINITY 100 //最大值

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef struct{

char city[MAX_VERTEX_NUM][10]; int cout;

}Path; //用于储存路径

typedef struct{

char vexs[MAX_VERTEX_NUM][10]; //顶点信息 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 } MGraph; //采用数组表示法的图的结构体 int LocateVex(MGraph &G,char city[]){ int i;

for(i=0;i

if(strcmp(G.vexs[i],city)==0) return i; if(i==G.vexnum) return -1;

} //定位城市在邻接表中的位置

void print(MGraph G) { int i,j;

printf(\图的邻接矩阵为：\\n\

for(i=0;i

for(j=0;j

printf(\if((j+1)%7==0) printf(\

29

printf(\

} //输出邻接矩阵

void CreateGraph(MGraph &G) {printf(\涉及城市为：\\n\ FILE *fp;

if((fp=fopen(\ } int i,j,k,w;

char city1[10],city2[10];

fscanf(fp,\读入城市的数量以及城市之间路径的总数 for(i=0;i

for(i=0;i

void Dijkstra(MGraph G,char city[]) //用迪杰斯塔拉算法求最短路径 {

int i,v,w,min,v0;

int D[MAX_VERTEX_NUM]={0}; //带权路径长度

int final[MAX_VERTEX_NUM]={0}; //建立一数组，并将所有值置为0，方便后续置换有最短路径的结点

Path path[MAX_VERTEX_NUM]={0}; //path[v]中储存着从v0到v当前求得最短路径上的顶点信息

for(j=0;j

G.arcs[i][j]=INFINITY; for(k=0;k

fscanf(fp,\ //输入一条边依附的顶点和权值 i=LocateVex(G,city1); //确定顶点位置 j=LocateVex(G,city2);

G.arcs[i][j]=G.arcs[j][i]=w; //给弧赋值 printf(\读入信息出错\\n\

30

if((v0=LocateVex(G,city))==-1) {

for(v=0;v

final[v0]=1; //初始化，将主函数输入的城市的标志置为1，即加入集合Q printf(\起始点 终止点 旅行时间 路径 \\n\\n\

//开始主循环，每次求得v0到某个v顶点的最短路径，并输出最短路径

for(i=1;i

min=INFINITY; //当前的最短路径为最大值 for(w=0;w

if(!final[w])

if(D[w]

{v=w;min=D[w];} //如果找到w顶点离v0顶点更近，则更改v和min

D[v]=G.arcs[v0][v]; //从v0到v的路径长度 if(D[v]

strcpy(path[v].city[path[v].cout++],city); strcpy(path[v].city[path[v].cout++],G.vexs[v]); printf(\图中无该点\\n\return;

} //如果显示为-1，则图中无所输入的结点

} //将主函数输入的城市作为起始点

final[v]=1;

printf(\for(w=0;w

for(w=0;w

if(!final[w]&&(min+G.arcs[v][w]

D[w]=min+G.arcs[v][w]; path[w]=path[v];

31

strcpy(path[w].city[path[w].cout++],G.vexs[w]);

}

} }

//3.cpp

#include #include #include #include \void main() {

MGraph G;

char city[10]={'\\0'},ch[10],b; while(1)

{

CreateGraph(G);

print(G);

printf(\读取数据成功\\n\ printf(\请输入起始点：\

scanf(\ strcpy(city,ch); Dijkstra(G,city);

}

} 32