CLRS-Cpp-Implementations-Chapter-10

stack

 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


namespace CLRS
{
  template <typename T, std::size_t n> class Stack;

  template <typename T, std::size_t n>
  bool stack_empty(const Stack<T, n> &s)
  {
    if(!s.top)
      return true;
    else
      return false;
  }

  template <typename T, std::size_t n>
  void push(Stack<T, n> &s, T x)
  {
    std::size_t l = s.top + 1;
    if(l > n)
      throw std::overflow_error("Stack size overflow.");
    s.top = l;
    s[s.top - 1] = x;
  }

  template <typename T, std::size_t n>
  T pop(Stack<T, n> &s)
  {
    if(stack_empty(s))
      throw std::underflow_error("Stack size underflow");
    --s.top;
    return s[s.top];
  }

  template <typename T, std::size_t n>
  class Stack
  {
    friend void push<T, n> (Stack<T, n> &, T);
    friend bool stack_empty<T, n> (const Stack<T, n> &);
    friend T pop<T, n> (Stack<T, n> &);
    T stack_array[n];
    std::size_t top = 0;
  public:
    T &operator[](std::size_t i) {return stack_array[i];}
  };
}

tree

1
2
3
4
5
6
7


/*
 * Almost as same struct as linked-list.
 * TODO: tree_search
 * TODO: tree_insert
 * TODO: tree_delete
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


namespace CLRS
{
  template <typename T> class TreeSiblingNode;

  template <typename T>
  class TreeSibling
  {
    TreeSiblingNode<T> *root = nullptr;
  };

  template <typename T>
  class TreeSiblingNode
  {
    TreeSiblingNode<T> *p = nullptr;
    TreeSiblingNode<T> *left_child = nullptr;
    TreeSiblingNode<T> *right_sibling = nullptr;
    T key;
  };
}

 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


namespace CLRS
{
  template <typename T> class TreeNode;

  template <typename T>
  class Tree
  {
    TreeNode<T> *root = nullptr;
  public:
    TreeNode<T> *get_root() {return root;}
    void set_root(TreeNode<T> *r) {root = r;}
  };

  template <typename T>
  class TreeNode
  {
    TreeNode *p = nullptr;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;
    T key;
  public:
    TreeNode(T k): key(k) {}
    T get_value() {return key;}
    TreeNode *get_left() {return left;}
    TreeNode *get_right() {return right;}
    TreeNode *get_parent() {return p;}
    void set_parent(TreeNode *parent) {p = parent;}
    void set_left(TreeNode *l) {left = l;}
    void set_right(TreeNode *r) {right = r;}
  };
}

queue

 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


namespace CLRS
{
  template <typename T, std::size_t n>
  class Queue;
  template <typename T, std::size_t n>
  void enqueue(Queue<T, n> &, T);
  template <typename T, std::size_t n>
  T dequeue(Queue<T, n> &);
  template <typename T, std::size_t n>

  class Queue
  {
    friend void enqueue<T, n> (Queue<T, n> &, T);
    friend T dequeue<T, n> (Queue<T, n> &);
    T queue_array[n];
    std::size_t head = 0;
    std::size_t tail = 0;
  public:
    T &operator[](std::size_t i) {return queue_array[i];}
  };

  template <typename T, std::size_t n>
  void enqueue(Queue<T, n> &q, T x)
  {
    if((q.tail + 1 == q.head) || (q.tail + 1 - n == q.head))
      throw std::overflow_error("Queue is overflow");
    q[q.tail] = x;
    if(q.tail == n - 1)
      q.tail = 0;
    else
      ++q.tail;
  }

  template <typename T, std::size_t n>
  T dequeue(Queue<T, n> &q)
  {
    if(q.tail == q.head)
      throw std::underflow_error("Queue is underflow");
    T x = q[q.head];
    if(q.head == n - 1)
      q.head = 0;
    else
      ++q.head;
    return x;
  }
}

list

 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


namespace CLRS
{
  template <typename T> class ListNode;
  template <typename T> class List;
  template <typename T> ListNode<T> *list_search(const List<T> &, T k);
  template <typename T> void list_insert(List<T> &, ListNode<T> &);
  template <typename T> void list_delete(List<T> &, ListNode<T> &);
  template <typename T>

  class ListNode
  {
    friend ListNode<T> *list_search<T> (const List<T> &, T k);
    friend void list_insert<T> (List<T> &, ListNode<T> &);
    friend void list_delete<T> (List<T> &, ListNode<T> &);
    ListNode *prev = nullptr;
    ListNode *next = nullptr;
    T key;
  public:
    ListNode(T t) {key = t;}
    inline T get_value() {return key;}
  };

  template <typename T>
  class List
  {
    friend ListNode<T> *list_search<T> (const List<T> &, T k);
    friend void list_insert<T> (List<T> &, ListNode<T> &);
    friend void list_delete<T> (List<T> &, ListNode<T> &);
    ListNode<T> *head = nullptr;
  };

  template <typename T> ListNode<T> *list_search(const List<T> &l, T k)
  {
    ListNode<T> *x = l.head;
    while(x != nullptr && x->key != k)
      x = x->next;
    return x;
  }

  template <typename T> void list_insert(List<T> &l, ListNode<T> &x)
  {
    x.next = l.head;
    if(l.head != nullptr)
      l.head->prev = &x;
    l.head = &x;
    x.prev = nullptr;
  }

  template <typename T> void list_delete(List<T> &l, ListNode<T> &x)
  {
    if(x.prev != nullptr)
      x.prev->next = x.next;
    else
      l.head = x.next;
    if(x.next != nullptr)
      x.next->prev = x.prev;
  }
}

 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


namespace CLRS
{
  template <typename T> class ListSentinelNode;
  template <typename T> class ListSentinel;
  template <typename T> ListSentinelNode<T> *list_sentinel_search(const ListSentinel<T> &, T k);
  template <typename T> void list_sentinel_insert(ListSentinel<T> &, ListSentinelNode<T> &);
  template <typename T> void list_sentinel_delete(ListSentinel<T> &, ListSentinelNode<T> &);
  template <typename T>
  class ListSentinelNode
  {
    friend class ListSentinel<T>;
    friend ListSentinelNode<T> *list_sentinel_search<T> (const ListSentinel<T> &, T k);
    friend void list_sentinel_insert<T> (ListSentinel<T> &, ListSentinelNode<T> &);
    friend void list_sentinel_delete<T> (ListSentinel<T> &, ListSentinelNode<T> &);
    ListSentinelNode *prev = nullptr;
    ListSentinelNode *next = nullptr;
    T key;
  public:
    ListSentinelNode(T t) {key = t;}
    ListSentinelNode() = default;
    inline T get_value() {return key;}
  };
  template <typename T>
  class ListSentinel
  {
    friend ListSentinelNode<T> *list_sentinel_search<T> (const ListSentinel<T> &, T k);
    friend void list_sentinel_insert<T> (ListSentinel<T> &, ListSentinelNode<T> &);
    friend void list_sentinel_delete<T> (ListSentinel<T> &, ListSentinelNode<T> &);
    ListSentinelNode<T> lsn;
    ListSentinelNode<T> *nil = &lsn;
  public:
    ListSentinel() {nil->prev = nil; nil->next = nil;}
  };
  template <typename T> ListSentinelNode<T> *list_sentinel_search(const ListSentinel<T> &l, T k)
  {
    ListSentinelNode<T> *x = l.nil->next;
    while(x != l.nil && x->key != k)
      x = x->next;
    if(x == l.nil)
      return nullptr;
    return x;
  }
  template <typename T> void list_sentinel_insert(ListSentinel<T> &l, ListSentinelNode<T> &x)
  {
    x.next = l.nil->next;
    l.nil->next->prev = &x;
    l.nil->next = &x;
    x.prev = l.nil;
  }
  template <typename T> void list_sentinel_delete(ListSentinel<T> &l, ListSentinelNode<T> &x)
  {
    x.prev->next = x.next;
    x.next->prev = x.prev;
  }
}

文章目录

stack

tree

queue

list