数据结构复习

1、第 1 章 绪 论 数据结构基本概念1. 数据： 在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。2. 数据元素： 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 构成数据元素的不可分割的最小单位称为数据项。3. 数据对象： 是具有相同性质的数据元素的集合，是数据的子集。4. 数据结构：是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构。存储结构要存储两方面的内容： 数据元素； 数据元素之间的逻辑关系。根据数据元素之间逻辑关系的不同，数据结构分为四类： 集合 线性结构 树结构 图结构会画四种基本

2、数据结构的逻辑结构图数据的存储结构又称为物理结构有两种存储结构顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 算法及算法分析什么是算法通俗地讲，算法是解决问题的方法；严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法必须满足下列五个重要特性： 输入： 输出： 有穷性： 确定性： 可行性： 算法的描述方法常用的描述算法的方法常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。算法分析1度量算法效率的方

3、法一种方法是事后统计的方法，先将算法实现，然后输入适当的数据运行，测算其时间和空间开销。其缺点： 编写程序实现算法将花费较多的时间和精力； 所得实验结果依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣。 另一种是事前分析估算的方法渐进复杂度，它是对算法所消耗资源的一种估算方法。2算法的时间复杂度问题规模问题规模是指输入量的多少。运行算法所需要的时间T是问题规模n的函数。基本语句是执行次数与整个算法的执行次数成正比的语句。这种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。即当只考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，称作算法的渐进时间复杂度，简称时间复

