Part I ：课件

绪论

数据结构的应用：

Web搜索系统：网页抓取，网页信息提取，建立倒排文档，查询输入，网页查找，网页输出

其中，网页信息提取需要用到串和树形结构。

倒排文档需要用到数组、链表、查找表、排序。

数据：对信息的一种符号表示，指所有能输入到计算机中进行程序处理的符号的总称。

例：如整型、实型等数据类型，声音、图像、视频等符号类型。
以数据元素（记录）为基本单位：数据元素通常作为整体处理。
- 由若干数据项组成。数据项是组成数据元素的具有独立含义的最小单位。
- 如“人与各器官”就是数据元素与数据项的关系。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作；
包含以下三元素：（D=数据元素的有限集合（数据对象），R=D上关系的有限集合，P=对D的基本操作的集合）
- 逻辑结构：数据元素间的逻辑关系；Data_structure = (D,R)。
- 存储表示（存储结构/物理结构）：数据元素及其关系在计算机存储内的表示（存储映像）；反映数据元素本身及其之间的关系。
  
  一般为顺序存储结构/链式存储结构；还有索引存储（建立索引表）和散列存储（关键码->存储地址）。
- 数据的运算：对数据施加的操作；定义在数据结构之上的对数据操作的总称。
  
  包括建立、清除（置空）、求长、判空、判满、获取、更新/修改、插入、删除、查找、遍历。
分为四种：集合结构、线性结构、树形结构、图形结构。
表现形式：
- 逻辑抽象模型 → 抽象数据类型（ADT）（如链表）=（D,R,P）。
- 具体实现：C/C++，Java

数据类型：一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称。

程序数据语言中，变量数据类型规定了其取值范围和可用操作。
看作程序设计语言中已实现的数据结构。
抽象数据类型：抽取问题本质，解决同类问题；层次化设计，统一接口，内部实现与外部特性分离。

算法：解决方法的准确而完整的描述，一系列解决问题的清晰指令；定义了输入实例上的操作。

描述方法：自然语言，图形（N-S(方块)，流程），算法，形式语言（数学）。
设计目标：正确性、可读性、健壮性、高效性。
特性：有穷性（有穷步骤，每步有穷时间）；确定性（每步含义确切）；可行性（语句可行，总体解决问题可行）；输入零个或多个；输出零个或多个（与输入有特定关系）。
效率：
- 时间复杂度：
  - 评价方法包括：实验性测试（需实现算法，只能测试有限输入，依赖硬件和软件环境）、综合分析（调用实例图/递推方程）
  - 最坏情况（最常使用，为上界，常发生）；平均（计算困难，通常与最坏处于同一水平）；最优
  - 渐近分析：忽略常数和低次项，考虑规模足够大的情况。
    - O：大O记号，最坏情况，渐近上界，$$f,g定义在非负整数上,f(n)=O(g(n))，如果\exist 常数c以及n_0,满足对\forall n \geq n_0,有f(n) \leq cg(n)$$。
      
      $$O(1) < logn < \sqrt{n} < n < nlogn < n^2 < n^3 < 2^n < n!$$
      
      多项式复杂度：$$O(n^k),k\geq 1$$；指数复杂度：$$O(a^n), a> 1$$。
    - $$\Omega(f(n))$$：Big Omega，最优情况，渐近下界，$$f,g定义在非负整数上,f(n)=\Omega(g(n))，如果\exist 常数c以及n_0,满足对\forall n \geq n_0,有f(n) \geq cg(n)$$
    - $$\Theta(f(n))$$：Big Theta，渐近紧界，$$f,g定义在非负整数上,f(n)=\Theta(g(n))，如果\exist 常数c以及n_0,满足对\forall n \geq n_0,有c_1g(n) \leq f(n) \leq c_2g(n)$$;
      
      $$f(n)=\Theta(g(n)) \iff f(n)=O(g(n)) & f(n)= \Omega(g(n))$$。
