算法导论 第三部分：数据结构

发表于
这是《算法导论》的第三部分（正在施工）

下面是动态集合上的操作
：查询操作，返回集合 中的指针 使得 ，若没有则返回 。
：插入操作。
：删除操作。
：返回 中最小的关键字元素的指针。
：返回集合 中最大的关键字元素的指针。
：返回集合 中比 大的下一个元素的指针，若 是最大的元素则返回 。
：返回集合 中比 小的下一个元素的指针，若 是最小的元素则返回 。

基本数据结构

栈和队列

栈采用先进后出的策略
队列采用后进先出的策略

栈

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
template <typename T> struct Stack{
	T* arr;
	size_t top=0;
	size_t capacity=0;
};

template<typename T> void STACK_INIT(Stack<T>& s, size_t capacity){
	s.arr = new T[capacity];
	s.capacity=capacity;
	s.top = 0;
}

template<typename T> bool STACK_EMPTY(const Stack<T>& s){
	return s.top == 0;
}

template<typename T> bool PUSH(Stack<T>& s, T data) {
	if (s.top == s.capacity) return false; //overflow case
	s.arr[s.top] = data;
	s.top++;
	return true;
}
  
template<typename T> bool POP(Stack<T>& s) {
	if (s.top == 0) return false; //underflow case
	s.top -= 1;
	return true;
}

template<typename T> size_t TOP(const Stack<T>& s) {
	return s.top - 1;
}

队列

队列有 队头（head） 和 队尾（tail）。 指向队头元素， 指向下一个元素将要插入的位置。操作为 入列（ENQUEUE） 和 出列（DEQUEUE）。

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
class Queue<T>{
    private T[] arr;
    public int length = 0;
    public int head = 0;
    public int tail = 0;
    
    @SuppressWarnings("unchecked")
    public Queue(int len) {
        arr = (T[]) new Object[len];
        length = len;
    }
    
    public void ENQUEUE(T x) throws Exception {
        if(this.FULL()) throw new NoSuchElementException();
        
        this.arr[this.tail] = x;
        
        if (this.tail == this.length - 1) {
            this.tail = 0;
        }
        else {
            this.tail += 1;
        }
    }
    
    public T DEQUEUE(){
        if(this.EMPTY()) throw new NoSuchElementException();
        
        T x = this.arr[this.head];
        
        if (this.head == this.length - 1) {
            this.head = 0;
        }
        else {
            this.head += 1;
        }
        return x;
    }
    
    public boolean EMPTY() {
        return this.head == this.tail;
    }
    
    public boolean FULL() {
        return (this.tail + 1) % this.length == this.head;
    }
}

链表

有哨兵的双向循环链表

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
75
76
77
78
79
80
81
82
83
template<typename T> struct Node {
	T key;
	Node<T>* prev;
	Node<T>* next;
	  
	Node(T k = T()) : key(k), prev(nullptr), next(nullptr) {}
};
  
template<typename T> class LinkedList {
	private:
		Node<T>* nil; //哨兵节点
		  
	public:
		LinkedList() {
		nil = new Node<T>();
		nil->next = nil;
		nil->prev = nil;
}
  
bool EMPTY() {
	return nil->next == nil;
}
  
void INSERT_FRONT(T x) {
	Node<T>* node = new Node<T>(x);
	  
	node->next = nil->next;
	node->prev = nil;
	  
	nil->next->prev = node;
	nil->next = node;
}
  
void INSERT_BACK(T x) {
	Node<T>* node = new Node<T>(x);
	  
	node->prev = nil->prev;
	node->next = nil;
	  
	nil->prev->next = node;
	nil->prev = node;
}

Node<T>* SEARCH(T key) {
	Node<T>* cur = nil->next;
	  
	while (cur != nil && cur->key != key) {
		cur = cur->next;
	}
	  
	return cur;
}
  
void DELETE(Node<T>* x) {
	if (x == nil) return;
	  
	x->prev->next = x->next;
	x->next->prev = x->prev;
	  
	delete x;
}

void PRINT() {
	Node<T>* cur = nil->next;
	  
	while (cur != nil) {
		cout << cur->key << " ";
		cur = cur->next;
	}
	cout << endl;
}
  
~LinkedList() {
	Node<T>* cur = nil->next;
	  
	while (cur != nil) {
		Node<T>* tmp = cur;
		cur = cur->next;
		delete tmp;
	}  
	delete nil;
}
};

对象的多维数组表示

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
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <vector>
#include <stdexcept>

class MultiArrayLinkedList {
private:
    std::vector<int> key;
    std::vector<int> next;
    std::vector<int> prev;
    int head;
    int free_list;
    const int NIL = -1;

public:
    MultiArrayLinkedList(int capacity) {
        key.resize(capacity);
        next.resize(capacity);
        prev.resize(capacity);
        
        head = NIL;
        free_list = 0;
        
        // 初始化自由链表
        for (int i = 0; i < capacity - 1; ++i) {
            next[i] = i + 1;
        }
        next[capacity - 1] = NIL;
    }

