数据结构与STL容器

一、

1、线性表

线性表包括顺序存储结构（用一段连续地址存储）和链式存储结构（数据域+指针域）。顺序存储结构的代表是C/C++中的数组，其读时间复杂度为O(1)，插入/删除为O（n），因为从插入/删除位置到最后一个元素都要向前/后移动一个位置。链式存储结构包括单链表（普通链表）、循环链表、双向链表等，单链表的读取为O(n)，插入/删除O(n)——不清楚第i个元素指针位置时，但是已知时为O(1)，代表为list容器。

2、栈

属于特殊的线性表，它一种先进后出的数据结构，代表为STL的stack。

3、队列

属于特殊的线性表，它一种先进先出的数据结构，代表为queue。

4、树

分为二叉树和多叉树（N叉树），map和set内部使用红黑树结构，在最坏的情况下查找、插入和删除仅消耗对数时间log(n)。

5、哈希表

STL中的unorder_map和unorder_set使用的就是hash table结构，查找、插入和删除消耗为常数级别O(1)。

二、

1、静态数组

静态数组就是大小固定不能扩展的数组，如C中普通数组、C++11中array。

2、动态数组

动态数组的空间大小在需要的时候可以进行再分配，其代表为vector。由于数组的特点，在位置0插入需要将整个数组后移一个位置来腾出空间，删除位置0的元素则需要将剩余元素前移一个位置，这两种最坏的情况为O(n)。所以vector只适合在末尾添加或删除元素，使用[]或迭代器随机访问是快速的。

deque可以可以看作是vector的增强版，它增加了在头部快速插入和删除元素。

3、链表

链表由一系列不必在内存中相连的结点组成，每个结点包含了结点元素和到后继结点的链。链表避免了插入和删除的线性开销，但随机访问效率很低。使用链表结构的代表是list容器，而且list是基于双向链表实现的。下图是普通链表与双向链表的示意图：

4、栈

栈的特点是后进先出，位于栈顶的元素是唯一可见的元素。栈可以使用链表来实现，通过在链表顶端插入元素来实现push，通过删除链表顶端元素来实现pop，top操作返回顶端元素。c++中栈数据结构的实现是容器适配器stack，stack其所关联的基础容器可以为vector、list、deque，默认为deque。

5、队列

队列的特点是先进先出，队列也可以使用链表来实现，enqueue（入队）是在链表的末端插入一个元素，dequeue（出队）是删除并返回链表开头的元素。c++中队列数据结构的实现是容器适配器queue，其所关联的基础容器可以为list或deque，默认为deque。

6、链表的创建和操作

typedef struct node
{
    int iIndex;
    struct node* pNext;
}Node, *NodePtr;

//创建链表
NodePtr CreateList(unsigned iLen)
{
    NodePtr pHeadNode = NULL, pLastNode = NULL;
    for (unsigned i = 0; i < iLen; i++)
    {
        NodePtr pNode = new Node;
        pNode->iIndex = i;
        if (pLastNode)
            pLastNode->pNext = pNode;
        else
            pHeadNode = pNode;

        pLastNode = pNode;
    }
    pLastNode->pNext = NULL;

    return pHeadNode;
}

//输出链表
void PrintList(NodePtr pHeadNode)
{
    NodePtr pNode = pHeadNode;
    do
    {
        cout << pNode->iIndex << ", ";
        pNode = pNode->pNext;
    } while (pNode);

    cout << endl;
}

//链表排序：利用选择排序法思想
void SelectSortList(NodePtr pHeadNode)
{
    NodePtr pNode = pHeadNode;
    while (pNode->pNext)
    {
        NodePtr pNodeMin = pNode;
        NodePtr pNodeNext = pNode->pNext;
        while (pNodeNext)
        {
            if (pNodeNext->iIndex < pNodeMin->iIndex)
                pNodeMin = pNodeNext;

            pNodeNext = pNodeNext->pNext;
        }

        if (pNodeMin != pNode)
            swap(&pNode->iIndex, &pNodeMin->iIndex);

        pNode = pNode->pNext;
    }
}

