1.数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科.

2.传统上，我们把数据结构分为逻辑结构和物理结构。

逻辑结构：是指数据对象中数据元素之间的相互关系。

物理结构：是指数据的逻辑结构在计算机中的存储形式。

3.集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他不三不四的关系。

线性结构：线性结构中的数据元素之间是一对一的关系。

树形结构：树形结构中的数据元素之间存在一对多的层次关系。

图形结构：图形结构的数据元素是多对多的关系。

4.存储器主要是针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。

6.数据元素的存储结构形式有两种：顺序存储和链式存储

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

7.clock():捕捉从程序开始运行到clock（）被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。

常数CLK_TCK：机器时钟每秒所走的时钟大点数。

用法模板：

 

#include
      
       #include
       
        clock_t start,stop;//clock_t是clock（）函数返回的变量类型double duration;//记录被测函数运行时间，以秒为单位int main(）{    //不在测试范围内的准备工作写在clock（）调用之前    start=clock();//开始计时    MyFunction()；//把被测函数加在这里    stop=clock()；    duration=((double)(stop-start))/CLK_TCK;    //其他不再被测范围的处理写在后面，例如输出duration的值    return 0;
       
      

8.什么是好的算法：

（1）空间复杂度S(n)：根据算法写成的程序在执行时占用存储单元的长度。

（2）时间复杂度T(n)：根据算法写成的程序在执行时耗费时间的长度。

在分析一般算法的效率时，我们经常关注下面两种复杂度

（1）最坏情况复杂度T_worst（n）

（2）平均复杂度T_avg(n)

                        T_avg(n)<=T_worst（n）

9.复杂度常用函数比较大小：

_{1<logn<n<nlog2n<n²<n³<2ⁿ<n!}

10.链表结点的定义：

链表的结点有两个域：一个是数据域，用来存放数据；另一个是指针域，用来存放下一个结点的位置，如图所示：

因此，链表的结构型定义如下：

