From: HAPPCOCK Forum
Node class
#ifndef node_h #define node_h Template
Class node // single link class
{
PUBLIC:
TYPE DATA;
Node
* LINK;
Node (): data (Type ()), link (null) {}
Node (const type & item): Data (item), link (null) {}
Node (Const Type & Item, Node
* P): Data (item), LINK (P) {}
}
#ENDIF
[Description] Because there is too much place to use this structure in the data structure, if you use the "data structure" declare, that declaration doesn't know how much it is better than this class. It is better to open a member. In fact, this structure is just the Struct in C, except for the convenience of initialization, there is no need for any method, the original book is a snake. Here's it shows that the PUBLIC section of the linked list does not return a function of Node or Node *, so other classes are not likely to use this open interface to operate the node in the list.
[Important Modification] The default constructor of the original book is this Node (): Data (NULL), LINK (NULL) {}. I was originally written, the result When I expanded, I found that it was wrong. When Type is a structure rather than a simple type (int, ...), no NULL value cannot be simplified. Doing so makes the defined template can only be used for very few simple types. Obviously, the default constructor of Type should be called here. This also requires that the class here must have a default constructor. This default constructor is used when constructed the chain table below. Of course, here is the latch table of the agreement with the head node, please think yourself if you don't take the head node.
[Gossip] Please do not have any doubts about INT * P = New Int (1); this syntax is actually int rt can also see a Class.
Single-link table class definition and implementation
#ifndef list_h # define list_h # ifndef Ture #define Ture 1 # Endif # ifndef false #define false 0 # endiftypedef int bool; #include "node.h" Template
Class List // Single List Definition
{
/ / Basically no parameters of member function operations are current nodes, namely the node of Current fingers
// I think "1st Node" is the 0th node, please note that the last node is the 0th node when the length is 1.
PUBLIC:
List () {first = current = last = new node
prior = NULL;}
~ List () {makeempty (); delete first;
void makeempty () // blanket
{
Node
* q;
While (first-> link! = null)
{
Q = first-> link;
First-> link = q-> link;
Delete q;
}
INITIALIZE ();
}
Bool isempty ()
{
IF (first-> link == null)
{
Initialize ();
Return Ture;
}
Else Return False;
}
INT length () const // calculates a single-link length with a header node
{
Node
* p = first-> link;
INT count = 0;
While (p! = null)
{
P = P-> link; count ;
}
Return count;
}
TYPE * GET () // Returns the address of the current node's data field
{
IF (current! = null) Return ¤t-> data;
Else Return NULL;
}
Bool Put (Type const & value) // change the DATA of the current node to make it value Value
{
IF (Current! = NULL)
{
Current-> Data = Value;
Return Ture;
}
Else Return False;
}
TYPE * getNext () // Returns the address of the data field of the next node of the current node, does not change the CURRENT
{
IF (current-> link! = null) Return ¤t-> link-> data;
Else Return NULL;
}
TYPE * NEXT () // Moves Current to the next node, return the address of the node data field
{
IF (Current! = Null && Current-> Link! = NULL)
{
PRIOR = CURRENT;
Current = Current-> Link;
Return ¤t-> data;
}
Else
{
Return NULL;
}
}
Void insert (const type & value) // Insert the node behind the current node, does not change the current
{
Node
* p = new node
(Value, Current-> Link);
Current-> link = P;
}
Bool INSERTBEFORE (CONST TYPE & VALUE) / / Insert a node in front of the current node, does not change the Current, change the prior
{
Node
* p = new node
Value;
IF (Prior! = NULL)
{
P-> Link = Current;
prior-> link = p;
PRIOR = P;
Return Ture;
}
Else Return False;
}
Bool Locate (INT I) // Moves Current to iPatho
{
IF (i <= -1) Return False;
Current = first-> link;
For (int J = 0; current! = NULL && J
PRIOR = CURRENT;
IF (current! = null) Return Ture;
Else Return False;
}
Void first () // Moving Current to the head
{
Current = first;
PRIOR = NULL;
}
Void end () // Mobile current to the end
{
IF (Last-> Link! = NULL)
{
For (; current-> link! = null; current = current-> link)
PRIOR = CURRENT;
Last = CURRENT;
}
Current = last;
}
Bool Find (const type & value) // Move current to data equal to Value node
{
IF (ISEMPTY ()) Return False;
For (current = first-> link, prior = first; current! = null && current-> data! = value;
Current = Current-> Link)
PRIOR = CURRENT;
IF (current! = null) Return Ture;
Else Return False;
}
Bool remove () // Deletes the current node, and the current point to the next node, if the current is tailing, then the current = null
{
IF (Current! = Null && Prior! = NULL)
{
Node
* p = current;
prior-> link = p-> link;
Current = P-> link;
Delete P;
Return Ture;
}
Else Return False;
}
Bool removeafter () // Delete the next node of the current node, does not change the CURRENT
{
IF (current-> link! = null && current! = NULL)
{
Node
* p = current-> link;
Current-> link = P-> link;
Delete P;
Return Ture;
}
Else Return False;
}
Friend Ostream & Operator << (Ostream & Strm, List
& l)
{
L.First ();
While (l.current-> link! = null) strM << * L.Next () << "
STRM << Endl;
L.First ();
Return Strm;
}
protected:
/ * Is mainly added to the efficient income algorithm. Because INSERT (), remove (), removeafter () is possible to change Last but do not change Last so this algorithm is not correct if this is not used in public unless it is not used. But in addition to being very useful in the queue, LAST is very useful in other times, there is no need to reduce INSERT (), remove () efficiency for this purpose, so put this part into protected, actually mainly inheriting the queue * / Void LastInsert (const type & value)
{
Node
* p = new node
(Value, Last-> LINK);
Last-> link = P;
Last = P;
}
Void Initialize () // Resets the pointer when the table is empty
{
Current = last = first;
PRIOR = NULL;
}
// This part of the function returns type Node
The pointer is an interface for extending the List function.
Node
* pget ()
{
Return Current;
}
Node
* pnext ()
{
PRIOR = CURRENT;
Current = Current-> Link;
Return Current;
}
Node
* pgetnext ()
{
Return Current-> Link;
}
Node
* pgetfirst ()
{
Return first;
}
Node
* pgetlast ()
{
Return Last;
}
Node
* PgetPrior ()
{
Return prior;
}
Void Putlast (Node
* P)
{
Last = P;
}
// This part is inserted into the delete function that does not establish or delete the node, which is an in situ operation.
Void Insert (Node
* P)
{
P-> Link = Current-> LINK;
Current-> link = P;
}
Void Insertbefore (Node
* P)
{
P-> Link = Current;
prior-> link = p;
PRIOR = P;
}
Void LastInsert (Node
* P)
{
P-> link = NULL;
Last-> link = P;
Last = P;
}
Node
* premove ()
{
IF (Current! = Null && Prior! = NULL)
{
Node
* p = current;
Prior-> link = current-> link;
Current = Current-> Link;
Return P;
}
Else Return NULL;
}
Node
* premoveafter ()
{
IF (current-> link! = null && current! = NULL)
{
Node
* p = current-> link;
Current-> Link = Current-> link-> link;
Return P;
}
Else Return NULL;
}
Private:
List (Const List)
& l);
Node
* First, * Current, * prior, * last;
// Try not to use Last, if you do not use end () to make the pointer Last correctly
}
#ENDIF
[Description] I put the function of the original book's cursor class Iterator in the chain table class, shielded the return value as Node and Node * type interface, such a simple, practical, and expandable performance.
When I finished my post, I found the advantage of the original book, that is, my practice. If you use the original author, you only need to write the corresponding function implementation when you complete a function. In my definition, a class must be derived first, then this feature is used as a member or a friend. But this comparison does not specify the definition of the book than me is reasonable. First, there are not many situations that use to operate, and the post-book operation is just a special case; in other words, the definition in the book is only more practical for the completion of the book. Second, when using the linked list, there is usually only a few functions such as insert, delete, take data, search, etc., my definition is enough. When a software is completed, the expansion function of the linked list is very clear in the design phase. At this point, a new class can be used in the entire software, which is more advantageous for the overall plan. For the operation of a single linked list, it is better understood as a member function. That is to say, my definition is not bad.
Single-stranded listing has some people recommend that it is best to separate the linkers and linked lists, C standard libraries are doing this; but for beginners, a class is better than two kinds of good operations. I don't know if this part of this section is tested, but I can't understand this statement:
ListNode
* PA, * Pb, * pc, * p;
Listiteratraiter (ah.poly);
Listiterator
Biter (ah.poly);
PA = pc = aiter.first (); PB = P = Biter.First ();
............................
PA-> Coef = PA-> Coef PB-> Coef;
P = Pb; PB = biter.next (); delete P;
What is PA, PB, P? You said this is very clear, ListNode
Such a node is. But according to the definition of the original book, the listiterator :: first (), etc. The function returns to the pointer to the DATA domain, how can they assign a value directly? In the following, the area pointed out of the PB directly decomposed TERM's data, that is, point to Term structure; then let ListNode
Type pointer P Point to this Term structure, finally, actually delete this structure, God, ListNode
The DATA field of such a node is delete!
If you start from the basic node operation, no one will get so messy. But it is because there is a few classes, many things are negligent. Therefore, I don't doubt the standard library's approach, just for beginners, it is best to operate only to one class. I have done this program based on my definition. I don't appreciate the in situ operation, the polynomial addition ( ), POLYA POLYB, and then b is gone, A will have a bunch (or less a bunch); how do you do intj intk? I have no change in J and K. In this way, heavy duty " " is not as well as Polya.Add (polyb) or PolyAdd (Polya, Polyb).
One yuan multi-model definition and implementation
#ifndef polynomial_h # Define Polynomial_h # include "list.h" Class Term {public: int Coef; int exp; term (): Coef (0), Exp (0) {} TERM (INT C, INT E): Coef c), Exp (E) {} TERM (INT C): Coef (c), Exp (0) {}}; Class Polynomial: List
{
PUBLIC:
Void input ()
{
COUT << Endl << "Enter the factor and index of the multi-term";
COUT << Endl << "Note: Please enter the items in descending order, the input coefficient 0 indicates the end" << ENDL;
INT COEF, Exp;
For (int i = 1; i )
{
Cong << "" "" << i << "is the coefficient:";
CIN >> COEF;
IF (COEF)
{
Cout << "Index:";
CIN >> Exp;
Term Term (COEF, Exp);
INSERT (TERM);
}
Else Break;
}
}
Void print ()
{
Cout << Endl;
First ();
IF (! iSempty ())
{
Term * p = next ();
COUT << p-> Coef;
IF (p-> eXP)
{
Cout << "x"; if (p-> exp! = 1) cout << "^" << p-> exp;
}
While (NEXT ()! = NULL)
{
p = get ();
IF (P-> Coef> 0) COUT << " ";
COUT << p-> Coef;
IF (p-> eXP)
{
Cout << "X";
IF (p-> exp! = 1) cout << "^" << p-> exp;
}
}
}
Cout << Endl;
}
Friend Void Polyad (Polynomial & Polya, Polynomial & Polyb)
{
Node
* Pa, * Pb;
POLYA.FIRST (); polyb.first ();
PA = polya.pnext (); pb = polyb.pnext ();
While (Pa! = null && pb! = null)
{
IF (PA-> DATA.EXP == PB-> DATA.EXP)
{
PA-> data.coef = pa-> data.coef pb-> data.coef;
Polyb.remove ();
IF (! PA-> DATA.COEF) polya.remove ();
Else Polya.pnext ();
}
Else
{
IF (PA-> DATA.EXP> PB-> DATA.EXP)
{
Polyb.premove ();
POLYA.INSERTBEFORE (PB);
}
Else IF (PA-> Data.exp
}
PA = polya.pget (); pb = polyb.pget ();
}
IF (pa == null)
{
POLYA.PGETPRIOR () -> link = Pb;
Polyb.pgetPrior () -> link = null;
}
}
}
#ENDIF
[Description] For polynomial, usually we are writing, so I ask for descending input. But for doing addition, it is convenient to be somewhat, so, in fact, it will become an ascended order. For the output format (I don't like this from C, try to take care of the habits, but when the number of factories is 1, it will output the factor, I really don't want to take an actual application. Outout. The function is very complicated. For me, it is convenient, the output has become ascended, please include it. The test program will not be given, it is very simple. In the continuation, I will complete a dollar polynomial " " "-" × "" = "overload - why there is no" ÷ ", this kind of operation, I will take a pen, I don't have it, I am more worried. I also clearly remember the pain when the multi-byte division program was written. In the next article, you can write A = B C * D; A.Print ().
In the following, some heavy load operators will be an example of our work will be to make a polynomial operation look more in line usage. Complete this is what I think I will change the " " of the original book to PolyAdd (), always give it to you.
Hereinafter, the overload of the assignment operation of the single-strand list will be completed, please add this part to the public part of the list class. Indeed, this part can also be placed in a polynomial class; however, copying a polynomial is actually copying a single-link table, making a multi-term assignment with its single-lapse list, making the derived class can be shared. Operator = (Const List)
& l)
{
Makeempty ();
For (Node
* p = l.first-> link; p! = null; p = p-> link) LastInsert (P-> DATA);
}
Remember this List in the private of the List class (Const List)
& l)? When I was afraid of it, I used it directly, since now = I can use it, for this grammar List
B = a; By the way, it will be completed. Now you can put it from private to public.
List (Const List)
& l)
{
First = current = last = new node
PRIOR = NULL;
For (Node
* p = l.first-> link; p! = null; p = p-> link) LastInsert (P-> DATA);
}
Finally, I can write A = B C * D this way.
friend Polynomial operator (Polynomial & polyA, Polynomial & polyB) {Polynomial tempA = polyA; Polynomial tempB = polyB; PolyAdd (tempA, tempB); return tempA;} friend Polynomial operator * (Polynomial & polyA, Polynomial & polyB) {Node
* PA = polya.pgetfirst () -> link;
Node
* Pb = polyb.pgetfirst () -> link;
Polynomial Polytempa, PolyTempb;
INT COEF, Exp;
IF (PA == NULL || PB == NULL) Return Polytempa;
For (pa = polya.pgetfirst () -> link; pa! = null; pa = pa-> link)
{
For (PB = polyb.pgetfirst () -> link; pb! = null; pb = pb-> link)
{
COEF = PA-> Data.coef * Pb-> data.coef;
Exp = PA-> DATA.EXP PB-> Data.exp;
Term Term (COEF, Exp);
Polytempb.lastInsert (TERM);
}
PolyAdd (POLYTEMPA, POLYTEMPB);
Polytempb.initialize ();
}
Return PolyTempa;
}
