下载文档原格式
哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构课程类型：必修实验项目名称：线性结构及其应用实验题目：线性结构及其应用一、实验目的二、实验要求及实验环境三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1．逻辑设计2．物理设计四、测试结果五、系统不足与经验体会六、附录：源代码（带注释）一、实验目的输入中缀表达式保存并显示，之后转换为后缀表达式，并且求出表达式的结果。
二、实验要求及实验环境实验要求(1)从键盘输入任意一个语法正确的（中缀）表达式，显示并保存该表达式。
(2)利用栈结构，把上述（中缀）表达式转换成后缀表达式，并显示栈的状态变化过程和所得到的后缀表达式。
(3)利用栈结构，对上述后缀表达式进行求值，并显示栈的状态变化过程和最终结果。
实验环境Dev-C++软件中运行Win7系统三、设计思想本实验中定义了int 型，char型，struct 型，char *型，struct型逻辑设计：应用栈后进先出的规律，在转换为后缀表达式时，将操作运算符压入栈中，碰见更高级运算符时栈中元素出栈，继续比较；否则压栈。
这样可以完成表达式的转换。
在利用得到的后缀表达式计算结果时，将操作数压栈，遇见符号直接计算，这是后缀表达式的特点。
物理设计：建立一个结构体数组的栈，数组中存放运算符。
数组的添加和减少都在数组末尾元素进行。
可以视为一个栈。
四、测试结果样例1. 输入1+2*（3-4/2）输出为1+2*（3-4/2） ->此为保存并输出的中缀表达式12342/-*+ ->此为输出后缀表达式3 ->此为表达式的值样例2. 输入1+2*3/4-5输出为1+2*3/4-5123*4/+5--3五、系统不足与经验体会不足1.此程序只能进行整形一位数上的计算，无法实现实数范围内的计算。
2.程序用的是结构体数组来表示栈的存储结构，数组定义时，定义一段很大的空间，导致空间利用率不高。
第4章图结构及其应用算法数据结构与算法Data Structures andgAlgorithms张岩海量数据计算研究中心哈工大计算机科学与技术学院第4章图结构及其应用算法2016/11/20Slide 4-2——图论欧拉欧拉1707年出生在瑞士的巴塞尔城，19岁开始发表论文，直到76岁。
几乎每一个数学领域都可以表论文直到76岁几乎每个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。
据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、力学占28%天文学占11%弹道学航海学建筑学等占3%。
1733年，年仅26岁的欧拉担任了彼得堡科学院学教授年到林担任科了彼得堡科学院数学教授。
1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明。
欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。
哥尼斯堡七桥问题能否从某个地方出发，穿过所有的桥仅一次后再回到出发点?学习目标图结构是一种非线性结构，反映了数据对象之间的任意关系，在计算机科学、数学和工程中有着非常广泛的应用。
了解图的定义及相关的术语，掌握图的逻辑结构及其特点；了解图的存储方法，重点掌握图的邻接矩阵和邻接表存储结构；掌握图的遍历方法，重点掌握图的遍历算法的实现；了解图的应用，重点掌握最小生成树、双连通性、强连通性、最短路径、拓扑排序和关键路径算法的基本思想、算法原理和实现过程。
本章主要内容4.1 图的基本概念4.2 图的存储结构4.3 图的遍历(搜索)4.4 最小生成树算法4.5 双连通性算法4.5双连通性算法4.6 强连通性算法4.7最短路径算法4.7 最短路径算法4.8 拓扑排序算法4.9 关键路径算法本章小结本章的知识点结构基本的数据结构（ADT）图无向图有向图加权图网络图（无向图、有向图；加权图----网络）知识点结构定义及相关术语逻辑结构及其特征ADT定义A逻辑结构静态的结构基本操作（算法）存储结构（描述）ADT基本动态的操作存储结构特点存储结构的定义ADT实现数据结构存储结构静态的结构操作（算法）实现算法的性能应用:最小生成树最短路径拓扑排序和关键路径动态的操作,,图的搜索(遍历)算法是有关图问题的重要核心算法！4.1基本定义4.1定义1 图(Graph)图是由顶点（vertex）的有穷非空集合和顶点之间边（edge）的集合组成的一种数据结构，通常表示为：G = (V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。
