常用数据结构与常用算法，

大家好，欢迎来到IT知识分享网。

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)，可选择直接插入排序或简单选择排序；元素初始状态基本有序时，选择直接插入排序或冒泡排序；元素较多时，选择快排、堆排或者归并，具体情况具体分析。