数据结构入门讲座

201707 （ACM）数据结构

参考资料

基本数据结构

• 数组
  
  • 搜索、插入、刪除的時間複雜度都是 O(N) 。
  • 数组经过排序之后可以进行二分搜索，复杂度 O(logN) 。
• 动态数组
  
  • 根據数据规模，調整数组大小，稱作动态数组。每當数组装满，就另外建立兩倍大的新数组，將数据搬到新数组，捨棄原数组。搬移的總時間複雜度是 O(1 + 2 + 4 + 8 + ... + N) = O(2N - 1) = O(N) 。
  • 可以直接使用 STL 的 vector 。
    
    • 头文件#include<vector>
    • 创建vector对象，vector<int> vec;
    • 尾部插入数字：vec.push_back(a);
    • 使用下标访问元素，cout<<vec[0]<<endl;，下标是从0开始的。
    • 使用迭代器访问元素

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
cout<<*it<<endl;

• 
  
  • 
    
    • 插入元素：vec.insert(vec.begin()+i,a); 在第i+1个元素前面插入a;
    • 删除元素：vec.erase(vec.begin()+2); 删除第3个元素
    • vec.erase(vec.begin()+i,vec.end()+j); 删除区间[i,j-1];区间从0开始
    • 查询大小:cout<<vec.size()<<endl;
    • 清空:vec.clear();
    • 使用reverse将元素翻转：需要头文件#include<algorithm> reverse(vec.begin(),vec.end());
    • 使用sort排序：需要头文件#include<algorithm> sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).
    • 可以通过重写排序比较函数按照降序比较，如下：

bool Comp(const int &a,const int &b)
{
    return a>b;
}
sort(vec.begin(),vec.end(),Comp);

• 队列
  
  • 只对队头元素进行删除操作，插入元素只插入到队尾。
  • 插入、刪除需時 O(1) 。搜尋需時 O(N) 。
  • 可以直接使用 STL 的 queue 。
  • uva 10935（简单模拟）
• 栈
  
  • 只对栈顶元素进行删除操作，插入元素只插入到栈顶。
  • 插入、刪除需時 O(1) 。搜尋需時 O(N) 。
  • uva 101（简单模拟） uva 514（火车进站） uva 673（括号序列）
• 双端队列
  
  • 兩頭皆能插入與刪除。

排序

• 排序
  
  • 數字、字符都可以排序，因為電腦中的字符就是數字（請參照 ASCII 表）。一般数据也可以排序，只要数据裡的某個特定字段是數字，這個字段被稱作鍵值（ key ）。
• 排序原理
  
  • 排序的基本原理，當今只有兩種，一是對調（數字是實數），二是放置（數字必須是整數）。
  • 純粹透過對調來排序，已證明出时间复杂度最少是 O(NlogN) ，不可能更少了。
  • 純粹透過放置來排序，需要額外的空間來放置數字。比如计数排序。
• 选择排序 O(N^2)
  
  • 掃描一遍所有數字，找到最小值，挪至数组左端。返回处理尚未排序的 N-1 個元素。

void selection_sort(int array[], int N)
{
    for (int i=0; i<N; ++i) // N改為N-1更精準
    {
        // 從尚未排序的數字當中，找出最小的數字。
        // （它也是全部數字當中第i小的數字。）
        int min_index = i;
        for (int j=i+1; j<N; ++j)
            if (array[j] < array[min_index])
                min_index = j;
        // 把第i小的數字，放在第i個位置。
        swap(array[i], array[min_index]);
    }
}

• 冒泡排序 O(N^2)
  
  • 由左到右，相鄰兩兩比較，較大者往右挪，最後最大值會出現在陣列右端。遞迴處理尚未排序的 N-1 個元素。

void bubble_sort(int array[], int N)
{
    for (int i=0; i<N; ++i) // N改為N-1更精準
        for (int j=0; j<N-i-1; ++j)
            if (array[j] > array[j+1])
                swap(array[j], array[j+1]);
}

• 
  
  • 稍做改良：一旦排序好，便趕快結束。當資料很亂時，這麼做效益不彰。

void bubble_sort(int array[], int N)
{
    for (int i=0; i<N; ++i) // N改為N-1更精準
    {
        bool sorted = true;
        for (int j=0; i<N-j-1; ++j)
            if (array[j] > array[j+1])
            {
                swap(array[j], array[j+1]);
                sorted = false;
            }
        if (sorted) return;
    }
}

