https://www.toutiao.com/a6634514748694069763/

2018-12-14 08:10:00

常用数据结构

1）元组

元组是一种静态的数据结构，无法修改，若要修改只能重新生成新的元组。

输出结果：

元组元素的获取是通过索引值去获得的；例如上面的tup1[0]返回apple；另外你可以直接把tup1一次性赋给多个值，例如上面的tup1一次性赋值给a,b,c,d; tup1[1:3]是对元组的截取，跟字符串的切片是一样，返回('banana', 'grape')

当然也是可以层次嵌套的；索引方法一样; y元组还支持直接通过+进行合并元组操作，其实是生成一个新的元组。

元组的遍历也是很简单的：

输出结果:

直接for遍历出来的是一个个元素，但最好还是建议先查询元素个数，然后根据索引值去获取value值，尤其对多层嵌套的元组来说，这种方式更好。

2）列表

列表是我们常用的，所以这一块一定要好好掌握：

输出结果：

列表的查询，遍历，和切片截取功能跟元组一样；添加元素可以一般是直接append("XXX")就往列表后面添加值，如果要指定位置添加元素，可以像lists.insert(4,"ouyang5")，在指定的索引值位置插入值；

移除可以用remove指定的元素，如果想要弹出最后一个元素，可以用pop方法；

列表的其他常用方法：

输出结果：

join是把列表转为字符串，用逗号隔开；sort是根据字典排序，即字母的数字编码大小排序；reverse是反转排序；最后一个clear就是清空列表；

3）字典

字典很多方法也是跟list是一样的：

输出结果：

字典是一个键值对集合，可以支持修改；排序方法，这里使用lambda函数，这里就先不讲了，后面会涉及这块知识，需要知道有这一块功能就行。

字典其他一些用法：

输出结果：

字典的浅复制copy和deepcopy在3.6版本的功能是一样的了，以前的版本，浅复制修改原字典，copy出来的字典也会跟着变化，但现在都不会了；因为原先copy出来的只是做了一个指引而已，内存地址一样。deepcopy就是新开辟一个内存空间。

字典的update很好用，他会合并两个字典，去掉重复的元素。

4）set集合

set集合里的元素是不能重复的，list里面的元素是可以重复的。

输出结果：

set的定义是在list列表的基础上的，去掉重复的，当然它的索引取值等方式是跟列表是一样的，这里就不在说，通样，它也有一个更新的功能，跟字典很类似。

总结：

这些集合是很常用，对常用的方法一定要熟悉，用的时候可以顺手拈来。

1. 常见数据结构

人们进行程序设计时通常关注两个重要问题，一是如何将待处理的数据存储到计算机内存中，即数据表示；二是设计算法操作这些数据，即数据处理。数据表示的本质是数据结构设计，数据处理的本质是算法设计。PASCAL之父，瑞士著名计算机科学家沃思（Niklaus Wirth）教授曾提出：算法+数据结构=程序。可以看出数据结构和算法是程序的两个重要组成部分，数据结构是指数据的逻辑结构和存储方法，而算法是指对数据的操作方法。尽快如C++的标准模板类STL已经设计好各种”轮子“，我们还是有必要了解轮子的构造的，这样我们就具备了因地制宜的能力，根据具体场景选择合适的数据结构和算法去解决问题。

1.1 线性表

线性表按存储方式可分为顺序表和链表。线性表的基本运算是指对线性表的操作，常见的包括：求长度、置空表、遍历、查找、修改、删除、插入、排序等。此外还有复杂的运算，比如线性表的合并、反转、求中值、删除重复元素等。

顺序表对应数组，STL中vector也是这样实现的。顺序表的特点是元素按逻辑顺序依次存储在一块连续的存储空间中，故是一种随机存取结构。操作时间复杂度：查询、修改、求长度O(1)，插入、删除、遍历O(n)。

