数据结构复习-第一部分

本系列文章为作者复习数据结构过程中的知识点总结、速通，欢迎补充

Written by SJTU-XHW

Reference: 张同珍老师 PPT | UNIkeEN

Chapter 1 数据结构绪论

1.1 数据结构逻辑分类

集合结构：次序任意，重视归属关系；
线性结构：有序序列，有前驱、后继关系；
树状结构：层次关系，分根元素-其他元素；
图状结构：一般的逻辑结构，不限前驱和后继；

1.2 逻辑结构基本运算类型

创、清、增删改查、访问、遍历

1.3 逻辑结构的运算实现

存储结点、数据元素间关系（顺序实现、链接实现、散列实现、索引存储）、附加信息

总结：一个数据结构就是针对某一逻辑结构讨论数据的存储实现和运算实现

1.4 算法优劣因素分析

正确性、易读性、健壮性、高效率（时间、空间性能）

时间复杂度：算法所需运算量和问题规模间的关系
- 时间复杂度因为会与被处理数据的分布有关，所以会有最好最坏和平均的说法
- 重要易错点：答题时注意除非说明，必须同时写上：最好、最坏、平均时间复杂度，少一个都不全面
- 算法运算量计算：不通用性
  $规定标准操作 \Longrightarrow 找出在n个数据规模下执行标准操作的次数\Longrightarrow 得到运算量f(n)和规模n之间的关系$
- 渐进时间复杂度：通用性
  $\begin{aligned} &大O表示法：若存在两个正常数\space c、N_0，当\space N\ge N_0时，有\space T(N)\le cF(N)，则记\space T(N)=O(F(N))\\ &大\Omega表示法：理解为与大O表示法相反的下限\\ &大\Theta表示法：理解为上下界数量级相等的表示\\ &小o表示法：理解为上下界不相等的\textbf{上界}表示\\ \end{aligned}$
- 知识补充：多项式时间算法$O(1)\lt O(log\space N)\lt O(N)\lt O(N\space log\space N)\lt O(N^c),\space c\in\mathbf{R}$
  
  和指数时间算法：$O(2^N)\lt O(N!)\lt O(N^N)$（NP问题可以认为是非多项式时间算法能解决的问题）
- 渐进时间复杂度计算定理
  $\begin{aligned} &1.\space 求和定理：\textbf{串行运行}时间\space T_1(n)+T_2(n)=O(max\{f(n),g(n)\})\\ &2.\space 求积定理：\textbf{嵌套循环}的时间\space T_1(n)\times T_2(n)=O(f(n)\times g(n))\\ &3.\space 推论：简单语句\space O(1)、分支语句相当于【条件串行分支的最大复杂度】、循环相当于【循环体嵌套循环次数】 \end{aligned}$

空间复杂度：辅助存储空间与问题规模间的关系

易错点警示：

1. 链表的指针所占用的空间不算辅助空间：因为这是被处理的数据结构本身的空间；

2. 递归调用的系统栈算辅助空间：讨论递归算法的空间复杂度一定要注意系统栈的情况！

Chapter 2 线性表

2.1 零碎概念集合

线性结构的定义：n（n ≥ 0）个结点的有穷序列 $(a_0, a_1,…,a_{n-1})$

起始结点、终端结点、元素的序号/位置、直接前驱、直接后继、空表的定义
线性表的地位：处理线性结构的工具；
线性表的基本运算种类：创清、增删查、访问遍历、求长；
均摊分析��；

2.2 顺序实现的线性表

存储实现：数组是天然的线性结构（连续空间）【数组容量、数组指针、数组长度】

template <class T>
class seqList {
private:
    T* data;
    int maxSize;
    int length;
    
    void doubleSpace();
    
public:
    seqList(int capacity=10);
    ~seqList() { if (data) delete[] data; }
    bool isempty() const;
    int length() const;
    void clear();
    void insert(int i, const T& dt);
    void remove(int i, T& x);
    T visit() const;
    void traverse() const;
};

运算实现

创建运算：开辟空间、设定表长和规模

template <class T>
seqList<T>::seqList(int capacity): length(0), maxSize(capacity) {
    data = new T[capacity];
}

清空运算$\textbf{O(1)}$：直接将表长置0

1 2	template <class T> void seqList<T>::clear() { length = 0; }

判空运算$\textbf{O(1)}$：直接判断表长不为0

1 2	template <class T> bool seqList<T>::isempty() const { return length == 0; }

插入运算$\textbf{O(1)}-\textbf{O(n)}-\textbf{O(n)}$：先看空间是否够，不够扩容，够依此向后移位；记得维护长度！！！

template <class T>
void seqList<T>::insert(int i, const T& dt) {
    if (length == maxSize) doubleSpace();
    for (int idx = length - 1; idx >= i; --idx) {
        data[idx + 1] = data[idx];
    }
    data[i] = dt; ++length;
}

扩容运算$\textbf{O(n)}$

template <class T>
void seqList<T>::doubleSpace() {
    T tmp = data;
    data = new T[maxSize * 2];
    for (int i = 0; i < length; ++i)
        data[i] = tmp[i];
    delete[] tmp;
    maxSize *= 2;
}

