[学习总结]数据结构课外实践.doc

数据结构课外实践报告 项 目 名 称: 安阳师院校园导游程序 所 在 班 级: 2011级java 2班 小 组 成 员： 全 政 何 壮 孙 超 指 导 教 师：刘运通 起 止 时 间：第16周 项目基本信息 项目名称 安阳师院校园导游程序 项目简介 实现导游程序，至少包括以下知识： （1） 邻接表 （2） 树的遍历 （3） 拓扑排序算法； （4） 求解关键路径； （5） 求解最短路径。 （6） 无向图 小组成员 全政(组长），孙超，何壮 任务分工 全政:制作PPT、树的遍历 孙超：最短路径算法的编程，队列入栈与出栈的编写 何壮：最短路径算法、主类编写，撰写报告册 课外实践评定成绩记录 指导教师意见 系统完成情况：优 良 中 差 报告完成情况：优 良 中 差 答辩评定成绩 团队整体成绩： 成员成绩 全政 何壮 孙超 综 合 成 绩 问题描述及分析 问题描述：实现安阳师院导游程序，需要满足以下功能 用无向网表示校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。（） 求多个景点的最佳（最短）游览路径。 根据系统功能结构图的描述，可以构造出该系统的几个基本的函数，其方法名和功能如表1所示。 函数 功能 typedef struct ArcNode 邻接表 typedef struct{ int weight; int info;} 邻接矩阵，存储景点距离、路线 void Create(ALGraph *tu) 建立邻接链表，实现景点的创建 void Rclear(MGrph *Ttu) 初始化邻接矩阵，（路径数与景点数已知）将矩阵路径长度初始化为Max，标志位初始化为0 void Turn(ALGraph *tu,MGrph *Ttu) 将邻接链表转换成邻接矩阵 void Rset(ALGraph *tu) 将邻接表中结点的标志以及边的标志初始化为0（路径数与景点数已知） void Rbuild(ALGraph *tu) 景点规划（最小生成树） void main() 信息的输入输出 表1 函数功能表 功能模块 图1 系统功能结构图 数据结构描述、代码分析 （1）定义一个权值的最大值、图的最大顶点数、队列的最大容量。 #includestdio.h #includestdlib.h #includestring.h #define MaxSize 100 #define Max 32767 （2）创建邻接表、邻接矩阵、邻接链表、最短路径结点、拓扑排序用栈、深度遍历生成树 //////////////////////邻接表 typedef struct ArcNode { int adjvex; int info; ///////标志是否被访问过 int weight; struct ArcNode *nextarc; }ANode; typedef struct { int info; ///////标志是否被访问过 char name[50]; ANode *firstarc; }VNode,AdjList[MaxSize]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; ////////////////////////邻接矩阵 typedef struct { int weight; int info; ///////0,表示无路径，1表示有路径 } AdjMatrix[MaxSize][MaxSize]; typedef struct { char names[MaxSize][50]; AdjMatrix arcs; int vexnum,arcnum; }MGrph; //////////////