//使用单向循环链表实现字典操作 INSERT、DELETE 和 SEARCH
[cpp] view plain copy #ifndef _SINGLY_CIRCULAR_LINKED_LIST_H #define _SINGLY_CIRCULAR_LINKED_LIST_H /**************************************************************** 10.2-5 使用单向循环链表实现字典操作 INSERT、DELETE 和 SEARCH *****************************************************************/ template <class T> class SinglyCircularLinkedList { public: // 一个表示链表结点的数据结构 class Node{ public: // 只有 StackUseSinglyLinkedList 才可以构造这个类型的对象 // 访问这个类型的私有成员 friend class SinglyCircularLinkedList < T > ; // 结点的值 T value; private: // 默认构造函数，要求类型 T 也要有默认构造函数 Node() :_next(nullptr){} // 将构造函数设置为私有的，防止在外部创建这个类型的对象 Node(const T& e) :_next(nullptr), value(e){} // 指向下一个元素，如果这个值为空， // 表示本结点是链表中的最后一个元素 Node* _next; }; SinglyCircularLinkedList(); ~SinglyCircularLinkedList(); // 测试链表是否为空，空链表的头结点的 _next 指向自身 bool empty() const { return _head->_next == _head; } void insert(const T&); void remove(const T&); Node* search(const T&) const; void print() const; private: Node* _head; }; template <class T> SinglyCircularLinkedList<T>::SinglyCircularLinkedList() { // 为头结点分配空间，初始头结点的 _next 指向自身 _head = new Node(); _head->_next = _head; } template <class T> typename SinglyCircularLinkedList<T>::Node* SinglyCircularLinkedList<T>::search(const T& element) const{ // 从链表头开始搜索再回到链表头 auto node = _head->_next; while (node != _head){ if (node->value == element) return node; node = node->_next; } return nullptr; } template <class T> void SinglyCircularLinkedList<T>::insert(const T& element){ // 在链表的头部插入元素，新元素指向头结点的下一个元素，头结节指向新元素 // 为新元素分配空间，当从元素从链表中删除时要释放这个元素占用的空间 Node* node = new Node(element); node->_next = _head->_next; _head->_next = node; } template <class T> void SinglyCircularLinkedList<T>::remove(const T& element){ // 必找到目标元素的前驱结点 auto node = _head->_next; auto prevNode = _head; while (node != _head) { if (node->value == element){ prevNode->_next = node->_next; delete node; break; } prevNode = node; node = node->_next; } } template <class T> void SinglyCircularLinkedList<T>::print() const{ auto node = _head->_next; while (node != _head){ std::cout << node->value << " "; node = node->_next; } std::cout << std::endl; } template <class T> SinglyCircularLinkedList<T>::~SinglyCircularLinkedList(){ // 将链表中元素占用的空间释放 Node* node = _head->_next; while (node != _head) { Node *n = node->_next; delete node; node = n; } // 释放头结点占用的空间 delete _head; }; #endif
