前、后缀表达式重建表达式树的实现
前言前、后缀表达式的基本含义可见本人的文章：传送门，本处不再赘述，表达式树在文中也有图示。针对只含有二元运算符的表达式树，树中所有的叶节点均为操作数，非叶节点均为操作符。前后缀表达式可以通过不同的遍历策略遍历表达式树得到，而通过前后缀表达式也可以重建得到表达式树，重建过程和二叉树的序列化与反序列化非
...
稀疏矩阵压缩存储之十字链表
发表于
|
分类于
数据结构
基础知识在使用三元组顺序表实现矩阵压缩存储时，三元组存放在连续的内存区域中，在进行矩阵运算时非零的元素可能变成零元素，非零元素会出现新值，此时需要移动数组中的三元组，对空间消耗是巨大的（本人三元组顺序表实现中直接开辟了一个新的数组），如果结合链表的优点，那么可以使用称为十字链表的数据结构，本文将实现
...
稀疏矩阵压缩存储之三元组
发表于
|
分类于
数据结构
基础知识在定义稀疏矩阵时，可以引入一个称为稀疏因子的数，其定义如下：假设对于一个 $m*n$ 矩阵，其中有 $t$ 个元素不为 $0$， 则定义稀疏因子 $δ=t/(m*n)$，一般认为 $δ<=0.05$ 的矩阵为稀疏矩阵。稀疏矩阵如果采用二维数组直接存储将会导致大量的空间存储 $0$ 值，
...
字符串模式匹配及KMP算法分析与实现
发表于
|
分类于
算法设计
字符串基础知识根据相关资料，字符串定义如下：字符串是由零个或者多个字符组成的有限序列，其中零个字符的串称为空串。字符串的主要存储方式有定长顺序存储（对应于C/C++中栈空间）、堆分配存储（动态申请内存）以及块链存储（链表节点为一个定长小块，多个小块依次组成一个实际串）。
字符串模式匹配是指给定两个串
...
前、后缀表达式转中缀表达式的实现
发表于
|
分类于
算法设计
前言前中后缀表达式的基本介绍可见文章：前中转后缀，本文不再赘述。
本文将实现将前缀、后缀表达式转变为中缀表达式。约定放置表达式的基本数据结构依然如下所示：
123456789101112131415161718enum OperType{ /*OPERAND-操作数，OPER
...
中、后缀转前缀表达式以及前缀表达式求值的实现
发表于
|
分类于
算法设计
前言前中后缀表达式的基本介绍可见上篇文章：前中转后缀，本文不再赘述。
本文将实现将中缀、后缀表达式转变为前缀表达式并且实现一个简单的前缀表达式计算器。同时本文依旧约定表达式的基本数据结构如下：
12345678910111213141516171819enum OperType{
...
前、中缀表达式转后缀表达式以及后缀表达式求值的实现
发表于
|
分类于
算法设计
前言前缀表达式又称波兰表达式，其将操作符放置于操作数前面，该类型的表达式无需括号仍然可以无歧义地被解析，如果将表达式以表达式树的形式展现，则前缀表达式对应于前序遍历结果。
中缀表达式在表达式中将操作符（双目）置于操作数的中间，是目前常用的一种表示方法，中缀表达式需要通过括号来指示运算优先顺序，一般中
...
数据结构之单向链表-游标实现
发表于
|
分类于
数据结构
基础知识单向链表的游标实现和指针实现最大的不同是游标实现无法采用指针的方式连接到下一个节点，其只能通过数组下标的方式进行下一节点的索引，因此游标实现相比指针实现需要手动管理数组内存使用情况，本文直接采用《数据结构与算法分析：C语言描述》中的思路，不过本文使用了一个哑节点，代码中约定数组第0号节点用来
...
数据结构之多重表的定义与实现
发表于
|
分类于
数据结构
多重表基础多重表是《数据结构与算法分析：C语言描述》一书中给出的概念，书中给出了一张多重表示意图，如下所示：
从图中可以看出多重表是指一个节点有多个链穿过，和矩阵压缩存储中的十字链表十分相似。书中是以大学选课为例说明的，本处以书中例子为蓝本设计实现一种多重表。由于书中并没有给出具体的API，故本文主
...
二叉树的非递归前、中、后、层序遍历的不同实现
发表于
|
分类于
数据结构
前言由于二叉树是一种递归定义的数据结构，采用递归的方式去遍历是一种非常简洁方便的做法，但是如果要求使用非递归的方式去遍历整棵二叉树则必须使用辅助的空间。以下分别实现二叉树的前序、中序、后序以及层序的遍历算法。约定二叉树的基本结构如下：
12345678template <typename Da
...