数组

规模可预估且稳定

数组 由相同类型变量构成的序列

  • 数组的分量(数组元素) 由数组和数组下标构成的变量.
  • 创建数组时, 系统会分配一块连续的存储空间.
  • 表示方式:
    • i. arr[1][3] C, C++, Python
    • ii. arr[1, 3] Pascal
    • iii. arr(1, 3) Basic
  • 数组元素数据类型相同.
  • 通过数组名和下标对数组元素的值进行访问.
  • 存储空间固定不变.
    • 动态数组 存储空间可以动态分配.

创建

在系统内存中划分一块连续的区域, 用于保存所有数据元素.

列表的索引列是连续的, 但元素在内存中的存储位置不一定是连续的.

访问

寻址带特定的数据元素, 并根据地址对其进行读取, 修改等操作.

元素插入 & 删除

  • 插入:
    • 后移 + 修改
  • 删除:
    • 删除 + 前移
  • 尽量避免此类操作

链表

将待处理对象以节点的形式, 通过指针串联在一起.

  • 头指针(表头, head)
    • i. 链表的入口
    • ii. 为循环链表设界
  • 单向链表 单指针指向后继节点.
  • 双向链表 双指针分别指向后继节点和前驱节点.
  • 空指针 尾结点指向空的指针, 标定链表末尾.
  • 同一链表中每个节点的结构均相同.
  • 链表占用的空间不固定.
  • 每个链表必定有一个头指针, 以实现对链表的引用和边界处理.

创建

  • 头指针指向空指针
  • 尾结点指向空指针

访问

head 进入, 相互指针访问.

元素插入 & 删除

索引 + 修改指针

遍历

head进入, 节点相互指针访问, 节点访问效率低.

线性表

线性表 由n(n≥0)个数据特性相同的元素构成的有限序列。

  • 除第一个元素之外，结构中的每个数据元素均只有一个
    前驱；
  • 除最后一个元素之外，结构中的每个数据元素均只有一
    个后继。

线性表的顺序表示

逻辑相邻，物理相邻

顺序表 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

其实, 顺序表就等价于上述笔记中的数组.

线性表的链式表示

逻辑相邻，物理不连续

首元节点 链表中存储第一个数据元素的节点。
头节点 首元节点之前的一个节点. (便于统一化的处理)

顺序表和链表的比较

比较内容 顺序表 链表
存储空间 固定 可变
存储密度 1 0.5
存储元素 连续 离散
访问元素 O(1) O(n)
插入元素 O(n) O(1)
删除元素 O(n) O(1)

在 C++ 中的实现

都放在这个仓库里面了.

一些详细的介绍以后再写吧…

这里只挑一些绝对有趣的地方写写, 详细的代码都应该去仓库看.

顺序表的数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <typename T>
class SequentialList
{
private:
    T *list;
    int capacity;
    int length;
public:
    ...

    // 这里实现了迭代器的功能, 从而可以使用 for(auto &i : list) 这种写法
    using iterator = T *;

    iterator begin()
    {
        return list;
    }

    iterator end()
    {
        return list+length;
    }

    // 这里实现了下标操作符, 从而可以使用 list[i] 这种写法
    T& operator[](int index)
    {
        if(index < 0 || index >= length)
        {
            throw "Index out of range";
        }
        return list[index];
    }
}

链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
template <typename T>
class SinglyLinkedList
{
private:
    struct Node
    {
        T data;
        Node* next;

        Node(T val) : data(val), next(nullptr) {}
    };

    Node *head;
    Node *tail;
    int length;

public:
    ...

    // 注意这种利用initializer_list的写法可以接受不定数量的参数
    SinglyLinkedList(initializer_list<T> initList) : length(0)
    {
        head = new Node(T());
        tail = head;

        for (auto &val : initList)
        {
            insertBackward(val);
        }
    }

    // 注意这里迭代器的类要自己重构
    class iterator
    {
    private:
        Node *ptr; // 指向当前节点的指针
    public:
        iterator(Node *p = nullptr) : ptr(p) {}

        // 重载操作符
        T &operator*() { return ptr->data; } // 解引用
        Node *operator->() { return ptr; }   // 成员访问
        iterator &operator++()
        { // 前置++
            ptr = ptr->next;
            return *this;
        }
        iterator operator++(int)
        { // 后置++
            iterator tmp = *this;
            ++(*this);
            return tmp;
        }
        bool operator==(const iterator &other) { return ptr == other.ptr; }
        bool operator!=(const iterator &other) { return ptr != other.ptr; }

        friend class SinglyLinkedList<T>; // 允许SinglyLinkedList访问iterator的私有成员
    };

    iterator begin() { return iterator(head->next); }
    iterator end() { return iterator(nullptr); }

    void insertForward(T value)
    {
        Node *newNode = new Node(value);
        newNode->next = head->next;
        head->next = newNode;
        if (tail == head)   // 前插法要注意判断头尾是否相同
        {
            tail = head->next;
        }
        length++;
    }
}

对于双向链表, 值得注意的是它的插入时要修改的指针比较多:

1
2
3
4
5
Node *newNode = new Node(value);
newNode->next = cur->next;
newNode->next->prev = newNode;
newNode->prev = cur;
cur->next = newNode;

同时, 它的特点是可以方便的前后遍历:

1
2
3
4
5
6
7
8
9
10
void backTranverse()
{
    Node *current = tail;
    while(current != head)
    {
        cout << current->data << " -> ";
        current = current->prev;
    }
    cout << "head" << endl;
}

线性表合并

思路很简单:

  1. 遍历 b 中每个元素.
  2. 对于 b 中每个元素 x, 判断是否在 a 中.
    1. 如果在, 则跳过;
    2. 如果不在, 则将 x 插入到 a 的末尾;

有序表合并

思路很简单:

  1. 两个指针 i, j 分别指向 a, b 的头部.
  2. 比较 a[i] 和 b[j], 较小的元素放入结果表, 并移动对应的指针.
    • 如果要求无重复元素
      • 则当 a[i] == b[j] 时, j 向后移动直到不重复;
      • 如果 i 或 j 后续元素也重复, 则i, j 都向后移动直到不重复;
    • 如果要求降序
      • 只需修改插入的位置为表头或者表尾;
  3. 重复步骤 2, 直到其中一个指针到达表尾.
  4. 将另一个指针未到达表尾的元素依次放入结果表.