- 空间复杂度：每次基本操作至多涉及常数规模的存储空间，故时间复杂度是空间复杂度的上界。
程序：基于编程语言的算法实现=数据结构+算法。
算法基于数据结构，两者相辅相成（住房的布局与装修）。

向量

线性表：由$$n \geq 0$$个数据元素构成的有限序列，记作$$(a_0,a_1,…a_{n-1})$$。

逻辑关系：邻接关系，除第一个元素外每个元素有且仅有一个直接前驱，除最后一个元素外每个元素有且仅有一个直接后继。

向量：线性表元素相继存放在一片连续的存储空间（线性表基于数组的存储表示）。

数组	向量
高级程序设计语言内置的数据类型	数组的抽象和泛化，由模板类实现
通过下标访问	通过秩访问（若元素e有r个前驱元素，其秩为r）
只能读取和修改	带有很多操作接口

重点：

秩：前驱元素个数
find(e):等于e且秩最大（从后往前找）
search(e)：<=e且秩最大（从后往前找）
    
deduplicate(); uniquify();

put(r, e); insert(r, e);

实现：

typedef int Rank;
#define DEFAULT_CAPACITY 3

template <typename T>
class Vector {
protected:
    Rank _size;  //当前规模
    int _capacity;  //容量
    T* _elem;
public:
    //构造函数
    Vector (int c = DEFAULT_CAPACITY, int s = 0, T v = 0) {  // 容量为c，规模为s，所有元素初始为v
        _elem = new T[_capacity = c];
        for (_size = 0; _size < s; _elem[_size++] = v) ;
    }
    //基于复制构造
    void copyFrom( T const* A, Rank lo, Rank hi) {
        _elem = new T[_capacity = 2 * (hi - lo)]; _size = 0;
        while (lo < hi)
            _elem[_size++] = A[lo++];
    }
    Vector (T const* A, Rank n) {  // 注：T const* = const T* = 常量T的指针
        copyFrom(A, 0, n);
    }
    //赋值
    Vector<T> operator = (Vector<T> const& V) {
        if (_elem)
            delete []_elem;
        copyFrom(V._elem, 0, V.size());
        return *this;
    }
    //析构
    ~Vector() {
        delete []_elem;
    }
    //扩充（在已经填满的时候就会扩）
    void expand() {
        if (_size < _capacity) return;
        if (_capacity < DEFAULT_CAPACIITY) _capacity = DEFAULT_capacity;
        T* oldElem = _elem;
        _elem = new T[_capacity <<= 1];
        for (int i = 0; i < _size; i++)
            _elem[i] = oldElem[i];
        delete []oldElem;
    }
    //重载[]
    T& operator[] (Rank r) const {
        return _elem[r];
    }
    //置乱
    void permute () {
        for (int i = _size; i > 0; i--)
            swap(_elem[i-1], _elem[rand() % i]);
    }
    //顺序查找，秩最大的为e的元素位置，否则返回lo-1
    //最坏O(n),最好O(1),平均O(n)
    Rank find(T cosnt& e, Rank lo, Rank hi) const {
        while ((lo < hi--) && (e != _elem[hi]));
    }
    //插入
    //最坏O(n),最好O(1),平均O(n)
    Rank insert(Rank r, T const& e) {  // assert 0 <= r <= size
        expand();
        for (int i = _size; i > r; i--)
            _elem[i] = _elem[i-1];
        _elem[r] = e; _size++;
        return r;
    }
    //删除区间[lo, hi)
    //最坏O(n),最好O(1),平均O(n)
    int remove(Rank lo, Rank hi) {
        if (lo == hi) return 0;
        while( hi < _size )
            _elem[lo++] = _elem[hi++];
        _size = lo;
        shrink();
        return hi - lo;
    }
    int remove(Rank r) {
        remove(r, r+1);
    }
    //唯一化
    //总体最坏复杂度O(n^2)
    int deduplicate() {
        int oldSize = _size;
        Rank i = 1;
        while (i < _size)
            (find(_elem[i], 0, i) < 0) ? i++ : remove(i);  //在前缀中找雷同
        return oldSize - _size;
    }
    //遍历
    template <typename VST>
    void traverse(VST& visit) {
        for (int i = 0; i < _size; ++i) visit(_elem[i]);
    }
    //判序
    //返回逆序相邻元素对的总数,n=0则有序
    //O(n)
    int disordered() const {
        int n = 0;
        for (int i = 1; i < _size; ++i)
            if (_elem[i - 1] > _elem[i]) n++;
        return n;
    }
    
