3 漫步孤独之海

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 25w+

STL红黑树

红黑树红黑树根据红连接的位置可以分为偏左红黑树和偏右红黑树。这两种树分别对应了2-3树和2-3-4树,本篇文章只对偏左红黑树偏左红黑树概念偏左红黑树是基于2-3树的思想的一种实现:红黑树是二叉树其中引入了红黑链接的概念,红链接对应2-3树中的3-结点,黑链接对应2-3树中的2-结点(普通节点)性质1.红链接均为左连接2.没有任何一个结点同时与两条红链接相连(1条红链接连接的两个结点构成1个3-结点,两条就是4-结点)3.红黑树是黑色平衡,任意空连接到根结点的路径上的黑链接数目相等4.根结点

2020-06-28 16:48:43

平衡树:2-3查找树

平衡树查找树相较于链表数组来说,查找效率很高,我们知道影响查找树效率的最大因素就是查找树的深度,最坏的情况就是所有的结点都在根结点的一侧就像下面这种情况平衡树思想就是为了优化树的查找,让根结点两侧结点数目“平衡”,来达到降低查找树高度的目的2-3查找树2-3查找树是一种平衡树的思想我们将标准二叉查找树的结点称为2-结点(含有一个键和两条链),而现在我们引入3-结点,它含有两个键和三条链。每一条链就是一个分区2-3查找树定义一棵2-3查找树要么为空,要么满足满足下面两个要求:2-结点:含有一

2020-06-26 11:36:29

STL优先队列实现

逻辑我们知道普通队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在某些情况下,我们可能需要找出队列中的最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要在这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能,需要每次遍历队列中的所有元素,比较并找出最大值,效率不是很高,这个时候,我们就可以使用一种特殊的队列来完成这种需求,优先队列。实现优先队列的底层是用堆实现的,因为堆顶就

2020-06-25 16:26:01

STL堆实现

逻辑堆是一种用数组模拟完全二叉树的结构完全二叉树:只有最后一层是不满的,其他层都是满的,而且最后一层左满又不满如果一个结点的位置为k,则它的父节点的位置为k/2,左子节点位置2k,右子结点2k+1堆规定父节点大于子节点,对子节点之间的大小不做要求代码实现#ifndef Heap#define Heapusing namespace std;template <class RandomAccessIterator, class T>//下沉操作void _adjust_hea

2020-06-20 14:26:33

C++折纸问题

