[Home, Previous, Next; Contents]
table of Contents
1 Foreword 1.1 Selected Textbook 1.2 Writing Reason 1.3 Some Conventions 1.4 History 1.5 Contact
2 Single-link table 2.1 code implementation 2.2 efficiency problem 2.3 Application: One yuan polynomial (addition and multiplication) 2.3.1 Basics 2.3.2 Code implementation 2.3.3 Description
3 Double Link Watch 3.1 Code Implementation 3.2 Description
4 cyclic chain list 4.1 Basic concept 4.2 Code implementation 4.3 Description 4.4 Application: Joseph
5.2 Code Implementation 5.3 Description 5.4 Application: Conversion to suffix expressions 5.4.1 Code implementation 5.4.2 Description
6 Queu 6.1 Basic Concept 6.2 Code Implementation 6.3 Application
7 Recursive 7.1 Basic Concept 7.2 Application 7.2.1 Sergey 7.2.2 Fiboaccai number 7.2.3 Hano Tag 7.2.4 Pasca Triangle (Yang Hui Triangle)
8 Binary Tree 8.1 Basic Concept 8.2 Code Implementation 8.3 Description 8.4 Application
9 Binary Search Tree 9.1 Basic Concept 9.2 Code Realization 9.3 Description
Chapter One
Foreword
1.1 selected textbook
The textbook I have chosen is "Analysis of Data Structure and Algorithm - C language Description" (original book 2), the name of the English version is "Data Structures and Algorithm Analysis in C", the author is :( US) Mark Allen Weiss . The original book has been rated as one of the 30 computer works in the 20th century. The reason why this book is chosen, but also because its simplified Chinese version is quite good, there is almost no obstacle to my reading. ^ _ ^
This textbook is the C language. Maybe many people will say that the C language is outdated, but I think it should be as simple as possible in the study of the data structure, so as to avoid entering the sub-branches of the language, but dilute theme. In fact, many universities (or even middle schools), data structures and algorithms are analyzed, such as MIT, extremely famous SICP courses. Oh, what else can you explain?
1.2 Reason for writing
Data structure and algorithm analysis is a compulsory course - but unfortunately, I am not a computer professional student at the university stage, so that I have learned this course without systematically follow the teacher. Now I have already worked, in the actual work, I often feel that my basic knowledge is not enough, there are many problems that cannot be solved. After experiencing a painful struggle, I chose self-study path, I want to learn this course.
Most of the code has been given in the textbook, so I basically only repeatedly knocked it once (or rewritten into C ), but this is not meaningless. We often feel that you have already understood it when you read a book, but if you really want to do your hand, you will feel unable to start. I think I personally enter a code and debug it, which is effective than any empty talk. In the specific code implementation, I may refer to MFC, STL ... but may also make certain modifications.
1.3 some conventions
I am using the Visual C 6.0 compiler and will write code with C / C (I may use C to rewrite the example in the original book, so that can be used in work, but some places will also use C), no Will use any of the platform-related features (so there is a better portability). The code style in the original book is very similar to my usual code style, but I may have some changes in some places.
I think the code of the data structure does not require any interface, so please create a new project, type Win32 Console Application, That is, a console project. Then add one .h header file and one .c / .cpp file. In the header file, I usually write 3 rows of fixed format pre-bucket statements as follows:
#ifndef __list_h__
#define __list_h__
// Todo: add header body code here
#ENDIF / / __LIST_H__
Indicates this is a list.h.
In addition, the implementation of the C operator NEW is not quite the same in different compilers. In VC6, if the New fails, it will return null. If I use the detection return value to determine if the New is successful, but if This code is compiled with another compiler, then pay special attention to whether the compiler is also used by null to indicate the NEW failed, otherwise it is likely to cause the unrecognized result.
In order to facilitate the debug memory leak, I will write such a code in some places:
#include
#include
#ifdef _Debug
#define debug_new new (_NORMAL_BLOCK, this_FILE, __LINE__)
#ENDIF
#ifdef _Debug
#define new debug_new
#undef this_file
Static char this_file [] = __file__;
#ENDIF
#ifdef _Debug
#ifndef assert
#define assert assert
#ENDIF
#ELSE // not _Debug
#ifndef assert
#define assert
#ENDIF
#ENDIF / / _DEBUG
as well as:
#ifdef _Debug
_CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#ENDIF
Don't use them directly when you read it, you can ignore it.
1.4 history
[2005-01-18] Two-fork search chapter. [2005-01-14] Two-Binary Tree Chapter. [2005-01-09] Recurrent chapter. [2005-01-08] Queue chapter. [2005-01-07] Stack chapter. [2005-01-05] Circulatory chapter chapter chapter. [2005-01-04] Double Link Map. [2004-12-30] Single-link table chapter.
1.5 Contact
Author: Luo Cong home page: http: //www.luocong.comE-Mail: admin [AT] Chapter luocong.com
Single list
Links are one of the most common, simplest and most basic data structures. Let's take a look at the implementation of single-strand tables.
2.1 code implementation
The implementation of single-link tables is as follows:
///
//
// filename: Slist.h
// Version: 0.10
// Author: Luo Cong
// Date: 2004-12-29 9:58:38
// Comment:
//
///
#ifndef __single_list_h__
#define __single_list_h__
#include
#include
#ifdef _Debug
#define debug_new new (_NORMAL_BLOCK, this_FILE, __LINE__)
#ENDIF
#ifdef _Debug
#define new debug_new
#undef this_file
Static char this_file [] = __file__;
#ENDIF
#ifdef _Debug
#ifndef assert
#define assert assert
#ENDIF
#ELSE // not _Debug
#ifndef assert
#define assert
#ENDIF
#ENDIF / / _DEBUG
Template
Class cnode
{
PUBLIC:
T data;
CNODE
Cnode (): DATA (t ()), Next (null) {}
CNODE (Const T &TData): Data (InitData), Next (NULL) {}
CNode (constly
}
Template
Class CSList
{
protected:
INT m_ncount;
CNODE
PUBLIC:
CSList ();
CSLIST (Const T &TData);
~ Cslist ();
PUBLIC:
INT ISEMPTY () Const;
INT getCount () const;
INT INSERTBEFORE (Const Int Pos, Const T Data);
INT INSERTAFTER (Const Int Pos, Const T Data);
Int Addhead (Const T Data);
Int Addtail (Const T Data);
Void Removeat (Const INT POS);
Void removehead ();
Void RemoveTail ();
Void transovell ();
T & GetTail ();
T gettail () const;
T & GetHead ();
T GetHead () Const;
T & Getat (Const INT POS);
T getat (const INT POS) const;
Void Setat (Const Int Pos, T Data);
INT FIND (CONST T data) const;
Template
Inline cslist
{
}
Template
Inline CSList
{
Addhead (InitData);
}
Template
Inline CSList
{
REMOVEAll ();
}
Template
Inline Int Cslist
{
Return 0 == m_ncount;
}
Template
Inline Int CSList
{
CNODE
PNEWNODE = New CNODE
IF (null == pnewnode)
Return 0;
PNEWNODE-> DATA = DATA;
PNEWNODE-> Next = m_pnodehead;
m_pnodehead = pnewnode;
m_ncount;
Return 1;
}
Template
Inline Int CSList
{
Return INSERTAFTER (GetCount (), DATA);
}
// if success, return the position of the new node.
// if fail, returnography.
Template
Inline Int Cslist
{
INT I;
Int nretpos;
CNODE
CNODE
CNODE
PNEWNODE = New CNODE
IF (null == pnewnode)
{
NRETPOS = 0;
Goto exit0;
}
PNEWNODE-> DATA = DATA;
// if the list is empty, replace the head node with the new node.
IF (null == m_pnodehead)
{
PNEWNODE-> Next = NULL;
m_pnodehead = pnewnode;
NRETPOS = 1;
Goto exit1;
}
// Is POS Range Valid?
ASSERT (1 <= POS && POS <= m_ncount);
// INSERT Before Head Node?
IF (1 == POS)
{
PNEWNODE-> Next = m_pnodehead;
m_pnodehead = pnewnode;
NRETPOS = 1; goto exit1;
}
// if the list is not Empty and is not inserted Before Head Node,
// seek to the pos of the list and insert the new node before it.
PTMPNODE1 = m_pnodehead;
For (i = 1; i { PTMPNODE2 = PTMPNODE1; PTMPNODE1 = PTMPNODE1-> NEXT; } PNEWNODE-> Next = ptmpnode1; PTMPNODE2-> Next = PNewNode; NRETPOS = POS; EXIT1: m_ncount; EXIT0: Return nretpos; } // if success, return the position of the new node. // if fail, returnography. Template Inline int CSList { INT I; Int nretpos; CNODE CNODE PNEWNODE = New CNODE IF (null == pnewnode) { NRETPOS = 0; Goto exit0; } PNEWNODE-> DATA = DATA; // if the list is empty, replace the head node with the new node. IF (null == m_pnodehead) { PNEWNODE-> Next = NULL; m_pnodehead = pnewnode; NRETPOS = 1; Goto exit1; } // Is POS Range Valid? ASSERT (1 <= POS && POS <= m_ncount); // if the list is not empty, // Seek to the pos of the list and insert The New Node After. PTMPNODE = m_pnodehead; For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PNEWNODE-> Next = ptmpnode-> next; PTMPNODE-> Next = pnewnode; NRETPOS = POS 1; EXIT1: m_ncount; EXIT0: Return nretpos; } Template Inline int CSList { Return m_ncount; } Template Inline void CSList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE CNODE PTMPNODE1 = m_pnodehead; // HEAD NODE? IF (1 == POS) { M_PnodeHead = m_pnodehead-> next; Goto exit1; } For (i = 1; i { // We will get the prep in node of the target node after // the for loop finished, and it would be stored Into PTMPNode2 PTMPNODE2 = PTMPNODE1; PTMPNODE1 = PTMPNODE1-> NEXT; } PTMPNODE2-> Next = ptmpnode1-> next; EXIT1: Delete ptmpnode1; --M_ncount; } Template Inline void cslist { Assert (0! = M_ncount); REMOVEAT (1); } Template Inline void cslist { Assert (0! = M_ncount); REMOVEAT (M_NCOUNT); } Template Inline void cslist { INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 0; i { PTMPNODE = m_pnodehead-> next; Delete m_pnodehead; M_PnodeHead = PTMPNode; } m_ncount = 0; } Template Inline T & CSList { Assert (0! = M_ncount); INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline T CSList { Assert (0! = M_ncount); INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline T & CSList { Assert (0! = M_ncount); return m_pnodehead-> data; } Template Inline T CSList { Assert (0! = M_ncount); Return M_PnodeHead-> Data; } Template Inline T & CSList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline T CSList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline void CSList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PTMPNODE-> DATA = DATA; } Template Inline Int Cslist { INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 0; i { IF (Data == Ptmpnode-> DATA) Return i 1; PTMPNODE = PTMPNODE-> NEXT; } Return 0; } #ENDIF / / __SINGLE_LIST_H__ The call is as follows: /// // // filename: slist.cpp // Version: 0.10 // Author: Luo Cong // Date: 2004-12-29 10:41:18 // Comment: // /// #include #include "slist.h" USING NAMESPACE std; int main () { INT I; Int ncount; CSList #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Slist.insertafter (slist.insertafter (slist.addhead (1), 2), 3); Slist.insertafter (slist.inset (), 4), 5); Slist.insertafter (slist.getcount (), 6); Slist.addtail (10); Slist.insertbefter (slist.insertbefore (slist.getcount (), 7), 8); Slist.set (slist.getcount (), 9); Slist.removehead (); Slist.removetail (); // Print Out Elements Ncount = slist.getcount (); For (i = 0; i Cout << slist.getat (i 1) << ENDL; } The code is relatively simple, I will understand it, I am too lazy to explain. If you have a bug, please tell me. 2.2 efficiency problem Considering the problem of efficiency, a member variable is declared: m_ncount, use it to record the number of nodes of the list. What is the benefit of this? In some cases, it will not be traversed, for example, speed can be improved at least in getCount (). The original book refers to the concept of "header" or "dummy node", this node is the first node, where is 0, it is not available, I personally think this It is a bit wasting space, so this practice is not used. Single-link list is the biggest efficiency is that if you want to insert a node to the end of the linked list or a node of the end, you need to traverse the entire linked list, and the time complexity is O (n). On average, to access a node, time complexity is also O (N / 2). This is caused by the nature of the list itself, there is no way to solve. However, we can use double-strand tables and loop chains to improve this situation. 2.3 Applications: One yuan polynomial (addition and multiplication) 2.3.1 Basic knowledge We use a dollar polynomial to illustrate the application of single-strand tables. Suppose there are two yuan in a polynomial: P1 (x) = x ^ 2 2X 3 as well as P2 (x) = 3x ^ 3 10X 6 Now use the basic knowledge of middle school, calculate them and: P1 (x) p2 (x) = (x ^ 2 2X 3) (3X ^ 3 10X 6) = 3X ^ 3 1x ^ 2 12X ^ 1 9 And calculate their product: P1 (x) * p2 (x) = (x ^ 2 2x 3) * (3X ^ 3 10X 6) = 3X ^ 5 6X ^ 4 19X ^ 3 26X ^ 2 42x ^ 1 18 How is it, it's easy? :) But we are a primate, such a cumbersome calculation how can it be done by hand? (Imagine if the polynomial is very large ...) Our goal is to complete these computing tasks with a computer, the code is below. 2.3.2 Code implementation /// // // filename: poly.cpp // Version: 0.10 // Author: Luo Cong // Date: 2004-12-30 17:32:54 // Comment: // /// #include #include "slist.h" #define max (x, y) ((x)> (y))? (x): (y)) Typedef struct tagpolynomial { CSList Int highpower; } * Polynomial; Static void addpolynomial Polynomial potysum, Const Polynomial Poly1, Const Polyn Mar Poly2 ) { INT I; Int sum; INT TMP1; INT TMP2; Polysum-> highpower = max (poly1-> highpower, poly2-> highpower); For (i = 1; i <= polysum-> highpower 1; i) { TMP1 = POLY1-> Coeff.Getat (i); TMP2 = Poly2-> Coeff.getat (i); SUM = TMP1 TMP2; Polysum-> Coeff.addtail (SUM); } } Static void MulpolyNomial Polynomial Polymul, Const Polynomial Poly1, Const Polyn Mar Poly2 ) { INT I; Int J; Int TMP; INT TMP1; INT TMP2; Polymul-> highpower = poly1-> highpower poly2-> highpower; // Initialize All Elements to Zero For (i = 0; i <= polymul-> highpower; i) Polymul-> Coeff.Addtail (0); For (i = 0; i <= poly1-> highpower; i) { TMP1 = POLY1-> Coeff.Getat (i 1); For (j = 0; j <= poly2-> highpower; j) { TMP = POLYMUL-> COEFF.GETAT (i J 1); TMP2 = Poly2-> Coeff.getat (j 1); TMP = TMP1 * TMP2; Polymul-> Coeff.Setat (i J 1, TMP); } } } Static void PrintPoly (const poly ") { INT I; For (i = poly-> highpower; i> 0; i - "PRINTF ("% DX ^% D ", Poly-> Coeff.Getat (i 1), i); Printf ("% d / n", poly-> coeff.getHead ()); } int main () { Polynomial poly1 = NULL; Polynomial poly2 = NULL; Polynomial polyResult = null; #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Poly1 = new (struct tagpolynomial); IF (null == poly1) Goto exit0; Poly2 = new (struct tagpolynomial); IF (null == poly2) Goto exit0; PolyResult = New (struct tagpolynomial); IF (null == polyResult) Goto exit0; // p1 (x) = x ^ 2 2X 3 Poly1-> Highpower = 2; Poly1-> Coeff.Addhead (0); Poly1-> Coeff.Addhead (1); Poly1-> Coeff.Addhead (2); Poly1-> Coeff.Addhead (3); // p2 (x) = 3X ^ 3 10X 6 Poly2-> highpower = 3; Poly2-> Coeff.Addhead (3); Poly2-> Coeff.Addhead (0); Poly2-> Coeff.Addhead (10); Poly2-> Coeff.Addhead (6); // add result = 3X ^ 3 1x ^ 2 12x ^ 1 9 AddPolyNomial (PolyResult, Poly1, Poly2); PRINTPOLY (POLYRESULT); // reset PolyResult-> Coeff.RemoveAll (); // mul result = 3x ^ 5 6x ^ 4 19x ^ 3 26X ^ 2 42x ^ 1 18 MulpolyNomial (PolyResult, Poly1, Poly2); PRINTPOLY (POLYRESULT); EXIT0: IF (poly1) { DELETE POLY1; Poly1 = NULL; } IF (poly2) { DELETE POLY2; Poly2 = NULL; } IF (polyResult) { DELETE POLYRESULT; PolyResult = NULL; } } 2.3.3 Description Only one yuan polynomial architecture is given in the original book, and the code of the single-chain list is not given. In fact, the maximum benefit of single-strand table is that the number of items in the polynomial can be anyga. (Of course, it is only theoretical. What? Your memory is infinite? Well, when I didn't say ...) I didn't achieve subtraction operation. In fact, the subtraction can be converted into an addition. For example, A - b can be converted into a (-b), then our goal is converted to make a negative operation. As for the division, it can be calculated by first conversion "-", and then use the in situ addition. (Now you understand how important it is. ^ _ ^) If you are interested, you try to complete it, my goal is just to master the use of single-stranded list, so no longer continue. third chapter Double-linked list After the single-link table is finished, it is just that the turn is a double-chain list. 3.1 code implementation The implementation of the double-linked list is as follows: /// // // filename: dlist.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-4 10:33:21 // Comment: // /// #ifndef __double_list_h__ #define __double_list_h__ #include #include #ifdef _Debug #define debug_new new (_NORMAL_BLOCK, this_FILE, __LINE__) #ENDIF #ifdef _Debug #define new debug_new #undef this_file Static char this_file [] = __file__; #ENDIF #ifdef _Debug #ifndef assert #define assert assert #ENDIF #ELSE // not _Debug #ifndef assert #define assert #ENDIF #ENDIF / / _DEBUG Template Class cnode { PUBLIC: T data; CNODE CNODE Cnode (): DATA (t ()), prior (null), Next (null) {} Cnode (Const T &TData): Data (InitData), PRIOR (NULL), NEXT (NULL) {} } Template Class CDList { protected: INT m_ncount; CNODE CNODE PUBLIC: CDList (); CDLIST (Const T &TData); ~ Cdlist (); PUBLIC: INT ISEMPTY () Const; INT getCount () const; INT INSERTBEFORE (Const Int Pos, Const T Data); INT INSERTAFTER (Const Int Pos, Const T Data); Int Addhead (Const T Data); Int Addtail (Const T Data); Void Removeat (Const INT POS); Void removehead (); Void RemoveTail (); Void transovell (); T & GetTail (); T gettail () const; T & GetHead (); T GetHead () Const; T & Getat (Const INT POS); T getat (const INT POS) const; Void Setat (Const Int Pos, T Data); INT FIND (CONST T DATA) Const; T & GETPREV (INT & POS); T & GetNext (INT & POS); } Template Inline CDList { } Template Inline CDList : m_ncount (0), m_pnodehead (null), m_pnodetail (null) { Addhead (InitData); } Template Inline CDList { REMOVEAll (); } Template Inline T & CDList { Assert (0! = M_ncount); ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } POS; Return PTMPNODE-> DATA; } Template Inline T & CDList { Assert (0! = M_ncount); ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } --POS; Return PTMPNODE-> DATA; } Template Inline Int CDList { INT I; Int nretpos; CNODE CNODE PNEWNODE = New CNODE IF (null == pnewnode) { NRETPOS = 0; Goto exit0; } PNEWNODE-> DATA = DATA; // if the list is empty, replace the head node with the new node. IF (null == m_pnodehead) { PNEWNODE-> prior = null; pnewnode-> next = NULL; m_pnodehead = pnewnode; m_pnodetail = pnewnode; NRETPOS = 1; Goto exit1; } // Is POS Range Valid? ASSERT (1 <= POS && POS <= m_ncount); // INSERT Before Head Node? IF (1 == POS) { PNEWNODE-> PNEWNODE-> PRIOR = NULL; PNEWNODE-> Next = m_pnodehead; M_PnodeHead-> prior = pnewnode; m_pnodehead = pnewnode; NRETPOS = 1; Goto exit1; } // if the list is not Empty and is not inserted Before Head Node, // seek to the pos of the list and insert the new node before it. PTMPNODE = m_pnodehead; For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PNEWNODE-> Next = PTMPNODE; PNEWNODE-> prior = ptmpnode-> prior; PTMPNODE-> prior-> next = pnewnode; PTMPNODE-> prior = pnewnode; // if tail node, must update m_pnodetail IF (null == pnewnode-> next) { m_pnodetail = pnewnode; } NRETPOS = POS; EXIT1: m_ncount; EXIT0: Return nretpos; } Template Inline Int CDList { INT I; Int nretpos; CNODE CNODE PNEWNODE = New CNODE IF (null == pnewnode) { NRETPOS = 0; Goto exit0; } PNEWNODE-> DATA = DATA; // if the list is empty, replace the head node with the new node. IF (null == m_pnodehead) { PNEWNODE-> PNEWNODE-> PRIOR = NULL; PNEWNODE-> Next = NULL; m_pnodehead = pnewnode; m_pnodetail = pnewnode; NRETPOS = 1; Goto exit1; } // Is POS Range Valid? ASSERT (1 <= POS && POS <= m_ncount); // if the list is not empty, // Seek to the pos of the list and insert The New Node After. PTMPNODE = m_pnodehead; For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PNEWNODE-> Next = ptmpnode-> next; PNEWNODE-> PRIOR = PTMPNODE; // if newnode's position is m_pnodetail, Update M_Pnodetail IF (ptmpnode-> next == m_pnodetail) { m_pnodetail-> prior = pnewnode; } PTMPNODE-> Next = pnewnode; // if tail node, must update m_pnodetail IF (null == pnewnode-> next) { m_pnodetail = pnewnode; } NRETPOS = POS 1; EXIT1: m_ncount; EXIT0: Return nretpos; } Template Inline T & CDList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline T CDList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } Return PTMPNODE-> DATA; } Template Inline Int CDList { Return INSERTBEFORE (1, DATA); } Template Inline int CDList { Return INSERTAFTER (GetCount (), DATA); } Template Inline CDList { Return 0 == m_ncount; } Template Inline CDList { Return m_ncount; } Template Inline T & CDList Assert (0! = M_ncount); Return M_Pnodetail-> Data; } Template Inline T CDList { Assert (0! = M_ncount); Return M_Pnodetail-> Data; } Template Inline T & CDList { Assert (0! = M_ncount); Return M_PnodeHead-> Data; } Template Inline T CDList { Assert (0! = M_ncount); Return M_PnodeHead-> Data; } Template Inline Void CDList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE // HEAD NODE? IF (1 == POS) { M_PnodeHead = m_pnodehead-> next; Goto exit1; } For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PTMPNODE-> prior-> next = ptmpnode-> next; EXIT1: Delete PTMPNode; --M_ncount; IF (0 == m_ncount) { m_pnodetail = NULL; } } Template Inline void cdlist { Assert (0! = M_ncount); REMOVEAT (1); } Template Inline void cdlist { Assert (0! = M_ncount); REMOVEAT (M_NCOUNT); } Template Inline void cdlist { INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 0; i { PTMPNODE = m_pnodehead-> next; Delete m_pnodehead; M_PnodeHead = PTMPNode; } m_ncount = 0; } Template Inline Void CDList { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE For (i = 1; i { PTMPNODE = PTMPNODE-> NEXT; } PTMPNODE-> DATA = DATA; } Template Inline Int CDList { INT I; Int ncount; CNODE Ncount = m_ncount; For (i = 0; i { IF (Data == Ptmpnode-> DATA) Return i 1; PTMPNODE = PTMPNODE-> NEXT; } Return 0; } #ENDIF / / __DOUBLE_LIST_H__ The call is as follows: /// // // filename: dlist.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-4 10:58:22 // Comment: // /// #include #include "dlist.h" Using namespace std; int main () { INT I; Int ncount; CDList #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Dlist.addtail (1); Dlist.addtail (3); Dlist.insertbefore (2, 2); Dlist.addhead (4); Dlist.removetail (); Ncount = DList.getCount (); For (i = 1; i <= ncount;) { Cout << DList.getNext (i) << endl; } } 3.2 Description There is only one pointer to the direct successive node in the node of the single-strand list, so it can only query other nodes after a node. Rely, if I want to visit the previous node of a node, can I start starting from the beginning of the head? The efficiency is really low! In other words, in the single-chain table, the time complexity of getNext () is O (1), and the time complexity of GetPrev () is O (n). To overcome this unidirectional disadvantage of single-strand table, we can use - "Dangdang", only you, is the double-linked list. As the name suggests, there are two pointers in the node of the double-linked list, one pointing to the direct success, the other pointing to the direct forward, in the C language is as follows: Struct Node { Struct Node * Prior; Struct Node * Next; T data; } Most of the dual-linked works (only the operations involving the pointers in the rear direction) are the same as the single-stranded list, but inserted, delete is very different, in the double-linked list, the two directions are modified. pointer. Therefore, you can directly inherit the class of single-strand tables to complete the double-linked list, and then change the different functions. But I didn't do this, don't ask why, the problem of character. If you have already proficiently grasped the pointer domain of a single-strand table, this part of the double-linked list should be difficult to fall. Not much to say, please see the code. If you have a bug, please tell me. ^ _ ^ Chapter Four Circulatory chain list 4.1 Basic Concept The loop chain can be a single-link list, or it can be a double-linked list, but I don't want to make the problem so complicated, just do the loop form of a single-link table. After we realize the list, we will inevitably ask a question: Can the list be ended? How to achieve? Answer: Can. In fact, the method of implementation is simple, that is, point the pointer domain of the last node in the table (P-> next = head;). This linked table of such a loop is referred to as a circular link. Imagine our exercise in the school's sports field (school ... good memories), around the 400m runway, running, it seems to be the same. This is because the first end of the runway is connected. After running a circle, "tail" suddenly turned "head", which is the same as the principle of circulating chain list. Ok, I understand this truth, it is simple, but it is necessary to pay attention to the number of nodes in the loop chain, cannot use the while () loop to travers, because this loop is never At the end, this can be carried out on a runway of 400 meters regardless of how long long-distance race. My approach is still the corresponding operation of M_NCount by adding an M_NCount variable, each time you add or delete a node. Features of the circular link: Other nodes in the table can be found from any knot. Operation only one point is different from the single-strand table: circulation conditions. Single-link list: P = null or p-> next = null loop list: P = head or p-> next = head 4.2 Code Implementation The implementation of the circular link is as follows: /// // // filename: clist.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-5 10:43:17 // Comment: // /// #ifndef __circ_list_h__ #define __circ_list_h__ #include "../../slist/src/slist.h" Template Class Cclist: Public CSList { protected: CNODE PUBLIC: Cclist (); PUBLIC: T & GetNext (); Void Removeat (Const INT POS); INT getcurrentindex () const; } Template Inline T & CClist { Assert (0! = M_ncount); IF ((NULL == m_pnodecurr) || (null == m_pnodecurr-> next)) m_pnodecurr = m_pnodehead; Else m_pnodecurr = m_pnodecurr-> next; Return M_Pnodecurr-> Data; } Template Inline int Cclist { Assert (0! = M_ncount); INT I; CNODE For (i = 1; i <= m_ncount; i) { IF (ptmpnode == m_pnodecurr) Return I; Else PTMPNODE = PTMPNODE-> NEXT; } Return 0; } Template Inline Void Cclist { ASSERT (1 <= POS && POS <= m_ncount); INT I; CNODE CNODE PTMPNODE1 = m_pnodehead; // HEAD NODE? IF (1 == POS) { M_PnodeHead = m_pnodehead-> next; // Added for loop list // m_pnodecurr will be set to m_pnodehead in function getNext () m_pnodecurr = null; Goto exit1; } For (i = 1; i { // We will get the prep in node of the target node after // the for loop finished, and it would be stored Into PTMPNode2 PTMPNODE2 = PTMPNODE1; PTMPNODE1 = PTMPNODE1-> NEXT; } PTMPNODE2-> Next = ptmpnode1-> next; // Added for loop list m_pnodecurr = ptmpnode2; EXIT1: Delete ptmpnode1; --M_ncount; } Template Inline Cclist { } #ENDIF / / __CIRC_LIST_H__ 4.3 Description Since most of the operation of the circulating linked list is the same as the non-circular linked list, my circulating chain table is inherited directly from single-chain table, and the variable M_PNODECURR indicating the current node is added, and several functions are overloaded. But there is still two points to pay special attention: In the getNext () function, you must have a condition that the current node should point to the next node. In the REMOVEAT () function, if you want to delete a node, the node is just the head knot, then the current node must point to NULL, so that the correct value of the header node can be re-obtained in GetNext (). . About these two points should have no doubt? Oh, let's continue ... What? You don't understand what the second point mean? I fell! Let us assume it, if the current node points to the tailpoint, then we call getnext (), then it is clear that the current node should point to the head node. But the problem is that the head knot has been deleted by us, then where can the current node point to? At this time, what can happen, the computer may format your hard drive, or you may give your love letter to the dinosaurship of the class, and you can tell your boss. You are willing to have a penny from this time. Always do over ... but the most likely thing is to produce an exception of memory access, so cough, computer is very stupid, must be personally telling it by us: "The head knot is already finished, so the current The node points to null, you have solved the next problem in the getnext () function. " do you understand? I still don't understand ... I ... I ... 4.4 Application: Joseph Joseph's problem is almost the most classic use to explain the circulatory chain. why? Let's take a look at the description of this problem. There is a team of adhered by N Adventurers to go deep into the tropical rainforest, but they have encountered the eating family, the rules of the eating people are let them enclose a circle, then select a number M, start reporting from the first person. Number, when I report to M, this person will be eaten, then start again from the next person, repeat this process, until the last person, this person is lucky, can leave without being Eat. So, who is this luckyer? Let's take an example: Suppose this expedition has 6 explorers, and the numerous number of eating people is 5, then in the first round, the 5th will be eaten, the rest is: 1, 2, 3, 4, 6 total 5 Personal, then starting from the 6th, starting to report 5 numbers: 6, 1, 2, 3, 4, so that it is eaten in the second round is 4 ... have been repeating this process, according to the order Yes: 5, 4, 6, 2, 3 were eaten, the remaining 1 will live. Solving this problem is not only using a loop linked list, but using a loop chain list should be most convenient. The code I wrote is as follows: /// // // filename: joseph.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-5 13:56:32 // Comment: // /// #include #include "clist.h" Using namespace std; int main () { INT I; Int n; Int m; Int nnumber; Int ncurindex; Cclist #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Cout << "Please enter the total number of people:"; cin >> n; Cout << "Please enter a dead number:"; Cin >> m; // Initialize the sequence number list: For (i = 1; i <= n; i) { CList.Addtail (i); } i = 0; DO { i; nnumber = clist.getnext (); IF (i == m) { Cout << "" "<< nnumber <<" is eaten! "<< Endl; // This person is unlucky ncurindex = clist.getcurrentIndex (); Clist.removeat (NCURINDEX); N; // The rest of the people resume the number i = 0; } } while (1! = n); COUT << "The last life is:" << clist.gethead () << endl; } In order to solve the problem of Joseph, I added a getCurrentIndex () function in the circular chain list to get the index value of the current node to delete the current node. The entire code should not understand, and it will be understood by actually doing it. :) chapter Five Stack 5.1 Basic Concept Stack (stack) is a table that limits insertion and deletion can only be performed at a location, which is the end of the table, called the top (TOP) of the stack, which is a backward first out (LIFO). The basic operation of the stack has only two kinds of PUSH (inrest) and POP (out of the stack). The former is equivalent to inserting, and the latter is equivalent to deleting the last element. Since the stack is essentially a restricted table, you can use any form of forms to implement it, and we are most commonly used: Lin list array The advantages and disadvantages of complexity are compared to: Time complexity when new and deleting elements Link list: The cost is very expensive on dynamic application memory (New or Malloc). Array: There is almost no sales, run in constant O (1), and compile the integer's PUSH and POP operations into a machine instruction when operating on registers with self-increasing and self-minus adding functions. Space complexity Link list: Since space is dynamic application, release, there is no waste of space, and as long as the physical memory is allowed, the maximum range unknown is conceivable. Array: Must be specified in initialization, it is possible to waste space or possibly enough. in conclusion: If the efficiency is very high in the runtime, it is possible to predict the size of the stack during initialization, then the array form should be premier; otherwise the chain form should be selected. Since the operation of the stack is always for the top of the stack (TOP), the advantages of the random access of the array are not, and the arrays must be pre-allocated, and the space size is limited, so in general (for runtime) The efficiency requirement is not too high) The linked list should be the first choice. 5.2 code implementation The stack is achieved as follows: /// // // filename: stack.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-6 11:42:17 // Comment: // /// #ifndef __stack_h__ #define __stack_h__ #include "../../slist/src/slist.h" Template Class Cstack: Public CSList { PUBLIC: INT Push (T Data); INT POP (T * Data = NULL); INT TOP (T * DATA) Const; } Template Inline Int Cstack { Return Addtail (data); } Template Inline Int Cstack { IF (iSempty ()) Return 0; IF (DATA) TOP (DATA); Removetail (); Return 1; } Template Inline Int Cstack { ASSERT (DATA); IF (iSempty ()) Return 0; * DATA = gettail (); Return 1; } #ENDIF / / __STACK_H__ The call is as follows: /// // // filename: stack.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-6 11:42:28 // Comment: // /// #include #include "stack.h" Using namespace std; Static void PrintValue (const Int nvalue) { IF (NRetcode) COUT << nvalue << endl; Else Cout << "Error Occured!" << Endl; } int main () { Cstack Int nvalue; Int nretcode; #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF STACK.PUSH (1); STACK.PUSH (2); STACK.PUSH (3); NRetcode = stack.top (& nvalue); PrintValue (Nretcode, NValue); NRETCODE = stack.pop (& nvalue); PrintValue (Nretcode, NValue); NRETCODE = stack.pop (& nvalue); PrintValue (Nretcode, NValue); NRETCODE = stack.pop (& nvalue); PrintValue (Nretcode, NValue); } 5.3 description The above code is the stack implemented on the basis of a single-strand table, you will see that under the inheritance mechanism of C , the stack is simple and terrible. :) An a problem that affects the operating efficiency of the stack is error detection. My stack implementation is carefully checked - Top and POP operations for empty stacks, and when the storage space is not enough, it will cause an exception. Obviously, we don't want to have this situation, but, If the detection of these conditions is placed in the code, it is likely to spend much more time like actual stack operation. For this reason, unless the error handling is extremely important (eg, in the operating system), it is generally used in the stack to become an ordinary customary method. But I think that a good program should first be strong, this is more important than efficiency, especially for this most basic data structure, it is likely to be used as a basic element. . So I don't save the wrong inspection mechanism because of the problem of efficiency. The cost of introducing an error checking mechanism is: It has become a cumbersome operation to TOP and POP. In the code, I use the return value 0 or 1 to represent success or fail, and the actual stack top element is returned by parameters. This must be dissatisfied with people - too much trouble! But this is the best solution I can think of. If you have a better way, please tell me. Runtime efficiency will be reduced. If you really cost too much time, you can check the error check, but the premise is that you can make sure that the entire running process will not be wrong - actually there must be an error check, but these errors will be placed outside. Do it. Ok, that's so much, let's take a look at the application of the stack. 5.4 Application: Conversion of the suffix expression The application of the stack is too wide (who is the most basic data structure element?), Such as balance symbols, expression conversion, etc., we have a more practical example - Dixed to suffix expressions. (Can be used in places such as compiler) 5.4.1 code implementation /// // // filename: postfix.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-6 16:00:54 // Comment: // /// // Algorithm: // 1) Check the next element of the input. // 2) If it is an operand, output. // 3) If it is a blockbus, it is stack it. // 4) If it is an operator, then // i) If the stack is empty, this operator is plagued. // ii) If the top of the stack is open, this operator is pressed. // iii) If the operator is highly priority than the top operand, this operator is pressed into the stack. // iv) Otherwise, the top operator operates the stack and outputs step 4. // 5) If it is a closed parentheses, the operator is out of the stack out of the stack and output until it encounters the parentheses. Stack out of the stack and discard it. // 6) If the input has not yet been completed, the jump to step 1. // 7) If the input is completed, all the remains of the remaining operations are stack and output them. #include #include "stack.h" // Return the priority of the operator // and - the priority is the same, the * and / priority are the same, but and - the priority is lower than * and / low. Static int GETPRI (Const Char Optr) { Switch (OPTR) { Case ' ': Return 1; Case '-': Return 1; Case '*': return 2; Case '/': return 2; DEFAULT: RETURN 0; } } / / Complete the priority comparison of operators and current operators in this function, / / And decide whether to output the current operator or the current operator to the stack processing. Static Void ProcessStackPRI ( Cstack Const Char Optr, Char ** szpostfix ) { Assert (* szpostfix); INT I; Int nretcode; CHAR ChSTACKOPTR; Int ncount = stack.getcount (); For (i = 0; i <= ncount; i) { NRETCODE = stack.top (& chSTACKoptr); IF (0 == nretcode) || // The top of the stack is empty, the new operator is added to the top of the stack (GetPri (chSTACKTR) ) { Stack.push (OPTR); Break; } Else { / / If the stack top operator is not less than the current, the top element is put into the stack and outputs: Stack.pop (); * (* szpostfix) = chSTACKOPTR; } } } Static void Infix2Postfix Const char * szinfix, Char * szpostfix ) { Assert (szpostfix); CHAR Choptr; Int nretcode; Cstack While (* szinfix) { Switch (* szinfix) { // Ignore spaces and TAB: Case '': Case '/ t': Break; / / The operator is prioritized to determine whether it is stack or output: Case ' ': Case '-': Case '*': Case '/': NRETCODE = stack.isempty (); IF (! nretcode) ProcessStackPRI (Stack, * Szinfix, & Szpostfix); Else Stack.push (* szinfix); // When the stack is empty, there is no doubt that the operator should enter the stack. Break; // When encountering the left bracket, there is unconditional entry because it is the highest. Case '(') STACK.PUSH (* szinfix); Break; // When you encounter the right bracket, the operator in the stack is put by the stack until you encounter the left bracket. Case ')': DO { NRETCODE = stack.pop (& choptr); IF (Nretcode && ('('! = choptr)) // Left bracket itself does not output * szpostfix = choptr; } while (! stack.isempty () && ('('! = choptr)); / / encountering the left bracket Break; // The rest of the situation, you can DEFAULT: * szpostfix = * szinfix; Break; } szinfix; } // If the input content has been analyzed, then the remaining operators in the stack out of the stack While (! stack.isempty ()) { NRETCODE = stack.pop (& choptr); * szpostfix = choptr; } * szpostfix = '/ 0'; } int main () { Char * szinfix = "A B * C (D * E F) * G"; Char szpostfix [255]; #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Infix2postfix (Szinfix, Szpostfix); Printf ("INFIX:% S / N", SZINFIX); Printf ("postfix:% s / n", szpostfix); } 5.4.2 Description There is already a detailed note in the source code, I will no longer come. I only do the conversion of , -, *, / four operators, in addition, if the parentheses do not match, for example, there is a left bracket but there is no right bracket, or in turn, the program may run incorrect, but this is not me. Written this example, I wrote it just to master the usage of the stack, if you are interested, you can try to improve it. Next, two examples are given: Pixel expression: A B * C (D * E F) * G Suffix expression: ABC * DE * F G * Pixel expression: 2 * (x y) / (1 - x) Suffix expression: 2xY * 1x- / Chapter Six Queue 6.1 Basic Concept Stack The queue is also a table. However, inserting a queue is inserted at one end and delete it is done at the other end, that is, the first advance first out (FIFO). The basic operation of the queue is Enqueue, which is inserted into an element at the end of the table (called Team (Rear); there is a Dequeue, it is deleted (or returned) at the beginning of the table (called Element of the header (front)). The queue generally has two types of chain queues and cyclic queues. The chain queue is equivalent to queuing in the bank. The later people are ranked in the final, the people will leave after the business is completed, let the next one go in; the cycle queue is very similar to the circulatory list. I only write the code of the chain queue here, and the loop queue can also inherit the self-circulating list, and there is not much Luo. It can be seen that the realization of the queue is also an amazing simple. 6.2 Code implementation of the queue is as follows: /// // // filename: lqueue.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-8 16:49:54 // Comment: // /// #ifndef __list_queue_h__ #define __list_queue_h __ # include "../../slist/src/slist.h" Template Class Clqueue: Public CSList { PUBLIC: INQUEUE (Const T Data); T Dequeue (); T & GetFront (); T Getfront () const; T & GetRear (); T getRear () const; } Template Inline Int Clqueue { Return Addtail (data); } Template Inline T Clqueue { T Data = GetHead (); REMOVEHEAD (); Return Data; } Template Inline T & Clqueue { Return getHead (); } Template Inline T Clqueue { Return getHead (); } Template Inline T & Clqueue { Return gettail (); } Template Inline T Clqueue { Return gettail (); } #ndif // __list_queue_h__ call as follows: /// // // filename: queue.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-8 17:00:40 // Comment: // /// #include #include "lqueue.h" Using namespace std; int main () { Clqueue #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF Queue.enqueue (1); Queue.enqueue (2); Queue.enqueue (3); While (! queue.Isempty ()) Cout << queue.dequeue () << endl; } 6.3 Application of Application Queue General is a discrete phenomenon in analog real life, such as bank queues, printer tasks, operator work, and more. It is also an algorithm that uses queues to improve operational efficiency, which is usually used in the graph algorithm. Considering the application of the queue is easier, or in a specific environment, I don't give an example of the application. If you are interested, you can try it yourself. Chapter VII Recursive 7.1 Basic Concepts According to the process of the original book, it should now be recursive. Recursive is a powerful mathematical tool. I don't know if you have learned LISP or have a dialect (such as scheme). If you have learned, you will be very familiar with recursive, because in Lisp and its dialect, there is no loop statement, if you want to construct a loop, It must be implemented in the form of recursive. At that time, my head didn't turn around, because I have been used to using for, while and other statements in C / C to cycle, I just started with almost no way to write a loop in Lisp. For example, the following code: for (int i = 0; i <= 10; i) { } Can be converted into recursive: Void Recursion_Loop (INT I) { IF (i == 10) Return; Else Recursion_loop (i 1); } // transfer: Recursion_loop (0); Recurns has the following properties: Recurrence is repeatedly calling itself during a certain process. For example, in the above example, it is called in the recursion_loop () function. There must be stop conditions. This is easy to understand, because if there is no stop condition, then this recursive will be a child and grandchildren. For example, in the above example, if (i == 10) is a condition that stops. The recursive will be limited by reality, such as in the stack size is not enough, resulting in failure. This is because the size of the stack is in the computer, and each recursive call function itself needs to save the return address, parameters and other information in the stack. After n-times recursive, the stack is likely to be full. This will result in unable to perform sub-(n 1) times. According to the nature of the above 3 we can know, not all languages support recursive - if some language can support recursive, it must be a structure that supports "stack". At present, the most exciting language I know is the most exciting language, LISP and its dialect are the well-deserved king. 7.2 Applying 唉, I didn't want to write an example, because these examples have been written countless times. It will definitely say that the three examples of steps, Fiboacci numbers and Hanno Taga, but in the purpose of treating textbooks, I still have a repetitive labor (but no longer An example is explained, and a book that is cascaded a data structure will have this content). Finally, a Pasca triangle is added, and in our country is the famous Yanghui triangle. 7.2.1 step ///// // // filename: factorial.c // Version: 0.10 // Author: Luo Cong // Date: 2005-1-8 21:23:16 // Comment: // /// #include Static Long Factorial (Const long N) { Return 0 == N || 1 == n? 1: n * Factorial (n - 1); } int main () { Long LRESULT = Factorial (10); Printf ("% ld / n", lresult); 7.2.2 Fiboacci number /// // // filename: Fib.c // Version: 0.10 // Author: Luo Cong // Date: 2005-1-8 21: 28: 56 // Comment: // /// #include Static Long Fib (Const Long N) { Return 0 == N || 1 == n? 1: FIB (n - 1) FIB (N - 2); } int main () { Long LRESULT = FIB (10); Printf ("% ld / n", lresult); } 7.2.3 Hannota /// // // filename: hanoi.c // Version: 0.10 // Author: Luo Cong // Date: 2005-1-8 21:40:44 // Comment: // /// #include Static Void Move (Const Char X, Const Int N, Const Char Z) { Printf ("Put the disc% D from the column% C to% C above / n", n, x, z); } Static Void Hanoi (Const Int N, Const Char X, Const Char Y, Const Char Z) { IF (1 == n) Move (x, 1, z); // If there is only one disk, then move it directly to Z Else { Hanoi (n - 1, x, z, y); // Put 1 ~ n - 1 disk from X to Y, use Z as a transfer Move (x, n, z); // Move the nth disc from X to z Hanoi (n - 1, y, x, z); // Put 1 ~ n - 1 disc from Y to z, use X as a transfer } } int main () { Hanoi (1, 'x', 'Y', 'Z'); } 7.2.4 Pasca Triangle (Yang Hui Triangle) The following value is called a Pasca triangle, in our country, is a famous Yang Hui triangle: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 The number on the triangular boundary is 1, each of the internals is the sum of the two numbers above it. Using recursive we can easily convert problems to this nature: assuming f (row, col) represents the row of the row of Row, the Yanghui triangle, then: f (Row, COL) = 1 (COL = 1 or ROW = COL), that is, the recursive stop condition. f (Row, COL) = f (Row - 1, COL - 1) F (Row - 1, COL), that is, two adjacent elements of the previous line. With this nature, our recursive procedures will be easily written. ^ _ ^ /// // // filename: pascaltriangle.c // Version: 0.10 // Author: Luo Cong // Date: 2005-1-9 14:53:57 // Comment: // /// #include Static Long getElement (Const Long Row, Const Long Col) { // The peripheral of each line is 1 IF ((1 == COL) || (ROW == COL)) Return 1; Else // The rest of the part is the sum of the previous line (COL - 1) and (COL) elements Return getElement (ROW - 1, COL - 1) GetElement (Row - 1, col); } Static Long Pascaltriangle (Const long n) { Int row; INT COL; For (ROW = 1; ROW <= N; ROW) { For (COL = 1; COL <= row; col) Printf ("% 4LD", getElement (Row, Col)); Printf ("/ n"); } } int main () { Pascaltriangle (5); } chapter eight Binary 8.1 Basic Concept Tree is a non-linear data structure that exists in the objective world, such as family scores and various social organizations in human society can be expressed. What we are most commonly used is trees and binary trees, which are more practical in bifuries. Why do you say this way? Because most of the operations can be transformed into a father, a left son and a right son are achieved, and the operation of the binary tree is simpler. 8.2 Code Implementation of the code of the binary tree is as follows: /// // // filename: btree.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-12 12:22:40 // Comment: // /// #ifndef __binary_tree_h__ #define __binary_tree_h__ #include #include #ifdef _Debug #define debug_new new (_NORMAL_BLOCK, this_FILE, __LINE__) #ENDIF #ifdef _Debug #define new debug_new #undef this_file Static char this_file [] = __file__; #ENDIF #ifdef _Debug #ifndef assert #define assert assert #ENDIF #ELSE // not _Debug #ifndef assert #define assert #ENDIF #ENDIF / / _DEBUG Template Class CBTNode { PUBLIC: T data; CBTNode CBTNode CBTNode CBTNode T Data = T (), CBTNode CBTNode CBTNode : DATA (DATA), PARENT (PARENT), Left (Left), Right (Right) {} } Template Class CBTree { protected: CBTNode PUBLIC: CBTree (CBTNode Void Assignto (CBTNode Void Copy (CBTree Private: CBTNode Void DestroyNode (CBTNode Void PreordRraverse Const CBTNode Void (* VISIT) (Const T & DATA) Const; Void inordertraverse Const CBTNode Void (* VISIT) (Const T & DATA) Const; Void PostRraverse Const CBTNode Void (* VISIT) (Const T & DATA) Const; Void GetNodescount (const cbtnode Void Getleafcount (const cbtnode Unsigned int getDepth (const CBTNode PUBLIC: T & GetNodeData (CBTNode T getnodedata (const cbtnode Void SetNodedata (CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode CBTNode PUBLIC: INT ISEMPTY () Const; Void destroy (); Void PreordRraverse (Void (* Visit)) Const; Void Inordertraverse (const T & DATA) Const; Void PostOrDertraverse (a Void (* Visit) (Const T & DATA) Const; Unsigned int GetNodescount () const; // get how much nodes Unsigned int getleafcount () const; Unsigned int getDepth () const; } Template Inline CBTree { } Template Inline CBTree { DESTROY (); } Template Inline void CBTree { ASSERT (P); m_pnoderoot = p; } Template Inline void CBTree { IF (NULL! = p.m_pnoderoot) m_pnoderoot = copy (p.m_pnoderoot); Else M_Pnoderoot = NULL; } Template Inline CBTNode { CBTNode IF (p) { PNEWNODE = New CBTNODE IF (null == pnewnode) Return NULL; PNEWNODE-> DATA = P-> Data; PNEWNODE-> PARENT = P-> Parent; PNEWNODE-> LEFT = COPY (P-> Left); PNEWNODE-> Right = Copy (P-> Right); Return pnewnode; } Else Return NULL; } Template Inline CBTNode { ASSERT (P); Return * (& (P-> Left); } Template Inline CBTNode { ASSERT (P); Return P-> LEFT; } Template Inline CBTNode { Assert (p); return * (& (p-> right)); } Template Inline CBTNode { ASSERT (P); RETURN P-> Right; } Template Inline CBTNode { ASSERT (P); IF (P-> Parent) Return * (& (P-> Parent-> Left); Else Return * (& (P-> Parent)); // Return NULL; } Template Inline CBTNode { ASSERT (P); IF (P-> Parent) RETURN P-> Parent-> Left; Else Return P-> Parent; // Return NULL; } Template Inline CBTNode { ASSERT (P); IF (P-> Parent) Return * (& (P-> Parent-> Right); Else Return * (& (P-> Parent)); // Return NULL; } Template Inline CBTNode { ASSERT (P); IF (P-> Parent) RETURN P-> Parent-> Right; Else Return P-> Parent; // Return NULL; } Template Inline CBTNode { ASSERT (P); Return * (& (p-> parent)); } Template Inline CBTNode { ASSERT (P); Return P-> Parent; } Template Inline T & CBTREE { ASSERT (P); Return P-> DATA; } Template Inline T CBTREE { ASSERT (P); Return P-> DATA; } Template { ASSERT (P); P-> DATA = DATA; } Template Inline int CBTREE { Return null == m_pnoderoot; } Template Inline CBTNode { Return * (& (m_pnoderoot)); } Template Inline CBTNode { Return m_pnoderoot; } Template Inline Void CBTree { IF (p) { DestroyNode (P-> Left); DestroyNode (P-> Right); Delete P; } } Template Inline void CBTree { DestroyNode (m_pnoderoot); M_Pnoderoot = NULL; } Template Inline void CBTree { Preordertraverse (M_Pnoderoot, Visit); } Template Inline Void CBTree Const CBTNode Void (* VISIT) (Const T & DATA) Const { IF (p) { Visit (P-> DATA); Preordertraverse (P-> Left, Visit); Preordertraverse (P-> Right, VISIT); } } Template Inline Void CBTree { InorderTraverse (M_Pnoderoot, Visit); } Template Inline void CBTree Const CBTNode Void (* VISIT) (Const T & DATA) Const { IF (p) { Inordertraverse (P-> Left, Visit); Visit (P-> DATA); Inordertraverse (P-> Right, Visit); } } Template Inline void CBTree PostOrDertraverse (M_Pnoderoot, Visit); } Template Inline void CBTree Const CBTNode Void (* VISIT) (Const T & DATA) Const { IF (p) { PostOrDertraverse (P-> Left, Visit); PostOrDertraverse (P-> Right, VISIT); Visit (P-> DATA); } } Template Inline unsigned int CBTREE { Unsigned int uncount; GetNodescount (m_pnoderoot, & uncount); Return uncount; } Template Inline void CBTree Const CBTNode Unsigned int * Uncount Const { ASSERT (Uncount); Unsigned int unleftcount; Unsigned int unrightcount; IF (NULL == P) * uncount = 0; Else IF (null == p-> left) && (null == p-> right))) * uncount = 1; Else { GetNodescount (P-> Left, & UnleftCount); GetNodescount (P-> Right, & unrightcount); * uncount = 1 uncleftcount unrightcount; } } Template Inline unsigned int CBTREE { Unsigned int uncount = 0; Getleafcount (m_pnoderoot, & uncount); Return uncount; } Template Inline void CBTree Const CBTNode Unsigned int * Uncount Const { ASSERT (Uncount); IF (p) { // if The Node's Left & Right Children Are Both Null, IT Must Be a Leaf IF ((NULL == P-> Left) && (null == p-> right)) (* uncount); Getleafcount (P-> Left, uncount); Getleafcount (P-> Right, Uncount); } } Template Inline unsigned int CBTREE // i Minus 1 Here Because I Think The root node's depth shouth be 0. // SO, IF u think the root node's Depth Should Be 1, The Needn't Minus. Return getDepth (m_pnoderoot) - 1; } Template Inline unsigned int CBTREE { Unsigned int undepthleft; Unsigned int undepthright; IF (p) { undepthleft = getDepth (p-> left); Undepthright = getDepth (p-> right); Return 1 // if Don't Plus 1 Here, The Tree's Depth Will Be Always 0 (Undepthleft> undepthright: undepthright); } Else Return 0; } #ENDIF / / __BINARY_TREE_H__Terate: /// // // filename: btree.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-12 13:17:07 // Comment: // /// #include #include "btree.h" Using namespace std; // Node data type Typedef char elementtype; // Tonance function: Visit () = printelement () Static Void Printelement (Const ElementType & Data) { Cout << data; } int main () { CBTNode CBTNode CBTNode CBTree #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF ProT = New CBTNode IF (null == prop) Return EXIT_FAILURURE; PleftChild = New CBTNode IF (NULL == PLEFTCHILD) Return EXIT_FAILURURE; PRIGHTCHILD = New CBTNODE IF (NULL == PRightchild) Return EXIT_FAILURURE; // Create a father node ProT-> DATA = ' '; ProT-> PARENT = NULL; ProT-> Left = PLEFTCHILD; Proot-> Right = PRIGHTCHILD; // Create a left son node PleftChild-> Data = 'a'; PleftChild-> Parent = proot; PleftChild-> Left = NULL; Pleftchild-> Right = NULL; // Create a right son node PRIGHTCHILD-> DATA = 'b'; PRIGHTCHILD-> PARENT = Proot; PRIGHTCHILD-> LEFT = NULL; PRIGHTCHILD-> Right = NULL; // Create a binary tree BTree.assignto (proot); // Output this binary tree COUT << "(" << btree.getnodedata (btree.getroot ()) << "<<" COUT << "/ //" << endl; Cout << "(" << btree.getnodedata (btree.getLeftchild (btree.getRoot ())))) << ") (" << btree.getnodedata (btree.getRight (btree.getroot ()))) << ")" << Endl << endl; Cout << "The number of leaves of this tree:" << btree.getleafcount () << Endl; COUT << "The depth of this tree is:" << btree.getDepth () << endl; Cout << "preface traversal:"; Btree.PreorderTraverse (Printelement); COUT << Endl << "in the middle traversal:"; BTree.inorderTraverse (Printelement); Cout << Endl << "sequence traversal:"; btree.postordertraverse (Printelement); Cout << Endl; Return EXIT_SUCCESS; } 8.3 Description You may have noticed a "strange" phenomenon: in my binary tree implementation, there are various access operations for nodes (such as calculating trees, various traversal), but there is no insertion and delete this A function of two operations. In fact, this is not worthwhile. Because the binary tree is basically the most "underlying" class, we will be inherited from the two-fork tree, and for the nonlinear data structure of the tree, insertion And delete is to specifically analyze the specific problems according to the environment it is - means that there is no specific rule (this is not like a linked list, the linked list is linear). So, in a specific application, I will give the specific insertion and delete code. Here, I used a very poor way to create a binary tree, please don't think about it in this issue. In the node CBTNode, I defined four member variables: DATA, PARENT, LEFT and RIGHT. Data indicates the data domain of the node, and the Parent indicates that the end of the node, the LEFT and RIGHT indicate the left and right son nodes of the node. Here, it will be described here: The Parent pointer is not required, but after it is, it will greatly simplify many of the operations of the father's node. Therefore, it should be considered in the case where resources are not very nervous. The root of the bifurcation of the binary tree should be assigned NULL. A large amount of tools mentioned earlier - recursion in the binary tree. For example, the traversal operation of the binary tree is achieved by returning (not recursive, you can simulate the stack, but the speed will be slow, and the speed will take a lot of space, that is, non-recursive algorithms Time complexity is still the only advantageous of the recursive. The only benefit of non-recurable is just a stack. Therefore, which one is selected, it is necessary to see the specific application environment). In addition, I used Visit () callback functions in the order, order, and back sequence, which is to increase the degree of freedom of processing. In addition, I also wrote a few subunies to use to use the traversal technology, such as: getleafcount (), is the number of leaves of the binary tree in order to obtain the binary tree. In this case, please contact me if you are unclear. 8.4 Applying basic binary tree still can't talk about what applications, so my sample program is just a conversion of expressions ... Do you want to say, do you have to conversion to expressions? Yes it is! But actually the data structure of the binary tree is the most intuitive storage and expression of the expression. It can even be said that it is born to an expression! My example code is an expression with a binary tree: A B. After execution, it will result in such an output: ( ) / / (a) (b) Number of leaves of this tree: 2 The depth of this tree is: 1 Supreme traversal: ab Sub-sequence traversal: A B Rear sequence traversal: AB Chapter nine One important application for binary search tree 9.1 Basic concepts is the use of them in findings. The concept of the binary search tree is relatively easy to understand, ie: For each node X in the tree, the value of all the keywords in the left subtree is less than the key value value of X, and all of its right subtree The keyword value is greater than the key of the X. This means that all elements of the tree can be sorted in a unified manner. For example, the following is a legitimate binary search tree: 6 / / 2 8 / / 1 4 / 3 The nature of the binary search tree determines that it has a very good performance in the search: find the minimum node of a tree, only need to start from the root node, as long as there is left son, the end of the node is the smallest Node. Looking for the biggest node is carried out right. For example, in the example above, the minimum node is 1, at the left side; the maximum node is 8, at the right side. 9.2 Code Realizing the code of the binary tree is implemented as follows: //// // filename: bstree.h // Version: 0.10 // Author: Luo Cong // Date: 2005-1-17 22:53:52 // Comment: // /// #ifndef __binary_search_tree_h__ #define __binary_search_tree_h__ #include "../../btree/src/btree.h" Template Class CBSTree: Public CBTREE { Private: CBTNode CBTNode CBTNode CBTNode CBTNode PUBLIC: CBTNode CBTNode CBTNode CBTNode CBTNode } Template Inline CBTNode { Return Find (data, m_pnoderoot); } Template Inline CBTNode { IF (NULL == P) Return NULL; IF (Data Return Find (Data, P-> Left); Else IF (Data> P-> DATA) Return Find (DATA, P-> Right); Else Return P; } Template Inline CBTNode { Return Findmin (m_pnoderoot); } Template Inline CBTNode IF (NULL == P) Return NULL; Else IF (null == p-> left) Return P; Else Return Findmin (P-> LEFT); } Template Inline CBTNode { Return Findmax (m_pnoderoot); } Template Inline CBTNode { IF (NULL == P) Return NULL; Else IF (null == p-> right) Return P; Else Return Findmax (P-> Right); } Template Inline CBTNode { Return INSERT (DATA, M_PNODEROOT); } Template Inline CBTNode { IF (NULL == P) { P = New CBTNode IF (NULL == P) Return NULL; Else { P-> DATA = DATA; P-> left = null; P-> Right = NULL; IF (NULL == m_pnoderoot) { m_pnoderoot = p; m_pnoderoot-> parent = NULL; } } } Else IF (Data { P-> Left = insert (data, p-> left); IF (P-> Left) P-> LEFT-> PARENT = P; } Else IF (Data> P-> DATA) { P-> Right = INSERT (DATA, P-> Right); IF (P-> Right) P-> right-> parent = p; } // else data is in the tree already, we'll do nothing! Return P; } Template Inline CBTNode { Return delete (data, m_pnoderoot); } Template Inline CBTNode { IF (NULL == P) { // Error! Data NOT Found!} Else IF (Data { P-> Left = delete (data, p-> left); } Else IF (Data> P-> DATA) { P-> Right = delete (DATA, P-> Right); } Else IF (P-> Left && P-> Right) // Found IT, And It Has Two Children { CBTNODE P-> DATA = PTMP-> DATA; P-> Right = delete (P-> Data, P-> Right); } Else // Found IT, And It Has One or Zero Children { CBTNode IF (NULL == P-> Left) P = P-> Right; Else IF (null == p-> right) P = P-> Left; IF (p) P-> Parent = PTMP-> Parent; IF (m_pnoderoot == PTMP) m_pnoderoot = p; Delete PTMP; } Return P; } #ENDIF / / __BINARY_SEARCH_TREE_H__ Test Code: /// // // filename: bstree.cpp // Version: 0.10 // Author: Luo Cong // Date: 2005-1-17 22:55:12 // Comment: // /// #include "bstree.h" int main () { CBSTREE #ifdef _Debug _CRTSETDBGFLAG (_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); #ENDIF BSTree.Insert (1); BSTree.Insert (2); BSTree.insert (3); BStree.delete (1); } 9.3 Description My Binary Search Tree Inherited from the binary tree, I wrote Find (), Findmin (), Findmax (), INSERT (), and delete () a total of five member functions. What to say here is that the operation of nonlinear data structures is always particularly not intuitive, because in general, we will choose to use recursive - and the human brain is generally less easily "debug" procedures - if recursive The number is less (for example, only 1, 2 times) that is better, but once more than 5 or 6 times, I am afraid that the "stack" of the human brain will overflow. Ok, complain, let me explain: Find (): If the tree is empty, return null; if the root node is smaller than it is small, it will be left left, otherwise, if you are more than your right son, you will do it, neither it is not less than it. Son, then this node must be what we are looking for. Findmin (): From the root node, as long as the left son is processed to the left until the end of the end is encountered. Findmax (): Except for the right son, the rest is the same as Findmin (). INSERT (): If you find the same element, you don't do anything; otherwise, recursively find the last point of the traversal path, and then perform the Insert operation. DELETE (): As many data structures, the most difficult operation is to delete. The deleted operation can be divided into the following cases: If the node is a leaf, it can be deleted immediately. If the node has a son, then the node can be removed after the finger node adjustment pointer is removed. The most complex situation is to process the nodes with two sons. We can use the smallest data of its right child (very easy to find) instead of the data of the node, and recursively delete the node. why? Because a node is definitely smaller than its right boutique, it is larger than its left sub-tree, so we only need to find the smallest node in its right child. It can meet the nature of the binary tree. (According to this rule, we can also replace the data of the node, the truth is the same, the truth is the same, and it is not clear that I still don't know clearly (mainly abstract. ), Please read by compiling my code and personally debug it. My test code does not output the result, because I want to write a function of printed binary tree, I feel a bit annoying, you can break down in the corresponding function, I personally think that as long as I can understand the delete () function, then don't have it. The problem is. :)