链表包括单链表、循环链表、双向链表和静态链表等。链表采用动态存储分配方式，需要时申请，不需要时释放。操作时间复杂度：插入、删除O(1)，查询、修改、遍历、求长度O(n)。空间性能方面，顺序表的存储空间是静态分配的，需提前确定其大小，更改的话容易造成浪费。适用于存储规模确定，不经常变更或变更不大的场合；动态链表是动态分配空间的，不容易溢出。适用于长度变化大的场合。但由于要存储指针，故空间利用率较低。

C++的STL中有很多和线性表相关的容器，如向量（vector)、列表（list）等顺序容器。

<pre name="code" class="cpp">//使用容器，要包含头文件
#include<vector>
using std::vector;
//定义向量对象
vector<int> ivec;      //定义向量对象ivec
vector<int> ivec1(ivec);  //定义向量对象ivec1，并用ivec初始化
vector<int> ivec2(n,i) ;  //定义向量对象ivec2,包含n个值为i的元素
vector<int> ivec3(n);    //定义包含n个值为0的向量
vector<int>::iterator it;  //定义迭代器，类比指针
vector<vector<int> > vivec; //定义二维向量，”>“之间要有空格

<span style="white-space:pre">    </span>向量vector常用接口可参见<a target=_blank href="http://www.cplusplus.com/reference/vector/vector/">向量vector常用接口</a>，列表list的操作与向量相似，具体可参见<a target=_blank href="http://www.cplusplus.com/reference/list/list/">列表list常用接口
</a>
 

2.2 栈、队列和串

栈（stack）是限定在尾部进行插入和删除操作的线性表。允许插入和删除操作的称为栈顶（top)，另一端称为栈底（bottom)。因此，栈的操作是后进先出原则进行的。栈的基本运算包括：置空栈、入栈、出栈、取栈顶元素和判空。由于栈是受限的线性表，故可以由顺序表和链表来实现。

队列也是受限的线性表。它只允许在一端插入，称为队尾（rear)；另一端删除，称为对头（front），在队尾插入称为入队，对头删除称为出队。基本运算包括：置空队、入队、出队、取队头和判队空。它也可以由顺序表或者链表来实现。

串也称字符串，是由字符构成的有限序列。串中任意个连续字符构成的串称为子串，原串称为主串。前缀子串指第一个字符到某个字符构成的子串，后缀子串是某个字符到最后一个字符构成的子串。串的基本操作包括：赋值、串连接、求长度、求子串、比较串大小、插入、修改、删除等。串的模式匹配算法包括朴素模式匹配算法、KMP算法和BM算法等，需要研究一下。

此外，还有多维数组和广义表、树（二叉树、B-tree、红黑树等）和图，这里不做详解，今后再做总结。

2.常见算法

常见算法有查找和排序两种，其中查找是计算机数据处理经常用到的一种重要应用，当需要反复在海量数据中查找制定记录时，查找效率成为系统性能的关键。查找算法分为静态查找和动态查找，其中静态查找包括：顺序查找、二分查找和分块查找；动态查找包括：二叉排序树和平衡二叉树。此外还有理论上最快的查找技术——散列查找。这里只给出二分查找的代码。排序的目的是便于查找，比如电话号码查找、书的目录编排、字典查询等。常用的排序算法有：插入排序、冒泡排序、堆排序、选择排序和归并排序等，它们的性能对比见下图。

2.1 二分查找

二分查找又称折半查找，它要求待查序列按关键码有序。它的基本思想是先确定待查记录所在的区间，然后逐步缩小范围直到找到或找不到该记录为止。折半查找要求线性表用顺序表作为存储结构，它特别需要注意的是边界控制的问题。该算法C++描述如下：

int Search_Bin(int a[], int n, int target)//a[0]不用，a[1]~a[n]存储数据
{
    int low = 1;
    int high = n;
    while(low<=high)
    {
        int mid = low+(high-low)/2; //防止溢出
        if(a[mid]==target) return mid;
        else if(a[mid]>target) high=mid-1;
        else low=mid+1;
    }
    return 0;
}
 

2.2 直接插入排序