    //归并排序
    void mergeSort (Rank lo, Rank hi) {
        if (hi - lo <= 1) return;
        int mi = (lo + hi) / 2;
        mergeSort(lo, mi); mergeSort(mi, hi);
        merge(lo, mi, hi);
    }
    void merge(Rank lo, Rank mi, Rank hi) {
        T* A = _elem + lo;
        int lb = mi - lo; T* B = new T[lb];
        for (Rank i = 0; i < lb; B[i] = A[i++]);
        int lc = hi - mi; T* C = _elem + mi;
        for (Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) {
            if ((j < lb) && ( !(k < lc) || (B[j] <= C[k]))) A[i++] = B[j++];
            if ((k < lc) && ( !(j < lb) || (C[k] < B[j]))) A[i++] = C[k++];  //注意到使用小于，故是稳定排序
        }
        delete []B;
    }
    
    //插入排序
    void insertSort(Rank lo, Rank hi) {
        for (int j = lo+1; j < hi; j++) {
            T key = _elem[j];
            int i = j - 1;
            while (i >= lo && _elem[i] > key) { // 是>所以是稳定排序
                _elem[i+1] = _elem[i];
                i--;
            }
            _elem[i+1] = key;
        }
    }
    
    //冒泡排序，顺次交换相邻元素
    void bubbleSort(Rank lo, Rank hi) {
        int times = 0; bool exchange = true;
        int nSort = hi - lo;
        while (times < nSort && exchange) {  //至多n-1趟冒泡
            exchange = false;
            for (int j = hi - 1; j > lo + times; j--)
                if (_elem[j-1] > _elem[j]) {
                    swap(_elem[j-1], _elem[j]);
                    exchange = true;
                }
            times++;
        }
    }
    
    //选择排序，选出最大/最小
    void selectionSort(Rank lo, Rank hi) {
        while (lo < --hi)
            swap(_elem[max(lo, hi)], _elem[hi]); //直接交换
    }
    Rank max(Rank lo, Rank hi) {
        Rank mx = hi;
        while (lo < hi--)
            if (_elem[hi] > _elem[mx]) mx = hi;  //严格大，故总给出秩最大的
        return mx;
    }
    
    //有序向量唯一化
    //低效版，最坏O(n^2)
    int uniquify() {
        int oldSize = _size; int i = 1;
        while (i < _size)
            _elem[i-1] == _elem[i] ? remove(i) : i++;
        return oldSize - _size;  //向量规模变化量
    }
    //高效版
    int uniquify() {
        Rank i = 0, j = 0;
        while (++j < _size)
            if (_elem[i] != _elem[j])
                _elem[++i] = _elem[j];
        _size = ++i;
        shrink();
        return j - i;
    }
    
