概述

树和图知识体系过于庞大，本文只总结严蔚敏《数据结构》包含内容

数据结构的存储方式

数据结构的基本存储方式只有两种：数组（顺序存储）和链表（链式存储）。

也可以理解为元存储结构，最小的存储结构只有数组和链表两种表示方法。

数据结构存储方式：顺序存储、链式存储、索引存储、散列存储

数据结构的基本操作

其本质是遍历+访问，具体表现就是增删查改。

数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。

算法与数据结构

算法

算法的基本要素

对数据对象的运算和操作：算术运算、逻辑运算、关系运算、数据传输
算法的控制结构
- 算法中各操作之间的执行顺序
- 描述算法的工具：传统流程图、N-S结构化流程图、自然描述语言、伪代码描述、程序
- 一个算法可以用顺序、选择（分支）、循环（重复）三种基本结构组合而成
算法的复杂度
- 时间复杂度：执行算法所需要的计算工作量（基本运算次数），与所用计算工具无关，与采用的算法描述语言无关，也不取决于算法环境
- 空间复杂度：执行算法所需要的内存空间（计算机所需存储空间）

设计算法时需要考虑算法的的时间和空间复杂度，但两者相互独立，毫无关联

算法分析方法：平均性态、最坏情况复杂性
算法分析目的：降低算法复杂度，提高算法的执行效率，以求改进
算法设计方法：列举法、归纳法、递推、递归、减半递推、回溯

算法的执行效率与数据的存储结构有关

算法强调动态的执行过程，不同于静态的计算公式

数据结构

数据

数据：需要处理的数据元素的集合

数据元素：数据的基本单位，即数据集合中的个体，也是结点

有时一个数据元素可由若干 数据项(Data Item) 组成，数据项是数据的 最小单位

结构：集合中各数据元素之间存在的某种前后件关系

数据结构：指带有结构的相互有关联的数据元素的集合

数据结构的分类

数据结构作为计算机的一门学科，主要研究三个方面：数据间固有逻辑结构关系、数据的存储结构关系、数据结构的运算

逻辑结构：反映数据元素之间的前后件逻辑关系的数据结构（与所使用的计算机无关）

线性结构（线性表、栈、队列）
非线性结构（树、图、二叉链表）

存储结构：即物理结构，数据的逻辑结构在计算机空间中的存放方式（不同的存储结构，数据处理的效率不同，与效率有关）

顺序结构：主要用于线性的数据结构
链式结构：每一个结点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系，优点是便于插入和删除操作
索引结构：带有目录与内容

数据结构的运算：插入、删除、查找、排序（增删改查）

线性表

基本概念

线性表强调元素在逻辑上紧密相邻。

两种储存方式，顺序表和链表。

顺序表

数组就是一种顺序表（静态存储）

优点

存储密度大（存满的情况下）
随机存取

缺点

插入删除需要移动大量元素
浪费存储空间（不满的情况下）
静态存储元素的个数不能自由扩充

顺序表的动态存储

实现原理

使用malloc分配内存空间
使用变量记录当前存储空间大小和当前存储量
如果插入一个元素时存储量超过当前存储空间大小，重新分配空间并将数据复制到新的空间，存储空间大小翻倍

struct sequent{
	int *data;
	int size;
	int length;
};

链表（linklist）

概念

数据域：存储节点数据。

指针域：储存直接后继节点的地址。

结点：用来存储数据元素的最小单位。

链表：

单链表：

双链表：

循环链表：

头指针：存储指向链表第一个节点地址的指针。

首元结点：链表中存储第一个数据元素的结点。

头结点：首元结点之前的一个结点，方便链表操作。

常见问题

如何表示空表？

没有头结点时，头指针为空表示空表

有头结点时，当头结点的指针域为空时表示空表

链表中设置头结点有什么好处？

1.便于首元结点的处理首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;
⒉便于空表和非空表的统一处理

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻

优点

数据元素的个数可以自由扩充
插入删除等操作不必移动数据，只需要修改相应节点的指针域，修改效率高

缺点

存储密度小（因为需要额外存储指针域）
存取效率不高，必须采用顺序存续（每次存续需要从头开始遍历至指定位置）

前插法&尾插法

前插法（先入后出，先插入的在后面）

尾插法（需要借助尾指针）

双向链表

指针域存储两个指针，分别指向前驱和后继。

双链表的插入和删除

分别需要修改前驱和后继的指针域

*静态链表

顺序表和链表的比较

	顺序表	链表