    // CLRS: Allocate-Object
    int allocate_object() {
        if (free_list == NIL) {
            throw std::out_of_range("Out of memory: 自由链表已空");
        }
        int x = free_list;
        free_list = next[x];
        return x;
    }

    // CLRS: Free-Object
    void free_object(int x) {
        next[x] = free_list;
        free_list = x;
    }

    // CLRS: List-Insert
    void insert(int key_value) {
        int x = allocate_object();
        key[x] = key_value;
        next[x] = head;
        prev[x] = NIL;
        
        if (head != NIL) {
            prev[head] = x;
        }
        head = x;
        std::cout << "Inserted " << key_value << " at index " << x << std::endl;
    }

    // CLRS: List-Delete
    void delete_node(int x) {
        if (prev[x] != NIL) {
            next[prev[x]] = next[x];
        } else {
            head = next[x];
        }
        
        if (next[x] != NIL) {
            prev[next[x]] = prev[x];
        }
        
        free_object(x);
        std::cout << "Deleted node at index " << x << std::endl;
    }

    void print_list() {
        int curr = head;
        std::cout << "List: ";
        while (curr != NIL) {
            std::cout << key[curr] << (next[curr] != NIL ? " <-> " : "");
            curr = next[curr];
        }
        std::cout << std::endl;
    }
};

对象的单维数组表示

对于一维数组，我们可以把节点分为三个部分：key, next和prev，其中next和prev分别指向下一个、前一个节点的key

1
2
|`````` | key | next | prev | ``````| //一维数组，访问时通过偏移量0，1，2来定位

实现

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
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <stdexcept>

class SingleArrayLinkedList {
private:
    std::vector<int> A;
    int head;
    int free_list;
    const int NIL = -1;

public:
    SingleArrayLinkedList(int capacity) {
        // 每个节点占用 3 个位置: key, next, prev
        A.resize(capacity * 3);
        
        head = NIL;
        free_list = 0;
        
        // 初始化自由链表，步长为 3
        for (int i = 0; i < capacity - 1; ++i) {
            // A[x + 1] 是 next 指针
            A[i * 3 + 1] = (i + 1) * 3;
        }
        A[(capacity - 1) * 3 + 1] = NIL;
    }

    // CLRS: Allocate-Object
    int allocate_object() {
        if (free_list == NIL) {
            throw std::out_of_range("Out of memory: 自由链表已空");
        }
        int x = free_list;
        free_list = A[x + 1]; // 读取 next 指针
        return x;
    }

    // CLRS: Free-Object
    void free_object(int x) {
        A[x + 1] = free_list;
        free_list = x;
    }

    // CLRS: List-Insert
    void insert(int key_value) {
        int x = allocate_object();
        
        A[x] = key_value;      // key
        A[x + 1] = head;       // next
        A[x + 2] = NIL;        // prev
        
        if (head != NIL) {
            A[head + 2] = x;   // 更新旧头节点的 prev
        }
        head = x;
        std::cout << "Inserted " << key_value << " at starting index " << x << std::endl;
    }

    // CLRS: List-Delete
    void delete_node(int x) {
        int prev_idx = A[x + 2];
        int next_idx = A[x + 1];
        
        if (prev_idx != NIL) {
            A[prev_idx + 1] = next_idx;
        } else {
            head = next_idx;
        }
        
        if (next_idx != NIL) {
            A[next_idx + 2] = prev_idx;
        }
        
        free_object(x);
        std::cout << "Deleted node starting at index " << x << std::endl;
    }

    void print_list() {
        int curr = head;
        std::cout << "List: ";
        while (curr != NIL) {
            std::cout << A[curr] << (A[curr + 1] != NIL ? " <-> " : "");
            curr = A[curr + 1];
        }
        std::cout << std::endl;
    }
};

对象的分配与释放

在没有原生对象和指针的编程环境（或为了追求极致的内存管理效率而构建“内存池”时），我们通常使用 数组（Arrays） 来模拟链表和对象的结构。
在这种设定下，我们不仅需要管理“正在被使用的节点数据”，还需要手动管理那些尚未被使用的空闲空间。CLRS 引入了 自由链表（Free List） 以及配套的 Allocate-Object 和 Free-Object 算法来完成这项工作。

1. 核心概念：自由链表 (Free List)

自由链表是一个单向链表，它将所有当前未被使用的数组元素（即空闲插槽）串联起来。

  • 结构：即使原数据结构是双向链表，自由链表也只需要单向链接（利用现有的 next 数组即可）。
  • 头指针：通常使用一个名为 free 的全局变量来保存自由链表的头节点下标。
  • 分配与释放的本质：
    • 分配（Allocate）：就是从自由链表的头部弹出一个节点供程序使用。
    • 释放（Free）：就是将废弃的节点作为新节点插入到自由链表的头部。
