The data structure is the basic class of computer professional. I didn't think there was anything in my school (of course, the teacher said that this is a very important course), which is useless in graduation design. It's almost two years, although it is still useless, but the gradually feeling of the data structure is increasingly important. This feeling is formed in the subtlety, so I find out that the textbook began to warm. The dust on the book is turned on, and suddenly I saw the loose page that was clipped in the book. The above recorded a paragraph of Mr. Houjie in "STL Source Analysis": "As a programmer, if you are a database programming, you can do not understand the assembly language. If you are writing drivers, you can don't have to know Artificial intelligence, can write a compiler, do not understand what computer graphics, the operating system kernel master does not have to master the website. However, if you don't understand the basic knowledge of the data structure and the algorithm, there is no basic skill of the data structure and algorithm, then It is qualified to become a programmer! " Seeing this, it seems that I returned to the era of confidence in the Chinese software in school. Oh, I have left the school for two years. If I don't want to see the kind of passion, it seems that I can't think of it.
Ok, let's talk about it. In the process of re-review, I realize the examples in the examples, and some have expanded. Here you take them out for your reference. Just like reading notes, but here, I have added some of my personal things, I hope to correct. (Reference: "Data Structure and Algorithm ------ Object-Oriented C Design Mode")
The embedded array is provided in C , but there are many shortcomings. For example: You cannot assign a number to another array, and the data is not crossed to the array, and the size of an array is static and fixed during compilation, unless the programmer uses dynamic memory allocation. Therefore, let's write a group class to improve these features. Just like the Carray class in the MFC, of course, the examples we write cannot be as good as the Microsoft package, however we can use a simple way to achieve complex features. Maybe it looks very low, it will be very slow, but it is indeed we write. Below is the definition of this array class, including member functions.
Template class array {private: t * pdata; unsigned int result; public: array (); array (array const); array (unsigned int, unsigned int = 0); ~ array (); T Const & Operator [] Const; T & Operator [] (int); array & operator = (array const "; bool operator == (array const);
bool IsEmpty () const; unsigned int GetBase () const; unsigned int GetLength () const; void SetLength (unsigned int, bool); void InsertAt (unsigned int nPos, T Value); void RemoveAt (unsigned int nPos);};
There are three member variables in the Private domain, and the member PDATA is a pointer to array data, member base, and length used to calculate the array subscript. Since the subscript starts from 0 in the array of C built-in, this is not changeable. Based, the member variable can help you modify this regulation. You can set the value of this variable at will, but if it is negative or more constructor than the length of the LENGTH will be processed according to the default. This class has been overloaded for [], =, == these three operators. In order to make this class support the subscript operation, assign value and compare operations. Of course, there may be a lot of bugs, which remains to be further modified.
# in c n n s;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; *********************************************** FUNCTION EXPLAIN: Default Construction Function * * Input Parameter: * Output parameter: * Return Values: **************************************************** ****************************************************** / TEMPLATE Inline Array :: array () : PDATA (New T [0]), Base (0), Length (0) {} / *************************************** *********************************************************** FUNCTION EXPLAIN: Overloaded Constructor, Free Set Base and Length * * Input Parameter: * Output Parameter: * Return Values: ************************ *********************************************************** **** / template inline array :: array (unsigned int unlength, unsigned int unbase) {ix (unbase> unblence) {length = 0; base = 0; pdata = new t [length];} else if (unbase <0) {base = 0; length = unlength; pdata = new t [length];} else {base = unbase; length = unlength; pdata = new T [{} / ***************************************************** ***************************************************** FUNCTION EXPLAIN: copy constructor * * Input parameter: * output parameter: * Return Values: ****************************************************** ******************************************************************************* / TEMPLATE Inline Array :: Array (Array Const & Array): PDATA (New T [Array.length]), Base (Array.Base), Length (Array.Length) {for (unsigned Int i = 0; i
} / ************************************************************************** **************************************** Function Explain: Destructor * * Input Parameter: * Output Parameter: * Return VALUES: *********************************************************** ************************************ / TEMPLATE Inline Array :: ~ Array () {delete [] PDATA; } / ******************************************************* *************************************** Function Explain: Returns INDEX Start Location * * Input Parameter: * Output Parameter: * Return VALUES : *********************************************************** ************************************** / TEMPLATE Inline unsigned int Array :: getBase () const {return base } / ***************************************************** **************************************** Function Explain: Return to Storage Length * * Input Parameter: * Return VALUES: *********************************************************** ************************************* / TEMPLATE Inline unsigned int Array :: getLENGTH () const {return length } / ****************** *********************************************************** ************ FUNCTION EXPLAIN: Overload Operator "=", implement two types of object assignment operation * * Input parameter: class object * Output parameter: * Return Values: **** *********************************************************** *********************** / TEMPLATE Inline Array & Array :: Operator = (Const Array & Array) {Array * & PTARRAY = const_cast *> (this); try {if (null == ptarray) {// throw std :: domain_ERROR ("Initialize Pointer First!"); PtaRay = new array (Array.getLength (), array.getbase ());} else {ptaRay-> setlength (array.getlength (), false);
} For (INT i = array.getbase (); i *> (this);} / ******************** *********************************************************** ******* Function Explain: Overload Operator "==", implement two class object comparison operations * * Input parameter: class object * Output parameter: * Return Values: ******** *********************************************************** **************************** / TEMPLATE Inline Bool Array :: Operator == (Array Const & Array) {f (this-> getLength () ! = array.getlength ()) {Return False;} Array * & ptaRay = const_cast *> (this);
For (int i = array.getbase (), int j = ptarray-> getBase (); i getLength (); i , j ) {if (array [i]! = (* ptarray) [j]) {return false;}} return true;} / ******************************************* ******************************************************* FUNCTION EXPLAIN : Heavy load operator "[]", implement the subscript operation of the class object * * Input Parameter: Index location * Output parameter: * Return Values: ****************** *********************************************************** ********* / TEMPLATE Inline T Const & Array :: Operator [] (int position) const {int const offset = position - base; try {= ((Offset> = INT) || (Offset <0)) {throw std :: out_of_range ("invalid position");}} Catch (Exception & E) {CERR << "caught: << E.What () << Endl } Return data [offset];} / ************************************************** ************************************* FUNCTION EXPLAIN: overload operator "[]", Implement the subscription operation * * Input Parameter: Index location * Output parameter: * Return Values: ********************************************************** **************************************** / TEMPLATE Inline T & Array :: Operator [] (int position) ) {INT const offset = posient - base; try {ife ((Offset> = (int) length) || (Offset <0)) {throw std :: out_of_range ("invalid position");}} catch (Exception & E ) {CERR << "Caught: << E.What () << Endl;} return pdata [offset];} / *********************** *********************************************************** ******* Function Explain: You can reset the storage capacity of the class object * * Input Parameter: The new length of the class object;
Whether to ask an element mobile sign * Output parameter: * Return Values: ****************************************************** *************************************************************************************************************** / TEMPLATE Inline Void Array < T> :: setlength (unsigned int newlength, bool bflag) {ix (getLength () == newLength) {Return;}
T * const newdata = new t [newLength]; if (bflag) {unsigned int const min = length Inline Bool Array :: ISempty () const {if (0 == length) {Return Ture;} else {return false;}} / ********************* *********************************************************** ************** FUNCTION EXPLAIN: Insert an element in the class object * * Input parameter: Specify Index position; insert value * Output parameter: * Return Values: ***** *********************************************************** ****************************** / TEMPLATE Inline Void Array :: Insert (unsigned int npos, t value) {ix (npos> length ) {Return;} i NT nnewlength = length 1; t * const pnewdata = new t [nnewlength]; for (int i = 0; i
Inline void array :: removeat (unsigned int NPOS) {i (npos> length) {return;} int nNewlength = length - 1; t * const pnewdata = new t [nnewlength]; for (int i = 0; I
