数据结构

calendar 2023-05-06 · 2 min read · 算法

文章目录

1. 数据结构

1.1 基本概念

  • 数据：所有能输入到计算机中，且能被计算机处理的符号集合
  • 数据元素：数据中的一个个体，数据元素可以使用数据项描述
  • 数据对象：具有相同性质的若干数据元素，数据元素需要具有相同的结构
  • 数据结构：数据对象内部，数据元素间的逻辑结构。数据结构可以使用一个二元组\(B=(D,R)\)表示，其中D是数据元素集合，R是关系的集合(有的结构需要多个关系表示，所以应该是关系的集合)。
  • 数据类型：是一个值的集合和定义在此集合上的一组操作的总称。数据类型就是已经实现的数据结构。
  • 抽象数据类型：不考虑计算机实现, 从求解问题的数学模型中抽象出来的数据逻辑结构和运算。实际上是对一个求解问题的形式化描述，可以在理解的基础上实现它。

1.2 数据结构的实现方式

  数据结构只是一组数据在逻辑上的组织关系，可以通过任意一门编程语言实现。数据结构的物理实现方式主要有顺序存储、链式存储、哈希和索引，选择实现语言时需要了解目标语言的特性。需要注意的是不同的物理实现方式所应用的场景不一样，各有各的优缺点。

  • 顺序: 几乎所有语言都有提供数组这个基本数据类型, 元素在内存中都是顺序存储的
  • 链式: C++中使用的是指针, Java中使用的是引用
  • 哈希: ...
  • 索引: ...

2 集合

  元素间无关系，每个元素除了属于同一个集合外别无其他逻辑关系，是最松散的，不受制约的关系。

1ADT Set {  
2Data:
3	{a1, a2, …,an-1, an}  
4Operation:
5	traversing(); //遍历每个元素
6	deleting();   //指定元素删除
7	inserting();  //指定元素插入
8	search();     //指定元素搜索
9}

3 线性表

  线性表是具有相同特性元素的有限序列，常见的变种有栈、队列、串、向量、数组（矩阵）。线性表的逻辑关系是除了头尾元素外，每个元素都有且仅有一个前去和后继。

 1ADT Array {  
 2Data:
 3	<a0, a1, a2, …,an-1, an>  
 4Operation:
 5	traversing(); //遍历每个元素
 6	inserting();  //指定位置插入元素
 7	deleting();   //指定位置删除元素
 8	update();     //指定位置更新元素
 9	search();     //指定位置获取元素
10}

  线性表物理实现方式

  • 顺序实现: 基于数组实现。
  • 链式实现: 链式实现需要在节点上记录下一节点的信息，实现迭代遍历。

3.1 栈

  栈的思想是后进先出, 后进的元素拥有更高的优先级进行处理. 例如: 运算符优先级处理、数组逆序(不推荐). 第一个出栈元素意味着这个元素前面的元素都在压栈中

1ADT Stack {
2Data:
3	<a0, a1, a2, …,an-1, an>
4Operation:
5	push();
6	pop();
7	top();
8}

  栈物理实现方式

  • 顺序实现: 基于数组实现, 定义栈顶指针和栈元素个数变量，通过这两个变量的状态判断栈空、栈满以及栈总元素。栈顶指针可以指向栈定元素，也可以指向栈顶元素下一个元素。
  • 链式实现: 基于链表, 在头部添加和删除元素。定义栈顶指针和链表头指针, 通过链表头指针判断栈空

3.2 队列

  思想是先进先出, 先进的元素拥有更高的优先级进行处理. 扩展：双端队列是允许两端插入，删除只能在一端的队列

1ADT Queue{
2Data:
3	<a0, a1, a2, …,an-1, an>
4Operation:
5	push();
6	pop();
7	front();
8	back();
9}

  队列物理实现方式

  • 顺序实现:
    • 实现1: 队头指针和队尾指针初始化为0, 队尾指针永远指向队尾元素的后一坐标，队头指针永远指向队头元素。
    • 实现2: 队头指针和队尾指针初始化为0, 队头指针永远指向队头元素的前一坐标，队尾指针永远指向队尾元素。队列元素个数可以通过(队尾指针-队头指针+队列最大长度)%队列最大长度。
  • 链式实现
    • 插入一般在尾部，删除一般在头部，需要建立一个尾指针
  • 堆实现: 基于堆

