数据结构笔记

基本概念

数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作等的学科。

数据（Data）是指所有能输入到计算机中并被计算机程序处理的符号的总称。（整数、实数、图像、声音）

数据元素（Data Element）是数据的基本单位。在计算机程序中通常作为一个整体进行考虑和处理。

数据项（Data item）是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。

数据对象（Data object）是性质（类型）相同的数据元素的集合，是数据的一个子集。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的形式定义为：数据结构是一个二元组

Data_Structure=(D,S)

D:元素的有限集 S:D上关系的有限集

逻辑结构 vs 存储结构

数据元素之间的相互关系称为逻辑结构。

数据结构在计算机中的表示称为数据的物理结构，又称存储结构。

两种不同的存储结构

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。

由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储结构是把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。

链式存储结构对逻辑上相邻的数据元素不要求其物理位置相邻，由此得到的存储表示称为链式存储结构。

数据元素间的逻辑关系通过附设的指针来表示。

数据结构的三要素

一般包括以下三方面的内容：

1. 数据元素之间的逻辑关系，称为数据的逻辑结构；
2. 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构，又称物理结构；即数据结构在计算机中的表示（又称映像）；
3. 数据的运算，即对数据施加的操作。最常用的运算包括：插入、删除、修改、查找、排序。

数据类型

数据类型（Data Type）是指一个值的集合和定义在此值集合上的一组操作的总称。

分为原子类型（整型、字符型）和结构类型（数组）。

抽象数据类型（Abstract Data Type）是指一个数学模型以及定义在该模型上的一组操作的总称。

由用户定义，可以表示应用问题的数学模型。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示无关。

抽象数据类型和数据类型实质上是一个概念。

算法

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：

1. 有穷性。一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性。算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入只能得出相同的输出。
3. 可行性。一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算有限次执行来实现的。
4. 输入。一个算法具有零个或多个输入，这些输入取自某个特定的数据对象集合。
5. 输出。一个算法具有一个或多个输出，这些输出是同输入有着某些特定关系的量。

设计一个“好”的算法应考虑以下几个方面:

1. 正确性：算法的执行结果应当满足预先规定的功能和性能要求。
2. 可读性：算法主要是为了人的阅读与交流，其次才是机器执行。一个算法应当思路清晰、层次分明、简单明了、易读易懂。
3. 健壮性：当输入不合法数据时，应能作适当处理，而不会产生一些莫名其妙的输出结果。
4. 高效率和低存储量：有效使用存储空间和有较高的时间效率。效率指的是算法执行时间。存储量指的是算法执行过程中所需要的最大存储空间。

时间复杂度

算法中的基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：

**T(n)=O(f(n)) ** 称T(n)为算法的(渐近)时间复杂度,简称时间复杂度。

其中, n是问题规模；f(n)指基本操作重复执行次数，是n的函数。○代表T(n)与f(n)是同一数量级，即随着n的增大，算法执行时间的增长率与f(n)的增长率相同。

算法的时间复杂度是由嵌套最深层语句的频度决定的。

一条语句的重复执行次数称作语句频度。

空间复杂度

算法空间复杂度作为算法所需存储空间的度量，记为:

S(n)=O(f(n)) 其中n为问题的规模（或大小）。

一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量。

程序运行所需的存储空间包括以下两部分：

1. 固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。
2. 可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。

线性表

线性表是一个由n(n≥0)个具有相同特性的数据元素a1，a2， …an组成的有限序列。

用一段地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。用这种方法存储的线性表简称顺序表。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（可以是连续的，也可以是不连续的）。

借助指针来指示数据元素之间一对一的线性关系。

为操作方便，通常在链表的第一个结点之前附设一个结点，称为头结点。头指针指向单链表中头结点，可唯一确定一个单链表。

循环链表：是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈（后进先出）和队列（先进先出）的基本操作（基本运算）是线性表操作的子集，它们是操作受限的线性表。

树

树是n(n≥0)个结点的有限集(可以是空集)。在任意一棵非空树中：

1. 有且仅有一个特定的称为根的结点；
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限子集T1,T2,…,Tm，其中每一个子集本身又是一棵树，并且称为根的子树。

