第五章树与二叉树

Posted on 2024-03-14 Edited on 2024-03-15 In 数据结构

树的基本概念

数的定义和基本术语

树：从树根生发，逐级分支。
空树：结点数为0的树。
非空树的特性：
- 有且仅有一个根结点。
- 没有后继的结点称为“叶子结点”（或终端结点）。
- 有后继的结点称为“分支结点”（或非终端结点）。
- 除了根结点外，任何一个结点都有且仅有一个前驱。
- 每个结点可以有一个或多个后驱。
树是 n （n >= 0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：
1. 有且仅有一个特定的称为根的结点。
2. 当 n > 1 时，其余结点可分为 m (m > 0)个互不相交的有限集合 T₁,T₂,…T_m，其中每个集合本身又是一颗树，并且称为根结点的子树。
树是递归定义的数据结构。
结点之间的关系描述：
- 祖先结点
- 子孙结点
- 双亲结点（父结点）
- 孩子结点
- 兄弟结点
- 堂兄弟结点
- 两个结点之间的路径：只能从上往下
- 路径长度：经过几条边
结点和树的属性描述：
- 结点的层次（深度）——从上往下数
- 结点的高度——从下往上数
- 树的高度（深度）——总共多少层
- 结点的度——有几个孩子（分支）
- 树的度——各结点的度的最大值
有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
有序树：逻辑上看，树中结点的各子树从左至右是无次序的，不能互换。
森林：森林是 m(M >= 0)棵互不相交的树的集合。

第四章串

Posted on 2024-03-12 Edited on 2024-03-13 In 数据结构

定义和基本操作

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = ‘a₁a₂……a_n‘（n >= 0)。其中，S 是串名，单引号（有的地方用双引号）括起来的字符序列是串的值；a_i可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n = 0时的串称为空串（用∅表示）
子串：串中任意个连续的字符组成的子序列。
主串：包含子串的串。
字符在主串中的位置：字符在串中的序号。
子串在主串中的位置：子串的第一个字符在主串中的位置。
空串和空格串：
- M = ‘’（空串）
- N = ‘ ‘（三个空格符号组成的空格串，每个空格字符占1B）
串是一种特殊的线性表，数据元素之间呈线性关系。
串的数据对象限定为字符集（如中文字符、英文字符、数字字符和标点符号等）。
串的基本操作，如增删改查等通常以子串为操作对象。
基本操作：
- ：赋值操作。把串T赋值为 chars。
- ：复制操作。由串 S 复制得到串 T。
- ：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
- ：求串长。返回串 S 的元素个数。
- ：清空操作。将 S 清为空串。
- ：销毁串。将串 S 销毁（回收存储空间）。
- ：串联接。用 T 返回由 S1 和 S2联接而成的新串。
- ：：求子串。用 sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
- ：定位操作。若主串中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0。
- ：比较操作。若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。
字符集：
- 英文字符——ASCII字符集
- 中英文——Unicode字符集
- 基于同一个字符集，可以有多种编码方案。

存储结构

第三章栈和队列

Posted on 2024-03-11 Edited on 2024-03-13 In 数据结构

栈的基本概念

栈（Stack）：一种操作受限的线性表，只允许在一端进行插入和删除操作的线性表。
- 特点：后进先出（Last In First Out，LIFO）
- 逻辑结构：与普通线性表相同
- 数据的运算：插入、删除操作有区别
重要术语：
- 空栈：栈里面没有任何数据元素
- 栈顶：允许插入和删除的一端
- 栈底：不允许插入和删除的一端
基本操作：
- ：初始化栈。构造一个空栈 S，分配内存空间。
- ：销毁栈。销毁并释放栈 S 所占用的内存空间。
- ：进栈，若栈 S 未满，则将 x 加入使其成为新栈顶。
- ：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
- ：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
- ：判断一个栈 S 是否为空。若 S 为空，返回 ture，否则返回 false。
n 个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}C^n_{2n}$，上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。