今天在复习树形结构的相关知识时，发现了对于树的高度还有深度存在两个版本的解释，因此在这里讨论一下 下图是《数据结构与算法分析-C语言描述（原书第二版）》（机械工业出版社）关于树深度和高度的描述 在文章中不难看出，树形结构的深度和高度实际上就是根节点（或者叶子结点）到目标节点边的条数 在上图这个树形结构中B的深度为1，高度为2；A的深度为0，高度为3。其他的节点可以以此类推 下图是《数据结构（C语言版）》（清华大学出版社）关于树深度和高度的描述 其中树中结点的最大层次根据该书前面的解释如下图 也就是说对于刚才提到的树形结构，树的高度和深度就发生了改变 A点的深度就变成了1，高度变成了4；B点的深度变成了2，高度变成了3。...
我又要开更一些比较低端的玩意了，作为自己学习的笔记 今天来说一下如何建立一棵哈夫曼树以及如何利用哈夫曼树对字符串进行编码和解码。 在这之前首先应该了解一下什么是哈夫曼树（最优二叉树）：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 带权路径长度：为所有叶子结点的带权路径长度之和。这么说或许还是有点抽象，带权路径长度简单可以这么理解： 一条路的路程长度为2，一条路的路程长度为6，那么从根节点到第一个叶子结点的带权路径长度为2+6=8，以此类推其他的带权路径长度也可以知道 哈夫曼树被称为最优二叉树，究其原因就是带权路径长度最短。所以它在一些编码方面使用的比较广泛。 在使用哈夫曼树进行编码解码的时候我们需要把这个问题拆解成几个小问题来处理 1...
好久没有记录自己的数据结构的学习进度了，现在来写一下最近的二叉树的创建和先中后序遍历 首先来说一下二叉树的创建，二叉树的创建实际上很简单，原理是使用递归调用，递归调用的一个好处就是不用自己设计Stack，使用的系统的Stack，这样就省去了一些麻烦 这里就不解释递归的工作原理了，直接上代码 C++ BiTree createBtree(BiTree *root){ char temp; scanf("%c",&temp); if(temp == '$') return NULL; if(!(*root)){ *root = (BiTree)calloc(1,sizeof(struct BTNode)); } (*root)->data = temp; createBtree(&((*root)->lchild));...
之所以说KMP磨人是因为，他真的不怎么好懂，就算懂了，也不怎么好写0.0也有可能是我太菜了 KMP算法就是为了应对暴力匹配字符串带来的庞大的消耗，总的来说就是在匹配字符串的过程中如果发生匹配失败，不采用暴力匹配的方法直接从当前字符串的下一个位置开始匹配，而是最大程度的把匹配串向右移动尽可能多的字符。当然这里的移动并不是随便移动，而是根据一个移动表格（next数组）来进行移动 暴力匹配的思想就是逐个匹配，但是这是KMP怎么会这么low，当然对于下面这个字符串，刚开始可能和暴力匹配差不多 BBC ABCDAB ABCDABCDABDE ABCDABD 依旧不相等，继续整体后移 BBC ABCDAB ABCDABCDABDE #ABCDABD 整体移动到下面位置时，匹配成功一个字符 BBC ABCDAB ABCDABCDABDE ### ABCDABD 然后匹配一次对后面的字符进行匹配 BBC...
作为栈的一个练习，使用栈来进行进制转换不得不说效率真的是非常低，超级低，最快的方法是直接用C语言的位运算 但是这里还是介绍一下操作思想 实际上进制转换这个东西本身不是很难，主要的工作部分都是在栈的建立和操作算法的编写上 至于什么是栈就不过多赘述了，这里主要是实现栈的三个主要功能，PUSH、POP和获取栈顶元素。 首先要为自己定义的栈开辟一块存储空间，常用情况是使用链表，但是这里我们使用的是一个完整的结构体来表示一个完整的栈 具体的声明方法如下： C++ struct numberStack{ DEFAULTYPE *bottom; DEFAULTYPE *top; DEFAULTYPE *dataSpace; int allLength; int nowLocation; }newStack; 1234567 struct numberStack{ DEFAULTYPE *bottom;...
所谓(A-B)U(B-A)，实际上就是A独有的那一部分和B独有的那一部分的并集 也就是简简单单的如图所示 其实这个问题本身用动态链表（就是常规链表）是很好解决的，但是由于我们要用静态链表来实现，所以就会显得略微有一些麻烦，到底哪里麻烦？ 相对于动态链表，静态链表的内存分配函数需要自己来实现 相对于动态链表，静态链表的内存回收函数需要自己来实现. 静态链表的连接方式，和动态链表也有所不同 静态链表在实际操作中比动态链表更容易断（人为因素） 首先大概说一下答题思想吧，如果想先把两个链表建立起来在互相查找删减，实现会很麻烦，因此我采用的方法是：首先我完全建立A集合，然后再B集合输入的过程中对A中已经存在的元素进行删除操作 由于我采用的是传统写法因此对于时间复杂度可能不会考虑太多 首先我们要解决的一个问题就是静态链表的初始化函数，这个其实还是挺简单的 伪代码： 木有 C语言代码： C++...