    //二分查找
    //版本A:三分支，多个命中不能保证秩最大，查找失败不能指示失败位置
    //查找长度：有序向量的比较操作的次数
    //理论证明：平均查找长度为O(1.5*log2n)
    //利用左分支比较次数少于右分支，可以通过加长前区域长度，如改为fibonacci查找，变为O(1.44*log2n)
    static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
        while (lo < hi) {
            Rank mi = (lo + hi) >> 1;
            if ( e < A[mi] ) hi = mi;
            else if (A[mi] < e) lo = mi + 1;
            else return mi;
        }
        return -1;
    }
    //版本B：在有序向量[lo,hi)内查找元素e
    //多个命中能返回最大秩，但不能提示失败位置
    static Rank binSearch (T* A, T const& e, Rank lo, Rank hi) {
        while (1 < hi - lo) {
            Rank mi = (lo + hi) >> 1;
            (e < A[mi]) ? hi = mi : lo = mi;
        }
        return (e == A[lo]) ? lo : -1;
    }
    //版本C
    //能返回最大秩，查找失败返回失败位置，返回了<=e的元素的最大秩
    //可以这么理解：查找区间变为A[lo-1,hi],其中A[lo-1]=-\infty, A[hi]=+\infty
    //始终有A[lo-1] <= e < A[hi]
    static Rank binSearch (T* A, T const& e, Rank lo, Rank hi) {
        while (lo < hi) {
            Rank mi = (lo + hi) >> 1;
            (e < A[mi]) ? hi = mi : lo = mi + 1;
        }
        return --lo;
    }
}

关于扩容

扩容即为动态空间管理。

每次扩容一倍：总复杂度为各次内存搬移大小之和，分摊复杂度为分摊到每个被扩充的空间上。

每次翻倍：总复杂度=（1+2+4+…+N）=2N，分摊复杂度=2N/N=2。

每次固定：总复杂度=x+2x+…+N=N/2*N/X=N^2/2x，分摊复杂度=N/2x。

关于各种排序的时间/空间复杂度

链表（列表）

按存储结构分，一种序列（线性表）的实现方式：元素的物理存放位置不是线性，而是任意。

struct ListNode{
    int data;
    ListNode* next;
    ListNode(int k, ListNode* next_ = NULL)
        : data{k}, next{next_} {}
}
class List{
private:
    ListNode* first;  //额外的表头指针
    List() { first = new LinkNode; }
}

插入

主要时间来源于访问。

表头插入特殊，故可以增加额外的表头结点。

// 0返回表头
// <0返回NULL
LinkNode* List::Locate(int i) {
    if ( i < 0) return NULL;
    ListNode* current = first; int k = 0;
    while (current != NULL && k < i) {
        current = current->next; k++;
    }
    return current;  //超出地址会返回NULL
}

// 插入在第i个节点之后
bool List::Insert(int i, int &x) {
    ListNode* current = Locate(i);
    if (current == NULL) return false;
    ListNode* newNode = new ListNode(x);
    newNode->next = current->next;
    current->next = newNode;
    return true;
}

删除

空表/表头特殊。

定位置被删除节点的前继节点。

//删除第i个元素
bool List::Remove(int i, T& x) {
    ListNode* current = Locate(i-1);
    if (current == NULL) return false;
    ListNode* del = current->next;
    current->next = del->next;
    delete del;
    return true;
}

双向列表带表头

typedef int Rank;
#define ListNodePosi(T) ListNode<T>*
template <typename T>
struct ListNode{
    T data;
    ListNodePosi(T) pred;
    ListNodePosi(T) succ;
    
    ListNodePosi(T) insertAsPred(T const& e) {
        ListNodePosi(T) x = new ListNode(e, pred, this);
        pred->succ = x;
        pred = x;
    }
    ListNodePosi(T) insertAsSucc(T const& e);
}
template <typename T>
class List{
private:
    int _size;
    ListNodePosi(T) header;  //头尾哨兵节点
    ListNodePosi(T) trailer;
protected:
    void init();
    int clear();
    void copyNodes(ListNodePosi(T) p, int n);
public:
    List() { init(); }
    List( List<T> const& L);
    List(List<T> const& L, Rank r, int n);
    List (ListNodePosi(T) p, int n);
    ~List() {  //O(n)
        while(0 < _size) remove(header->succ);
        delete header;
        delete trailer;
    }
    
    T remove(ListNodePosi(T) p) {
        T e = p->data;
        p->pred->succ = p->succ;
        p->succ->pred = p->pred;
        delete p;_size--;
        return e;
    }
    