直接插入排序的原理可类比打牌时整理手中牌的过程，即不断地将新来的元素插到有序序列的合适位置。它是一种稳定的排序算法，特别适合于待排序序列基本有序的情况。该算法C++描述如下：

void InsertSort(int r[],int n) //r[0]不用，n为元素个数
{
    for(int i=2;i<=n;i++) //从2~n循环，共n-1趟排序
    {
        if(r[i]<r[i-1])
        {
            r[0]=r[i];
            r[i]=r[i-1];
        }
        for(int j=i-2;r[j]>r[0];j--) //边查边后移
            r[j+1]=r[j];
        r[j+1]=r[0];
    }
}
 

2.3 冒泡排序

冒泡排序的方法是在待排序的元素中选择两个相邻的元素进行比较，反序则交换，直至没有反序为止。为了减少记录的重复比较，这里给出改进版的起泡排序，它是一种稳定的排序算法。

//普通版
void BubbleSort(int r[],int n)
{
    for(int i=1;i<n;i++) //n-1 趟
    {
        for(int j=1;j<=n-i;j++) //内循环，每一趟减少一个比较元素
        {
            if(r[j]>r[j+1]) //相邻元素比较，交换
            {
                r[0]=r[j];
                r[j]=r[j+1];
                r[j+1]=r[0];
            }
        }
    }
}
//改进版
void BubbleSort(int r[],int n)
{
    int pos=n;
    while(pos!=0)
    {
        int bound=pos; //比较边界，之后的为有序，无序比较
        int pos=0;
        for(int i=1;i<bound;i++)
        {
            if(r[i]>r[i+1])
            {
                pos=i; //记录打破有序的位置
                r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];
            }
                
        }
    }
}

2.4 快速排序

快速排序是起泡排序的改进算法，由于起泡排序是在相邻位置进行的，故要比较移动多次才能到达目的地，而快排元素的比较和移动是从两端向中间进行的，移动的距离比较远，更靠近目的地，因此效率较高。

int Partion(int r[],int first,int end)
{
    int i=first;
    int j=end;
    int pivot=r[i];
    while(i<j)
    {
        while(i<j && r[j]>pivot) j--; //右侧扫描，不符合条件左移
        r[i]=r[j];
        while(i<j && r[i]<pivot) i++; //左侧扫描，不符合条件右移
        r[j]=r[i];
    }
    r[i]=pivot;
}
void Qsort(int r[],int i,int j)
{
    if(i<j)
    {
        int pivotloc = Partion(r,i,j);//每趟排好一个元素
        Qsort(r,i,pivotloc-1);
        Qsort(r,pivotloc+1,j);
    }
}

2.5 简单选择排序

选择排序的基本方法是：每趟选择待排序序列中关键码最小的元素，顺序添加到已排好序的有序序列后面，直到全部记录排序完毕。

void SelectSort(int r[],int n)
{
    for(int i=1;i<n;i++) //n-1趟排序
    {
        int index=i;
        for(int j=i+1;j<=n;j++)
        {
            if(r[j]<r[index])
            {
                index=j; //记录最小元素的索引
            }
        }
        if(index!=i) //若r[i]即为最小，无序交换
        {
            r[0]=r[i];r[i]=r[index];r[index]=r[0];
        }
    }
}
 

2.6 堆排序

堆排序通过构造大根堆或者小根堆的数据结构来记录简单选择排序中前一趟的比较结果，从而减少比较次数，提高整个排序的效率。这里以大根堆为例，给出堆排序算法的C++描述。

void Sift(int r[],int k,int m) //用数组记录堆，k是要调整的节点，通过调整使得满足堆的性质
{
    int i=k,j=2*i;//初始化，找到k的左孩子
    while(j<=m)
    {
        if(j<m && r[j]<r[j+1]) j++;//寻找左右孩子中较大的一个
        if(r[i]>r[j]) break;//满足条件，跳出
        else
        {
            r[0]=r[i];
            r[i]=r[j];
            r[j]=r[0];
            i=j; j=2*i;//比较节点下移
        }
    }
}
void HeapSort(int r[],int n)
{
    for(int i=n/2;i>=0;i--) //构建堆
        Sift(r,i,n);
    for(int i=n;i>1;i--)
    {
        r[0]=r[1];r[1]=r[i];r[i]=r[0];//输出堆顶元素
        Sift(r,1,i-1); //调整使满足堆的性质
    }
}
 

