欢迎学习 数据结构与算法分析
欢迎学习 数据结构与算法分析
第一章数据结构和算法 大多数计算机程序的主要目标是存储信 息和尽快地检索信息。因此,研究数据 结构和算法就成了计算机科学的核心问 题。本书的目的就是帮助读者理解怎样 组织信息,以便支持高效的数据处理 介绍常用的数据结构 引入并加强“权衡”( tradeoff的概念,每 个数据结构都有其相关的代价和效益的权衡 评估一个数据结构或算法的有效性
第一章 数据结构和算法 • 大多数计算机程序的主要目标是存储信 息和尽快地检索信息。因此，研究数据 结构和算法就成了计算机科学的核心问 题。本书的目的就是帮助读者理解怎样 组织信息，以便支持高效的数据处理。 – 介绍常用的数据结构 – 引入并加强“权衡”(tradeoff)的概念，每一 个数据结构都有其相关的代价和效益的权衡 – 评估一个数据结构或算法的有效性
程序设计的目标 1.设计一种容易理解、编码和调试的算法。 2.设计一种能有效利用计算机资源的算法 目标1主要涉及到的是软件工程原理; 本书主要讲的是与目标2有关的问题
程序设计的目标 1．设计一种容易理解、编码和调试的算法。 2．设计一种能有效利用计算机资源的算法 目标1主要涉及到的是软件工程原理； 本书主要讲的是与目标2有关的问题
效率度量 算法分析: 估算一种算法或者一个计算机程序的效率的方 法 算法分析可以度量一个问题的内在复杂程度
效 率 度 量 • 算法分析： – 估算一种算法或者一个计算机程序的效率的方 法 – 算法分析可以度量一个问题的内在复杂程度
学习数据结构的必要性 个数据结构就是一类数据的表示及其 相关操作。 个数据结构被认为是一组数据项的组 织或者结构。 存储一组数据项,数据结构执行所有必 需的运算:查找、打印或排序,或者更 改数据项的值。选择不同的数据结构可 能会产生很大的差异
学习数据结构的必要性 • 一个数据结构就是一类数据的表示及其 相关操作。 • 一个数据结构被认为是一组数据项的组 织或者结构。 • 存储一组数据项，数据结构执行所有必 需的运算：查找、打印或排序，或者更 改数据项的值。选择不同的数据结构可 能会产生很大的差异
资源限制 资源限制包括空间和时间。 算法的代价(cost)是指这种算法消耗的资 源量 选择数据结构的步骤: 1.分析问题,以确定任何算法均会遇到的 资源限制 2.确定必须支持的基本操作,并度量每种 操作所受的资源限制。 3.选择最接近这些开销的数据结构
资源限制 • 资源限制包括空间和时间。 • 算法的代价(cost)是指这种算法消耗的资 源量。 • 选择数据结构的步骤： – 1．分析问题，以确定任何算法均会遇到的 资源限制。 – 2．确定必须支持的基本操作，并度量每种 操作所受的资源限制。 – 3．选择最接近这些开销的数据结构
选择数据结构需要考虑的问题 开始时是将所有数据项都插人数据结构, 还是与其他操作混合在一起插入 数据项能否删除 所有数据项是否按某一个已经定义好的 顺序排列,是否允许查找特定的数据项
选择数据结构需要考虑的问题 • 开始时是将所有数据项都插人数据结构， 还是与其他操作混合在一起插入。 • 数据项能否删除。 • 所有数据项是否按某一个已经定义好的 顺序排列，是否允许查找特定的数据项
代价与效益 家银行的简单交易情况: 顾客可以新开账户、注销账户以及从 账户上存款和取款。 可以从两个层面上考虑这个问题: (1)银行用来与顾客交互的物理基础结构和工 作处理流程的需求 (2)管理账户的数据库系统的需求
代价与效益 一家银行的简单交易情况： • 顾客可以新开账户、注销账户以及从 账户上存款和取款。 可以从两个层面上考虑这个问题： (1)银行用来与顾客交互的物理基础结构和工 作处理流程的需求， (2)管理账户的数据库系统的需求
抽象数据类型和数据结构 类型(ype)是一组值的集合。 数据项( data item)是一条信息或者其值属 于某种类型的一条记录,数据项又称数 据类型的成员( member) 数据类型( data type)是指一种类型和定义 在该类型上的一组操作
抽象数据类型和数据结构 • 类型(type)是一组值的集合。 • 数据项(data item)是一条信息或者其值属 于某种类型的一条记录，数据项又称数 据类型的成员(member)。 • 数据类型(data type)是指一种类型和定义 在该类型上的一组操作
抽象数据类型和数据结构(续) 抽象数据类型(ADT)是指数据结构作为 个软件组件的实现 ADT的接口用一种类型和该类型上的一组操 作来定义,每个操作由它的输入和输岀定义。 数据结构( data structure)是ADT的实现
抽象数据类型和数据结构(续) • 抽象数据类型(ADT)是指数据结构作为一 个软件组件的实现。 – ADT的接口用一种类型和该类型上的一组操 作来定义，每个操作由它的输入和输出定义。 • 数据结构(data structure)是ADT的实现