//合并两个有序链表为一个
NodePtr UnionList(NodePtr pHeadNode1, NodePtr pHeadNode2)
{
    NodePtr pHeadNode = new Node;//新的链表添加一个头结点
    NodePtr pNode1 = pHeadNode1, pNode2 = pHeadNode2, pNode = pHeadNode;

    while (pNode1 && pNode2)
    {
        if (pNode1->iIndex <= pNode2->iIndex)
        {
            pNode->pNext = pNode1;
            pNode = pNode->pNext;
            pNode1 = pNode1->pNext;
        }
        else
        {
            pNode->pNext = pNode2;
            pNode = pNode->pNext;
            pNode2 = pNode2->pNext;
        }
    }

    pNode->pNext = pNode1 ? pNode1 : pNode2;//插入剩余段

    NodePtr pReturnNode = pHeadNode->pNext;
    delete pHeadNode;//删除新链表的头结点
    return pReturnNode;
}

//链表逆序：定义三个节点指针分别指向前三个节点，第二个节点的pNext重新指向第一个节点，三个节点指针再往后移动，如此往复
NodePtr TurnList(NodePtr pHeadNode)
{
    if (pHeadNode->pNext)
    {
        NodePtr pLastNode = pHeadNode;
        NodePtr pNode = pLastNode->pNext;
        NodePtr pNextNode = pNode->pNext;

        while (pNextNode)
        {
            pNode->pNext = pLastNode;

            pLastNode = pNode;
            pNode = pNextNode;
            pNextNode = pNextNode->pNext;
        }

        pNode->pNext = pLastNode;
        pHeadNode->pNext = NULL;

        return pNode;
    }
    else
        return pHeadNode;
}

View Code

三、

1、顺序容器：

vector为向量容器，支持使用下标来快速随机访问（所以提供了[]和at()访问元素的方法，迭代器支持++、--、+=、-=算数操作），支持在尾部快速插入、删除元素（使用push_back()、pop_back()方法），不支持在头部或中间快速插入数据（虽然也提供了insert()方法但头部或中间来插入元素，但这样做会导致容器将插入位置之后的所有元素重新定位，或者导致重新分配整个内存）。

list为链表容器，支持在容器头、尾、内部快速插入、删除元素（insert()方法可以在任何地方之前插入元素，插入或删除不会重新分配内存），不支持快速随机访问（不提供[]或at()来访问元素，也不提供迭代器的+=、-=操作，仅提供迭代器的++、--操作，使用find()查找元素会很慢）。

虽然list的迭代器不提供+、-、+=、-=操作，但其实可以通过advance、next/prev方法来实现这些操作，但是通过这些方法获得的list的迭代器进行distance操作的话会出错，所以如果想要对list进行advance、next等操作的话应该想一想使用的容器是不是改成vector更合适：

    std::list<int> myList = {1, 2, 3, 4, 5};

    auto it = myList.begin();
    std::advance(it, 4); //advance移动当前迭代器
    int n = *it; //5

    auto it2 = std::next(myList.begin(), 1); //next/prev获得迭代器之后/之前的迭代器，不改变当前迭代器
    n = *it2; //2

    n = std::distance(myList.begin(), myList.end()); //5，distance获得迭代器之间的距离
    n = std::distance(it, it2); //error

View Code

queue队列，适合队尾插入元素，队头删除元素的情况，它是容器适配器，其所关联的基础容器可以为list或deque，默认为deque。

deque为双端队列，它可以看作是queue的增强版，其支持在头部和尾部快速插入和删除元素。

priority_queue为优先级队列，允许设置元素的优先级，将新的元素放置在比它优先级低的元素前面，要求提供随机访问的功能，所以其所关联的基础容器可以为vector、deque，默认基础容器为vector

stack栈，适合后进先出的情况，它是容器适配器，其所关联的基础容器可以为vector、list、deque，默认为deque

2、关联容器

map、unordered_map、multimap为映射容器，支持通过键来快速查找和读取元素，其元素为键-值对的形式，键相当于元素的索引，值为元素所存储的数据。当使用下标[]来引用映射容器内元素的时候如果当前容器内没有该键则会自动创建该键值对。map元素是排序的，multimap支持同一个键多次出现。

set、multiset为集合容器，其元素仅包含一个键，有效的支持某个键是否存在的查询。set中元素是排序的，multiset支持同一个键多次出现。

3、vector等容器对于元素的要求是可复制和可赋值，map容器的key还需要支持<比较操作，所以如果把自定义类型作为map的key的话需要重载<，如：

struct Data
{
    int i;
    bool operator<(const Data& d)const
    {
        return i < d.i;
    }
};