《数据结构》
课程设计报告
课题名称：__ 数 据 结 构 ____
专业班级：
学 号：
姓 名：_______
指导老师：
成 绩：__________________
2012 年 12 月
一、课题名称
二、主要内容
三、课题设计的基本思想，原理和算法描述
四、运行示例及结果分析
五、调试和运行程序过程中产生的问题及采取的措施
六、总结
七、参考文献
一、 课题名称
公交车站路线管理系统
二、 主要内容
公交车站路线管理系统的实现是对公交路线信息的简单模拟，以完成建立公交路线信息、
修改公交路线信息和删除公交路线信息等功能。基本功能如下：
（1）公交车站的创建：车站名称不能重复。
（2）公交路线的创建：两个车站间可以创建交通路线及其长度（来回路线长度可以不
一样）,已经创建过路线的两个站点间不能再创建路线。
（3）公交路线的查询：输入两个站点，看是否存在路线。
（4）公交路线的删除：输入两个站点，删除两个站点间的直接路线。
（5）某乘客要从一个站点到另外一个站点（两个站点间不一定有直接的公交路线），
请找出最优的公交线路（如果有的话）
1.公交车站的创建，我选择任意添加的形式。首先给出空图，通过函数的调用来添加顶
点。车站名称不能重复就需要一个查找函数来执行。创建车站的同时给新建车站的路线初
始化。
2.公交路线的创建，创建路线要有三个判断，首先判断起始站和终点站是否存在，然后
是起始站和终点站是否重和，再然后是路线是否已存在。（起始站与终点站重合的情况下
重新输入终点站）
3.公交路线的查询，首先判断起始站和终点站是否存在，是否重合。两点间的路线包括
直接路线及间接路线。
4.公交路线的删除，首先判断起始站和终点站是否存在，是否重合。然后将路线置为
INF。
5.最优路线查询，通过狄克斯特拉算法实现。
三、 课题设计的基本思想，原理和算法描述
算法设计：
函数 CheckStation（）的设计：此函数是用来判定参数给定的值，是否存在于图中。
int CheckStation(MGraph &g,char m[11])
{
int i,temp=-1;
for(i=0;i<g.n ;i++)
{
if(!strcmp(m,g.vexs [i].info ))
{
temp=i;
}
}
return temp;
}
功能菜单
公交车站的创建 公交路线的创建 公交路线的查询 公交路线的删除
最优路线查询 退出系统
temp==-1 时不存在，否则返回的事输入车站在图中的编号。
函数 CreateStation（）的设计：此函数是用来添加车站的，所以它最主要的功能就是给
图中添加顶点，即给 info 赋值。添加顶点的同时，注意顶点的 info 值不能重复，所以调用
CheckStation（）函数来判断。添加完成之后将路线初始化。
strcpy(g.vexs [q+i].info ,s);
for(i=q ;i<q+k;i++)
{
for(j=0;j<q+k;j++)
{
if(i==j)
g.edges[i][j]=0;
else
{
g.edges[i][j]=INF;
g.edges[j][i]=INF;
}
}
}
此处的赋值比较特殊，因为原有的顶点路线已经赋值所以只能给新添的顶点路线赋值
如图所示只给空白部分赋值。
函数 CreateRoute（）的设计：此函数是用来添加车站之间的路线的，所以它最主要的共
能就是给符合条件的 edges 赋值，此函数在添加路线之前也要用到 CheckStation（）函数的
判断功能，及路线是否已经存在的判断。
if(g.edges [temp1][temp2]!=INF)
{
printf("此路线已存在，请重新添加！\n");
}
else
{
g.edges [temp1][temp2]=m;