4、杂度，通常用大O（读作“大欧”）记号表示。定义1-1 若存在两个正的常数c和n0，对于任意nn0，都有T(n)c×f(n)，则称T(n)=O(f(n)（或称算法在O(f(n)中）。大O记号的含义:3最好、最坏和平均情况4算法的空间复杂度算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。通常记作：S(n)=O(f(n)，其中，n为问题规模，分析方法与算法的时间复杂度类似。5. 算法分析举例定理1-1 若A(n)=amnm +am-1nm-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)。第

5、2 章 线 性 表 线性表的定义 线性表的顺序存储结构及实现设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：LOC(ai)= LOC(a1)(i1)×c线性表的顺序存储结构顺序表顺序表的实现建一个空的顺序表顺序表插入算法。顺序表删除算法。顺序表查找算法 按位查找 按值查找 查找算法的时间复杂度。线性表的链接存储结构及实现线性表的链接存储结构单链表线性表的链接存储结构单链表的实现在单链表上按位查找 单链表的插入算法。插入算法的时间复杂度。单链表的构造：即生成一个有n个结点的单链表。有两种方法：头插法和尾插法。 头插法算法 尾插法算法删除算法。 顺序表和单链表的比较循环链表

6、双链表双链表的性质第 3 章 栈、队列栈的定义栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。 栈的顺序存储结构及实现 栈的顺序存储结构顺序栈栈的顺序存储结构称为顺序栈。 顺序栈的实现顺序栈入栈算法Push 顺序栈出栈算法Pop在栈i中插入元素x的算法在栈i中删除栈顶元素的算法栈的链接存储结构及实现1. 栈的链接存储结构链栈链栈的示意图链栈中是否需要头结点？为什么？2. 链栈的实现链栈的插入算法链栈的删除算法 顺序栈和链栈的比较 队列的定义， 队列的顺序存储结构及实现1. 队列的顺序存储结构循环队列队列的假溢出及其解决循环

7、队列2. 循环队列的实现循环队列的入队算法，循环队列的出队算法队列的链接存储结构及实现队列的链接存储结构链队列队列的链接存储结构称为链队列。链队列的实现创建链队列的算法。入队算法。 出队算法循环队列和链队列的比较第4章 数组、串和广义表数组的定义数组的特点数组的基本操作 存取：给定一组下标，读出对应的数组元素； 修改：给定一组下标，存储或修改与其相对应的数组元素。存取和修改操作本质上只对应一种操作寻址数组的存储结构与寻址一维数组设一维数组的下标的范围为闭区间l，h，每个数组元素占用 c 个存储单元，则其任一元素 ai 的存储地址可由下式确定： Loc(ai)Loc(al)(il)×c

8、 二Loc(aij)Loc(al1l2)(il1)×(h2l21)(jl2)×c维数组按行优先存储的寻址特殊矩阵和稀疏矩阵串和广义表的定义第 5 章 树和二叉树树的定义和基本术语1. 树的定义2. 树的基本术语结点的度、树的度 叶子结点、分支结点孩子结点、双亲结点、兄弟结点路径、路径长度祖先、子孙结点的层数、树的深度（高度）层序编号有序树、无序树森林 树的遍历操作1. 前序遍历2. 后序遍历3. 层序遍历 树的存储结构双亲表示法 孩子表示法 多重链表表示法 孩子链表表示法双亲孩子表示法孩子兄弟表示法 二叉树的定义二叉树具有五种基本形态： 空二叉树； 只有一个根结点； 根结点

9、只有左子树； 根结点只有右子树； 根结点既有左子树又有右子树。会画二叉树的五种基本形态：几种特殊的二叉树： 斜树 满二叉树 完全二叉树 二叉树的基本性质性质1 二叉树的第i层上最多有2i-1个结点（i1）。 性质2 在一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。性质3 在一棵二叉树中，如果叶子结点的个数为n0，度为2的结点个数为n2，则n0n21。 性质4 具有n个结点的完全二叉树的深度为。性质5 对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1in）的结点（简称为结点i），有： 如果i1，则结点i的双亲的编号为；否则结点i是根结点，无双亲；

10、 如果2in，则结点i的左孩子的编号为2i；否则结点i无左孩子； 如果2i1n，则结点i的右孩子的编号为2i1；否则结点i无右孩子。 不同组合根结点DD的左子树LD的右子树R前序LRD中序LDR后序LRD 二叉树的遍历操作二叉树的组成：1. 前序遍历2. 中序遍历3. 后序遍历4. 层序遍历任意一棵二叉树的遍历序列都是唯一的。由二叉树的前序遍历序列和中序遍历序列，唯一确定这棵二叉树；由二叉树的后序序列和中序序列也可唯一确定一棵二叉树，但是，如果只知道二叉树的前序序列和后序序列，则不能唯一地确定一棵二叉树。 二叉树的存储结构及实现1 顺序存储结构2 二叉链表·前序遍历的递归算法二叉树前

11、序遍历递归算法PreOrder前序遍历的非递归算法二叉树的前序遍历非递归算法PreOrder·中序遍历的递归算法： ·中序遍历的非递归算法： ·后序遍历的递归算法 二叉树的建立算法 线索链表为什么要建立线索链表？基本概念：线索：线索二叉树：线索链表：·线索链表的结点结构为：前序线索链表中序线索链表后序线索链表。1中序线索链表的建立算法2在中序线索链表上查找结点p的后继结点算法3在中序线索链表上查找结点p的前趋结点算法树、森林与二叉树的转换1树转换为二叉树将一棵树转换为二叉树的方法是：2森林转换为二叉树将一个森林转换为二叉树的方法是： 哈夫曼树及哈夫曼编码

12、1. 哈夫曼树叶子结点的权值二叉树的带权路径长度哈夫曼树哈夫曼算法的基本思想是：2. 哈夫曼编码·等长编码：·不等长编码：·前缀编码：第 6 章 图 图的定义和基本术语 在图中，常常将数据元素称为顶点，将顶点之间的关系用边来表示。1. 图的定义2. 图的基本术语简单图邻接、依附无向完全图、有向完全图稠密图、稀疏图顶点的度、入度、出度权、网路径、路径长度、回路简单路径、简单回路子图连通图、连通分量强连通图、强连通分量生成树、生成森林图的遍历操作1. 深度优先遍历 2. 广度优先遍历 图的存储结构及实现6.2.1 邻接矩阵1. 存储方法： 建立一个无向图的邻接矩阵存储的算法 2. 深度优先遍历5. 广度优先遍历 邻接表·存储方法：vertexfirstedge adjvex next顶点表结点 边表结点·结点结构： 建立一个有向图的邻接表存储的算法2. 深度优先遍历3. 广度优先遍历算法 图的连通性 生成树生成树可以在图的遍历过程中得到。 最小生成树1. MST性质2. Prim算法Prim算法的基本思想。 3. 克鲁斯卡尔（Kruskal）算法 Kruskal算法的基本思想： 最短路径1. 单