Author: happycock from: Yesky
The original book is much more content, and at least a lot relative to the circular chain list. I believe that when you make a single-stranded pointer domain, this part should be difficult to fall. Now my question is, can you send two-way linked list from a single-link table?
You can have several practices: one is to define a double-link node - but it must call node, this is something wrong; otherwise you have to copy a single-link realization file, put it Node all replaced with your double-link name name, but this is not called inherited. Another approach is to define a structure for example:
Template class newtype {public: type data; node * link;}
When you derive a two-way linked list, you write Template Class DBLLST: Public List >, pay attention to the continuous two ">" There is a space. Or do not define such a structure, take the Node type directly, for example, I will give it below. However, please note that you want to complete the "==" overload, otherwise you have to rewrite the Find function, and other certain operations are not convenient. Before starting your bidirectional linked list, you want to add the interface to the current pointer and the current forward-drive pointer to the base class, as shown below:
Protected: Void Put (Node * p) // Try not to use, the two-way linked list will use this complete mobile {current = P;} void putprior (Node * p) // Try not to use, the reason is { PRIOR = P;}
Because this interface is very dangerous, it is almost not available, so I have not given it in front, but I have to complete the two-way linked list of "outstanding" advantages - moving the current pointer forward, must be used. In addition, I have never planned from a single-link watch to derive double-linked list, below you will see that this process is very annoying, or even rewriting a provincial thing, the effectiveness is not very good, this labor force What does it mean to do if it does not want? Indeed, I also think I am in the rhombus. Definition and implementation
#ifndef dbllist_h # define dbllist_h # include "list.h" template class dbllist: public list > {public: type * get () {if (pget ()! = null) Return & Pget ( ) -> data.data; else return null;} type * next () {pNext (); return get ();} type * prior () {i (pgetPrior! = Null) {PUT (PGETPRIOR ()); putprior (Node > *) Pget () -> Data.Link; return get ();} return null;} void insert (const type & value) {node newdata (value *) Pget ()); list > :: insert (newdata); if (pgetnext () -> link! = Null) PgetNext () -> link-> data.link = (Node < TYPE> *) PgetNext ();} Bool Remove () {if (list > :: remove ()) {pget () -> data.link = (node *) pgetPrior (); Return Ture;} Return False;}}; # ENDIF [Description] Completed only the most important Insert and REMOVE functions and the most featured PRIOR () function, other no re-implement. So, you use a single-link list here, I don't guarantee certain correct. Moreover, the pointer type conversion here is dependent on the compiler, and I can't affirm that other compiler can be compiled and correct. For DATAs who don't let PRIOR return to head nodes, I consider it three. Use first (); get (); such a combination can also return, so I don't care about him, so if you use prior to return NULL, it will The head node of the DATA output is coming. [Supplement] As for the two-way circular chain list, you can also derive from this two-way linked list (in the method of derived loop linked list); or derive from the loop list (in the method of derivating the two-way linked list), it will take the same example (then doing this, I It's really troubled to vomit blood). At this point, it can be concluded that various structures of the linked list can be derived from a single-link table. In other words, the single-link table is fundamentally, if the study is a single-link table, various chain structures are not difficult. A small test program
Void dbllistTest_int () {dbllist a; for (int i = 10; i> 1; I - a.insert (i); for (i = 10; i> 1; i -) cout << * a.next () << "; a.first (); cout << Endl; cout << * a.next () << endl; cout << * a.next () << endl; cout < <* A.next () << endl; cout << * a.next () << Endl; A.Remove (); cout << * a.get () << endl; cout << * a.prior () << Endl; cout << * a.prior () << endl; cout << * a.prior () << end1;} [post] From my unrealistic implementation of the two-way list, I I don't want to achieve two-way linked lists, I just try to maximize the use of existing classes to implement this type. Practice has proved that it is better to override one. Others look well, don't worry about it. However, this process makes me more about the call and return of the function. If you can write the INSERT function here for the first time, I believe that you must feel a certain amount of C . I also think that only do some innovations can be more in-depth. For example, these data structures can be used directly in the C standard library (STL), why we have worked hard, the result is not as good as people. To learn, this is the reason, this is the reason that everything is stupid.
