vector的指针主要包括：start, finish, end_of_storage。start指向第一个存储数据的空间、finish指向最后一个存有数据的空间之后的一个空间，end_of_storage指向vector最后一个存储空间之后的位置。也就是说，start和finish是针对于数据而言的，end_of_storage是针对于vector的整个存储空间而言的。

例如以下C++代码，第一行创建一个空的且存储空间为100的向量；第二行是将0.1从后端插入向量。

    vector <double> weights(100);
    weights.push_back(0.1);

结构如下：

向量是一种标准模板容器(STL)，迭代器内部的几个方法：

    iterator begin()
    {return start;}

    iterator end()
    {return end;}

    unsigned size()
    {return finish-start;}

    bool empty()
    {return start==finish;}

扩容操作：

扩容的条件：finish==end_of_storage时，向量会发生扩容操作以保证插入操作的正常进行。

扩容的步骤：

1.创建容量为旧数组二倍的新数组（就是2倍，规定。。）

2.将旧数组的数据拷贝到新数组中

3.将旧数组的指针拷贝到新的数组中

4.插入新的数据（先将插入位置之后的所有元素向后移动，再插入新元素worstTime(n)=O(n)）

5.收回旧的存储空间（这点容易忘记，考试的时候我就忘了TAT）

关于插入操作：

    iterator insert(iterator position, const T& X);

需要注意的是，insert返回的是迭代器类型，一般insert都返回迭代器类型（vector,deque,list）

二、双端队列 Deques(double ended queue)

概念与优缺点：

(1) 给定下标，支持常数时间修改这个下标上的项。

(2) 头插/尾插的平均时间复杂度为常数，但是worstTime(n)=O(n)

(3) 在任意位置插入，worstTime(n)=O(n), averageTime(n)=O(n)

物理结构与逻辑结构：

思考：怎样将五个元素插入双端队列、然后经过删除头元素和尾部元素操作之后将元素顺序输出？

代码如下（示例）：

    deque<string> words;
    string word;
    
    for(int i=0;i<5;i++)
    {
        cin>>word;
        words.push_back(word);
    }

    words.pop_front();
    words.pop_back();
    
    for(unsigned i=0;i<words.size();i++)
    {
        cout<<words[i]<<endl;
    }

结构如下：

其中start和finish是迭代器，各个包含有4个指针，其中的last指向每个区块最后一个存储空间之后的位置，map是用来区分双端队列头和尾的指针。

三、链表 list

这里讲到的链表特指有头结点的双向循环链表。单向的有点简单，就先不记了哈~

概念与优缺点：

(1) 访问和修改序列中任意一项花费线性时间。原因：list的迭代器不是随机访问的迭代器，而是双向迭代器。

(2)给定某一位置的迭代器，在这个位置上插入或者删除一项需要花费常数时间。

缺点：不支持下标运算，只能用迭代器，而deque和vector可以使用下标运算。

list和vector、deque的选择与权衡：

（1）如果需要访问或者修改顺序容器中位置迥异的项，就选择向量（或者双端队列）

（2）如果迭代通过一个顺序容器并在迭代器中进行插入和删除，就选择链表。

实现原理：

push_front(const T & x), push_back(const T & x)

pop_front(), pop_back()

empty(), size(),begin(), end()

insert(iterator position, const T & x)

erase(iterator position), erase(iterator first, iterator last)

    list<double> words;
    double word;
    for(int i=0;i<20;i++)
    {
        cin>>word;
        words.push_back(word);
    }

    list<double>::iterator itr;
    for(itr=--words.end();itr!=--words.begin();itr--)
    {
        cout<<*itr<<endl;
    }

new methods:

1. void splice(iterator position, list<t> & x);

e.g. words="a","b","c","d";

new_words="e","f";

已知itr指向"c",如果调用words.splice(itr, new_words);

结果为："a","b","e","f","c","d"

2. void sort();升序排列

3. list的删除方法包括：pop_front(), pop_back(), erase(), delete

前三种删除方法在链表中删除的是数据和空间，在vector和deque中只删数据；delete在所有容器中都只是删除数据。

4.前置--

    iterator & operator--()
    {
        node=node->prev;
        return *this;
    }

5. insert的八步操作

请不要死记硬背，画图理解。

    iterator insert(iterator position, const T & x)
    {
        list_node * tmp = get node();            //创建节点，并用tmp指向
        (*tmp).data = x;                         //赋值
        //也可以写成  construct(value_allocator,address((*tmp).data).x);
        (*tmp).next = position.node;             //将tmp的next指向position.node
        (*tmp).prev = (*position.node).prev;     //将tmp的prev指向position.node指向的前一个节点
        (*position.node).prev=tmp;               
        ((*position.node).prev).next = tmp;
        ++length;    //很容易忘记的一步操作
        return tmp;
    }

