数据结构与算法 第1讲 绪论1.ppt

数据结构与算法(C++版)课件 第1章 绪论 “学生”表格 UNIX文件系统的系统结构图 数据（data） 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合 数值性数据 非数值性数据 什么是数据结构 数据类型 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称 如C语言中有如下数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值 算法评价标准 时间特性(时间复杂度T(n) ) 空间特性(空间复杂度S(n) ) 健壮性 健壮性指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果 算法描述方法 用自然语言描述算法 用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法 用流程图描述算法 　　 一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。也有其他的图形辅助工具 用其它方式描述算法 　 我们还可以用数学语言或约定的符号语言来描述算法 　　用C++描述算法 　　 在本课中，我们将采用C++来描述算法,所有算法的描述都用C++中的函数模板或函数形式来描述 为表示各种状态信息，定义枚举类型StatusCode供使用，具体声明如下： // 自定义类型 enum StatusCode { SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED }; 算法和程序的关系 算法着重体现思路和方法，程序着重体现计算机的实现 程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，算法中的指令无此限制 一个算法若用计算机语言来书写，它就可以是一个程序 数据结构与算法分析（C++版），清华大学出版社 数据结构讨论的范畴 对于数值计算问题的解决方法，主要 是用数学方程建立数学模型，例如 天气预报的数学模型为二阶椭圆偏微分方程 预测人口增长的数学模型为常微分方程 求解这些数学模型的方法是计算数学 研究的范畴，比如采用 差分算法 有限元算法 无限元算法 对于非数值计算问题，主要采用数据结构的方法建立数学模型 下面通过实例加以说明 / (root) bin lib user etc math ds sw yin tao xie Stack.cpp Queue.cpp Tree.cpp 要在n个网站建立通信网格，要求使得网络中任一网站出现故障时，整个网络仍能正常通信，如图所示，这些网站之间形成一种图结构 综合以上例子可见，描述这类非数值计算问题的数学模型是诸如表、树和图之类的数据结构 因此简单说来，数据结构的研究范畴主要是非数值计算问题的操作对象及其它们之间的关系以及在计算机中的表示和实现 数据结构基本概念 数据元素 (data element) 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理 有时一个数据元素可以由若干数据项(Data Item)组成。数据元素又称为元素、结点、记录 定义: 由某一数据元素的集合及该集合中所有数据元素之间的关系组成 记为： Data_Structure = (D, S) 其中，D 是某一数据元素的有限集合，S 是该集合中所有数据元素之间的关系组成的有限集合 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型 数据的逻辑结构可归结为以下四类 线性结构 树形结构 图状结构 集合结构 数据的存储结构 数据的存储结构是逻辑结构用计算机语言的实现 数据的存储结构依赖于计算机语言 顺序存储表示 链接存储表示 顺序存贮 　 　所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻 　　 链式存贮 　　 所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确