typedef struct Node {     int data;//这里默认的是int型，如需其他类型那个可直接修改     struct Node *next;//指向Node型变量的指针}Node;

11.二叉树结点的定义：

typedef struct BTNode {    int data;    struct BTNode *lchild;    struct BTNode *rchild; }BTNode;

12.线性表:由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素成为记录，而由多个记录构成的线性表又称为文件。

非空线性表的结构特性：

(1)有且只有一个根节点a_{1,它无前件。}

(2)有且只有一个终端结点a_{n,它无后件}

(3)除根节点和终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。节点个数n为线性表的长度，当n=0时，称为空表。

13.线性表的顺序存储结构具有以下两个基本特点：

(1)线性表中所有元素的所占存储空间是练习的;

(2)线性表中各数据元素再存储空间中是按逻辑顺序依次存放的。

a_i 的存储地址：

ADR(a_i)=ADR(a_i)+(i-1)K,ADR(a_i)为第一个元素的地址，K代表每个元素所占的字节数。

14.顺序表的插入运算：

插入的过程：

首先处理3种异常情况：

(1)当存储空间已满时为“上溢”错误，不能插入，算法结束；

(2)当i>n时，认为在最后一个元素之后插入;

(3)当i<n时，认为在第一个元素之前插入。

然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。

最后将新元素插入到第i个位置，并且将线性表的长度增加1。

15.顺序表的删除元素

删除的过程：

首先处理一下2种异常情况：

(1)当线性表为空(即n=0)时即为“上溢”错误，算法结束；

(2)当i<1或i>n时，

然后从第i+1个元素开始，直到最后一个元素，其中每个元素依次向前移动一个位置。

最后将线性表的长度减少1。

16.所有的指针变量只占4个字节，用第一个字节的地址表示整个变量的地址。

17.顺序表不像链表一样在结点中存在指针域，因此存储密度大。插入运算方便和删除运算方便是链表的优点。线性表的顺序存储结构必须占用一片连续的存储空间，而链表不需要这样。顺序表不便于元素的插入和删除，因为要移动多个元素。链表在插入和删除的过程中不需要移动元素，只需修改指针。线性表是具有相同特性数据元素的一个有序序列。

18.静态链表中指针指示的是链表中下一元素在数组中的地址。虽然静态链表用数组来存储，但其指针域和一般单链表一样，指出了表中下一个结点的位置。静态链表具有链表的的插入和删除方便的特点，也不需要移动较多的元素，这是优于顺序表的地方。

19.KMP算法

(1)字符串查找问题：给定文本串text和模式串pattern，从文本串text中找出模式串pattern第一次出现的位置

(2)最基本的字符串匹配算法：暴力求解(Brute Force):时间复杂度O(m*n)

(3)KMP算法是一种线性时间复杂度的字符串匹配算法，它是对BF算法改进。

(4)记：文本串长度为N，模式串长度为M

(I)BF算法的时间复杂度O(M*N),空间复杂度O(1);

(II)KMP算法的时间复杂度O(M+N),空间复杂度O(N);

(5)KMP算法的核心就是避免不必要的回溯，那么什么事不必要的呢？问题由模式串决定，不是由目标决定。

(6)分析BF与KMP的区别

(I)假设当前文本串text匹配到i位置，模式串pattern串匹配到j位置

(II)BF算法中，如果当前字符串匹配成功，即text[i+j]==pattern[j],令i++,j++，继续匹配下一个字符；如果失败，即text[i+j]=/=（不等于）pattern[j],令i++,j=0;即每次匹配失败的情况下，模式串pattern相对于文本串text向右移动了一位。

(7)KMP算法中，如果当前字符匹配成功，即text[i+j]==pattern[j],令i++,j++,继续匹配下一个字符；如果失败，即text[i+j]=/=(不等于)pattern[j],令i不变，j=next[j],(这里，next[j]<=j-1),即模式串pattern相对于文本串text向右移动了至少1位(移动的实际位数j-next[j]>=1)。

(8)在暴力求解中，为什么模式串的索引会回溯？

因为模式串存在重复字符。

(9)对于模式串的位置j，考察Pattern_j-1=P₀P₁...P_j-2P_j-1,查找字符串Pattern_j-1最大相等k前缀和k后缀。注：计算next[j]时，考察的字符串是模式串的前j-1个字符，与pattern[j]无关。即：查找慢走条件的最大的k，是得P₀P₁...P_k-2P_k-1 =P_j-kP_j-k+1...P_j-2P_j-1 。

(10)next的递推关系：

(I)对于模式串的位置j,有next[j]=k,即：P₀P₁...P_k-2P_k-1 =P_j-kP_j-k+1...P_j-2P_j-1 

(II)则，对于模式串的位置j+1,考察P_j;

(III)若p[k]==p[j] 

　　next[j+1]=next[j]+1

(IV)若p[k]=/=p[j],记h=next[k];如果p[h]==p[j],则next[j+1]=h+1,否则重复此过程。

(11)进一步分析next

(I)文本串匹配到i,模式串匹配到j,此时，若text[i]=/=pattern[j],即匹配失败的情况：

(II)若next[j]=k,说明模式串应该从j滑动到k位置;

(III)若此时满足pattern[j]==pattern[k],因为text[i]=/=pattern[j],所以，text[i]=/=pattern[k]

(i)即i和k没有匹配，应该继续滑动到next[k]。

(ii)换句话说：若原始的next数组中，若next[j]=k并且pattern[j]==pattern[k],next[j]可以直接等于next[k]。

(12)代码

//BF算法，暴力算法int index(Str str,Str substr){    int i=0,j=0,k=i;    while(i
      

20.

(1)串是限定了数据元素是字符的线性表，串的数据元素必须是单个字符

(2)串的两种最基本存储方式是顺序存储方式和链式存储方式。

(3)空格字符也是串中的一个字符。

21.希尔排序

#include
      
       #include
       
        #define MAXNUM 10 //希尔排序 void shellSort(int array[],int n,int t) {     int a,dk;     for(a=1;a<=t;a++)         {             dk=(int)(pow(2,t-a+1)-1);//计算增量              int i,j,temp;            for(i=dk;i
        
         =i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行                 array[j+dk]=array[j];                if(j!=i-dk)                array[j+dk]=temp;//插入             }             }  }     void main()  {      void shellSort(int array[],int n,int t);//t为排序的趟数      int array[MAXNUM],i;      for(i=0;i
        
       
      

22.进行冒泡排序

#include 
      
       #include 
       
        #define MAXNUM 10/* run this program using the console pauser or add your own getch, system("pause") or input loop */void maopaoInsert(int R[],int n){    int i,j,temp;    for(j=0;j
        
         R[i+1])//每次进行两两比较             {                temp=R[i];                R[i]=R[i+1];                R[i+1]=temp;            }        }    }        }   void main()  {      int array[MAXNUM],i;    for(i=0;i
        
       
      

23快速排序

#include 
      
       #include 
       
        #define MAXNUM 10void kuaisuSort(int a[],int left,int right){    if(left>=right)//如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了    {        return;     }     int i=left;    int j=right;    int key=a[left];//以a[left]为轴中心    while(i
        
         =a[i])//这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想就是把数组网两边礽，所以左右两边的数大小与key的关系相反         {            i++;        }        a[j]=a[i];    }          a[i]=key;//当在当组内找完一遍以后就把中间数key回归    kuaisuSort(a,left,i-1);//最后用同样的方式把对分出来的左边的小组进行同上的做法    kuaisuSort(a,i+1,right);//最后用同样的方式把对分出来的右边的小组进行同上的做法     //当然最后可能会出现很多分左右，直到每一组的i=j为止。  } void main()  {      int array[MAXNUM],i;    for(i=0;i
        
       
      

24.简单选择排序

#include 
      
       #include 
       
        #define MAXNUM 10/* run this program using the console pauser or add your own getch, system("pause") or input loop */void jiandanxuanzeSort(int R[],int n){    int i,j,min;int minR;//储存最小的数组     int temp;    for(i=0;i
       
      

25.最大公约数

//最大公约数int gcd(int v1,int v2){    while(v2)    {        int temp=v2;        v2=v1%v2;        v1=temp;     }        return v1;}

26.交换

(1)指针