6. push_front()与push_back()

    void push_front(const T & x){insert(begin(),x);}
    void push_back(const T & x){insert(end(),x);}

物理结构与逻辑结构：

非空的有头节点的双向链表：

list类的结构声明：

    template<class T>
    class list{
    protected:
        unsigned length;
        struct list_node
        {
            list_node * next;
            list_node * prev;
            T data;
        }
        list_node * node;
        //迭代器的初始化，一个冒号后面跟着由逗号分隔的许多字段的初始化（字段标识符+圆括号中的初始值）
        iterator(list_node * x):node(x){}    
        //......
    }

注意node指向的节点为头节点，node字段是iterator类的，而不是list类的，缺省构造器如下：

    (*node).next=node;
    (*node).prev=node;

调用缺省构造器得到的是空链表：（length=0）

尤其要注意的是链表的插入操作怎样实现，常考(请看实现原理部分)

四、容器适配器与队列和栈container adapter & queues & stacks

容器适配器container adapter：

概念：容器适配器C使用一些基础的容器对象定义C的方法，容器适配器将一些基础容器转换成类C的容器。例如：queue, stack, priority queue（队列、栈、优先级队列）。

基础容器（向量、链表、双端队列）可以被视为嵌入在容器适配器中的芯片。容器适配器利用基础容器的优点，使用基础容器对象的方法。容器适配器的最终目的是实现方法，是对基础容器的改造，而不是继承。

以queue为例，队列可以采用任意一个包含有push_back, pop_front, front, back, size, empty方法的容器，例如deque、list。但是vector不如前两者合适。

队列：

概念与优缺点：

(1) 插入只允许从尾部进行。

(2) 检索和修改只允许从头部进行。

原则：FIFO (first-in, first-out) 先来先服务。

优点：队列不存在迭代器，deque（缺省）可以平均以常数时间处理尾部插入、头部删除和头部访问。

实现原理：

queue类的声明和定义：

template<class T, class Container = deque<T>>  //以deque为模板参数的情况，缺省值为T

method interfaces:

1. 用Container的拷贝初始化队列：

explicit queue(const Container &= Container());

只能在显式构造的时候使用（只能和构造器一起使用），编译器不当在构造器语句中自动类型转换。

2. bool empty() const;

3. unsigned size() const;

4. void push(const value_type & x);

5. T & front();

const T & front();

6. T & back(); 返回对队列尾项的引用

const T & back(); 返回队列尾项的常量引用

7. void pop();

物理结构与逻辑结构：

queue没有迭代器！！只能通过队列头部进行访问

push “Alice”：

push “Bob” and “Cindy”：

pop：

应用：洗车模拟。

栈stacks

概念：也是一种容器适配器，只能对top元素（相对于back）进行push和pop操作，也没有迭代器。

原则：先入后出

栈需要有empty, size, pop_back, push_back, back方法，因此基础容器可以是vector, list, deque三种都可以。

实现原理：

栈的声明如下

    template<class T, class Container=deque<T>>
    class stack
    {
    protected:
        Container c;
    public:
        void push_back(const value_type & x)
        {
            c.push_back(x);
        }
    }

方法接口：

1. explicit stack(const container & =container());

2. bool empty();

3. unsigned size();

4. void push(const T& x);

5. T & top();

6. const T & top() const;

7.void pop();

栈的应用：用栈实现递归。

五、二叉树

概念与优缺点：

二叉树的递归定义：

要么为空，要么由一项（根项）和两个不相交的二叉树组成。

注意：二叉树不是基础容器，也不是一个数据结构。

相关概念：sibling, ancestor, descendant, leaf, branch, expression tree, parent, left/right child, path, lefttree(t), righttree(t), height(t)

二树：除了叶节点之外的节点都有一个左孩子和一个右孩子。

满树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

表达式树：叶为操作数，非叶为操作符。

二叉树的遍历方法：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）

物理结构与逻辑结构：

完全二叉树和数组的相互转换：

完全二叉树：

转换成数组：

因此可以用vector存完全二叉树，而list不合适。

为每一项建立索引，如果正整数索引 i 上的项有子女，那么：

根据父母索引找孩子：

左子女索引= 2 i + 1

右子女索引= 2 i + 2

其中 i 是父母索引。

根据孩子索引找父母：

父母索引= （ i - 1 ）/ 2

其中i为子女索引。

实现原理：

1. 用递归的方式求二叉树t中的树叶的数量

    //伪代码，理解即可
    if t is empty
        leaves(t)=0
    else if t consists of a root only
        leaves(t)=1
    else
        leaves(t)=leaves(leftTree(t))+leaves(rightTree(t))