    //无序列表查找
    //在p的n个真前驱中，找到等于e的秩最大者
    //p可能为trailer
    //O（n）
    ListNodePosi(T) find(T const& e, int n, ListNodePosi(T) p const) {
        while(0 < n--)  //n次
            if (e == (p = p->pred)->data) return p;
        return NULL;
    }
    
    //有序列表查找
    ListNodePosi(T) search(T const& e, int n, ListNodePosi(T) p) const {
        while (0 <= n--)
            if ((p = p->pred)->data <= e) break;  //最左关键码为-inf，故最后一次必然跳出
        return p;
        //失败会返回左边界的前驱（可能是header）
    }
    
    //唯一化：O(n^2)
    int deduplicate() {
        if (_size < 2) return 0;
        int oldSize = _size;
        ListNodePosi(T) p = header; Rank r = 0;
        while (trailer != (p = p->succ)) {
            ListNodePosi(T) q = find(p->data, r, p);
            q ? remove(q) : r++;
        }
    }
    
    //有序列表唯一化：高效版
    //反复考察相邻节点，O(n)
    int uniquify() {
        if (_size < 2) return 0;
        int oldSize = _size;
        ListNodePosi(T) p = first();
        ListNodePosi(T) q;
        while (trailer != (q = p->succ))
            if (p->data != q->data) p = q;
        	else remove(q);
        return oldSize - _size;
    }
    
    //插入排序
    //稳定
    //最好O(n),最坏O(n^2),总体O(n^2)
    void insertionSort(ListNodePosi(T) p, int n){
        for (int r = 0; r < n; r++) {
            insertA(search(p->data, r, p), p->data);  //新建了以p的数据为数据的节点插入
            p = p->succ; remove(p->pred);
        }
    }
    
    //选择排序
    //稳定,O(n^2)
    void selectionSort(ListNodePosi(T) p, int n) {
        ListNodePosi(T) head = p->pred;
        ListNodePosi(T) tail = p;
        for (int i = 0; i < n; ++i) tail = tail->succ;
        //待排序区间为（head, tail）
        while(1 < n) {
            ListNodePosi(T) max = selectMax(head->succ, n);//歧义时后者优先
            insertB(tail, remove(max));
            tail = tail->pred; n--;
        }
    }
    
    //归并排序：**就地排序**
    //p起n个元素，与L中q起m个元素归并
    //O（m+n）
    void merge(ListNodePosi(T) & p, int n, List<T> &L, ListNodePosi(T) q, int m ) {
        ListNodePosi(T) pp = p->pred;
        while (0 < m)  //q尚未移出区间
            if (0 < n && p->data <= q->data) {
                if (q == (p = p->succ)) break; n--; 
            }
       		else {
                insertB(p, L.remove((q = q->succ)->pred)); m--;
            }
        p = pp->succ;
    }
    void mergeSort(ListNodePosi(T) &p, int n) {
        if (n < 2) return;
        int m = n >> 1;
        ListNodePosi(T) q = p;
        for (int i = 0; i < m; ++i) q = q->succ;
        mergeSort(p, m);
        mergeSort(q, n-m);
        merge(p, m, *this, q, n-m);
    }
};

T& List<T>::operator[] (Rank r) const{
    ListNodePosi(T) p = first();
    while(0 < r--) p = p->succ;
    return p->data;
}

求长：size();
首/尾节点：first/last();
首/末节点插入:insertAsFirst/Last(e);
作为当前节点的前/后插入:insertB/A(p, e);
删除p位置的节点，返回数值:remove(p);
查找目标元素e，失败返回NULL:find(e);
遍历：traverse();
判是否非降序：disordered();
排序：sort();
去重：deduplicate();

有序列表特殊去重：uniquify();
有序列表返回不大于e且秩最大的元素：search(e);

列表无法二分查找！

所有排序都就地，都稳定。归并更适合用列表实现（就地）。

从存储结构分类是得到向量和列表，下面对运算做一定的约束。