文档章节

数据结构与STL容器

o
 osc_z1hvg4cu
发布于 2018/04/24 11:31
字数 1901
阅读 7
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

一、

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()访问元素的方法,迭代器支持++、--、+=、-=算数操作),支持在尾部快速插入、删除元素,不支持在头部或中间快速插入数据(因为这样会导致重新分配整个内存)。

    list为链表容器,支持在容器头、尾、内部快速插入、删除元素(插入、删除不会重新分配内存),不支持快速随机访问(不提供[]或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;
    }
};

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
C++标准库STL介绍

C/C++与STL 1.1. 什么是STL? STL -- 数据结构和算法的分离,模板(GP); STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念,但这种分离确实使得STL变得非常通用。例如,由于...

彼得雷
2015/10/31
1
0
为什么C ++ STL不提供任何“树”容器?

为什么C ++ STL不提供任何“树”容器,而最好使用什么呢? 我想将对象的层次结构存储为树,而不是将树用作性能增强... #1楼 海事组织,一个遗漏。 但是我认为有充分的理由不在STL中包含Tree结...

javail
02/20
31
0
游戏开发视频教程_基于MFC设计的MINI快跑游戏

基于MFC设计的MINI快跑游戏(游戏开发、MFC精讲、线程与进程通信) 课程分类:游戏开发 适合人群:初级 课时数量:36课时 用到技术:MFC涉及项目:MINI快跑游戏 咨询QQ:1840215592 游戏开发视...

mianhuatang
2014/12/19
48
0
Effective STL - 容器

STL(standard template library)提供了一组表示容器,迭代器,函数对象和算法的模板。容器是一个与数组类似的单元,可以存若干个值。 STL容器是同质的,即存储的值的类型相同;算法是完成特...

積木leayn
2013/10/07
159
0
你懂得C,所以C++也不在话下

前言:C++最初诞生时,仅仅被称作带类的C。这说明C和C++是一衣带水的关系,随后C++扩充了很多特性,成为了面向对象的一个语言,真正成了扛把子。那么C++有什么优势呢?举个例子类比,一个C代...

osc_jdkg3xt0
2018/04/05
13
0

没有更多内容

加载失败,请刷新页面

加载更多

Py之imblearn:imblearn/imbalanced-learn库的简介、安装、使用方法之详细攻略

Py之imblearn:imblearn/imbalanced-learn库的简介、安装、使用方法之详细攻略 目录 imblearn/imbalanced-learn库的简介 imblearn/imbalanced-learn库的安装 imblearn/imbalanced-learn库的使...

osc_8cqhsn24
5分钟前
0
0
B站是一家游戏公司?二次上市传言背后,游戏收入占比五成

撰文/文姬 出品/趣识财经 曾几何时,有着“中国YouTube”之称的哔哩哔哩,以“浪潮”三部曲吸引了一众吃瓜群众的注意。 此后,B站与知名财经UP主的“爱恨情仇”,以及高价签约知名游戏UP主...

镭射财经
6分钟前
6
0
WeChat:微信小程序设计流程注册&完善、设计&开发、审核&发布之详细攻略

WeChat:微信小程序设计流程注册&完善、设计&开发、审核&发布之详细攻略 目录 微信小程序设计流程 1、注册 2、小程序信息完善 3、开发小程序 3.1、开发文档 3.2、开发者工具 3.3、设计指南 ...

osc_e4tx8h6g
6分钟前
10
0
RecyclerView动画源码浅析

RecyclerView动画源码浅析 adapter.notifyItemRemoved(1)会回调到 RecyclerViewDataObserver: adapter.notifyItemRemoved RecyclerViewDataObserver onItemRangeRemoved triggerUpdateProce......

osc_35ne77sz
7分钟前
8
0
中科院计算所包云岗:从多场硕博答辩中,我看到了国内人才培养的进步 - 知乎

中国的计算机科学领域里,前沿研究的质变正在发生。 机器之心整理,参与:蛋酱、泽南。 国内的计算机科学领域,是否可以称得上引领方向了呢?近年来,我们在很多计算机科学,特别是人工智能顶...

osc_8i2fhl7z
9分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部