#include 
      
       using namespace std;void swap(int *px, int *py){    int temp;    temp=*px;    *px=*py;    *py=temp;}int main(){    int a,b;    a = 1;    b = 10;    cout << "传指针的方法: " << endl;    cout << "a = " << a << ", b = " << b << endl;    //拷贝的指针(地址)     swap(&a,&b);    cout << "a = " << a << ", b = " << b << endl;    return 0;}
      

(2)宏函数

#include 
      
       #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))using namespace std;int main(){    int a, b, temp;    a = 1;    b = 10;    cout << "使用宏定义函数: " << endl;    cout << "a = " << a << ", b = " << b << endl;    SWAP(a,b,temp);    cout << "a = " << a << ", b = " << b << endl;    return 0;}
      

(3)引用

#include 
      
       using namespace std;//引用就是别名 void swap(int &a,int &b){    int temp;    temp=a;    a=b;    b=temp; } int main(){    int a,b;    a = 1;    b = 10;    cout << "传引用: " << endl;    cout << "a = " << a << ", b = " << b << endl;    swap(a,b);    cout << "a = " << a << ", b = " << b << endl;    return 0;}
      

(4)C++标准库 swap

#include 
      
       using namespace std;int main(){    int a, b;    a = 1;    b = 10;    cout << "使用std::swap函数: " << endl;    cout << "a = " << a << ", b = " << b << endl;    std::swap(a,b);    cout << "a = " << a << ", b = " << b << endl;    return 0;}
      

27.图

(1)邻接矩阵

代码：

#include 
      
       using namespace std;#define MAX_VERTS 20 //保存最多的顶点数 //顶点 class Vertex{    public:        Vertex(char lab){Label=lab;    }     private:            char Label;        };//图  邻接矩阵 (对称) class Graph{    public:        Graph();        ~Graph();        void addVertex(char lab);//增加顶点         void addEdge(int start,int end);//增加边        void printMatrix();//打印矩阵     private:        Vertex* vertexList[MAX_VERTS];//数组(保存最多的定点数)         int nVerts;//实际上的顶点数         int adjMat[MAX_VERTS][MAX_VERTS]; //邻接矩阵 } ;//构造函数，有效点为0，初始化矩阵 Graph::Graph(){    nVerts=0;    for(int i=0;i
      

(2)邻接表

#include 
      
       #include 
       
        using namespace std;class Vertex{public:    char Label;    Vertex(char lab) { Label = lab; }};ostream& operator<<(ostream& out, const Vertex& v){    cout << v.Label;    return out;}template
        
         class Graph{public:    Graph(const int vertices) : n(vertices)    {        VertexList = new T*[n];        HeadNodes = new list
         
          [n];        nVerts = 0;    }    ~Graph()    {        delete[] VertexList;        delete[] HeadNodes;    }    void addVertex(T* v);    void addEdge(int start, int end);    void printVertice();    void printAdjList();private:    T** VertexList;    list
          
           * HeadNodes;    int n;    int nVerts;};template
           
            void Graph
            
             ::addVertex(T* v){ VertexList[nVerts++] = v;}template
             
              void Graph
              
               ::addEdge(int start, int end){ HeadNodes[start].push_back(end);}template
               
                void Graph
                
                 ::printVertice(){ for(int i=0; i
                 
                  void Graph
                  
                   ::printAdjList(){ for(int i=0; i
                   
                     "; for(list
                    
                     ::iterator iter = HeadNodes[i].begin(); iter != HeadNodes[i].end(); ++iter) cout << *iter << " -> "; cout << "end" << endl; }}int main(){ //Graph
                     
                       g(5); //char a = 'A'; //char b = 'B'; //char c = 'C'; //char d = 'D'; //char e = 'E'; Graph
                      
                        g(5); Vertex a('A'); Vertex b('B'); Vertex c('C'); Vertex d('D'); Vertex e('E'); g.addVertex(&a); g.addVertex(&b); g.addVertex(&c); g.addVertex(&d); g.addVertex(&e); g.printVertice(); g.addEdge(0,1); g.addEdge(0,3); g.addEdge(1,0); g.addEdge(1,4); g.addEdge(2,4); g.addEdge(3,0); g.addEdge(3,4); g.addEdge(4,1); g.addEdge(4,2); g.addEdge(4,3); g.printAdjList(); system("pause"); return 0;}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

(3)深度优先搜索(DFS) 使用堆栈

 

代码：(以邻接矩阵图形为案例)

#include 
      
       #include
       
        #define MAX_VERTS    20using namespace std;class Vertex{public:    Vertex(char lab)     {         Label = lab;         wasVisited=false;//新构造的顶点没有访问过     }public:    bool wasVisited;     char Label;};class Graph{public:    Graph();    ~Graph();    void addVertex(char lab);    void addEdge(int start, int end);    void printMatrix();    void showVertex(int v);//显示顶点     void DFS();//深度优先搜索 private:    Vertex* vertexList[MAX_VERTS];    int nVerts;    int adjMat[MAX_VERTS][MAX_VERTS];    int getAdjUnvisitedVertex(int v); //获得临接的下一个且没有访问的顶点 };void Graph::DFS(){    stack
        
          gStack;    vertexList[0]->wasVisited=true;//顶点     showVertex(0);    gStack.push(0);//顶点放入到堆栈     int v;    while(gStack.size()>0)    {        v=getAdjUnvisitedVertex(gStack.top());//总是以堆栈中最上一个为准         if(v==-1)// 如果没有，则返回             gStack.pop();        else//找到         {            vertexList[v]->wasVisited=true;            showVertex(v);            gStack.push(v); //找到放入到堆栈中         }    }    cout<
         
          wasVisited=false;} //获得临接的下一个且没有访问的顶点//是否是邻接的？是否访问过 int Graph::getAdjUnvisitedVertex(int v){    for(int j=0;j
          
           wasVisited==false))            return j;    return -1;}void Graph::showVertex(int v){    cout<
           
            Label<<" ";} Graph::Graph(){ nVerts = 0; for(int i=0; i
           
          
         
        
       
      

 

(4)广度优先搜索(BFS) 使用队列

 

 代码：

#include 
      
       #include 
       
        #include
        
          #define MAX_VERTS    20using namespace std;class Vertex{public:    Vertex(char lab)     {         Label = lab;         wasVisited = false;    }public:    bool wasVisited;    char Label;};class Graph{public:    Graph();    ~Graph();    void addVertex(char lab);    void addEdge(int start, int end);    void printMatrix();    void showVertex(int v);    void DFS();    void BFS();//广度优先 private:    Vertex* vertexList[MAX_VERTS];    int nVerts;    int adjMat[MAX_VERTS][MAX_VERTS];    int getAdjUnvisitedVertex(int v);};void Graph::DFS(){    stack
         
           gStack;    vertexList[0]->wasVisited = true;    showVertex(0);    gStack.push(0);    int v;    while(gStack.size() > 0)    {        v = getAdjUnvisitedVertex(gStack.top());        if(v == -1)            gStack.pop();        else        {            vertexList[v]->wasVisited = true;            showVertex(v);            gStack.push(v);        }    }    cout << endl;    for(int j=0; j
          
           wasVisited = false;}void Graph::BFS(){    queue
           
            gQueue; vertexList[0]->wasVisited=true; //设置顶点为访问过了， showVertex(0); gQueue.push(0);//把顶点放入到队列中 int vert1,vert2; while(gQueue.size()>0) { vert1=gQueue.front();//把队列中顶点拿出来 gQueue.pop();//队列顶点删除 vert2=getAdjUnvisitedVertex(vert1);//邻接且没有访问过的 while(vert2!=-1)//有 邻接且没有访问过的 { vertexList[vert2]->wasVisited=true; showVertex(vert2); gQueue.push(vert2);//放入到队列中 vert2=getAdjUnvisitedVertex(vert1);//继续寻找vert1中其他符合条件的 //(因为getAdjUnvisitedVertex这个函数只是保证找到符合条件就返回) } } cout<
            
             wasVisited = false; } int Graph::getAdjUnvisitedVertex(int v){ for(int j=0; j
             
              wasVisited == false)) return j; return -1;}void Graph::showVertex(int v){ cout << vertexList[v]->Label << " ";}Graph::Graph(){ nVerts = 0; for(int i=0; i
             
            
           
          
         
        
       
      

28.红黑树

(1)红黑树特征：节点都有颜色，插入和删除节点时要遵循红黑规则

(2)红黑规则：

(I)每一个节点不是红色的就是黑色的。

(II)根总是黑色的

(III)如果节点时红色的，则它的子节点必须是黑色的

(IV)从根到叶节点的每条路径，必须包含相同数目的黑色节点。

(3)修正方法

(I) 修改节点的颜色

(II)旋转

(4)C++标准库中的红黑树

#include 
      
       #include 
       
      

(5)红黑树(自编)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          // SEE UPDATE COMMENTS AT END OF FILE// 2006-01.29 fixed memory leaks// eliminate need to qualify standard library with std::using namespace std;// ===============================================================// C++ NEEDS SOME DECLARATIONS BEFORE THE MAIN RedBlackTree class.// skip down a little to line this up with the other side// ===============================================================// requires forward declaration to resolve cycle between NodeVisitor and RedBlackTreetemplate
          
            class RedBlackTree;// use an abstract class for the node visitor. it is templatized to match the templated RedBlackTree declarationtemplate
           
             class NodeVisitor {public: // need a virtual destructor for the concrete classes virtual ~NodeVisitor() {} // ise a pure virtual function so a concrete class must implement // the proper signature virtual void visit(const RedBlackTree
            
              *node,int depth) = 0;};// =============================================// >>>>>>>>>>>>>>>>> RED BLACK TREE STARTS HERE// =============================================// in line with the STL conventions, this template uses 'by-value' semantics for the contained// object. This means that the 'T' object will need to have the correct constructor and copy assignment// semantics or it won't work. primitive types are OK but object instances would have to be// put together correctly. template
             
               class RedBlackTree { private: /* Red/Black tree implementation based on Algorithms in C++, Sedgewick Introduction To Algorithms Cormen, Thomas H. / Leiserson, Charl es E . / Rivest, Ronald L . The MIT Press 07/1990 NOTE : LOOK AT END OF FILE TO SEE DIFFERENCES IN TRAVERSAL IDIOMS */ // yes, i could use an enum but since i want to print the values, using an enum is more // trouble than it is worth. static const int red = 0; static const int black = 1; // use a common instance variable naming convention 'm_'. others use a single leading '_' int m_color; T m_val; RedBlackTree *m_left; RedBlackTree *m_right; RedBlackTree(RedBlackTree *b) { m_val = b->m_val; m_left = b->m_left; m_right = b->m_right; m_color = red; } void copy(RedBlackTree *x) { m_val = x->m_val; m_left = x->m_left; m_right = x->m_right; m_color = x->m_color; // UPDATE 2006-01-28 // node pointed to by 'x' is no longer needed, delete it. // first make sure the delete won't descend into other nodes x->m_left = 0; x->m_right = 0; delete x; } RedBlackTree *RBinsertLeft(T k,int sw) { RedBlackTree *l; RedBlackTree *b; l = m_left; if (l == 0) { m_left = b = new RedBlackTree(k); } else { b = l->RBinsert(k,sw); } return b; } RedBlackTree *RBinsertRight(T k,int sw) { RedBlackTree *r; RedBlackTree *b; r = m_right; if (r == 0) { m_right = b = new RedBlackTree(k); } else { b = r->RBinsert(k,sw); } return b; } RedBlackTree *rotLeft() { RedBlackTree *x; RedBlackTree *me; if (m_right == 0) return 0; // make the changes in a copy of current node __self // on return, the caller will copy in 'me' to current node me = new RedBlackTree(this); x = me->m_right; me->m_right = x->m_left; x->m_left = me; return x; } RedBlackTree *rotRight() { RedBlackTree *x; RedBlackTree *me; if (m_left == 0) return 0; // make the changes in a copy of current node __self // on return, the caller will copy in 'me' to current node me = new RedBlackTree(this); x = me->m_left; me->m_left = x->m_right; x->m_right = me; return x; } RedBlackTree *RBinsert(T k,int sw) { RedBlackTree *b = 0; RedBlackTree *x; RedBlackTree *l; RedBlackTree *ll; RedBlackTree *r; RedBlackTree *rr; // if current node is a 4 node, split it by flipping its colors // if both children of this node are red, change this one to red // and the children to black l = m_left; r = m_right; if ((l != 0)&&(l->m_color==red)&&(r != 0)&&(r->m_color==red)) { m_color = red; l->m_color = black; r->m_color = black; } // go left or right depending on key relationship if (k < m_val) { // recursively insert b = RBinsertLeft(k,0); // on the way back up check if a rotation is needed // if search path has two red links with same orientation // do a single rotation and flip the color bits l = m_left; if ((m_color == red)&&(l != 0)&&(l->m_color == red)&&(sw == 1)) { x = rotRight(); if (x != 0) { // copy returned node to 'this' copy(x); } } // flip the color bits l = m_left; if (l != 0) { ll = l->m_left; if (ll != 0) { if ((l->m_color == red)&&(ll->m_color == red)) { x = rotRight(); if (x != 0) { copy(x); } m_color = black; r = m_right; if (r != 0) { r->m_color = red; } } } } } else { b = RBinsertRight(k,1); // on the way back up check if a rotation is needed // if search path has two red links with same orientation // do a single rotation and flip the color bits r = m_right; if ((m_color == red)&&(r != 0)&&(r->m_color == red)&&(sw == 0)) { x = rotLeft(); if (x != 0) { // copy returned node to 'this' copy(x); } } // flip the color bits r = m_right; if (r != 0) { rr = r->m_right; if (rr != 0) { if ((r->m_color == red)&&(rr->m_color == red)) { x = rotLeft(); if (x != 0) { // copy returned node to 'this' copy(x); } m_color = black; l = m_left; if (l != 0) { l->m_color = red; } } } } } return b; } // ==================================================// PUBLIC METHODS// ==================================================public: // construct with an initial value RedBlackTree(T x) { m_val = x; m_left = 0; m_right = 0; m_color = red; } ~RedBlackTree() { if (m_left != 0) { delete m_left; } if (m_right != 0) { delete m_right; } } // return a string representation string str() const { stringstream s(stringstream::out); // m_val (type T) must have the proper ostream insertion operator // or this implementation won't work s << "[" << m_val << "," << m_color << "]"; return s.str(); } // 'const' means this method doesn't change the object state T val() const { return m_val; } // 'const' means this method doesn't change the object state int color() const { return m_color; } // 'const' means this method doesn't change the object state // and it returns a pointer to a const node that the caller // cannot change, only inspect const RedBlackTree *find(const T &key) const { const RedBlackTree *result = 0; if (key == m_val) { result = this; } else if (key < m_val) { if (m_left != 0) { result = m_left->find(key); } } else { if (m_right != 0) { result = m_right->find(key); } } return result; } // 'const' means this method doesn't change the object state // and the visitor is not allowed to change the object state. // that may not be what is desired but is used here to // illustrate something you can do in C++ that you can't do // in the other languages and that illustrates the bias towards // extensive static type checking void inorder(NodeVisitor
              
                *visitor,int depth) const { if (m_left != 0) { m_left->inorder(visitor,depth+1); } visitor->visit(this,depth); if (m_right != 0) { m_right->inorder(visitor,depth+1); } } RedBlackTree *insert(T k) { RedBlackTree *b; b = RBinsert(k,0); m_color = black; return b; }};// define a concrete class for the node visitorclass IntNodeVisitor : public NodeVisitor
               
                 {public: virtual ~IntNodeVisitor() {} // the node is 'const' so the visitor can't change it, only look at it virtual void visit(const RedBlackTree
                
                  *node,int depth) { if (node->val() != 0) { cout << "(" << node->val() << ":" << node->color() << ":" << depth << "), "; } }};// ==================================// test program// ==================================int main(int argc,char *argv[]) { int nodelist[] = { 11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1}; NodeVisitor
                 
                   *v; // anonymous class implementing the NodeVisitor interface v = new IntNodeVisitor; // insert all the data into the tree RedBlackTree
                  
                    *root = new RedBlackTree
                   
                    (2); root->insert(11); root->insert(4); root->insert(8); root->insert(14); root->insert(17); root->insert(6); //显示红黑树里的数据 root->inorder(v,0); return 0; // need to do an ugly calculation to figure out length of the nodelist array // if i used a collection object instead of an array, then I couldn't have // done static initialization. so its a tradeoff for(int i=0;i<(sizeof(nodelist)/sizeof(nodelist[0]));i++) { root->insert(nodelist[i]); } // print the header cout << "C++ = "; // visit all the nodes in order root->inorder(v,0); // print a newline cout << endl; // find the specified element and print its value const RedBlackTree
                    
                      *x = root->find(16); cout << x->str() << endl; // no garbage collection, need to explicitly delete delete root; // will recursively delete all the nodes delete v;} // ===================================================================// UPDATE 2006-01-29// there are memory leaks that need to be fixed. // 1. the algorithm leaks nodes after a rotate// two possible fixes : // find where the leaks occur and do the needed deletes // in this case the 'copy' method handles // deleting unused nodes// use an appropriate smart pointer to handle deleteing// 2. the tree is not properly disposed of when the program completes// In the STL tradition a delete of the tree should// delete all tree resources but not the contained data. the application// should handle deleting the contained data elements, if needed, prior// to deleting the tree. In this case a recursive delete of the // nodes works gets rid of the tree resources//// these issue show that one of the big difficulties in C++ is to // handle disposing of data after you are done with it. that is indeed a// source of many C++ program errors of the type that are related more to// dealing with the complexity of the language rather than the solving // the problem. In this code the leaks are probably fixed but there is always// a lingering doubt "Did I get all the leaks?"// Thats a problem with C++, its hard to be certain.//// a modern approach is to use smart pointers to simulate garbage // collection. the Boost library referenced counted smart pointers// will be included in the next standard revision of the C++ library// so they are used here to handle all the cases.// ===================================================================
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