重点：均摊法分析：每过n、2n、…的时机，可能会进行 O(n) 的扩容。均摊下来，平均时间复杂度还是相当于单次插入的 O(n)。

删除运算$\textbf{O(1)}-\textbf{O(n)}-\textbf{O(n)}$：先看是否为空，不空则后面元素向前覆盖，记得维护表长！！！

template <class T>
void seqList<T>::remove(int i, T& x) {
    if (length == 0) throw noElementException();
    x = data[i];
    for (int idx = i + 1; idx < length; ++idx)
        data[i - 1] = data[i];
    --length;
}

访问和遍历$\textbf{O(n)}$：无需多言

template <class T>
T seqList<T>::visit(int i) const { return data[i]; }

template <class T>
void seqList<T>::traverse() const {
    for (int i = 0; i < length; ++i)
        std::cout << data[i] << ' ';
}

查找运算$\textbf{O(n)}$：”哨兵技巧“

template <class T>
int seqList<T>::find(const T& dt) const {
    for (int i = length - 1; i >= 0; --i)
        if (data[i] == dt) return i;
    return -1;
}

易错点
- 表长度值忘记维护；
- 混淆 length 和 maxSize 的意义；
- 检查异常处理；

2.3 链接实现的线性表

让每个结点保存相关的结点地址+本身数据，来保存结点之间的关系；

链接实现不仅可以用来表示线性结构，还能表示许多非线性结构，例如集合、树、图等；

避免了顺序表插入、删除的元素大规模移动；

动态存储；

单链表

存储实现：结点 = 数据+后继指针×1；【单链表头、单链表长（不必要）】

添加”头结点“以一般化一些特殊情况！

template <class T>
class SLinkedList {    //0-index.
private:
    struct sNode {
        T data;
        sNode* next;
        sNode() { next = 0; }
        sNode(T dt, sNode* n=0)
            : data(dt), next(n) {}
    };
    
    sNode* head;
    int length;
    // （注：此法无需存在，用前后指针法也行）
    sNode* move(int i) const;
public:
    SLinkedList();
    void clear();
    int length() const;
    bool isempty() const;
    void insert(int i, const T& dt);
    void remove(int i, T& x);
    T visit(int i) const;
    void travese() const;
    ~SLinkedList() { if (head) clear(); }
};

运算实现（含有哑结点）

创建运算：赋头指针、置表长；

template <class T>
SLinkedList<T>::SLinkedList() {
    head = new sNode(); length = 0;
}

清空运算$\textbf{O(n)}$：表长置0，循环释放

template <class T>
void SLinkedList<T>::clear() {
    length = 0;
    while (head) {
        sNode* tmp = head;
        head = head->next;
        delete tmp;
    }
}

求长、判空$\textbf{O(1)}$：略

(PRIVATE) 移动指针$\textbf{O(1)}-\textbf{O(n)}-\textbf{O(n)}$（注：此法无需存在，用前后指针法也行）

template <class T>
sNode* SLinkedList<T>::move(int i) const {
    sNode* ans = head;
    for (int idx = 0; idx <= i && idx < length; ++idx)
        ans = ans->next;
    return ans;
}

插入运算（复杂度取决于移动指针）：移动指针至指定位置的直接前驱，插入，记得维护表长；

template <class T>
void SLinkedList<T>::insert(int i, const T& dt) {
    if (i < 0 || i >= length) return;
    sNode* cur = move(i - 1);
    cur->next = new sNode(dt, cur->next); ++length;
}

删除运算（复杂度取决于移动指针）：移动指针至指定位置的直接前驱，删除，记得维护表长；

template <class T>
void SLinkedList<T>::remove(int i, T& x) {
    if (i < 0 || i >= length) return;
    sNode* cur = move(i - 1);
    sNode* tmp = cur->next;
    cur->next = tmp->next;
    delete tmp; --length;
}

访问运算（……）：移动……，返回；

template <class T>
T SLinkedList<T>::visit(int i) const {
    if (i < 0 || i >= length) return;
    sNode* cur = move(i);
    return cur->data;
}

查找运算$\textbf{O(n)}$：同顺序表

template <class T>
int SLinkedList<T>::find(const T& dt) const {
    sNode* cur = head->next;
    for (int i = 0; cur; ++i) {
        if (cur->data == dt) return i;
        cur = cur->next;
    }
    return -1;
}

遍历运算$\textbf{O(n)}$：同~

template <class T>
void SLinkedList<T>::traverse() const {
    sNode* cur = head->next;
    while (cur) {
        std::cout << cur->data << ' ';
        cur = cur->next;
    }
}

易错点
1. 循环条件设置不好，导致空指针的访问；
2. 指针操作有误，导致内存泄漏（尤其是删除结点的时候）；
3. 操作野指针；

经典考试题（以至于不放在题型板块）：单链表的逆序，要求线性时间、常数空间

template <class T>
void SLinkedList<T>::reverse() {
    sNode* tail = head->next, pre;
    if (!tail) return;
    while (pre = tail->next) {
        tail->next = pre->next;
        pre->next = tail;
        head->next = pre;
    }
}