Data structure (3)

Two articles introduced two linear storage structures, arrays, and linked lists. They have their own advantages and disadvantages, so that you have to use them. If you use it, you will help you.

The care and lift of the friends, many pairs of two articles have been commented. Many people feel that it is too long and is too lazy to look. I don't think that the empty things and theories have written enough in the textbook, and you need to write some practical things. When schools, many times are that books don't know how to start. In fact, this time maybe theoretical knowledge is very familiar, and it is probably no problem. If you don't have to write code demonstration, you can go to the second grade learning, the school girl lecture class (exaggerated). At that time, I wanted to find a write code, but the conditions were not allowed. Now work, I feel that some simple things will be seen to see if I still have any problems. Maybe it's not perfect, there will be a lot of vulnerabilities, but I think it can still play the effect of "understanding the spirit". The code is much more, because the package is more than the method, but also uses some unused things, which is also an improvement in breadth.

I wrote these code, debug passes on VC6.0, where I also make a single step debugger. You can copy these code and add #include to start debugging.

Write the topic after doing some replies for the stickers. This article introduces a stack.

In the textbook, the stack is like a gun shuttle, and the last bullet will go out first. This is already very image, it is also very understandable. It is said that the stack is the container that is only added and deleted only on the top of the stack. Therefore, the stack is a "secondary first out" (LIFO) data structure. So, what are the functions of the stack?聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽 聽聽I went back and returned to the work that I just interrupted. " As can be seen from this example, the stack energy records have been partially completed.

Say the basic concept, this is very understandable. I think it is more conducive to understanding. For example, when a method is called in the program, the address of the first instruction after the instruction is called into the top of the stack in the method of the current thread. When the return command of the called method is performed, the address is popped up from the stack and then proceeding from the address.

The simplest data structure in many containers is the stack. It only provides PUSH and POP operations. The former is pressed, the latter is popped up. In addition to both operations, typical stack operations also provide a TOP operation. It always returns the data item on the top of the stack without deleting it.

First, create a base class for stack. This class defines three pure virtual functions of PUSH, POP, and TOP. This polymorphic method can be used to implement the stack of this data structure in our approximate group and linked list.

Template class stack {public: Virtual t & top () const = 0; Virtual Void Push (T &) = 0; Virtual T Pop () = 0; protected: int NLENGTH; int ncount;};

The way to implement Stack with a chain is as follows:

Template Class StackList: Public Stack {public: stacklist (int NcNT) {ncount = 0; NLENGTH = NCNT; PLIST = New LinkedList ();} ~ stacklist () {delete plist;} T & TOP () const {if (0 == nConut) {throw domain_error ("stack is empty!");} Return const_cast (plist-> getfirst () -> getdatum ());} void push & Value) {if (ncountt> NLENGTH) {Throw Domain_ERROR ("stack is full!");} Plist-> prepend (value); ncount;} T POP () {if (0 == nconut) {throw Domain_ERROR ("Stack is Empty!");} T TRESULT = PLIST-> getFirst () -> getDatum (); PLIST-> Removeat; --nconut; returnit;} private: LinkedList * PLIST; // int ncount; // int NLENGTH;}; The method of implementing Stack with arrays is as follows:

Template Class StackArray: Public Stack {public: stackarray (int NCNT) {POS = 0; NLENGTH = NCNT; NCOUNT = 0; PARRAY = New Array (NCNT);} ~ stackarray () {If (null! = Parray) {delete parray;}} T & TOP () const {if (0 == ncount) {throw Domain_ERROR ("stack is empty!");} Return (* parray) [POS - 1] } Void Push (T & Value) {IF (POS == NLENGTH) {Throw Domain_ERROR ("Stack is Full!");} (* Parray) [POS] = value; ncount; Pos;} T POP () {If (0 == ncount) {throw Domain_ERROR ("stack is empty!");} Int n = --pos; - Ncount; return (* parray) [N];} private: array * parray; // int NLENGTH; INT POS; // int ncount;};