• 树的结点：包含一个数据元素及若干指向其子树的分支；
• 结点的度：结点拥有子树数；
• 叶子结点：度为0的结点称为叶子结点或终端结点；
• 分支结点：度不为0的结点称为分支结点或非终端结点；
• 树的度： 树内各结点的度的最大值；
• 孩子结点：结点的子树的根称为该结点的孩子；
• 双亲结点 (父结点)：B 是A的孩子，则A是B的双亲（父结点）；
• 兄弟结点：同一双亲的孩子结点互称兄弟；
• 祖先结点: 从根到该结点所经分支上的所有结点；
• 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
• 结点的层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层，…
• 堂兄弟结点：其双亲结点在同一层上的结点互为堂兄弟；
• 树的深度：树中结点的最大层次称为树的深度或高度；
• 有序树：无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树；

森林：森林是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。它的特点是每个结点至多只有两颗子树，并且，二叉树的子树有左右之分。

满二叉树: 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时,称这样的二叉树为完全二叉树.

遍历二叉树(Traverse)是指按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。

结点的权：根据应用的需要可以给树的结点赋权值。

结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度。

树的带权路径长度 WPL：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。

最优二叉树(Huffman树):带权路径长度最小的二叉树叫最优二叉树。

图

图是顶点集V和边集E组成的二元组G=（V,E）,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则称为有向图。

重点算法

线性表

1. 合并线性表 o(ListLength(LA)*ListLength(LB))
2. 非递减合并线性表 o(ListLength(LA)+ListLength(LB))
3. 插入与删除 o(n)

单链表

1. 带头结点单链表上的查找运算 o(n)
2. 带头结点单链表上的插入删除运算 o(n)
3. 头插法创建单链表 o(n)
4. 非递减合并单链表 o(n)
5. 头插法就地逆置 o(n)
6. 双向链表插入删除 o(n)
7. 一元多项式相加

栈

1. 顺序栈，链栈
2. 建立栈
3. 取栈顶元素
4. 出入栈
5. 数制转换
6. 括号匹配
7. 简单行编辑
8. 迷宫
9. 表达式求值

队列

1. 链队列
2. 循环队列 MAXQSIZE

树

1. 树的基本概念
2. 满二叉树，完全二叉树
3. 先序遍历，中序遍历，后序遍历
4. 线索化二叉树
5. 树与二叉树，森林与二叉树的转化
6. 哈夫曼树与赫夫曼编码

图

1. 图与网的基本概念
2. 图的存储结构（邻接矩阵，邻接表，逆邻接表，十字链表法，邻接多重表）
3. 图的深度优先搜索，广度优先搜索
4. 最小生成树（普里姆算法o(n²)，克鲁斯卡尔算法o(nlogn)）
5. 拓扑排序
6. 关键路径
7. 最短路径（迪杰斯特拉算法 o(n²) 弗洛伊德算法 o(n³)）

查找

1. 顺序查找 o(n) 平均查找长度 (n+1)/2
2. 折半查找及判定树平均查找及失败长度：利用判定树计算
3. 索引分块查找
4. 二叉排序树的查找插入删除 平均查找长度同判定树
5. 平衡二叉树及平衡处理

LL：右旋 RR：左旋 LR：先左后右 RL：先右后左

1. B+,B-树
2. 哈希表

哈希函数的构造

1. 直接定址法（线性函数）
2. 数字分析法（频率大，变化多）
3. 平方取中法（平方后的中间几位）
4. 折叠法（移位叠加、间界叠加）
5. 除留余数法(取模运算)
6. 随机数法

###解决冲突的方法

1. 开放定址法
   1. 线性探测再散列法
   2. 二次探测再散列法
   3. 随机探测再散列法

2. 链地址法

   平均查找长度按照比较次数计算

排序

排序方法	平均时间	最坏情况	最好情况	空间复杂度	稳定性	复杂性
直接插入排序	O(n2)	O(n2)	O(n)	O(1)	稳定	简单
希尔排序	O(n1.3)	难分析	难分析	O(1)	不稳定	较复杂
冒泡排序	O(n2)	O(n2)	O(n)	O(1)	稳定	简单
快速排序	O(nlog2n)	O(n2)	O(nlog2n)	O(log2n)	不稳定	较复杂
简单选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定	简单
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不稳定	较复杂
二路归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	稳定	较复杂
基数排序	O(d(n+rd))	O(d(n+rd))	O(d(n+rd))	O(rd)	稳定	较复杂