项目二:校园导游咨询
一、问题的分析与任务定义：
分析用Dijkstra算法解析最短路径问题的基本方法。实验要求我们给出的示例代码能求解任何两点之间的最短路径。
二、逻辑设计：
基于Dijstra算法：求任意两点的最短路径。
2.1数据结构
数据类型的定义：为了实现最短路径，需要设置两个结构体，一个是Vertex,用于存放景点信息，另一个是MGraph,用于存放景点路径。
程序中主要使用其中的几个重要算法：
void Qallspots()
操作结果：浏览学校全景。
void Qspots()
操作结果：查询景点信息。
void Dijkstra()
操作结果：求出景点之间的最短路径。
2.2算法描述
1)假设用邻接矩阵表示带权图，又设s为已找到最短路径的终点集合，则初态S={v}时，其中v是源点，且设v所对应的下标为i,辅助数组dist 的每个分量dist[j] 记录从v到y当前最短路径长度。则初态情况下，dist[i]=0,dist[j]=w[i][j]
(2) 选择，使得dis[k]=min {dist[j]|∈V -S}, 则就是求得的一条从v出发的最短路径终点。令S=SU{}。
(3) 修改dist[u], 其中u∈V -S,。
若dist[k] +w[k][u]
(4) 重复(2)，(3)共n-1次，由此求得从V到其余各点的最短路径。
算法实现:为了便于程序实现，用一个与顶点对应的一维数组S[MaxSize]作为辅助储结构，起到表示所有己求得最短路径长度的顶点所构成的集合与尚未求得最短路径长度的顶点所构成的集合之间的区分作用:其分量S[j]=0表示顶点V尚未求得最短路径长度,S[j]=1表示顶点已求得最短路径长度( j=0,1,···，n-1).
另设个整型数组path,其分量path[i]保存的值是到达顶点的当前最短路径长度的前驱顶点的下标。初始时，path[j]的值如下设置:
-1， j=i, i为原点v的下标
path[j]={-1, j≠i,且w[i][j]= ∞
i，j≠i,且w[i][j]≠∞
由于到达顶点，的前趋顶点的路径长度也是最短的，所以通过path[j],path[path[j]],...,i 可反向跟踪出由;(=v为源点)到vy的最短路径所经过的顶点下标及顶点。所以path中保存了从源点到其余各个顶点的最短路径信息。
在算法执行中，path的内容也随之变化,即在上述第(3)中，当调整从源点到u的当前最短路径长度时，用path[u]=做调整，因是当前最短路径上u的前驱结点。
项目三：算数表达式求解
一、问题的分析与任务定义：
分析用堆栈解析算术表达式的基本方法。实验要求我们给出的示例代码能求解任何包括+，-，*，/，()和0到9数字组成，可多层嵌入的算术表达式。设计一个简单的算数表达式计算器。
二、逻辑设计：
基于堆栈的算法：从左到右扫描每一个字符。
2.1数据结构
利用C++STL库，
2.2算法描述
一.将“中缀表达式”转换为“后缀表达式”
思路：
1.从中缀表达式中从左往右依次取出数据
2.如遇到操作数，直接输出到后缀的队列里。
3.如果遇到操作符（包括括号），再定义一个存放操作符的栈，则:
i.如果操作符是'(',入栈
ii.如果操作符是')',则把栈里的操作符依次出栈并插入到后缀序列后面，直到遇到'('.
iii.如果操作符不是‘(’和‘)’,则：
(1). 如果操作符的优先级比top的优先级高，则入栈
(2).如果操作符优先级等于或小于top优先级，则将top出栈并插入到后缀序列后面，pop后,再比较栈顶元素的优先级，重复iii，直到把此操作符插入，将此操作符入栈。
如果中序队列里的数据已经读取完毕，记录操作符的栈里，还有操作符的话，依次出栈插入到后缀序列的后面。
二.后缀表达式求值
思路：
1.从左至右扫描表达式，遇到数字时，将数字压入栈中，遇到运算符时，弹出栈顶的两个数，其中先出栈的是右操作数，后出栈的是左操作数。
2.用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；
3.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
