一、队列
1.基本特征：先进先出，FIFO
2.基本操作：压入(push)、弹出(pop)
3.实现要点：初始化空间，从前端(front)弹出，从后端(rear)压入，循环使用，判空判满
思考：用堆栈实现队列。二、链表
1.基本特征：内存中不连续的节点序列，彼此之间通过指针相互关联，前指针(prev)指向前节点，后指针(next)指向后节点。
2.基本操作：追加、插入、删除、遍历
3.实现要点：
void 讲故事 (void) {
从前有座山;
山里有个庙;
庙里有个老和尚;
if (老和尚圆寂了)
return;
讲故事 ();
}
三、二叉树
1.基本特征
1)树型结构的最简模型，每个节点最多有两个子节点。
2)单根。除根节点外每个节点有且仅有一个父节点，整棵树只有一个根节点。
3)递归结构，用递归处理二叉树问题可以简化算法。
2.基本操作
1)生成
2)遍历
D-L-R：前序遍历
L-D-R：中序遍历
L-R-D：后序遍历
有序二叉树(二叉搜索树)
L<=D<=R
50 70 20 60 40 30 10 90 80
50
/
/-- --
20| 70
/ /
10 40 60 90
/ /
30 80
/
10
中序遍历：10 20 30 40 50 60 70 80 90
bstree.cpp
#include <iostream> using namespace std; // 有序二叉树(二叉搜索树) class Tree { public: // 构造过程中初始化为空树 Tree (void) : m_root (NULL), m_size (0) {} // 析构过程中销毁剩余节点 ~Tree (void) { clear (); } // 插入数据 void insert (int data) { insert (new Node (data), m_root); ++m_size; } // 删除第一个匹配数据，不存在返回false bool erase (int data) { Node*& node = find (data, m_root); if (node) { // 左插右 insert (node->m_left, node->m_right); Node* temp = node; // 右提升 node = node->m_right; delete temp; --m_size; return true; } return false; } // 删除所有匹配数据 void remove (int data) { while (erase (data)); } // 清空树 void clear (void) { clear (m_root); m_size = 0; } // 将所有的_old替换为_new void update (int _old, int _new) { while (erase (_old)) insert (_new); } // 判断data是否存在 bool find (int data) { return find (data, m_root) != NULL; } // 中序遍历 void travel (void) { travel (m_root); cout << endl; } // 获取大小 size_t size (void) { return m_size; } // 获取树高 size_t height (void) { return height (m_root); } private: // 节点 class Node { public: Node (int data) : m_data (data), m_left (NULL), m_right (NULL) {} int m_data; // 数据 Node* m_left; // 左树 Node* m_right; // 右树 }; void insert (Node* node, Node*& tree) { if (! tree) tree = node; else if (node) { if (node->m_data < tree->m_data) insert (node, tree->m_left); else insert (node, tree->m_right); } } // 返回子树tree中值与data相匹配的节点的父节点中 // 指向该节点的成员变量的别名 Node*& find (int data, Node*& tree) { if (! tree) return tree; else if (data == tree->m_data) return tree; else if (data < tree->m_data) return find (data, tree->m_left); else return find (data, tree->m_right); } void clear (Node*& tree) { if (tree) { clear (tree->m_left); clear (tree->m_right); delete tree; tree = NULL; } } void travel (Node* tree) { if (tree) { travel (tree->m_left); cout << tree->m_data << ' '; travel (tree->m_right); } } size_t height (Node* tree) { if (tree) { size_t lh = height (tree->m_left); size_t rh = height (tree->m_right); return (lh > rh ? lh : rh) + 1; } return 0; } Node* m_root; // 树根 size_t m_size; // 大小 }; int main (void) { Tree tree; tree.insert (50); tree.insert (70); tree.insert (20); tree.insert (60); tree.insert (40); tree.insert (30); tree.insert (10); tree.insert (90); tree.insert (80); tree.travel (); cout << tree.size () << ' ' << tree.height () << endl; tree.erase (70); tree.travel (); tree.insert (70); tree.insert (70); tree.insert (70); tree.travel (); tree.remove (70); tree.travel (); tree.insert (40); tree.insert (40); tree.travel (); tree.update (40, 69); tree.travel (); cout << boolalpha << tree.find (50) << endl; cout << tree.find (55) << endl; tree.clear (); tree.travel (); return 0; }
list.cpp
#include <iostream> #include <stdexcept> using namespace std; // 双向线性链表 class List { public: // 构造过程中初始化为空链表 List (void) : m_head (NULL), m_tail (NULL) {} // 析构过程中销毁剩余的节点 ~List (void) { for (Node* next; m_head; m_head = next) { next = m_head->m_next; delete m_head; } } // 追加 void append (int data) { m_tail = new Node (data, m_tail); if (m_tail->m_prev) m_tail->m_prev->m_next = m_tail; else m_head = m_tail; } // 插入 void insert (size_t pos, int data) { for (Node* find = m_head; find; find = find->m_next) if (pos-- == 0) { Node* node = new Node (data, find->m_prev, find); if (node->m_prev) node->m_prev->m_next = node; else m_head = node; node->m_next->m_prev = node; return; } throw out_of_range ("链表越界！"); } // 删除 void erase (size_t pos) { for (Node* find = m_head; find; find = find->m_next) if (pos-- == 0) { if (find->m_prev) find->m_prev->m_next = find->m_next; else m_head = find->m_next; if (find->m_next) find->m_next->m_prev = find->m_prev; else m_tail = f return; } throw out_of_range ("链表越界！"); } // 正向遍历 void forward (void) const { for (Node* node = m_head; node; node = node->m_next) cout << node->m_data << ' '; cout << endl; } // 反向遍历 void backward (void) const { for (Node* node = m_tail; node; node = node->m_prev) cout << node->m_data << ' '; cout << endl; } // 下标访问 int& operator[] (size_t index) { for (Node* find = m_head; find; find = find->m_next) if (index-- == 0) return find->m_data; throw out_of_range ("链表越界！"); } const int& operator[] (size_t index) const { return const_cast<List&> (*this) [index]; } private: // 节点 class Node { public: Node (int data = 0, Node* prev = NULL, Node* next = NULL) : m_data (data), m_prev (prev), m_next (next) {} int m_data; // 数据 Node* m_prev; // 前指针 Node* m_next; // 后指针 }; Node* m_head; // 头指针 Node* m_tail; // 尾指针 }; int main (void) { try { List list; list.append (10); list.append (30); list.append (50); list.append (60); list.append (80); list.insert (1, 20); list.insert (3, 40); list.insert (6, 70); list.forward (); list.backward (); list.erase (5); list.erase (5); list.erase (5); list.forward (); for (size_t i = 0; i < 5; ++i) ++list[i]; const List& cr = list; for (size_t i = 0; i < 5; ++i) cout << /*++*/cr[i] << ' '; cout << endl; } catch (exception& ex) { cout << ex.what () << endl; return -1; } return 0; }
listex.cpp
// 练习：实现一个单向线性链表类 // 1.建立、测长、正反向打印 // 2.逆转 // 3.获取中间节点值，单次遍历 // 4.有序链表的插入和删除 #include <iostream> #include <stdexcept> using namespace std; class List { public: List (void) : m_head (NULL), m_tail (NULL) {} ~List (void) { for (Node* next; m_head; m_head = next) { next = m_head->m_next; delete m_head; } } void append (int data) { Node* node = new Node (data); if (m_tail) m_tail->m_next = node; else m_head = node; m_tail = node; } size_t size (void) const { size_t cn = 0; for (Node* node = m_head; node; node = node->m_next) ++cn; return cn; } void print (void) const { for (Node* node = m_head; node; node = node->m_next) cout << node->m_data << ' '; cout << endl; } void rprint (void) const { rprint (m_head); cout << endl; } /* void reverse (void) { reverse (m_head); swap (m_head, m_tail); } */ void reverse (void) { if (m_head != m_tail) { Node* p1 = m_tail = m_head; Node* p2 = p1->m_next; Node* p3 = p2->m_next; for (p1->m_next=NULL;p3;p3=p3->m_next) { p2->m_next = p1; p1 = p2; p2 = p3; } (m_head = p2)->m_next = p1; } } int middle (void) const { if (! m_head || ! m_tail) throw underflow_error ("链表下溢！"); if (m_head == m_tail) return m_head->m_data; Node* mid = m_head; for (Node* node = m_head; node->m_next && node->m_next->m_next; node = node->m_next->m_next) mid = mid->m_next; return mid->m_data; } // 插入data，仍然保持有序 void insert (int data) { } // 删除所有的data void remove (int data) { } private: class Node { public: Node (int data = 0, Node* next = NULL) : m_data (data), m_next (next) {} int m_data; Node* m_next; }; void rprint (Node* head) const { if (head) { rprint (head->m_next); cout << head->m_data << ' '; } } void reverse (Node* head) { if (head && head->m_next) { reverse (head->m_next); head->m_next->m_next = head; head->m_next = NULL; } } Node* m_head; Node* m_tail; }; int main (void) { List list; for (int i = 0; i < 11; ++i) list.append (i); cout << list.size () << endl; list.print (); list.rprint (); list.reverse (); list.print (); cout << list.middle () << endl; return 0; }
lqueue.cpp
#include <iostream> using namespace std; // 基于链式表的队列 class Queue { public: // 在构造过程中初始化为空队列 Queue (void) : m_rear (NULL), m_front (NULL) {} // 在析构过程中销毁剩余的节点 ~Queue (void) { for (Node* next; m_front; m_front = next) { next = m_front->m_next; delete m_front; } } // 压入 void push (int data) { Node* node = new Node (data); if (m_rear) m_rear->m_next = node; else m_front = node; m_rear = node; } // 弹出 int pop (void) { if (empty ()) throw UnderFlow (); int data = m_front->m_data; Node* next = m_front->m_next; delete m_front; if (! (m_front = next)) m_rear = NULL; return data; } // 判空 bool empty (void) const { return ! m_front && ! m_rear; } private: // 下溢异常 class UnderFlow : public exception { const char* what (void) const throw () { return "队列下溢！"; } }; // 节点 class Node { public: Node (int data = 0, Node* next = NULL) : m_data (data), m_next (next) {} int m_data; // 数据 Node* m_next; // 后指针 }; Node* m_rear; // 后端 Node* m_front; // 前端 }; int main (void) { try { Queue queue; for (int i = 0; i < 10; ++i) queue.push (i); while (! queue.empty ()) cout << queue.pop () << endl; }Node* catch (exception& ex) { cout << ex.what () << endl; return -1; } return 0; de* }
lstack.h
#ifndef _LSTACK_H #define _LSTACK_H #include <stdexcept> using namespace std; // 基于链式表的堆栈 class Stack { public: // 构造过程中初始化为空堆栈 Stack (void) : m_top (NULL) {} // 析构过程中销毁剩余的节点 ~Stack (void) { for (Node* next; m_top; m_top = next) { next = m_top->m_next; delete m_top; } } // 压入 void push (int data) { /* Node* node = new Node; node->m_data = data; node->m_next = m_top; m_top = node;*/ m_top = new Node (data, m_top); } // 弹出 int pop (void) { if (empty ()) throw UnderFlow (); int data = m_top->m_data; Node* next = m_top->m_next; delete m_top; m_top = next; return data; } // 判空 bool empty (void) const { return ! m_top; } private: // 下溢异常 class UnderFlow : public exception { const char* what (void) const throw () { return "堆栈下溢！"; } }; // 节点 class Node { public: Node (int data = 0, Node* next = NULL) : m_data (data), m_next (next) {} int m_data; // 数据 Node* m_next; // 后指针 }; Node* m_top; // 栈顶 }; #endif // _LSTACK_H
queue.cpp
#include <iostream> using namespace std; // 基于顺序表的队列 class Queue { public: // 构造过程中分配内存 Queue (size_t size = 5) : m_array (new int[size]), m_size (size), m_rear (0), m_front (0), m_count (0) {} // 析构过程中释放内存 ~Queue (void) { if (m_array) { delete[] m_array; m_array = NULL; } } // 压入 void push (int data) { if (full ()) throw OverFlow (); if (m_rear >= m_size) m_rear = 0; ++m_count; m_array[m_rear++] = data; } // 弹出 int pop (void) { if (empty ()) throw UnderFlow (); if (m_front >= m_size) m_front = 0; --m_count; return m_array[m_front++]; } // 判空 bool empty (void) const { return ! m_count; } // 判满 bool full (void) const { return m_count == m_size; } private: // 上溢异常 class OverFlow : public exception { const char* what (void) const throw () { return "队列上溢！"; } }; // 下溢异常 class UnderFlow : public exception { const char* what (void) const throw () { return "队列下溢！"; } }; int* m_array; // 数组 size_t m_size; // 容量 size_t m_rear; // 后端 size_t m_front; // 前端 size_t m_count; // 计数 }; int main (void) { try { Queue queue; queue.push (10); queue.push (20); queue.push (30); queue.push (40); queue.push (50); // queue.push (60); cout << queue.pop () << endl; // 10 queue.push (60); cout << queue.pop () << endl; // 20 queue.push (70); // queue.push (80); cout << queue.pop () << endl; // 30 cout << queue.pop () << endl; // 40 cout << queue.pop () << endl; // 50 cout << queue.pop () << endl; // 60 cout << queue.pop () << endl; // 70 // queue.pop (); } catch (exception& ex) { cout << ex.what () << endl; return -1; } return 0; }
squeue.cpp
#include <iostream> #include "lstack.h" using namespace std; // 基于堆栈的队列 class Queue { public: // 压入 void push (int data) { m_i.push (data); } // 弹出 int pop (void) { if (m_o.empty ()) { if (m_i.empty ()) throw underflow_error("队列下溢！"); while (! m_i.empty ()) m_o.push (m_i.pop ()); } return m_o.pop (); } // 判空 bool empty (void) const { return m_i.empty () && m_o.empty (); } private: Stack m_i; // 输入栈 Stack m_o; // 输出栈 }; int main (void) { try { Queue queue; for (int i = 0; i < 10; ++i) queue.push (i); cout << queue.pop () << endl; // 0 cout << queue.pop () << endl; // 1 cout << queue.pop () << endl; // 2 cout << queue.pop () << endl; // 3 cout << queue.pop () << endl; // 4 queue.push (10); queue.push (11); queue.push (12); while (! queue.empty ()) cout << queue.pop () << endl; } catch (exception& ex) { cout << ex.what () << endl; return -1; } return 0; }