• 插入排序 O(N^2)
  
  • 由左到右，逐一把數字插入到目前已排过序的数组當中。
  • 需將大量數字往右挪，以騰出空間插入數字。

void insertion_sort(int array[], int N)
{
    for (int i=2; i<N; ++i)
    {
        int pivot = array[i];
        int j;
        for (j=i-1; j>=0; --j)
            if (pivot < array[j])
                array[j+1] = array[j];  // 先行往右挪
            else
                break;
        array[j+1] = pivot; // 插入
    }
}

• 归并排序 O(NlogN)
  
  • 運用分治的思想：待排序数组分成兩半，两半各排好序之后再合并起来。
  • 复杂度计算？
    
    • 长度为N的数组每次分成两半，那么只要分最多logN次，数组的长度就会变成1。
    • 每次归并的复杂度是 O(N)。
  • uva 10810（逆序数）
• 快排 O(NlogN)
  
  • 運用分治的思想：选定关键字，然後把数组分成大的一邊和小的一邊，两边再同样这样做。
  • uva 755
• 计数排序
  
  • 全部數字依其數值大小，放到相符位置。接著由小到大讀取各個位置的數字。
  • uva 484 uva 11462

void counting_sort(int array[], int N)
{
    // 歸類並標記
    int count[10000] = {0};
    for (int i=0; i<N; ++i)
        count[ array[i] ]++;
    // 計數陣列的索引值大小順序，正是元素大小順序。
    for (int i=0, k=0; k<N; ++i)
        while (count[i]--)
            array[k++] = i;
}

struct Data {int key, data;};
void counting_sort(Data* array[], int N)
{
    // 歸類並標記
    vector<Data*> count[10000];
    for (int i=0; i<N; ++i)
        count[ array[i]->key ].push_back( array[i] );
    // 索引值的大小順序，剛好也是元素的大小順序。
    for (int i=0, k=0; k<N; ++i)
        for (int j=0; j<count[i].size(); ++j)
            array[k++] = count[i][j];
}

• stl sort
  
  • 对结构体进行排序时，可以通过重载运算符定义优先级。
  • uva 482

struct Node {
    int a,b;
    bool operator < (const Node &tmp) const {
        if(a==tmp.a) return b<tmp.b;
        return a<tmp.a;
    }
}

• 一些和上面讲的没什么关系的题
  
  • uva 12192（二维矩阵中查找一个数）
    
    • 具体解析可以看这里（页面中 ctrl+F 查找关键字[Search in Sorted Matrix: Saddleback Search]）

集合

• 集合表示与操作
  
  • 数组/vector
  • 链表
  • bool数组。a[i]表示值为i的元素是否存在。
  • bitset
    
    • 因为只需要表示是否存在，所以每一个二进制位可以表示一个数是否存在。
    • c++自带stl bitset，具体用法可百度。
  • uva 10041 uva 496（判断集合间关系） uva 11218
• 并查集
  
  • 详解
  • uva 10158 uva 10583 uva 10608 uva 11987

int pre[N];
void init() {
    for(int i=0;i<N;++i) pre[i]=i;
}
int find(int x) {
    if(x==pre[x]) return x;
    return pre[x]=find(pre[x]);
}
void join(int x,int y) {
    int fx=find(x);
    int fy=find(y);
    pre[fx]=fy;
}

• 最小生成树Kruskal算法
  
  • 最小生成树：给定带边权图，求图中的边权和最小的一棵生成树
  • Kruskal算法
    
    • 将原图Graph中所有边按权值从小到大排序
    • 从权值最小的边开始遍历
      
      • 如果这条边连接的两个节点不在同一个连通分量中，加入这条边，并且把连接的两个节点用并查集联通
  • POJ 2485 cfgym 101252C

优先队列

• 优先队列：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。
• 可以用 STL 的 priority_queue 实现，也可以用堆实现。

#include<queue>
priority_queue<int> q;
for(int i=0;i<N;++i) {
    q.push_back(a[i]);
    cout<<q.top()<<endl;//输出堆中最大的元素
}
q.pop();//弹出堆中最大的元素

• foj 1327 uva 501 uva 11997

线段树

• 树上的每个节点对应一段区间，每个节点维护对应区间的信息。
• 详解及代码

树状数组

• 可以用来维护区间最值，代码比线段树短很多。
• 详解及代码