Data structure (2)

The data structure (1) After passing to the Internet, it has been supported by many people and the support of classmates, and thank you here. This kind of concern and support have brought me more power, which makes me feel better, and then take the knowledge and experience you have for exploring. Other people helping to a certain extent, are improving themselves.

In this article I continue to introduce the linear table, it is another linear storage structure ------ linked list. Links, although and arrays are linear storage structures, there is a big difference. The fundamental difference is that the linked list is not stored with a continuous address space, so it is not possible to obtain data in the form of a subscript as the array. It uses a pointer called "Next" to point to the next storage element, of course, can also point to a storage element, which is referred to as "prev". If you can't store the elements in the form of a subscript being considered a linked list, then the linked list can be easily changed to change its storage capabilities. It is because the linked list is not to store an element with a continuous address space but to mark the position of the upper element and the next element with a pointer, so it can change the address of the element by changing the "NEXT" pointer and "prev" pointer. The structure of the linked list. For example: A-> B-> C, three elements are stored on this chain. Now I want to delete B, and change the length of the linked list. So, A-> C, DELETE B, realized our goal.

A single-strand table, a two-way linked list, and a loop list are included in the family of the linked list. According to different needs and different occasions, we can choose to use different forms of linked lists to meet our needs.

The list is a brief description of the list, maybe you are not very clear, then take a look at the code below you will be open. Here is a two-way chain table as an example.

First, we want to define a node class (Listerlement). This class contains three member variables, one is used to store data (Datum), called data field; one is used to point to an address (PPREV), called a PREV field; one is used to point to the next node Address (PNEXT), called a NEXT domain. Other member functions only do some simple operation processing.

Template Class LinkedList;

Tbertlement {private: t dam; listelement * pprev; listElement * pnext; public: / **************************** *********************************************************** * * Infut parameter: * output parameter: * Return Values: ****************************************** ***************************************************** / LISTELEMENT () { DATUM = 0; pprev = 0; pnext = 0;} / ******************************************* *************************************************** * function explain: * * Input parameter: * Output parameter: * Return Values: ***************************************************** ********************************************* / LISTELEMENT (t const & _datum, listlement * _prev, listelement * _next) {DATUM = _DATUM; pprev = _prev; pnext = _next;} / ******************************************* ***************************************** * Function Explain: * * Input Parameter : * Output Parameter: * Return VALUES: ************************************************* ************************************************** / LISTELEMENT (Listelement Const & PCLASS) {IF Pclass! = this) && (pclass! = null)) {this-> datum = pclass.datum; this-> pprev = pclass.pprev; this-> pnext = pclass.pnext;}} / ****** *********************************************************** ********************* * function explain: * * input parameter: * output parameter: * Return Values: ************ *********************************************************** *************** / T Const & GetDatum () const {return Datum

} / ******************************************************* ****************************** * function explain: * * Input parameter: * Output parameter: * Return Values: **** *********************************************************** *********************** / VOID SETDATUN (T Value) {DATUM = Value;} / ************* *********************************************************** ************* * Function Explain: * * Input Parameter: * Output Parameter: * Return Values: ******************* *********************************************************** ******** / Listelement * getnext () const {return pnext;} / *************************************** ******************************************************** * Function EXPLAIN: * * Input parameter: * output parameter: * Return Values: ************************************************************** **************************************************** / VOID SETNEXT (Listelement * Const PNEW ) {PNEXT = PNEW;} / ************************************************************ ********************************* * Fu NCTION EXPLAIN: * * OUTPUT parameter: * Return Values: ******************************************* **************************************************** / LISTELEMENT * GETPREV () Const {Return PPREV;} / ************************************************************ ***************************************** * function explain: * * Input parameter: * Output parameter: * Return Values: *********************************************************** ************************************* / VOID SETPREV (listElement * const pnew) {pprev = PNEW;

} / ******************************************************* ****************************** * function explain: * * Input parameter: * Output parameter: * Return Values: **** *********************************************************** *********************** / LISTELEMENT & OPERATOR = (& listelement! = This) {this-> Datum = Listelement.datum; This-> pprev = listelement.pprev; this-> pnext = listelement.pnext; return * this;} Return * this;} // Friend LinkedList ;};

