20132014数据结构复习.doc

数据结构 数据是对客观事务的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理 数据项多个数据项可组成一个数据元素，数据项是数据的不可分割的最小单位。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据的结构是相互之间存在一种或多种特定关系的数据元素的集合 四类基本结构（1）集合2）线性结构3）树形结构4）图状结构或网状结构 逻辑结构：数据结构的二元组定义只是对操作对象的一种数学描述，反映的是数据元素之间的逻辑关系，所以称为数据结构的逻辑结构。 储存结构：数据结构在计算机中的表示称为物理结构。又称存储结构。 算法的设计取决于 选定的逻辑结构 算法的实现依赖于采用的存储结构 数据的结构的表示:顺序存储结构 、链式存储结构 数据类型：是一个值的集合和定义在这个值上的一组操作的总称 1）原子数据类型2）结构数据类型 抽象数据类型：是指数学模型以及定义在该模型上的一组操作。它可以通过固有的数据类型来表示和实现。 1）原子数据类型（2）固定聚合类型（3）可变聚合类型 算法：是对特定问题求解步骤的一种描述。 算法的五个特性：1）有穷性2）确定性3）可行性4）输入5）输出 算法的描述（1）自然语言（2）专用工具：流程图、表格、伪代码（3）程序设计语言 算法设计的要求：1）正确性 a. 程序不含语法错误 b. 程序对几组输入有正确输出c. 程序对几组典型、苛刻的输入有正确输出d. 程序对一切合法输入有正确输出 （2）可读性（3）健壮性（4）高效率与低存储量需求 一个程序的执行时间通常有两种方法： (1)事后统计的方法。 缺点：不利于较大范围内的算法比较。（异地，异时，异境） (2)事前分析估算的方法。 一个程序的执行时间取决于以下因素：（1）算法的策略（2）问题的规模（3）书写程序的语言（4）编译程序所产生的机器代码的质量（5）机器执行指令的速度 算法的时间量度：从算法中选取一种原操作（对于所研究的问题来说是基本运算），以该基本操作重复执行的次数(执行频度）作为算法的时间量度。 时间复杂度：T(n)=O(f(n)) 上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。 解决的方法：（1）平均时间复杂度（2）最坏情况的时间复杂度 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度，记为： S（n ）=O（f（n）） 2.1 线性表的概念 说明：设 A=（a1, a2, ... , ai -1, ai , ai+1, …, an ）是一线性表 1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的； 2）在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前驱，ai+1 是ai 的直接后继； 3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构； 4）线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； 5）ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表中的位置，仅取决于它的序号； 顶点：表示数据 边：表示是数据间的顺序结构关系 线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。 · 在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存储顺序反映（表示）出来； · 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i – 1) t线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。 结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点； 结点的数据域 ：结点中用于保存数据元素的部分; 结点的指针域 ：结点中用于保存数据元素直接后继存储地址的部分; 栈是限定仅能在表尾一端进行插入、删除操作的线性表 第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素 队列是限定仅能在表头进行删除，表尾进行插入的线性表第一个入队的元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素 队空、队满都有front=rear如何判断循环队列队空、队满？ 有两种方法：1）