学好这13种数据结构,应对各种编程语言(C++版)

学了这么长时间数据结构和算法,有必要来个总结了,顺便回顾一下我们这段时间的学习成果。以 C++ 语言本身提供的数据结构为例。如果能掌握这 13 种数据结构,相信在学习其它语言的时候就不费劲了。

数组 Array

数组在初始化的时候就需要知道其大小,后续是不可以改变其大小的,可以通过下标来获取某个 index 中存放的元素。在 C++ 中通过源码可以知道,它其实是在 C 数组的基础上封装的:

#include <array>void testArray() {    // 创建一个数组    std::array<int, 5> a = {2, 4, 6, 8, 10};    // 对数组进行遍历    for (const auto i : a) {        std::cout << i << std::endl;    }    for(int i = 0; i < a.size(); i++) {        std::cout << a[i] << std::endl;    }    // 取第一个值,通过 [index] 获取    std::cout << "a[0] = " << a[0] << std::endl;    // 修改数组中第一个值    a[0] = 5;    /**     at 会检查 index 是否越界,越界将 crash,而 a[index] 不会;     libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: array::at     */    a.at(0);    // 数组是否为空    a.empty();    // 求数组的长度    std::cout << "a.size()=" << a.size() << std::endl;    // 获取第4个值    int value = std::get<4>(a);    std::cout << "a(4) = " << value << std::endl;    // 创建一个空数组,数组中的值为0或者是与类型相等的其它值    std::array<int, 5> a2;    std::cout << "end a2" << a2[0] << std::endl;    // 比较两个数组中的元素是否都相等    if (a == a2) {}}

可变数组,向量vector

在C++中使用 Vector 存当可变数组,它的容量可以动态改变,初始化的时候不需要确定数组的大小。使用的方法和数组基本一致。

#include <vector>// 向量void testVector() {    /**     vector<T> 它与Array不同,它的大小是可变的     */    std::vector<std::string> v;    // 增加容器的容量,至少容纳 20 个元素    v.reserve(20);    // 初始化一个向量    std::vector<int> v2 = {2, 4, 5, 7};    // 以数组初始化一个vector    std::array<std :: string, 5> words {"one", "two","three", "four", "five"};    std::vector<std::string> words_copy {std::begin(words) , std::end(words)};    // 通过 v[index] 获取或者修改元素    std::cout << "v[0] = " << v2[1] << std::endl;    // 获取第一个元素    std::cout << "v.front() = " << v2.front() << std::endl;    // 在末尾插入值为 9    v2.push_back(9);    // 在末尾插入值为 2    v2.emplace_back(2);    // 删除第一个元素,传入的值是一个迭代器    v2.erase(v2.begin());    // 长度    v2.size();    // 删除所有元素    v2.clear();    // 删除末尾元素    v2.pop_back();    // 在末尾插入元素    v2.insert(v2.end(), 3);}

双向链表 list

双向链表具有指向前一个节点和后一个节点的指针。C++ 中本身提供了双向链表的实现。

#include <list>void testList() {    list<string> words {"hello", "list"};    // 头部插入元素    words.push_front("push_fron");    words.emplace_front("emplace_front");    // 尾部插入    words.push_back("push_back");    words.emplace_back("emplace_back");    // 指定位置插入    words.insert(words.begin()++, "insert");    // 删除元素    words.remove("push_fron");    // 通过迭代器来访问链表中的元素    list<string>::iterator beg_iter = words.begin();    list<string>::iterator end_iter = words.end();    cout << "beg_iter:" << *beg_iter << endl;    cout << "end_iter:"  << *end_iter << endl;        for (auto a : words) {        cout << a << endl;    }}

单链表 forward_list

单链表只有指向下一个节点的指针,前面关于单链表我们做了好多算法题。

#include <forward_list>void testForwardList() {    forward_list<string> flist {"name", "lefe", "hello"};    // 计算它的大小    auto count = distance(begin(flist), end(flist));    cout << "size:" << count << endl;    // 头部插入    flist.push_front("before3");    // 在头部插入    flist.insert_after(flist.begin(), "before2");    // 在头结点前面插入    flist.insert_after(flist.before_begin(), "before1");    // 遍历单链表    for (auto word : flist) {        cout << word << endl;    }}

队列 queue

队列是一种先进先出的数据结构,C++底层使用「双端队列」实现。关于队列的更多内容,可以看这篇内容 图解设计一个循环队列。

#include <queue>void testQueue() {    queue<int> s;    // 入队    s.push(1);    // 出队    s.pop();    // 队首    s.front();    // 队尾    s.back();    // 队大小    s.size();}

双端队列deque

双端队列可以对队头和队尾元素进行操作。在做算法的时候我们设计过一个双端队列 图解设计一个双端队列