2. Allocate-Object 详解

Allocate-Object 扮演着类似于 C 语言中 malloc() 或 Java/C++ 中 new 关键字的角色。它负责从自由链表中寻找一个可用的空闲空间，并返回其下标。

2.1 伪代码
1
2
3
4
5
6
ALLOCATE-OBJECT()
1  if free == NIL
2      error "out of space"
3  x = free
4  free = next[x]
5  return x
2.2 逐行解析
  1. 第 1-2 行 (溢出检查)：如果 free 指针等于 NIL（通常在编程中用 -1 表示），说明自由链表已经空了，此时没有多余的内存可以分配，抛出“内存耗尽”错误。
  2. 第 3 行 (获取节点)：将当前自由链表的头节点下标暂存到变量 中，这个 就是我们即将分配出去的可用空间。
  3. 第 4 行 (更新头指针)：将 free 指针向后移动一位，指向原来头节点的下一个节点（即 next[x]）。这一步等于把节点 从自由链表中“摘除”。
  4. 第 5 行 (返回结果)：返回被分配的节点下标 。
    时间复杂度：，因为它只涉及简单的指针（下标）赋值。
3. Free-Object(x) 详解

Free-Object 扮演着类似于 C 语言中 free() 或 C++ 中 delete 关键字的角色。当我们在业务逻辑中删除了一个节点（比如 List-Delete），我们必须将它归还给自由链表，以便将来重复利用。

3.1 伪代码
1
2
3
FREE-OBJECT(x)
1  next[x] = free
2  free = x
3.2 逐行解析

这里执行的是标准的单链表头部插入操作。

  1. 第 1 行 (建立新链接)：将被释放节点 的 next 指针，指向当前的自由链表头节点 free。
  2. 第 2 行 (更新头指针)：将自由链表的头指针 free 更新为 。这样， 就成功回到了空闲池的最前面。
    时间复杂度：，仅包含两步赋值操作。

有根树的表示

二叉树

对于属性为 的节点，若 则为根结点，没有孩子则 或 为 。

分支无限制的有根树

使用 左孩子右兄弟 的表示方法，其中 指向结点 的最左边的子结点， 指向 的右侧同级的兄弟节点。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <string>

// 树节点定义
template <typename T>
struct TreeNode {
    T key;
    TreeNode* left_child;
    TreeNode* right_sibling;

    // 构造函数
    TreeNode(T val) : key(val), left_child(nullptr), right_sibling(nullptr) {}
};

// 左孩子右兄弟树类
template <typename T>
class LCRSTree {
private:
    TreeNode<T>* root;

    // 递归释放内存
    void destroy_tree(TreeNode<T>* node) {
        if (node != nullptr) {
            // 注意：这里使用的是后序遍历的思想来销毁
            destroy_tree(node->left_child);
            destroy_tree(node->right_sibling);
            delete node;
        }
    }

    // 递归打印树形结构（用于可视化测试）
    void print_tree(TreeNode<T>* node, const std::string& prefix = "", bool is_last = true) const {
        if (node == nullptr) return;

        std::cout << prefix;
        std::cout << (is_last ? "└── " : "├── ");
        std::cout << node->key << std::endl;

        // 遍历所有子节点
        // 子节点构成了以 left_child 为头结点的单链表（通过 right_sibling 链接）
        TreeNode<T>* child = node->left_child;
        while (child != nullptr) {
            bool child_is_last = (child->right_sibling == nullptr);
            std::string new_prefix = prefix + (is_last ? "    " : "│   ");
            print_tree(child, new_prefix, child_is_last);
            child = child->right_sibling;
        }
    }

public:
    LCRSTree() : root(nullptr) {}
    
    ~LCRSTree() {
        destroy_tree(root);
    }

    // 设置根节点
    TreeNode<T>* set_root(T val) {
        if (root != nullptr) {
            destroy_tree(root);
        }
        root = new TreeNode<T>(val);
        return root;
    }

    // 给指定父节点添加一个新的子节点（追加到最右侧）
    TreeNode<T>* add_child(TreeNode<T>* parent, T val) {
        if (parent == nullptr) return nullptr;

        TreeNode<T>* new_node = new TreeNode<T>(val);

        // 如果父节点还没有子节点，直接作为左孩子
        if (parent->left_child == nullptr) {
            parent->left_child = new_node;
        } 
        // 否则，顺着左孩子的右兄弟链表找到最后一个兄弟，将其接在后面
        else {
            TreeNode<T>* current = parent->left_child;
            while (current->right_sibling != nullptr) {
                current = current->right_sibling;
            }
            current->right_sibling = new_node;
        }

        return new_node;
    }

    // 打印整棵树
    void print() const {
        if (root == nullptr) {
            std::cout << "Empty Tree" << std::endl;
        } else {
            print_tree(root);
        }
    }
};

树的其他表示方法

在之前，我们用 堆 来表示完全二叉树。在后面还有别的方式。