LinkedList is the chain class we have to use. This class will put each node and eventually form a complete chain. We let it become a friend of the Listerlement class, in order to get better access to the data domain, the Prev domain, and the NEXT domain.

Template Class LinkedList {Private: Listelement * Phead; Listelement * Ptail; Int Count; Public: LinkedList (): PHEAD (0), Ptail (0), Count (0) {} LinkedList (Listelement * _Head, Listelement * _tail) {PHEAD = _Head; ptail = _tail; count = 0;} ~ linkedList () {purge (); linkedList (const link); linkedList & operator = LinkedList Const &); Listelement const * getHead () const; listElement const * gettail () const; limited (int POS); Bool ISempty () const; limited () const; limited () Const; ListerEmpty * GetFirst; Const; Listelement * getlast () const; void repnd (t const); void delelement (int POS); Void Removeat (Void purge (); Void Inserafter (Listelement const *, t const &; void inSerbefore (Listelement const *, t const "; void setcountSub (); void setcountsub (); int getLength ();}; / ********; / ******** *********************************************************** ******************* Function Explain: * * Input Parameter: * Output Parameter: * Return Valu ES: ********************************************************** ************************************************ / TEMPLATE Inline Void LinkedList :: purge () {while (0 ! = PHEAD) {Listelement * const ptemp = PHEAD; PHEAD = PHEAD-> getNext (); setcountsub (); delete Ptemp;} PTAIL = 0;} / ************* *********************************************************** *************** Function Explain: * * Input parameter: * Output parameter: * Return Values: ********************* *********************************************************** ********* / TEMPLATE Inline Listelement * LinkedList

:: getfirst () const {if (0 == PHEAD) {Try {throw Domain_ERROR ("List is Empty!");} Catch (Exception & E) {CERR << "caught:" << E.What () < getdatum ();} / ***************************************** ***************************************************** FUNCTION EXPLAIN: * * Input parameter: * output parameter: * Return Values: ****************************************************** ***************************************************************************************** / TEMPLATE Inline Listelement * LinkedList :: getLast () const {f (0 == ptail) {try_rrow std :: domain_error ("list is empty");} catch (exception & e) {caugh < getdatum ();} / **************************************** *********************************************************** Function explain: * input parameter: * output parameter: * Return Values: ******************************************* ************************************************************************************** / TEMPLATE Inline void LinkedList :: Prepend {Listelement * Ptemp = new Listelement (Item, 0, PHEAD); if (0 == PHEAD) {PTAIL = PTEMP; PTEMP = NULL; setCountPlus (); } / ******************************************************* ***************************** Function Explain: Last INSERT * * INPUT parameter: * output parameter: * Return Values: ** *********************************************************** ********************************** / TEMPLATE Inline Void LinkedList :: Append (T Const Item) {Listelement * Ptemp = New Listelement (item, ptail, 0); if (NULL ==

PTEMP; PTAIL = PTEMP; PTEMP = NULL; setCountPlus ();} / ********************************** *********************************************************** *********** Function Explain: * * Input Parameter: * Output Parameter: * Return Values: ********************** *********************************************************** **** / template Inline LinkedList :: LinkedList (Const LinkedList & LinkedList): PHEAD (0), PTAIL (0) {Listelement const * ptr; for (Ptr = LinkedList .phead; ptr = ptr-> getNext ()) {append (ptr-> getdatum ());}} / ******************* *********************************************************** ******** Function Explain: * * Input Parameter: * Output Parameter: * Return Values: ********************************* *********************************************************** ** / template Inline LinkedList & LinkedList :: Operator = (LinkedList const & linkedlist) {if (& linkedList! = this) {purge (); Listelement const * ptr; For (PTR = LinkedList.phead; Ptr ! = 0; PTR = Ptr-> getNext ()) {append (ptr-> getdatum ());}} return * this;} / ******************* *********************************************************** ********** Function Explain: * * Input Parameter: * Output Parameter: * Return Values: ******************************** *********************************************************** *** / template inline void linkedlist :: removeat (t const & item) {listElement * Ptr = PHEAD; Listelement * prevptr = 0; while ((PTR! = 0) && (PTR-> getDATUM ()! = item)) {prevptr = Ptr; PTR = Ptr-> getNext ();} if (0 =

= PTR) {throw std :: invalid_argument ("item not found");} if (ptr == PHEAD) {PHEAD-> getNext () -> setprev (null); PHEAD = Ptr-> getNext (); else {Ptr-> getNext () -> setPrev (prevptr-> setnext (ptr-> getnext ());} if (ptr == ptail) {ptail = prevptr; prevptr-> setnext (null);} setcountsub (); Delete PTR;} / *********************************************************** ******************************************** FUNCTION EXPLAIN: * * Input Parameter: * Output Parameter: * Return VALUES: ****************************************************************** ************************************************ / TEMPLATE Inline Void LinkedList :: Inserafter (Listelement Const * Arg, T Const & Item) {Listelement * Ptr = const_cast *> (arg); if (0 == Ptr) {throw std :: invalid_argument ("invalid position");} // Listelement * const ptemp = new listElement (item, ptr-> getnext (), 0); Listelement * const ptemp = new listElement (item, ptr, ptr-> getNext () ); Ptr-> setnext (PTEMP); Ptr-> getNext () -> setPREV (PTEMP); if (ptail == Ptr ) {PTAIL = PTEMP;} setCountPlus ();} / *********************************************** ************************************************** Function Explain: * * INPUT parameter: * Output parameter: * Return Values: **************************************************** ***************************************************************** / Template Inline Void LinkedList :: INSERBEFORE Listelement Const * Arg, T Const & Item) {Listelement * PTR = const_cast *> (arg); if (0 == Ptr) {throw std :: invalid_argument ("invalid position" );

} Listelement * const ptemp = new listElement (item, ptr-> getprev (), ptr); if (PHEAD == PTR) {PHEAD-> setPrev (PTEMP); PHEAD = PTEMP;} else { Ptr-> getPrev () -> setnext (ptemp); PTR-> setPrev (PTEMP);} setCountPlus ();} / ******************************** *********************************************************** ****** Function Explain: Get The element which is designated. * * Input parameter: * output parameter: * Return Values: ********************** *********************************************************** ****** / Template inline Listelement * LinkedList :: getElement (int POS) {Try {IF ((POS <0) || (POS> getLength ())) { Throw std :: domain_error ("list is empty");} listElement * prevptr = PHEAD; for (int i = 1; i getnext ();} return prevptr; {CATCH (EXCEPTION & E) {CERR << "Caught: << E.WHAT () << Endl; return null;}} / ********************** *********************************************************** ********* Function Explain: delete the elem Ent Which is designated. * * Input parameter: * output parameter: * Return VALUES: ******************************************* ************************************************************************************** / TEMPLATE Inline Void LinkedList :: Delelement (int POS) {Listelement * TempleElement = 0; // New Listelement (0,0,0); TempleElement = getElement (POS); if ((NULL) == Templement-> getPrev ()) && (NULL! = templement-> getNext ())) {tempelement-> getnext () -> setprev (0); PHEAD = Templement-> getNext ();} else ing Null! = Templelement-> getPrev ()) &&

(NULL == Templement-> getNext ())) {tempelement-> getPrev () -> setnext (0); ptail = tempelement-> getPrev ();} else {tempelement-> getPrev () -> setnext (TempleElement- > GetNext ()); tempelement-> getNext () -> setprev (Templelement-> getPrev ());} setcountsub (); delete templement;} / ************************ *********************************************************** *********** Function Explain: * Input Parameter: * Output Parameter: * Return Values: ********************** *********************************************************** **** / template Inline Bool LinkedList :: == PHEAD) {Return True;} else {return false;}} / ******* *********************************************************** ******************** Function Explain: * INPUT parameter: * output parameter: * Return Values: ************* *********************************************************** ************ / TEMPLATE Inline void LinkedList :: setCountPlus () { count;} / ************* ********************************************************* **************** FUNCTION EXPLAIN: * * Input parameter: * Output parameter: * Return Values: **************** *********************************************************** ********** / TEMPLATE Inline void LinkedList :: setCountSub () {--count;} / **************** *********************************************************** *********** Function Explain: * * Input Parameter: * Output Parameter: * Return Values: *********************** *********************************************************** ***** / Template Inline int linkedlist :: getLength () {Return Count