线索二叉树
定义
二叉树虽然是非线性结构,但二叉树的遍历却为二叉树的结点集导出了一个线性序列因而，二叉树的结点存在关于这个线性序列的前驱和后继。对应于前序、中序、后序遍历,除了相应序列的第一个和最后一个，二又树的每个结点都存在前序前驱/后继、中序前驱/后继、后序前驱/后继。
……继续阅读 »
yanzexi
1年前 (2023-10-15) 241浏览 0评论
1个赞
二叉树遍历的非递归实现
先序遍历
stack<TreeNode*> S;
void per(TreeNode* root){
TreeNode* now = root;
while(true){
while(now){
cout << now -> val << '\t';
……继续阅读 »
yanzexi
1年前 (2023-10-14) 247浏览 0评论
1个赞
树
引入
树中的元素之间并不像顺序表和链表一样，存在天然的直接后继或直接前驱关系。不过只要附加某种约束（比如遍历），也可以在树中的元素之间确定某种线性次序，因此树属于半线性结构（semi-linear structure）。以下是一些易混淆的概念：
分支结点：除叶结点外的其……继续阅读 »
yanzexi
1年前 (2023-10-13) 250浏览 0评论
1个赞
$KMP$算法
$next$数组
$next$数组的实质是一个前缀表，其作用是用来回退，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。具体来说前缀表记录下标$i$之前（包括$i$）的字符串中，有多大长度的相同前缀后缀，即最长公共前后缀。
文章中字……继续阅读 »
yanzexi
1年前 (2023-10-12) 216浏览 0评论
1个赞
表达式计算
后缀表达式计算
int op(int a, int b, char Op){
if(Op == '+'){
return a + b;
}
if(Op == '-'){
return a - b;
}
if(Op == '*'){
return a + b;
}
if(Op =……继续阅读 »
yanzexi
1年前 (2023-10-11) 243浏览 0评论
1个赞
$PS：$邓书里的向量实际上就是顺序表、而列表则相当于链表。接下来以殷书为主，王道和邓书作为补充。一些太简单的就懒得记录了。
顺序表
顺序表
顺序表逻辑结构为线性，存储结构为顺序存储；性能分析如下：
$$
\begin{cases}
\frac{n+1}{2}&……继续阅读 »
yanzexi
1年前 (2023-10-09) 244浏览 0评论
1个赞
向量的空间管理
静态空间管理的弊端
内部数组所占物理空间的容量，若在向量的生命期内不允许调整，则称作静态空间管理策略。该策略的空间效率难以保证。一方面，容量固定可能在此后的某一时刻，无法加入更多的新元素，即上溢$(overflow)$。另一方面如果为降低风险而预留部分空间，也很难明确界定一个合理的预留量。
&……继续阅读 »
yanzexi
1年前 (2023-10-04) 245浏览 0评论
1个赞
最为基本的线性结构统称为序列$（sequence）$，根据其中数据项的逻辑次序与其物理存储地址的对应关系不同，又可进一步地将序列区分为向量$（vector）$和列表$（list）$。在向量中，所有数据项的物理存放位置与其逻辑次序完全吻合，此时的逻辑次序也称作秩$（rank）$；而在列表中，逻辑上相邻的数据项在物理上未必相邻，而是采用间接定址的方式……继续阅读 »
yanzexi
1年前 (2023-10-03) 242浏览 0评论
2个赞
算法
算法：是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列，一般情况下应当具备以下要素：
输入与输出 I/O
输入：待计算问题的任一实例，都需要以某种方式交给对应的算法，对所求解问题特定实例的这种描述统称为输入。
输出：经计算和处理之后得到的信息，即针对输入问题实例的答案，称作输出。
基本操作、确定性和可行性
确定性和可行性是指算法可描述为由若干语义明确的基本操作组成的指令序列，且每一基本……继续阅读 »
yanzexi
2年前 (2023-08-28) 304浏览 0评论
2个赞