(6)红黑树(模版)

#ifndef RED_BLACK_TREE_H_#define RED_BLACK_TREE_H_#include "Wrapper.h"#include "Except.h"// Red-black tree class.//// CONSTRUCTION: with negative infinity object//// ******************PUBLIC OPERATIONS*********************// void insert( x )       --> Insert x// void remove( x )       --> Remove x (unimplemented)// Comparable find( x )   --> Return item that matches x// Comparable findMin( )  --> Return smallest item// Comparable findMax( )  --> Return largest item// bool isEmpty( )        --> Return true if empty; else false// void makeEmpty( )      --> Remove all items// ******************ERRORS********************************// Throws exceptions as warranted.template 
      
       class RedBlackTree;template 
       
        class RedBlackNode;template 
        
         class RedBlackTree{  public:    RedBlackTree( const Comparable & negInf );    RedBlackTree( const RedBlackTree & rhs );    ~RedBlackTree( );    Cref
         
           findMin( ) const;    Cref
          
            findMax( ) const;    Cref
           
             find( const Comparable & x ) const; bool isEmpty( ) const; void makeEmpty( ); void insert( const Comparable & x ); void remove( const Comparable & x ); enum { RED, BLACK }; const RedBlackTree & operator=( const RedBlackTree & rhs ); typedef RedBlackNode
            
              Node; private: Node *header; // The tree header (contains negInf) Node *nullNode; // Used in insert routine and its helpers (logically static) Node *current; Node *parent; Node *grand; Node *great; // Usual recursive stuff void reclaimMemory( Node *t ) const; RedBlackNode
             
               * clone( Node * t ) const; // Red-black tree manipulations void handleReorient( const Comparable & item ); RedBlackNode
              
                * rotate( const Comparable & item, Node *parent ) const; void rotateWithLeftChild( Node * & k2 ) const; void rotateWithRightChild( Node * & k1 ) const;};template 
               
                class RedBlackNode{ Comparable element; RedBlackNode *left; RedBlackNode *right; int color; RedBlackNode( const Comparable & theElement = Comparable( ), RedBlackNode *lt = NULL, RedBlackNode *rt = NULL, int c = RedBlackTree
                
                 ::BLACK ) : element( theElement ), left( lt ), right( rt ), color( c ) { } friend class RedBlackTree
                 
                  ;};// Construct the tree.// negInf is a value less than or equal to all others.template 
                  
                   RedBlackTree
                   
                    ::RedBlackTree( const Comparable & negInf ){ nullNode = new Node; nullNode->left = nullNode->right = nullNode; header = new Node( negInf ); header->left = header->right = nullNode;}// Copy constructor.template 
                    
                     RedBlackTree
                     
                      ::RedBlackTree( const RedBlackTree
                      
                        & rhs ){ nullNode = new Node; nullNode->left = nullNode->right = nullNode; header = new Node( rhs.header->element ); header->left = header->right = nullNode; *this = rhs;}// Destroy the tree.template 
                       
                        RedBlackTree
                        
                         ::~RedBlackTree( ){ makeEmpty( ); delete nullNode; delete header;}// Insert item x into the tree.// Throws DuplicateItemException if x is already present.template 
                         
                          void RedBlackTree
                          
                           ::insert( const Comparable & x ){ current = parent = grand = header; nullNode->element = x; while( current->element != x ) { great = grand; grand = parent; parent = current; current = x < current->element ? current->left : current->right; // Check if two red children; fix if so if( current->left->color == RED && current->right->color == RED ) handleReorient( x ); } // Insertion fails if already present if( current != nullNode ) throw DuplicateItemException( ); current = new Node( x, nullNode, nullNode ); // Attach to parent if( x < parent->element ) parent->left = current; else parent->right = current; handleReorient( x );}// Remove item x from the tree.// Not implemented in this version.template 
                           
                            void RedBlackTree
                            
                             ::remove( const Comparable & x ){ cout << "Sorry, remove unimplemented; " << x << " still present" << endl;}// Find the smallest item the tree.// Return the smallest item wrapped in a Cref object.template 
                             
                              Cref
                              
                                RedBlackTree
                               
                                ::findMin( ) const{ if( isEmpty( ) ) return Cref
                                
                                 ( ); Node *itr = header->right; while( itr->left != nullNode ) itr = itr->left; return Cref
                                 
                                  ( itr->element );}// Find the largest item in the tree.// Return the largest item wrapped in a Cref object.template 
                                  
                                   Cref
                                   
                                     RedBlackTree
                                    
                                     ::findMax( ) const{ if( isEmpty( ) ) return Cref
                                     
                                      ( ); Node *itr = header->right; while( itr->right != nullNode ) itr = itr->right; return Cref
                                      
                                       ( itr->element );}// Find item x in the tree.// Return the matching item wrapped in a Cref object.template 
                                       
                                        Cref
                                        
                                          RedBlackTree
                                         
                                          ::find( const Comparable & x ) const{ nullNode->element = x; Node *curr = header->right; for( ; ; ) { if( x < curr->element ) curr = curr->left; else if( curr->element < x ) curr = curr->right; else if( curr != nullNode ) return Cref
                                          
                                           ( curr->element ); else return Cref
                                           
                                            ( ); }}// Make the tree logically empty.template 
                                            
                                             void RedBlackTree
                                             
                                              ::makeEmpty( ){ reclaimMemory( header->right ); header->right = nullNode;}// Test if the tree is logically empty.// Return true if empty, false otherwise.template 
                                              
                                               bool RedBlackTree
                                               
                                                ::isEmpty( ) const{ return header->right == nullNode;}// Deep copy.template 
                                                
                                                 const RedBlackTree
                                                 
                                                   &RedBlackTree
                                                  
                                                   ::operator=( const RedBlackTree
                                                   
                                                     & rhs ){ if( this != &rhs ) { makeEmpty( ); header->right = clone( rhs.header->right ); } return *this;}// Internal method to clone subtree.template 
                                                    
                                                     RedBlackNode
                                                     
                                                       *RedBlackTree
                                                      
                                                       ::clone( Node * t ) const{ if( t == t->left ) // Cannot test against nullNode!!! return nullNode; else return new RedBlackNode
                                                       
                                                        ( t->element, clone( t->left ), clone( t->right ), t->color );}// Internal routine that is called during an insertion// if a node has two red children. Performs flip and rotations.// item is the item being inserted.template 
                                                        
                                                         void RedBlackTree
                                                         
                                                          ::handleReorient( const Comparable & item ){ // Do the color flip current->color = RED; current->left->color = BLACK; current->right->color = BLACK; if( parent->color == RED ) // Have to rotate { grand->color = RED; if( item < grand->element != item < parent->element ) parent = rotate( item, grand ); // Start dbl rotate current = rotate( item, great ); current->color = BLACK; } header->right->color = BLACK; // Make root black}// Internal routine that performs a single or double rotation.// Because the result is attached to the parent, there are four cases.// Called by handleReorient.// item is the item in handleReorient.// parent is the parent of the root of the rotated subtree.// Return the root of the rotated subtree.template 
                                                          
                                                           RedBlackNode
                                                           
                                                             *RedBlackTree
                                                            
                                                             ::rotate( const Comparable & item, Node *theParent ) const{ if( item < theParent->element ) { item < theParent->left->element ? rotateWithLeftChild( theParent->left ) : // LL rotateWithRightChild( theParent->left ) ; // LR return theParent->left; } else { item < theParent->right->element ? rotateWithLeftChild( theParent->right ) : // RL rotateWithRightChild( theParent->right ); // RR return theParent->right; }}// Rotate binary tree node with left child.template 
                                                             
                                                              void RedBlackTree
                                                              
                                                               ::rotateWithLeftChild( Node * & k2 ) const{ Node *k1 = k2->left; k2->left = k1->right; k1->right = k2; k2 = k1;}// Rotate binary tree node with right child.template 
                                                               
                                                                void RedBlackTree
                                                                
                                                                 ::rotateWithRightChild( Node * & k1 ) const{ Node *k2 = k1->right; k1->right = k2->left; k2->left = k1; k1 = k2;}// Internal method to reclaim internal nodes in subtree t.template 
                                                                 
                                                                  void RedBlackTree
                                                                  
                                                                   ::reclaimMemory( Node *t ) const{ if( t != t->left ) { reclaimMemory( t->left ); reclaimMemory( t->right ); delete t; }}#endif
                                                                  
                                                                 
                                                                
                                                               
                                                              
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 29.冒泡排序

(1)从左到右扫描数据，选择最大的数据，放在右边。

(2)要点:比较相邻的两个树，如果左边的数大于右边的数就进行交换。

(3)代码:

#include 
      
       using namespace std;void BubbleSort(int list[], int n);int main(){    int a[] = {
    2,4,6,8,0,1,3,5,7,9};    BubbleSort(a,10);    for(int k=0; k<10; k++)        cout << a[k] << " ";    cout << endl;    return 0;}void BubbleSort(int list[], int n){        for(int i=0; i
       
         list[j+1])                std::swap(list[j],list[j+1]);        }    }}
       
      

30选择排序

(1)从当前未排序的整数中找一个最小的整数，将它放在已排序的整数列表的最后。

(2)要点：选择排序最小的，往左边选。

#include 
      
       using namespace std;void SelectSort(int *a, const int n);int main(){    int x[] = {
    1,3,5,7,9,0,2,4,6,8};    SelectSort(x,10);    for(int k=0; k<10; k++)        cout << x[k] << endl;    return 0;}void SelectSort(int *list, const int n){    //           i
      

31.折半查找

v#include 
      
       using namespace std;int BinarySearch(int *a, const int x, const int n);int BinSearch(int *a, const int x, const int n);int main(){    int x[] = {
    1,2,3,4,5,6,7,8,9,10};    int 结果;    int num;    num = 6;    结果 = BinSearch(x, num, 10);    if(结果 < 0)        cout << "没找到! " << endl;    else        cout << "在x[" << 结果 << "]找到" << num << endl;    return 0;}int BinSearch(int *a, const int x, const int n){    int left = 0, right = n-1;    while(left<=right)    {        int middle = (left + right)/2;        if(x < a[middle]) right = middle-1;        else if(x > a[middle]) left=middle+1;        else return middle;    }    return -1;}int BinarySearch(int *a, const int x, const int n){    int low, high, mid;    low = 0, high = n-1;    while(low<=high)    {        mid = (low + high) / 2;        if(a[mid] == x)            return mid;        else if(a[mid] < x)            low = mid+1;        else if(a[mid] > x)            high = mid - 1;    }    return -1;}
      

#include 
      
       using namespace std;int BinarySearch_I(int *a, const int x, const int n);int BinarySearch_R(int *a, const int x, const int left, const int right);int main(){    int m[] = {
    1,2,3,4,5,6,7,8,9};    int 结果;    int num = 7;    if((结果 = BinarySearch_R(m,num,0,8))<0)    {        cout << "递归算法: 没找到!" << endl;    }else{        cout << "递归算法: 在m[" << 结果 << "]找到" << num << endl;    }    if((结果 = BinarySearch_I(m,num,9))<0)    {        cout << "迭代算法: 没找到!" << endl;    }else{        cout << "迭代算法: 在m[" << 结果 << "]找到" << num << endl;    }    return 0;}int BinarySearch_I(int *a, const int x, const int n){    int left = 0, right = n-1;    while(left <= right)    {        int middle = (left+right)/2;        if(x
       
        a[middle]) left = middle + 1;        else return middle;    }    return -1;}int BinarySearch_R(int *a, const int x, const int left, const int right){    if(left<=right)    {        int middle = (left+right)/2;        if(x
        
         a[middle]) return BinarySearch_R(a,x,middle+1,right);        else return middle;    }    return -1;}
        
       
      

32.排列组合

#include 
      
       using namespace std;//字符，开始的下标，最后的下标 void Permutations(char *p,const int k,const int m){    //k的变换， Permutations(p,k+1,m)中的k+1赋值给了k     if(k==m)//已经到了最后一个，不需要递归     {        cout<<"ddddddddddddd"<
      

33.快速排序

#include 
      
       using namespace std;template
       
        void QuickSort(T *a, const int left, const int right){    if(left
        
         pivot);            if(i
        
       
      

34.约瑟夫问题

据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后，39个犹太人与Josephus以及他的朋友多到一个洞中，39个犹太人决定死也不要被敌人抓住，于是决定了一个自杀方式，41个人排成一个园圈，由第1个人开始报数，每报道第3个个就必须自杀，然后再由下一个重新报数，直到所有人自杀身亡为止。

然而Josephus和它的朋友安排在第16个和第31个为止，于是逃过了这场死亡游戏。

程序模拟给出了死亡游戏自杀顺序。

//n个人围圈报数，报m出列，最后剩下的是几号？#include 
      
       #include 
       
        typedef struct node{    int data;//存储了排列的序号。    struct node *next;}node;//创建循环链表node *create(int n){    node *p = NULL, *head;    head = (node*)malloc(sizeof (node ));    p = head;    node *s;    int i = 1;    if( 0 != n )    {        //尾后插入法        while( i <= n )        {            s = (node *)malloc(sizeof (node));            s->data = i++;    // 为循环链表初始化，第一个结点为1，第二个结点为2。            p->next = s;            p = s;        }        s->next = head->next;//最后一个节点指向第一个节点(不是头节点)    }    free(head);//删除头节点    return s->next ;//返回第一个节点}int main(){    int n = 41;    int m = 3;    int i;    node *p = create(n);    node *temp;    m %= n;   // m在这里是等于3    while (p != p->next )//链表剩下最后一个    {        for (i = 1; i < m-1; i++)//找到第一个节点        {            p = p->next ;//p指向第二节点        }        printf("%d->", p->next->data );//打印第三个节点的数值        temp = p->next ;                //删除第m个节点        p->next = temp->next ;        free(temp);        p = p->next ;//p是第四个节点    }    printf("%d\n", p->data );//打印最后一个    return 0;}