姓名 ：
学号：指导老师：
学院：班级 ：
日期：一 、 课程设计题目。
图的结构建立和最短路径算法和最短路径算法。
二 、 课程设计内容。
熟悉图的各种存储结构（特别是邻接矩阵和邻接表）。设计一个交通咨询系统，求得最短路径。此外建立一个aoe网，求得关键路径。
三 、 算法设计。
最短路径的算法设计。
程序设计总体思路。
1、该程序可以读取文件中相邻两地点的距离信息，在程序中用邻接矩阵构造一个有向网，并计算网中任意节点到其它节点的最短路径并输出。
2、在磁盘中新建一个文件存储两个地点的距离信息，要求先输入起点，以空格间隔，然后输入终点，再以空格间隔，然后输入这两个地点间的距离，如此法，依次输入各路径间的起点，终点和距离。
3、根据界面所给的提示信息首先输入保存交通网的文件名，然后输入要求哪一个节点到其它节点的最短路径。
4、程序运行后，在屏幕上将输出所求节点经过某些中转站到达它所能达到的节点及最短路径的值，并将各节点与其对应的编号保存到文件“编号与地名对照表”中，以便它用。
5、程序执行的命令包括：
1）求place数组中的记录在顶点向量中的坐标、
2）采用邻接矩阵存储结构，构造有向网、
3）用dijkstra算法求最短路径、
4）输出最短路径。
1、概要设计。
基本操作：creatgraph(mgraph &g)
操作结果：采用邻接矩阵存储结构，构造有向网g
locatevex(mgraph &g,char * place)
初始条件：用邻接矩阵存储的有向网g已存在。
操作结果：返回place数组中的记录在顶点向量中的坐标。
shortestpath_dij(const mgraph &g,int v0,pathmatrix &p,shortpathtable &d)
初始条件：用邻接矩阵存储的有向网g已存在。
操作结果：求网g的v0顶点到其余顶点v的最短路径及其带权长度。
print(mgraph &g,pathmatrix p,shortpathtable d,int v0)
初始条件：用邻接矩阵存储的有向网g，最短路径p，带权长度d已存在。
操作结果：输出最短路径。
2、详细设计：
1)元素类型： typedef int vrtype;
typedef char infotype;
typedef char * vertextype;
typedef char pathmatrix[max_vertex_num][max_vertex_num];
typedef int * shortpathtable;
2）结点类型：typedef struct arecell
vrtype adj;//权值。
infotype * info;//附加信息。
arccell,adjmatrix[max_vertex_num][max_vertex_num];
typedef struct
vertextype vexs[max_vertex_num];
adjmatrix arcs;//邻接矩阵。
int vexnum,arcnum;//顶点个数，弧的条数。
mgraph;
3）主程序模块：
void main()
mgraph g;
pathmatrix p;
shortpathtable d;
int v0;
creatgraph(g);
d=(int *)malloc(
printf("求哪一个顶点到其余顶点的最短路径？");
scanf("%d",&v0);
shortestpath_dij(g,v0,p,d);
print(g,p,d,v0);
4）构造有向网的模块：
void creatgraph(mgraph &g)
file *fp;
int i,j;
char filename[20],place1[10],place2[10],num[10],c;
//初始化邻接矩阵。
for(i=0;i for(j=0;j
for(i=0;i
printf("请输入保存交通网的文档名");
gets(filename);
if((fp=fopen(filename,"r"))null)
c=fgetc(fp);
while(c!=eof)
place1+i)='0';/添加结束符。
while(c=='c=='n')
c=fgetc(fp);
i=0;while(c!='c!='n' &c!=eof)
place2+i)='0';/添加结束符。
while(c=='c=='n')
c=fgetc(fp);
i=0;while(c!='c!='n' &c!=eof)
num+i)='0';/添加结束符。
while(c=='c=='n')
c=fgetc(fp);
边数加1i=locatevex(g,place1);/确定第一个地名在邻接矩阵中的位置。
j=locatevex(g,place2);/确定第二个地名在邻接矩阵中的位置。
构造邻接矩阵。
fclose(fp);
if((fp=fopen("标号与地名对照表。txt","w"))null)
//打印一张标号与地名对照表。
for(i=0;i<
fprintf(fp,"%d表示%s",i,fclose(fp);
//向屏幕输出一张标号与地名对照表。
for(i=0;i<
printf("%d表示%s",i,
5) 求最短路径的模块：
void shortestpath_dij(const mgraph &g,int v0,pathmatrix &p,shortpathtable &d)
int v,i,w,min,final[max_vertex_num];
for(v=0;v<
d[v0]=0;
final[v0]=true;//初始化，vo顶点属于s集。
//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集。
for(i=1;i<
final[v]=true;//离v0顶点最近的v加入s集。
for(w=0;w<
//for6）输出最短路径的模块：
void print(mgraph &g,pathmatrix p,shortpathtable d,int v0)
int i,v,w,no=0;
for(v=0;v<
else ;
if(no==0)printf("%s到任意地点都没有路径",3、测试结果。
输入文件。在输入任意一个地点。
结果如下图。
关键路径的算法设计。
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...