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

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

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

双向链表是链表的一个分支,相比单向链表来说多了个一个前向指针pre,指向当前节点的前一个节点,查找起来更为灵活。 二、链表节点实现 双向链表的节点可以继承单向链表的节点,添加一个pre成员即可。两者声明和实现方式都差不多: 二、链表实现 2.1 类声明 双向链表和单链表非常相似,因此没有添加很多操作...
阅读全文
数据结构之列表:单向链表实现 C/C++

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

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

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

队列是一种先进先出的数据结构,因和平常生活中的排队流程一样因此被称为队列。操作逻辑和栈刚好相反。 常用操作: enqueue: 元素入队 dequeue: 首元素出队 size: 返回队列中元素的个数 empty: 判断队列是否为空 front: 返回队首元素 它有两个指针分别指向队列开头和结尾,出...
阅读全文
数据结构之栈(三):顺序栈实现 C/C++

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

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

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

链栈的原理和链表的原理一样,通过一个next指针把一个个的节点链起来: 初始时,栈底指针和栈顶指针都为空,每插入一个节点,栈顶指针改变,当前插入节点的next指针指向之前的栈顶元素。 同样,在使用top()和pop()两个方法时,也要先判断栈是否为空。 一、栈节点 二、栈 2.1 类定义 2.2 类...
阅读全文

数据结构之栈:使用数组和vector实现栈

栈是一种“先进后出”的数据结构,最先进入栈的元素位于栈的底端,最后进入的位于顶端。 其主要的接口函数为: pop(): 弹出顶端元素 size(): 返回栈容量 empty(): 判断栈是否为空 push(T data): 添加元素到栈顶 top(): 返回顶端元素 注意事项 对于栈的top()和p...
阅读全文
排序算法之冒泡排序 C/C++

排序算法之冒泡排序

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

排序算法之选择排序

一、原理 选择排序和插入排序原理差不多,插入排序是把元素插到合适的位置,选择排序则是在每个位置上选择合适的元素。 在最开始的时候,找到最小的元素放在第一个元素,然后在剩下的里面找到最小的放到第二个位置,按照这个方法依次查找直到最后一个元素。它的时间复杂度为O(n^2),是一种不稳定的排序。 (更多&...
阅读全文
排序算法之插入排序 C/C++

排序算法之插入排序

一、原理 从排序序列的第二个元素开始,依次往前面查询,知道找到一个合适的位置就把它插进去。每个元素在交换完成之后都是一个有序序列,它的时间复杂度为O(n^2)。 排序逻辑: (更多…)
阅读全文