漫步孤独之海-CSDN博客

原创 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 335

原创平衡树:2-3查找树

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

2020-06-26 11:36:29 227 1

原创 STL优先队列实现

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

2020-06-25 16:26:01 1267

原创 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 184

原创 C++折纸问题

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

2020-06-13 11:25:21 1824

原创 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 453

原创 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 168

原创 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 711 1

原创 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 118

原创 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 450

原创 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 4862

原创 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 120

原创 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 513

原创 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 352 1

原创 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 150

原创 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 263

原创 C++单链表反转

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

2020-05-26 19:30:17 636

原创 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 464

原创排序的稳定性

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

2020-05-26 15:31:46 127

原创 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 144

原创 C++归并排序

算法归并排序运用的是分治递归的思想1.将待排序元素拆分成左子序列和右子序列2.重复操作1直到分为n个单独的元素为止一共可以分logn层3.对每一层进行归并排序归并算法：1.创建一个临时数组存放归并之后的元素：temp2.设置三个指针分别指向左子序列的起始元素，右子序列的起始元素，临时数组：p1,p2,temp_index3.比较p1,p2指向的内容较小的存进临时数组，p++4.重复操作3直到p1或p2指向的子序列遍历完5.将未遍历完的子序列按顺序存进临时数组6.将临时数组中的元素写回待

2020-05-22 10:11:47 371

原创 C++希尔排序

算法1.设定步长将待排序元素分组2.对每组进行插入排序3.减小步长重复2操作直到步长为1代码void ShellSort(int* arr,int len){ int t; int gap; //1.设定步长变化 for(gap=len/2;gap>=1;gap=gap/2){ //2.希尔排序：根据步长对数据进行分组，在组内进行插入排序 //2.1找到待插入元素：根据分析第一个待插入元素为gap位置上的元素，从gap到len

2020-05-22 09:45:19 141

原创 C++插入排序

算法1.将元素分为有序和无序两部分2.将无序的元素插入到有序元素的合适位置上代码void InsertionSort(int* arr,int len){ int t; //将数组分为两部分：1.有序的，2.无序的，我们要做的操作时将无序的元素插入到有序的元素中 for(int i=0;i<len-1;i++){ //将待插入数a[i+1]插入到前面的有序数组中 for(int j=i+1;j>0;j--){

2020-05-22 09:19:01 126

原创 C++选择排序

算法1.设定一个指针min所指向的元素是每轮中最小的2.遍历每轮的元素如果找到比此时更小的元素就将min指向该元素3.每轮结束后将每轮最小的元素与每轮起始的位置交换代码void SelectSort(int* arr,int len){ int t; int min; //设定一个指针，指针所指向的元素是每轮中最小的元素 for(int i = 0; i < len-1; i++){//一共n-1轮 //设定每轮的第一个元素是最小的

2020-05-22 08:44:37 94

原创 C++冒泡排序

算法冒泡排序是每一轮通过相邻两个数的比较将较大的数不断地向右交换找到合适的位置。代码void BubbleSort(int* arr,int len){ int t; //1.一共n-1轮 for(int i=len-1;i>0;i--){ //2.每一轮需要遍历的元素减一（后面的已经有序了） for(int j=0;j<i;j++){ //比较相邻的两个数如果左边的较大就交换 if(arr[j]>arr[j+1]){ t=arr[j]; arr

2020-05-22 08:34:49 60

原创 C++11的荣光：右值引用

学过C++的应该都知道C++中独有的概念—引用。int b=1;int& a = b;大家都知道引用是一个地址的别名。C++11中将引用分为左值引用和右值引用。左值引用就是上面那个例子，大家应该都了解这里不再详谈，这篇文章重点讨论右值引用：C++11左值，纯右值和将亡值通俗理解上，左值就是可以放在等号左边的值，右值就是放在等号右边的值。更专业的说法是：左值：左值指定了一个函数或对象，是一个可以取地址的表达式（能取地址就行）右值：不和对象相关联的值（字面量）或者求其值结果是字面量或

2020-05-17 17:38:14 151

原创 C++多态相较于重定义的优势

这段时间先后学习了C++的重定义和多态。刚学多态的时候心里一直有个疑问：多态是同样的方法在不同的派生类中可以有不同的实现，重定义因为同名隐藏的机制也可以做到同样的方法在不同的派生类中可以有不同的实现。从功能上看多态似乎和重定义没啥区别，而且多态的开销还要更大些。为什么还要在引入多态这个概念呢。下面我们就来说一说多态所具备的独特的优势。首先：由于同名隐藏机制，只要在派生类中将方法重定义之后，基类中所有的同名方法我们都无法调用了。可能有人会说，既然已经选择重定义这个方法，基类中的方法也就没有调用的必要了

2020-05-15 15:55:25 191

mxy568767179的博客