数据结构之二叉搜索树 C/C++

数据结构之二叉搜索树

一、二叉搜索树 1.1 什么是二叉搜索树 算法导论中对二叉搜索树(Binary Search Tree, 简称BST)的定义: 设x是二叉搜索树中的一个节点,如果y是x左子树中的一个节点,那么y.ke...
阅读全文
数据结构之树:二叉树的实现 C/C++

数据结构之树:二叉树的实现

相对于栈和链表等数据结构来说,树有着更复杂的结构。正如我们平常生活中看到的树一样,它有很多分支,而且分支上面还会有分支。 树的用途十分广泛,最常见的树是二叉树,衍生了很多类型的树,红黑树,搜索树等等,...
阅读全文
数据结构之列表:双向链表的实现 C/C++

数据结构之列表:双向链表的实现

双向链表是链表的一个分支,相比单向链表来说多了个一个前向指针pre,指向当前节点的前一个节点,查找起来更为灵活。 二、链表节点实现 双向链表的节点可以继承单向链表的节点,添加一个pre成员即可。两者声...
阅读全文
数据结构之列表:单向链表实现 C/C++

数据结构之列表:单向链表实现

链表是一种线性结构,通过多个节点彼此串联起来,能很方便地进行插入和删除操作。 其数据结构中包含两个部分,一个代表当前元素的内容data,还有一个指针next记录下一个元素的地址。 链表的接口多样化,根...
阅读全文
数据结构之队列:队列的实现 C/C++

数据结构之队列:队列的实现

队列是一种先进先出的数据结构,因和平常生活中的排队流程一样因此被称为队列。操作逻辑和栈刚好相反。 常用操作: enqueue: 元素入队 dequeue: 首元素出队 size: 返回队列中元素的个数...
阅读全文
数据结构之栈(三):顺序栈实现 C/C++

数据结构之栈(三):顺序栈实现

顺序栈的实现和使用数组实现原理一样,都是预先申请一段连续的地址块作为数据域,通过栈顶下标或指针移动完成压栈、出栈等操作。不同的是,使用指针的顺序栈支持栈满时扩容操作,原理更倾向于vector的实现。 ...
阅读全文
数据结构之栈(二):链式栈实现 C/C++

数据结构之栈(二):链式栈实现

链栈的原理和链表的原理一样,通过一个next指针把一个个的节点链起来: 初始时,栈底指针和栈顶指针都为空,每插入一个节点,栈顶指针改变,当前插入节点的next指针指向之前的栈顶元素。 同样,在使用to...
阅读全文
排序算法之冒泡排序 C/C++

排序算法之冒泡排序

一、原理 读书的时候学的第一个排序就是冒泡排序,它的原理很简单,每次把最大或者最小的从最后往前慢慢浮上来,一直到最后只剩下一个的时候序列就是有序了。冒泡排序的时间复杂度为O(n^2),是一种稳定的排序...
阅读全文
排序算法之选择排序 C/C++

排序算法之选择排序

一、原理 选择排序和插入排序原理差不多,插入排序是把元素插到合适的位置,选择排序则是在每个位置上选择合适的元素。 在最开始的时候,找到最小的元素放在第一个元素,然后在剩下的里面找到最小的放到第二个位置...
阅读全文