3.3 字符串

  由零个或多个字符组成的有限序列

 1ADT Queue{
 2Data:
 3	<a0, a1, a2, …,an-1, an>
 4Operation:
 5	assign()
 6	delete()
 7	replace()
 8	equal()
 9	concat()
10	substr()
11}

  字符串的相关概念:

  • 字符串的长度：串中所含的字符个数称为串的长度
  • 空字符串：含零个字符的串称为空串
  • 字符串相等：长度相等且对应位置的字符都相同
  • 子字符串：一个串中任意连续字符组成的子序列，真子串是不包含原序列的子串

  串物理实现方式

  • 顺序实现: 字符串一般使用数组实现。

3.4 向量

1ADT Vector{
2Data:
3	<a0, a1, a2, …,an-1, an>
4Operation:
5	              
6}

4 树

  树的表示法, 树形表示法、文氏图法、凹入表示法、括号表示法(广义表)

 1ADT Tree{
 2Data:
 3	{<a0, a1>, <a0, a2>,... }
 4	一个根节点和若干子树构成. 
 5Operatiofn:
 6	init();		//遍历
 7	addChild();	//添加结点
 8	delChile();	//删除结点
 9	getRoot();	//获取根结点
10	getChild();	//获取结点的子结点
11	getDepth();	//获取树的深度
12	foreach();	//遍历树
13	isEmpty();	//判断树是否为空
14	clear();	//清空树
15}
  • 树的基本概念
    • 节点的度与树的度：一个节点的子树个数称为节点的度；所有节点中度的最大值称为树的度。通常将度为m的树称为m叉树
    • 分支节点与叶子节点：度为0的节点称为分支节点、度不为0的节点称为分支节点。
    • 路径与路径长度：两个节点间的节点序列<x,x,x,x>称为两个节点的路径，节点序列的节点个数减一称为路径长度
    • 节点的层次：第一层的层次为1, 往以此类推
    • 树的深度(高度): 所有结点的最大层次称为树的高度
    • 森林：n个互不相交的数称为一个森
    • 树的性质
      • \(节点个数=1+\sum{单个节点的度}\)
      • 具有n个节点的m叉树最小高度为\(\log_m{n(m-1)+1}\)，最大高度为\(n-(m-1)\)
      • 高度为h的m叉数至多有\(\frac{m^{h}-1}{m-1}\)个节点, 第i层至多有\(m^{i-1}\)个节点
    • 树的存储结构：
      • 双亲表示法：
      • 孩子表示法：
      • 左孩右兄表达法：
  • 二叉树：
    • 与二次树的区别：二次数最少3个节点，二叉树最少0个节点
    • m叉树转换为二叉树: 通过左孩右兄法将m叉树转换为二叉树, 复原时只需要复原结点的兄弟关系即可.
    • 森林转换为二叉树: m叉树先转换为二叉树. 有两种方法连接树的根结点, 一种是直接生成一个新的根结点进行链接, 另一种是第一颗树做根结点其余树作为根结点的兄弟, 采用左孩右兄法连接.
    • 性质：
      • \(n_{0} = n_{2}+1\)
      • 含n个结点的二叉树可以通过先序(后序)遍历和中序遍历唯一确定. 先序(后序)遍历可以确定根, 从而区分中序遍历的子树遍历
  • 满二叉树：除了叶子结点所有节点的度为2的树
    • 满二叉树的节点个数为\(2^{h}-1\)
  • 完全二叉树：高度为h的树, 前n-1层为满二叉树, 最后一层所有结点靠左的树称为完全二叉树
    • \(\begin{cases}n_{1}=0 & n为奇数 \n_{1}=1 & n为偶数 \end{cases}\)当n确定时, 完全二叉树的\(n{0}\)、\(n{1}\)和\(n{2}\)确定, 树形确定
    • \(h=\log_2{n+1}\)
    • 结点层序编号, 编号从0开始(从1开始), 若节点编号为\(i\)，则双亲节点的编号为\(\frac{i-1}{2}\)(从1开始\(\frac{i}{2}\)),左孩子的编号为\(2i+1\)(从1开始\(2i\))，右孩子的编号为\(2i+2\)(从1开始\(2i+1\))
  • 二叉排序(搜索)树
    • n个关键字构成的二叉排序树有\(\frac{1}{n+1}C_{2n}^{n}\)
    • 二叉排序树插入操作一定在叶子结点
    • 二叉排序树若删除的是叶子结点则可以直接删除; 若删除的是仅有左子- 树或右子树的的结点, 其父结点直接指向被删除结点的子树; 若删除的是包含左子树和右子树的结点, 使用中序前驱或中序后继覆盖结点, 然后删除中序前驱或中序后继, 被删除结点仍然是双子树结点, 重复操作.
    • 构造n个元素的二叉搜索树:
      • 最好情况是平衡二叉树, 底层的n/2节点的深度是lgnewr, 那么就需要花费nlg n
      • 最差情况是一个链表, 插入时间是一个等差数列, 要花费n^2时间
    • 本质: 二叉搜索树的构造过程其实和快速排序的思想是一致的, 随机二叉搜索数只需随机选择一个根节点即可(对数组中的元素随机化排列). 构造的二叉搜索数通过中序遍历即可获取排序结果.
    • 二叉搜索树的运行时间等于各个节点深度的和, 对该等式求期望可以推出节点的期望深度是 lgn, 但不能确定树的深度就是lgn, 定理证明了随机化的二叉搜索树是它的深度一定是 lgn. 随机化二叉搜索树的节点深度大部分都是lgn, 意味着它的查询时间就是lgn
  • 平衡二叉树: 平衡因子即左右子树高度差的绝对值, 所有左右子树的平衡因子小于或的等于1的树称为平衡二叉树
    • 平衡二叉树的插入调整:
      • LL和RR型: 根结点的左(右)结点上升为根的父节点, 其左(右)子树作为新根的左(右)子树, 右(左)子树子作为旧根右(左)子树
      • LR和RL型: 根结点的左(右)结点的右(左)结点上升为根结点的父节点, 原根结点的左(右)结点作为新根结点的左子树

