Shulou(Shulou.com)06/01 Report--

In this article, the editor introduces in detail the "C++ two-way circular chain list class example code analysis", with detailed contents, clear steps and proper handling of details. I hope that this "C++ two-way circular chain table class template example code analysis" article can help you solve your doubts, following the editor's ideas slowly in depth, together to learn new knowledge.

1. Insert a node process

As shown in the following figure:

The corresponding code is as follows:

/ * insert a new node * / bool insert (int I, const T & value) {if (! ((I > = 0) & & (inext = pre- > next; / / Link the next of the new node node to the next node node- > prev = pre; / / Link the prev of the new node node to the previous node pre- > next- > prev = node / / Link the prev of the next node to the new node node pre- > next = node; / / Link the next of the previous node to the new node node m_length + = 1; return true;} 2. Constructor modification

In the constructor, you need to point both the next and prev of the header node to yourself to achieve a closed-loop state, as shown in the following code:

LinkedList () {m_header.next = & masked header; m_header.prev = & masked header; m_length = 0;} 3. Reimplement the append and prepend functions

Because it is a two-way circular linked list, we can easily get the header node and footer node. The code is as follows:

Void append (const T & value) {Node* node = new Node (value); / / new a new node node- > next = & masked header; / / the next node of the new node is the head node node- > prev = massively header.head; / / the last node of the new node is the end node node- > prev- > next = node / / the next node of the previous node of the new node is the new node m_header.prev = node; / / the previous node of the beginning node is I m_length + = 1;} void prepend (const T & value) {Node* node = new Node (value); / / new a new node node- > next = m_header.next / / the next node of the new node is the next node- > prev = & masked headers of the new node; / / the previous node of the new node is the header node m_header.next = node; / / set the next node of the header node to node node- > next- > prev = node; / / before the node precursor node m_length + = 1;} 4. Modify the iterator class

Since it is now a circular double linked list, the next of each node has a value, so we need to judge whether the current index of m_current is equal to the header node, and if so, it means that it has reached the end of the linked list. So the code is as follows:

Bool hasNext () {return (m_current & & m_current! = list- > constHeader ());}

Since there are now prev members, you need to add the forward traversal function:

Void toEnd () {m_current = list- > constHeader ()-> prev;} bool hasPrev () {return (m_current & & m_current! = list- > constHeader ());} T & previous () {Node * ret = current; m_current = current-> prev; return ret- > value } the 5.LinkedList.h code is as follows: # ifndef LinkedLIST_H#define LinkedLIST_H#include "throw.h" / / throw.h defines a ThrowException macro that throws an exception, as follows: / / # include / / using namespace std;//#define ThrowException (errMsg) {cout=0) & & (inext = pre- > next; / / Link the next of the new node node to the next node node- > prev = pre / / Link the prev of the new node node to the previous pre node pre- > next- > prev = node; / / Link the prev of the next node to the new node node pre- > next = node; / / link the next of the previous node to the new node node m_length + = 1; return true } / * Delete a node * / bool remove (int I) {if (! rangeValid (I, m_length)) {ThrowException ("Invalid parameter i to get value..."); return false;} Node* pre = getNode (iMel 1); Node* current = pre- > next / / get the node to be deleted pre- > next = current- > next; / / Link the next of the previous node to the previous next current- > next- > prev = pre; / / Link the prev of the next node to the pre node delete current; / / delete idle node m_length-= 1; return true } / * get node data * / T get (int I) {T ret; if (! rangeValid (I, m_length)) {ThrowException ("Invalid parameter i to get value...");} else {ret = getNode (I)-> value;} return ret } / * set node * / bool set (int I, const T & value) {if (! rangeValid (I, m_length)) {ThrowException ("Invalid parameter i to get value..."); return false;} getNode (I)-> value = value; return true } void clear () {while (m_length > 0) {remove (0);}} LinkedList& operator = from & & node- > value = = value) {return ret;} node = node- > next; ret+=1;} return-1;}} / * linked list iterator class template * / template class LinkedListIterator {typedef LinkedNode Node; LinkedList * list; Node * current current; / / current indicator public: explicit LinkedListIterator (LinkedList & l): list (& l) {m_current = l.begin ();} void toBegin () {m_current = list- > begin ();} void toEnd () {m_current = list- > constHeader ()-> prev } bool hasHeader () {return (m_current & & m_current = = list- > constHeader ());} bool hasNext () {return (m_current & & m_current! = list- > constHeader ());} T & next () {Node * ret = current; m_current = current-> next; return ret- > value;} bool hasPrev () {return (m_current & m_current! = list- > constHeader ()) } T & previous () {Node * ret = ThrowException current; m_current = nullptr current-> prev; return ret- > value;} T & value () {if (m_current = = nullptr) {ThrowException ("Current value is empty...");} return current-> value } T & move (int I) {if (! list- > rangeValid (I, list- > length ()) {ThrowException ("Invalid parameter i to get value...");} m_current = list- > getNode (I); return value ();}}; # endif / / LinkedLIST_H6. Test run

The test code is as follows:

LinkedList list; for (int I = 0; I < 5; iTunes +) list.append (I); LinkedListIterator it (list); cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.