问题描述给定输入参数N,代表纸条从下边向上方对折N次,请从上到下打印所有折痕方向分析1.将一张纸分为粉,黑两面,粉色为正面,黑色为反面。2.第一次对折时粉色朝上,对折之后产生一个向下的折痕,这时我们把对折之后的纸粉色朝下,让折痕朝上把这个折痕看成是二叉树的根结点。3.第二次对折新产生的两个折痕就是根结点的子节点,4.之后每一次对折都产生一层结点5.我们规定左节点为下折痕,右节点为上折痕6.从上到下打印这很方向就是这棵树的中序遍历代码class paperNode{public:

2020-06-13 11:25:21

C++二叉查找树的深度

算法采用递归的方法1.如果左子树不为空,递归计算左子树的深度left2.如果右子树不为空,递归计算右子树的深度right3.比较left和right,树的深度为较大者+1(加上根结点)代码//计算整个树的深度 int maxDepth(){ return maxDepth(root); } //计算指定子树的深度 int maxDepth(Node<Value>* x){ int depth = 0;

2020-06-12 14:19:01

C++二叉查找树遍历

前情回顾队列模板实现二叉查找树实现基础方法按照根结点的遍历顺序划分1.前序遍历:根->左->右2.中序遍历:左->根->又3.后序遍历:左->右->根前序遍历:E,B,A,D,C,G,F,H中序遍历:A,B,C,D,E,F,G,H后序遍历:A,C,D,B,F,H,G,E代码 //获取整个树中所有的键 void preErgodic(){ preErgodic(root); } //获取指定树x的所有键,

2020-06-12 14:01:31

C++队列模板实现

逻辑队列一种先进先出的数据结构只能在一端进行插入,在另一端进行删除代码template <typename T>class Queue{private: class Node { public: T item; Node* next; Node(){} Node(T item, Node* next) { this->item = item;

2020-06-10 17:45:44

C++二叉查找树

原理左节点比根节点小,右结点比根结点大API设计结点类:Node<Value>public Node* leftpublic Node* rightpublic int keypublic Value value二叉查找树:BinaryTree<Value>private Node* root //根节点private int N //元素个数public void put(Key key,Value value) //向树插入键值对private No

2020-06-08 11:02:20

C++逆波兰式求解

算法1.建立一个栈2.遍历字符串:2.1如果当前元素为操作符就从栈中弹出两个操作数o1,o2进行运算o2.operator(o1),并将结果压栈2.2如果当前元素为操作数直接压栈代码string int2string(int a){ stringstream ss; ss<<a; string resault; ss>>resault; return resault;}int caculate(vector<string

2020-05-27 13:38:07

C++括号匹配问题

第一种算法用栈来解决:1.建立一个栈2.遍历字符串如果是左括号就压栈3.如果是有括号:判断此时栈是否为空3.1如果为空则不匹配3.2如果不为空则弹出一个元素4.遍历结束后判断栈是否为空:若为空则匹配,不为空不匹配bool isMatch(string str){ //1.建立一个栈 Stack<char> s; //2.遍历字符串 for(int i=0;i<str.length();i++) { //2.1如果当前

2020-05-27 12:26:35

C++模板栈实现

代码template<class T>class Stack{private: class Node { public: T x; Node* next; Node(){} Node(T t,Node* next){ this->x = t; this->next = next; } Node(Node&amp

2020-05-27 12:02:57

C++循环链表解决约瑟夫问题

算法1.构建循环链表2.设置计数器count模拟报数3.如果报数为k则删除结点且重置count4.重复操作3直到只剩下一个结点为止代码void Joseph(int n,int k){ //1.构建循环链表 Node<int>* head = new Node<int>(1,nullptr); Node<int>* pre = head; for(int i=2;i<=n;i++) { Node&

2020-05-27 10:31:31

C++单链表环入口

算法1.先设置快慢指针fast,slow判断链表是否有环2.判断出有环之后,设置一个临时指针temp指向头结点当temp和slow相遇时这个结点就是入口代码template <typename T>T inCircle(Node<T>* head){ //1.设置两个指针slow,fast指向head Node<T>* fast = head; Node<T>* slow = head; //2.遍历链表:slow每

2020-05-27 09:30:06

C++单向链表是否有环

算法用快慢指针解决这个问题1.设置fast,slow两个指针2.遍历链表fast每次走两步,slow每次走一步3.如果fast和slow相遇说明有环代码bool isCircle(Node<T>* head){ //1.设置两个指针slow,fast指向head Node<T>* fast = head; Node<T>* slow = head; //2.遍历链表:slow每次走一步,fast每次走两步 while(

2020-05-27 09:19:58

C++快慢指针:链表中间值

算法1.设置fast,slow两个指针指向链表头结点2.fast每次走两步,slow每次走一步3.当fast为空或fast->next为空时结束循环4.此时slow指向的结点就是链表的中间结点 T getmid() { Node* fast = head; Node* slow = head; while(fast!=nullptr&&fast->next!=nullptr){ fas

2020-05-26 20:53:17

C++单链表反转

算法递归反转链表中的每一个结点:1.递归反转当前节点的下一个结点返回值设为pre2.如果当前结点的下一个结点为空则此时已经找到链表的最后一个结点,这是递归的出口:head->next = curr ,return curr3.从最后一个结点开始递归返回,将返回值作为当前结点的前驱结点4.反转当前结点:pre->next = currvoid Reverse(){ if(head->next == nullptr){ return;

2020-05-26 19:30:17

C++实现单向链表Linklist

template <typename T>class Linklist{private: class Node { public: T x; Node* next; Node(){} Node(T x, Node* next):x{x},next{next}{} Node(Node& node){ this.x = node.x;

2020-05-26 18:21:22

排序的稳定性

稳定性的概念假设在数组中有两个相等的元素A,B且A在前B在后;当进行排序之后A和B的先后关系不变则称排序是稳定的排序稳定性的意义当一组数据只进行一次排序时稳定性是没有意义的,当一组数据需要进行多次排序时稳定性是有意义的:假设这样一种情况,一种商品我们需要先按价格排序,然后再按销量排序如果排序是不稳定的,当我们按价格排序时A的价格大于B的价格排在了B的前面,当按照销量排序时A的销量和B的销量是相同的,不稳定的排序排完之后A排到了B的后面破坏了第一次排序的结果。排序稳定性可以在多次排序中可以减少开

2020-05-26 15:31:46

C++快速排序

算法1.设置两个指针low,high分别指向数组的第一个元素和最后一个元素,设置第一个元素为参考元素key2.先从右向左移动high指针直到找到比key值小的元素为止3.从左向右移动low指针直到找到比key值大的元素为止4.交换low指向的元素和high指向的元素5.重复步骤3,4,5直到low指针与high指针相遇6.将此时low指针指向的元素与元素key交换位置7.递归排序左子序列8.递归排序右子序列代码void QuickSort(int* arr,int first,int l

2020-05-26 15:01:25

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。