void testDeque() {   // 初始化一个空双端队列    deque<int> my_deque;    // 初始化一个含有两个元素双端队列    deque<string> name_queue {"lefe", "wsy"};    cout << "[0] = " <<  name_queue[0] << endl;    // 获取队头元素    cout << "front = " <<  name_queue.front() << endl;    // 获取队尾元素    cout << "back = " <<  name_queue.back() << endl;    // 从尾部入队    name_queue.push_back("bx");    name_queue.pop_front();}

优先队列 priority_queue

优先队列和普通队列一样只能在队尾插入元素,队头删除元素,但是它有一个特点,队头永远是优先级最大的元素,出队顺序与入队顺序无关。C++ 中的底层使用「堆」实现的,这样时间复杂度可以控制在 O(logn)。

void testPriorityQueue() {    // 创建优先队列    priority_queue<int> q;    // 向队列中添加元素    q.push(4);    q.push(1);    for(int i = 0 ; i < q.size() ; i++) {        cout << q.top() << endl;        // 删除第一个元素        q.pop();    }    // 队列是否为空    q.empty();}

堆heap

堆是一颗完全二叉树,某个节点的值总是不大于父节点的值(大根堆),可以使用数组来表示一个堆,C++ 默认提供的是大根堆。在堆排序中我们有详细介绍了堆。图解排序 6/10 - 堆排序(题目写出了)。在这篇文章中,我们实现了一个堆 动手写个“堆”

C++ 中的堆是通过算法实现的,需要导入 #include <algorithm>

#include <algorithm>void testHeap() {    vector<int> numbers {6, 20, 7, 3, 5};    /**提供判断方法*/    // make_heap(numbers.begin(), numbers.end(), [](int a,int b){return a < b;});    // 创建堆后,numbers 中元素的值为: 20,6,7,3,5,大根堆    make_heap(numbers.begin(), numbers.end(), [](int a,int b){return a < b;});    // 向堆中添加元素    numbers.push_back(40);    // 重组堆:40,6,20,3,5,7 大根堆,调用 push_heap 先确保先前的 vertor 是个堆    push_heap(numbers.begin(), numbers.end());    // 移除堆顶元素,需要把 numbers 中的尾部元素移除,不会自动移除    pop_heap(numbers.begin(), numbers.end());    numbers.pop_back();}

栈 stack

栈是一种先进后出的数据结构,C++ 底层使用双端队列实现。在以前最小栈算法中我们详细介绍了这种数据结构。图解最小栈(LeetCode155. Min Stack)

#include <stack>void testStack() {    stack<int> s;    s.push(1);    s.pop();    cout << "top=" << s.top() << endl;    s.size();}

映射 map、unordered_map

map 是一种保存 key 和 vaule 的数据结构,key 是唯一的。C++ 中提供了有序的 map 和无序的 map 「unordered_map」。

#include <unordered_map>#include <map>void testMap() {    // 初始化    map<string, string> m;    pair<map<string, string>::iterator, bool> ret_iter =     m.insert(pair<string, string>("name", "lefe"));    if (ret_iter.second == false) {        cout << "name have existed" << endl;    }    // 初始化    map<int, string> m2 = {        {2014, "iOS"},        {2015, "Android"},    };    // 单值插入    m["name"] = "wsy";    // 多值插入    m.insert({{"age", "20"}, {"from", "nmg"}});    cout << "size = " << m.size() << endl;    // 使用迭代器删除    m.erase(m.begin());    // 查找    map<string, string>::iterator find_iter = m.find("from");    if (find_iter != m.end()) {        cout << "find" << endl;    }    // 遍历, key 是有序的    for (pair<string, string> v : m) {        cout << v.first << " = " << v.second << endl;    }    // 删除全部元素    m.clear();}

pair

pair中保存了两个值,这两个值的类型可以是任意类型,也可以不同。通过 first 和 second 来获取对应的值。

void testPair() {    pair<string, string> p = {"name", "lefex"};    // 通过first 和 second 来获取第一个和第二个值    cout << p.first;    cout << p.second;}

元组 tuple

它是 pair 的扩充版,可以存储多个不同类型的元素。

void testTuple() {    pair<string, string> p = {"name", "lefe"};    // 创建一个 tuple,类型为 <strinng, int, double, pair>    auto my_tuple = make_tuple("name", 20, 10.3, p);    // 获取第一个元素    cout << "0 = " << get<0>(my_tuple) << endl;    // 获取第二个元素    cout << "1 = " << get<1>(my_tuple) << endl;}

集合 set

集合中不能存储相同的元素,它底层基于平衡二叉树实现,在前面的文章中我们通过二分搜索树实现了 set。使用 BST 实现 Set。在 C++ 中 set 是有序的,同时也提供了无序的 set 「UnorderSet」。

#include <set>#include <unordered_set>void testSet() {    set<int> s {7, 3, 4};    s.insert(5);    // 3,4,5,7    for (auto v : s) {        cout << v << endl;    }        unordered_set<int> us {7, 3, 4};    us.insert(5);    // 7,3,4,5    for (auto v : us) {        cout << v << endl;    }}

总结

我们介绍了 C++ 语言本身提供的数据结构,有线性结构和非线性结构。这些数据结构在其它语言中几乎也会提供,而且底层实现基本一致,所有只有掌握了这些数据结构原理,在学习一门其它语言变的非常轻松,调用 API 时更爽。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励