4.2 红黑树

4.3 堆

  非叶子结点的值都小于或大于其子结点的值的完全二叉树称为堆. 由于完全二叉树的编号特点, 一般采用顺序存储结构存储.

1ADT Tree{
2Data:
3	{<a0, a1>, }
4	一个根节点和若干子树构成. 
5Operatiofn:
6	push()
7	pop()
8	heapful()
9}
  • 堆的根结点大于或等于(小于或等于)其子树称为大根堆(小根堆)
  • 堆是完全二叉树的一种变形，采用顺序存储结构存储
  • 完全二叉树的非叶子结点的下标在c语言中可以通过size/2-1得到（根结点从0开始）

4.4 Hufman树

二叉树叶子结点的路径长度与结点权值的乘积之和称为二叉树的带权路径长度WPL, 最小带权路径长度的二叉树称为Huffman树

  • 特点:
    • 权值越大的叶子结点越靠近根结点
    • 权值越小的叶子结点越远离根结点
    • 无度为1的结点(配合二叉树的性质可求n0和n2的值)

5 图

图中元素的对应关系是多对多. 所有元素都可能有多个前驱和多个后继元素。

  • 度之和的一半等于边数, 有向图中入度和出度之和作为结点的度.
  • 子图了: 一个图的结点集和边集都是另一个图的子集则这个图为那个图的子图
  • 完全图: 完全图代表图中边最多的情况
    • 完全无向图: 任意顶点间存在一条边
      • 包含\(\frac{n(n-1)}{2}\)条边
    • 完全有向图: 任意顶点间存在方向相反的两条边
      • 包含\(n(n-1)\)条边
  • 路径
    • 路径长度
    • 简单路径: 除开始和结束结点外, 其余结点均不相同
    • 简单回路: 开始结点和结束结点相同的简单路径
  • 连通图:
    • 无向连通图: 图中任意结点间存在路径
    • 有向连通图:
  • 联通分量: 无向图中极大连通子图成为连通分量,. 无向连通图的极大联通子图即本身, 无向非连通图总能找到汗若个连通分量的子图.
  • 强联通分量: 有向图中极大连通子图称为强连通分量
  • 带权图(网): 边上带有权的图
  • 存储结构
    • 邻接矩阵: 矩阵横纵坐标枚举结点, 矩阵中是否有1判断结点是否有边
    • 邻接表: 向量枚举结点, 结点通过拉链法存储其边