2.用递归的方法求二叉树中的节点的数量

    //伪代码，理解即可
    if BT is empty
        n(t)=0
    else
        n(t)=n(leftTree(t))+n(rightTree(t))+1

3.height(t):根和最远树叶之间的树枝的数量，针对整个树而言。空树的树高为-1

    //伪代码，理解即可
    if tree is empty
        height(t)=-1
    else
        height(t)=1+max(height(leftTree(t)),height(rightTree(t)))

4. level和depth不针对整个树，而是针对于节点而言。从root到x的树枝的数量。

    //伪代码，理解即可
    if x is the root item
        depth(x) = 0
    else
        depth(x) = 1 + depth(parent(x))

5. 二叉树定理

对任意的非空二叉树：

注意后面几个式子的商是浮点数。

六、二叉查找树BST

概念：

递归定义：t 是一个二叉树，要么为空，要么：

（1）leftTree(t)的每一项都小于根项

（2）rightTree(t)的每一项都大于根项

（3）leftTree(t)和rightTree(t)都是二叉查找树

注意BST不必满足完全二叉树或者二树，但是可以满足满树和二树。

如果BST是满树或者完全二叉树，那么树高与节点数成对数关系。如果成链，树高和节点数成线性关系，如果不成链，也可能是线性关系。

关联容器：

项通过和其他的项比较确定它在容器中的位置。每个项有一个键，是项的一部分，用来进行比较。

BST的实现原理：

BinSearchTree()

unsigned size() const;

Iterator find(const T & item) const ;

Iterator insert(const T & item);

void erase(iterator itr);

Iterator begin();

Iterator end(); //返回header，erase(--end())用于删除最大的一个元素

~BinSearchTree()

注意没有push_back()和push_front()方法，用erase()取代。

    struct tree_node
    {
        Item item;
        tree_node * parent,
                  * left,
                  * right;
        bool isHeader;
    }
    tree_node * header;
    unsigned node_count;

物理结构：

七、红黑树

五条规则：

规则1：节点是红色或黑色的；
规则2：根节点是黑色的；
规则3：每个叶子节点都是黑色的空节点（NIL节点）；
规则4：每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不可能有两个连续的红色节点）；
规则5：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点；

必考：红黑树插入新元素时怎样进行调整（变色与旋转等操作）？

首先要明确的是，插入的节点的初始状态一定是红色的叶子，插入位置的确定方法和二叉查找树是一样的。需要调整的有以下五种情况：

（1）如果原来的树为空树，插入红色节点作为根节点，再将这个节点变为黑色。

（2）如果新插入的节点的父节点为黑色，且父节点没有兄弟节点，即下图这种情况：

那么直接插入就行了，不需要变色或者旋转。

（3）如果新插入的节点的父节点有与父节点颜色相同的兄弟节点（都为红色），即下图这两种情况之一：

那么插入之后只变色就行。父节点和父节点的兄弟节点变成黑色，祖父节点变成红色。

（4）新插入节点的父节点为红色，父节点的兄弟节点为黑色。从祖父到新插入的节点为 “左左” 或者 “右右”，先变色，再大旋（祖父左旋或者右旋）

如下图所示：

（5）新插入的父节点为红色，父节点的兄弟节点为黑色。从祖父到新插入的节点为 “左右” 或者 “右左”，先对父节点旋转，再变色，再对祖父大旋（祖父左旋或者右旋）

如下图所示：

对树的左旋和右旋不太明白的可以参考这个视频：

https://www.youtube.com/watch?v=q4fnJZr8ztY

八、一些声明方法和需要注意的操作

常见的对象声明方法：

优先级队列对象的声明方法：priority_queue<string, vector<string>, greater<string>> pq;

set对象的声明：set<int, greater<int>> batt;

multiset对象的声明： multiset<double, greater<double>> salaries;

map对象的声明：map<double,int,less<double>> xx;

multimap对象的声明：multimap<double, float, greater<double>> mm;

一些需要注意的操作：堆的插入和删除（hole，删根节点）、二叉查找树的删除（三种方法）插入和查找遍历（我的另一篇博客中有二叉查找树的C++实现代码）。

总结

文章写得平平无奇，这些都是我在复习过程中记的笔记，所以记得比较粗略，主要就是捡一些易错的地方记下来，像哈希冲突处理之类的都没写。。。考试的时候双哈希写错了，有点阴影吧（很勉强的理由QAQ）。。。有问题的话，欢迎大家指正！！！感激不尽！！！

码农公寓

前言

一、向量 vector

二、双端队列 Deques(double ended queue)

三、链表 list

四、容器适配器与队列和栈container adapter & queues & stacks

五、二叉树

六、二叉查找树BST

七、红黑树

八、一些声明方法和需要注意的操作

总结

相关文章