- 博客(61)
- 收藏
- 关注
RSS订阅转载 STL
C++ STL详解 转载自：http://www.cnblogs.com/shiyangxt/archive/2008/09/11/1289493.html 一、STL简介STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R ...
2019-05-17 19:44:28
244
原创 BinarySearchTree
二叉搜索树的性质：1、每一个节点都有一个作为搜索依据的关键码（key），所有节点的关键码都不同。2、左子树上所有关键码（key）都小于根节点的关键码（key）。3、右子树上所有关键码（key）都大于根节点的关键码（key）。4、左右子树都是二叉搜索树。查找高度次，LogN构造函数拷贝构造赋值运算符重载析构函数插入(bool)：树为空，直接插到根节点；树不为空，定义一个parent记录cur的父亲，...
2018-04-19 11:57:12
515
原创 RBTree
红黑树保证最长路径不超过最短路径的2倍，因而近似平衡1、每个节点，不是红色就是黑色2、根节点是黑色3、如果一个节点是红色的，则他的两个子节点是黑色的（没有连续的红节点）4、每条路径上黑色节点数量相等5、每个叶子节点都是黑的（这里的叶子节点指的是空节点）当新插入节点是红色的，其父亲也是红色的，那么就知道了祖父是黑色的，所以叔叔的颜色比较重要第一种：cur为红，p为红，g为黑,u存在且为红，则将p,u...
2018-04-18 10:26:39
966
原创 AVLTree
左单旋：思路：1、创建节点subR和subRL2、parent的右指向subRL3、判断subRL是否存在 若存在，subRL的父亲就是parent 若不存在，也不影响4、subR的左指向parent 那么subR的父亲就是parent的父亲了5、给parent的父亲创建一个节点ppNode parent的父亲也就是ppNode,也就是subR6、如果ppN...
2018-04-12 14:53:48
1476
原创 resize和reserve的区别
1、resize(n)：调整容器的长度大小，使其能容纳n个元素。如果n小于容器当前的size，则删除多出来的元素，否则，添加采用值初始化的元素。reserve(n，t)：多一个参数t，将所有新添加的元素初始化为t。2、reserve(n)：预分配n个元素的存储空间。 capacity：容量（容器当前拥有的元素个数） size：长度（容器在必须分配新存储空间之前可以存储的元素总数...
2018-03-26 20:48:48
2788
原创 一个数组实现两个栈
看到题目，首先要考虑什么是数组，什么是栈，两者的特性都是怎样的，其次再考虑如何实现题目要求。通常会想到：方法一：栈1从数组的开头开始，栈2从数组的末尾开始，这样比较节省空间，当栈1和栈2的栈顶相遇时，我们就进行扩容。方法二：既然方法一可以从两边开始，那么我们也可以从中间开始向两边延伸，但这样有可能就会造成空间浪费，比如某一个栈分配了大量的空间，可是实际其只有一两个数据。方法三：在讨论中，有的同学建...
2018-03-07 11:18:19
420
原创 实现一个栈，实现Push（出栈）、Pop（入栈）、Min（返回最小值的操作）的时间复杂度为O(1)
在这里选取两个栈来实现，一个用于存放数据，栈名为S1；另一个用于存放最小值，栈名为S2。入栈：如果此时S2里无元素，则直接将元素插入S1栈顶；如果S2内有元素，则将要插入的元素与S2栈顶的元素作比较，要插入的元素如果小于或等于S2栈顶元素，则两个栈都插入该元素；反之，只插入到S1栈顶。出栈：如果S1和S2栈顶元素相等，则都出栈，反之出S1。最小值：S2栈顶是最小值，出栈S2栈顶即可.#includ...
2018-03-05 15:06:40
502
原创 关于类型萃取
简单理解：类型萃取是使用模板技术来萃取类型的某些特性，这里的萃取类型包括自定义类型和内置类型，用以判断该类型是否含有某些特性，从而在泛型算法中来对该类型进行特殊的处理，以提高效率等。类型萃取主要涉及函数派送机制，影响其机制的两个原因就是模板的编译机制和模板函数的重载。（简单理解，后续跟进）...
2018-03-05 13:36:08
406
原创 为什么模板不支持分离编译？
我们一般在使用模板时，大都包括头文件（.h），实现文件（.cpp），测试文件（test.cpp），模板写在实现文件中，在测试文件中进行测试调用，模板不支持分离编译大都报错是链接错误，程序包括预处理、编译、汇编、链接，此处的错误提示在于链接。之所以有这个问题还在于模板的两次编译：第一：实例化之前，是为了检查语法错误；第二：是为了在替换了类型之后，再次检查语法错误。而模板代码的实现体在一个文件里，实例...
2018-03-05 11:46:56
234
原创 计算器简单分析
例如给出一个计算公式：2-3*4+5 其中2、3、4、5属于操作数；-、*、+属于操作符。考虑到操作符的优先级，当我们读取这个公式时，需要将其重新写成计算机可以读取的形式，如234*-5+（遇见一个操作符号，就将符号前面紧挨着的两个元素进行运算）如图： 如果是直接针对2-3*4+5，在这里需要两个栈s1和s2，遇见操作数则将其入栈s1，遇到操作符则将其入
2017-12-19 14:36:53
515
原创 多态的对象模型
一、多态 定义：多态是同一个实体同时具有多种形式，它是面向对象程序设计的一个重要特征，c++的多态性体现在编译和运行时，编译时多态是静态多态，在编译时可以确定编译对象的形式；运行时是动态多态，运行时可以确定具体引用的对象。实现多态有：虚函数、抽象类、模板、覆盖。 作用：把不同的子类对象都当做父类来看，可以屏蔽不同子类对象之间的差异，写出通用的代码，做出通用的程序
2017-12-07 12:33:30
237
原创 菱形继承与虚继承
一、菱形继承 定义：菱形继承就是多个类继承一个公共类，而这些派生类又同时被一个子类继承。如我们所想的几何菱形那样，如下图：A为父类，B,C为派生类，同时继承父类A，然后D又继承B和C，这样就构成一个菱形继承。 代码展示： 这里已经可以看出，当D里面的对象d调用fun()函数时，fun()函数下方已经出现红色波浪线，这是因
2017-12-06 13:09:34
348
原创 Iterator迭代器
一、迭代器是是什么？ 迭代器是一种检查容器内元素并遍历元素的数据类型。每种容器类型都定义了自己的迭代器类型，如vector： vector:: iterator iter;定义了一个名为iter的变量，它的数据类型是由vector定义的iterator类型。 使用迭代器（iterator）读取容器（vector）中的每一个元素：
2017-12-04 22:57:45
250
原创 vector和list
一、vector定义：vector是表示可以更改大小的数组的序列容器。 就像数组一样，vector使用相邻的存储位置来存储元素，也就是说，它们的元素也可以使用“偏移量”来访问它的元素，就像数组一样有效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。 在内部，vector使用一个动态分配的数组来存储它们的元素。当插入新元素时，这个数组可能需要
2017-12-04 20:04:46
2021
原创 C和C++在结构体和类方面的不同
这里将C和C++写的顺序表的部分代码列出来作以对比：本质是一样的，C写一个显示的形参，C++不用，C++把顺序表的信息数据传给PushBack函数了，只不过是编译器在做，把数据传给了隐含的this指针。表层：面向过程，数据和方法是分离的。面向对象，数据和方法是封装在一起的。
2017-11-09 16:04:59
290
原创 虚函数表
虚表只存的地址class Base{public:virtual void func1(){}virtual void func2(){}private:int a;};void Test1(){Base b1;//虚函数表指针_vfptr,虚函数的重写，完成多态，指向虚函数的一张表，其实是个数组，指针数组，存的虚函数的地址cout }
2017-11-07 12:31:26
381
原创 纯虚函数
纯虚函数定义：在成员函数的形参后面写上=0，包含纯虚函数的类是抽象类，抽象类不能实例化出对象，纯虚函数在派生类重新定义之后，派生类才能实例化出对象。class Person{public:virtual void Display() = 0;//纯虚函数protected:string _name;};class Student :public Person
2017-11-07 10:12:03
474
1
原创 虚函数与多态需要注意的地方
1、派生类重写基类的虚函数实现多态，要求函数名、参数列表、返回值完全相同（协变除外）这里的协变在上一篇博客提到过2、基类中定义了虚函数，在派生类中该函数始终保持虚函数的特性。3、只有类的成员函数才能定义为虚函数。4、静态成员函数不能定义为虚函数。5、如果在类外定义虚函数，只能在声明函数时加virtual，类外定义函数时不能加virtual。6、构造函数不能为虚函数，虽然可以将o
2017-11-06 14:53:09
425
原创 虚函数与多态
是否构成多态的条件：1、父类的指针或引用2、虚函数的重写是否构成虚函数的条件：1、有virtual2、函数完全相同（协变：返回值可以不同，但返回值是父子关系的引用或指针）#include using namespace std;//基类class Person{public:virtual void BuyTickets(){cout }
2017-11-06 12:58:04
556
原创 String类的写时拷贝
1、Copy-On-Write的工作原理是什么？答：是引用计数2、String类在什么情况下才共享内存？答：这意思就是你用我的，才会出现共享。在使用别的类的数据时，只有两种情况，第一种就是以别的类构造自己，这个会触发拷贝构造函数；第二种就是以别的类赋值，这个会触发赋值运算符的重载。注意：不要看见“=”就以为是赋值，人家可能是调用了拷贝构造，尤其是前面带了类名的。还有要注意不要看见后
2017-10-27 22:20:20
431
原创 剖析new/delete、new[]/delete[]到底做了些什么事情
要知道new/delete和new[]/delete[]，首先要知道operator new和operator delete，他们都是C++中的库函数。void * operator new(size_t);void * operator delete(void*);给一句：Class *pA = new A(10);new做的工作是：1、调用operator new标
2017-10-26 11:04:17
320
原创 new/delete和malloc/free的关系与区别
new/deletemalloc/free是运算符（只能重载，不能定义）库函数（名字随便起）能调用构造函数和析构函数只能申请内存空间抛异常不抛异常，会返回NULL分配内存设计，分配算法，查找，避免内存碎片，导致效率太低，因此程序员喜欢自己写new/delete，或者创建一
2017-10-26 11:03:42
585
原创 深拷贝和浅拷贝的区别
深浅拷贝的区别： 浅拷贝是将原始对象中的数据型字段拷贝到新对象中去，将引用型字段的“引用”复制到新对象中去，不把“引用的对象”复制进去，所以原始对象和新对象引用同一对象，新对象中的引用型字段发生变化会导致原始对象中的对应字段也发生变化。 深拷贝是在引用方面不同，深拷贝就是创建一个新的和原始字段的内容相同的字段，是两个一样大的数据段，所以两者的引用是不同的，之后的新对象中的引用型
2017-10-24 21:27:45
29570
1
原创 拷贝构造和赋值运算符函数的重载
1、C++对传参和传返回值时构造的优化处理 当拷贝构造存在连续的赋值情况的时候， 当多个临时对象连续赋值的时候 简单点来说就是，再一次拷贝构造结束后，并没有直接返回给要创建的对象而是又再次进行了拷贝构造。或者是，建立一个临时对象，来进行拷贝构造，然后又返回了一个临时对象，再用这个返回的临时对象继续拷贝构造。这时候，系统就会自动优化。2. Test1中调用了_
2017-10-23 14:56:48
358
原创 操作符重载
这里是借鉴他人的结论在此学习，拓展，后面会继续修改完善//操作符实现重载的方式有两种，一种是“友元函数”，一种是“类成员函数”//类成员函数只有一个参数，因为类成员函数可以使用this指针获取自身的对象#include using namespace std;class Point{public:int x;int y;Point(int _x, i
2017-10-19 12:25:39
221
原创 拷贝构造函数为什么使用引用类型
#include using namespace std;class Test{int _Test;public:Test(int x) :_Test(x)//带参构造函数{cout }Test(const Test&te)//拷贝构造函数{_Test = te._Test;cout }Test& operator=(const Test
2017-10-19 11:21:12
593
原创 区别无参、带参、拷贝构造函数、赋值函数
#include #include using namespace std;struct Student//在结构体中{string name;int age;Student() //无参构造函数{cout age = -1;name = "Unknown";}Student(string name, int age)//带参构造函数{
2017-10-19 10:17:41
473
原创 对象成员的引用
//1、对象名.成员名//2、指向对象的指针class Time{public:int hour;int minute;};Time t, *p; //定义对象t和指针变量pp = &t; //使p指向对象tcout hour;//输出p指向的对象中的成员hour//3、通过对象的引用来访问Time t1;
2017-10-18 17:27:12
290
原创 类内类外定义成员函数
//1、类外定义成员函数class Student{public:void display();//公用成员函数声明private:int num;char name[20];char sex;};void Student::display()//类外定义display函数，“::”是作用域运算符，在类外要加类名，不然就是全局函数{cout co
2017-10-18 17:26:11
10265
原创 数据和操作的封装
//定义了两个Student类的对象stud1,stud2，这里对象stud1,stud2是占空间的//目前封装在类中的对象stud1和stud2都是对外界隐蔽的，外界不能调用它们，只有本对象中的函数display//才可以引用本对象中的数据，这里就引出“接口”
2017-10-18 17:21:49
437
原创 类和对象、访问限定符、默认成员函数
1、类的定义，访问限定符，面向对象封装性，对象的引用。 （1）每个实体都是对象，对象的类型是类，而对象是类的具体实例。类是抽象的，不占用内存，而对象是具体的，占用存储空间。 类是用户建立的类型，如果程序中要用到类类型，必须根据自己的需要进行声明，或者使用别人已设计好的类。 关键字class和类名组成类头，class是声明类时必须使用的关键字，相当于声明结构体类型时
2017-10-17 21:25:11
2218
原创 查找单链表的倒数第k个节点，要求只能遍历一次链表
//遍历一遍找第K个节点//不足k个返回空Node* FindKNode(Node* pHead, size_t k){Node* slow = pHead, * fast = pHead;while (--k)//走k-1步{if (fast == NULL){return NULL;}fast = fast->next;}while (fas
2017-09-28 14:25:45
486
原创 查找单链表的中间节点，要求只能遍历一次链表
//遍历一遍，找中间节点//快慢指针问题Node* FindMidNode(Node* pHead){Node* slow = pHead, *fast = pHead;while (fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;}void TestT
2017-09-28 14:25:21
475
原创 合并两个有序链表,合并后依然有序
//合并两个有序链表，合并后依旧有序//当第一个链表是空链表就把它和第二个链表合并，结果是第二个链表；同样，第二个链表是空表，合并结果是第一个链表；如果两都是空链表，合并结果也是空链表//比较两个链表的头结点，小的作为合并后的头结点，在剩余节点中，再次比较两个链表的头结点Node* MergeList(Node* pHead1, Node* pHead2){if (
2017-09-28 14:24:53
10941
1
原创 单链表排序（冒泡排序)
//单链表冒泡排序//需要三个指针cur,next,tail，tail指向每次冒泡冒到的终止位置//第一趟next为空停止，把cur给tail，再让cur和next到前面去再开始冒泡void BubbleSort(Node* pHead){Node* tail = NULL;if (pHead == NULL || pHead->next == NULL)//头指针为空，或
2017-09-28 14:24:25
1206
1
原创 逆置/反转单链表
//单链表逆置//3个指针n0,n1,n2void ReverseList(Node** ppNode){Node* n0 = NULL; Node* n1 = *ppNode;Node* n2 = n1->next;if (*ppNode == NULL){return;}while (n1){n1->next = n0;n0 = n1;
2017-09-28 14:23:51
250
原创 单链表实现约瑟夫环
//单链表实现约瑟夫环Node* Josephus(Node* hus, size_t k){Node* man, *next;assert(hus);man = hus;while (man->next != man){int count = k;while (--count){man = man->next;}next = man->next
2017-09-27 21:53:38
303
原创 在无头单链表的一个节点前插入一个节点
//无头单链表一个节点pos前插一个节点x//1 2 3 [x] 4 5，3所在位为pos位，把3和x互换位置void InsertFront(Node* pos, DataType x){Node* next,*tmp;assert(pos);next = pos->next;//4是nexttmp = BuyNode(pos->data);//tmp指向3pos
2017-09-27 21:52:58
858
原创 删除一个无头单链表的非尾节点
//删除非尾节点pos，无头结点//把pos的下一个值给pos，pos的下一个节点Free掉void EraseNonTail(Node* pos){Node* next;assert(pos && pos->next);//断言保证Pos和它的下一个节点都存在，这也保证了不删除尾节点next = pos->next;//先确定next是pos的下一个节点pos->da
2017-09-27 21:52:33
269
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人