2.7 归并排序

归并排序的基本思想是：将两个或两个以上的有序序列归并成一个有序序列.

//归并两个有序序列
void Merge(int r[],int r1[],int s,int m,int t)
{
    int i=s,j=m+1,k=s;
    while(i<=m && j<=t)
    {
        if(r[i]<r[j])
            r1[k++]=r[i++];
        else
            r1[k++]=r[j++];
    }
    while(i<=m) r1[k++]=r[i++];
    while(j<=t) r1[k++]=t[j++];
}
//递归归并
void MergeSort(int r[],int r1[],int s,int t)
{
    if(s==t) r1[s]=r[s];
    else
    {
        int m=(s+t)/2;
        MergeSort(r,r1,s,m);
        MergeSort(r,r1,m+1,t);
        Merge(r1,r,s,m,t);
    }
}

2.8 小结

迄今为止，排序算法还有很多。在常见的算法中，就时间性能而言，在希尔排序、堆排序、快速排序和归并排序算法中，快速排序被认为是最快的一种，而在待排序元素个数比较多的情况下，归并排序较堆排序更快。就稳定性而言，直接插入排序、冒泡排序和归并排序是稳定的排序算法，而简单选择排序、快排和堆排是不稳定的。元素较少时（n<50)，可选择直接插入排序或简单选择排序；元素初始状态基本有序时，选择直接插入排序或冒泡排序；元素较多时，选择快排、堆排或者归并，具体情况具体分析。

• 前言
  所有的容器归根到底都是内存空间的排列方式和在空间上施加各种各种不同的限制所得的。空间排列方式只有线性和链式两种方式，链式是通过记录每一个数据的地址来实现查找下一位数据的。而每一个容器所具有的特性就决定了它所适用的情况，总的来看容器常用的无非是增删改查操作，下面将从适用场景、常用操作来进行总结。

• array数组
  内存空间为连续的一段地址，适用于提前已知所要存储的数据类型和数量、进行大量的查、改操作，不适用于含有大量交换、删除、增加数据的操作，该容器无法动态改变大小，所以说提前已知存储数据类型和数量。图片介绍了数组的初始化、赋值、遍历、获取大小、获取特定位置数据的方法。
  

• queue队列
  该容器内存结构最好为链式结构，最知名的特点是先进先出，能动态调整大小，适用于包含大量增、删操作的情况，但不适用于含有大量查找操作的数据。图片介绍了队列初始化、赋值、弹出操作。
  

• stack 栈
  栈在内存上可为连续或者链式，于队列相反的是它为先进后出，适用于压栈出栈操作，如可用于图的遍历、递归函数的改写等，图片介绍了栈的创始化、压栈、出栈等操作。
  

• list 链表
  链表在内存结构上为链式结构，也就决定它可以动态增加，适用于包含大量增加、删除的应用，但不适用于包含大量查询的操作，图片介绍了链表的创建、添加数据、删除数据、获取数据等操作。
  

• map
  map为关联式容器，提供一对一服务，每个关键字在容器中只能出现一次，适用于一对一服务。
  

• set 集合
  set集合最大的特点是里面的元素按序排列不重复，图片演示集合初始化、插入、删除、查找等操作。
  

• vector向量
  vector向量和array不同，它可以根据数据的大小而进行自动调整，图片仅展示初始化、插入、删除等操作。
  

• 总结
  这些容器在http://www.cplusplus.com/网站都有详细的介绍，看文档很容易学会它们，毕竟都把实现过程都隐藏起来了，只需要多加实践即可掌握这些容器的使用方法，多练多操作。