存储空间	预先分配，会导致空间限制或溢出	动态分配，不会出现存储空间限制或者溢出
存储密度	不用额外存储空间表示数据元素间的逻辑关系，存储密度等于1	需要借助指针来体现元素间的逻辑关系，存储密度小于1
存取元素	随机存取，按位置访问元素的时间复杂度为O(1)	顺序存取，按位置访问元素的时间复杂度为O(n)
插入删除	需要移动大量元素，时间复杂度为O(n)	不需要移动元素，确定删除位置后，时间复杂度为O(1)

顺序表适用情况：

表长变化不大，能事先确定变化范围（确定表大小）
很少进行插入删除操作，经常按元素位置需要访问数据元素

链表适用情况：

长度变化较大（不能事先确定大小）
频繁进行插入删除操作

*二路归并（合并两个有序表）

栈与队列

限制操作的线性表

栈

基本概念

后进先出 的线性表

限定仅在表尾进行插入删除操作的线性表，因此，对栈来说，表尾端有特殊含义，称为栈顶，表头端称为栈底。不含元素的空表称为空栈。

定义：只能在表的一端（栈顶）进行插入和删除运算的线性表

栈顶：

栈底：

顺序栈和链栈

struct sqstack{
  int *base;
  int *top;
  int stacksize;
}

为什么结构体没有包含一个顺序表用来存储数据元素？

初始化顺序栈之后，malloc向内存申请一段连续的空间，地址赋给base，使用top操作内存中的数据。

在链栈中，base和top分别指向第一个结点和尾结点，不需要保存栈大小

队列

先进先出的线性表

队头：删除元素的一端

队尾：插入数据的一端

双端队列

链队列

struct node{
	int data;
	node *next;
}
struct queen{
	struct node *front;
	struct node *rear;
}

循环队列

将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用

struct sqquene{
  int *data;
  int front;
  int rear;
}

使用数组来存储一个队列，对下标求余运算使数组头尾相连

串

定义：由零个或多个字符组成的有序序列

长度：串中字符的数目n称为串的长度

空串：零个字符的串称为空串

子串：串中任意连续的字符组成的子序列称为该串的子串

主串：包含子串的串相应的称为主串

位置：字符在序列中的符号为该字符在串中的位置

相等：只有当两个字符串的长度相等，且各个对应位置上的字符都相等时才相等

空格串：由一个或多个空格组成的串称为 空格串

串的堆分配存储

struct HString{
  char *ch;
  int length;
}

以一组地址连续的存储单元存放串值的字符序列

串的块链存储结构

struct Chunk{
  char ch[size];
  struct Chunk *next;
}

串的模式匹配算法&KMP

数组和广义表

树

树和子树：指n(n＞0)个元素的有限集合，它有且仅有一个称为根的元素，其余元素是互不相交的子树

结点：

结点的度：结点拥有的子树数称为 结点的度

叶子（终端结点）：度为0的结点称为 叶子或终端结点

分支结点（非终端结点）：度不为0的结点称为 分支结点或非终端结点

树的度：是树内各结点度的最大值。

孩子双亲：结点的子树称为孩子，相应的该结点称为孩子的双亲

兄弟：同一双亲的孩子互称兄弟

祖先：从根结点到该结点所经过的分支上所有的结点

子孙：以某节点为根的子树中的任一结点都称为该结点的子孙

层次：

堂兄弟：

深度：树中结点的最大层次称为树的深度

有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换）则称为 有序树，否则为 无序树

森林：m棵互不相交的树的集合。

二叉树

特点每个结点至多只有两棵子树，二叉树的子树有左右之分，其次序不能任意颠倒。

特殊二叉树

满二叉树
完全二叉树

二叉树的性质：

在二叉树的第k层上，最多有2^(k-1)个结点（指定第几层求结点）
深度为m的二叉树最多有2^(m)-1个结点（指定层数求结点）
度为0的结点称为叶子结点，度=0的结点总比度=2的结点多1个
有n个结点的二叉树深度至少为[log(2)n]+1（指定结点求深度）
性质5 P124

二叉树的存储结构

顺序存储结构（数组存储）
链式存储结构（链表存储）

遍历二叉树

二叉树的遍历：按照一定的顺序不重复不遗漏地访问二叉树中的结点

深度优先遍历（递归遍历）
- 前序遍历
- 中序遍历
- 后序遍历
广度优先遍历（迭代遍历）
- 层序遍历

其本质是对非线性结构线性化操作

*线索二叉树

为什么要建立线索？解决什么问题？

树和森林

*树的存储结构

双亲表示法
孩子表示法

*森林与二叉树的转换

*树和森林的遍历

哈夫曼树

最优二叉树

哈夫曼编码

图

顶点

边

弧

弧头

弧尾

有向图

无向图

完全图

图的存储

邻接矩阵
邻接表
十字链表
邻接多重表

图的遍历

广度优先遍历