常用数据结构和算法汇集

Queue

/////////////////////////////////////////////////////////////////

static int q[1024*1024],q_s=0, q_e=0;

static void q_init() {q_s=0;q_e=0;}

static void q_in(int v){q[q_e++] = v;}

static int  q_out(void){return q[q_s++];}

static bool q_empty(void){return q_s == q_e;}

/////////////////////////////////////////////////////////////////

Stack

/////////////////////////////////////////////////////////////////

static int s[1024*1024],s_s=0, s_e=0;

static void s_init() {s_s=0;s_e=0;}

static void s_push(int v){s[s_e++] = v;}

static int  s_pop(void){return s[--s_e];}

static bool s_empty(void){return s_s == s_e;}

/////////////////////////////////////////////////////////////////

QuickSort

/////////////////////////////////////////////////////////////////

static void swap(int *a, int i, int j){

   int t;

   t = a[i];

   a[i] = a[j];

   a[j] = t;

}

static void quicksort(int *a, int n)

{

    if(n>1)

{

        int p=0,j;

        for(j=1;j<n;j++)

            if(a[j]<a[0])

                swap(a,++p,j);

        swap(a,0,p);

        quicksort(a,p);

        quicksort(a+p+1,n-p-1);

    }

}

/////////////////////////////////////////////////////////////////

Tree Traverse

/////////////////////////////////////////////////////////////////

static void preOrder(BinTree *root)    
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

static void inOrder(BinTree *root)      
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }    
}

static void HierarchyBiTree(BiTree Root)
{
	LinkQueue *Q;    
	InitQueue(Q); 

	if (Root == NULL) return ; 
	BiNode *p = Root;         
	Visit(p->data);    
	if (p->lchild)
	EnQueue(Q, p->lchild);  
	if (p->rchild)
	EnQueue(Q, p->rchild);

	while (!QueueEmpty(Q)) 
	{                
	    DeQueue(Q, p); 
	    Visit(p->data);

	    if (p->lchild)
	    EnQueue(Q, p->lchild); 
	    if (p->rchild)
	    EnQueue(Q, p->rchild);
	}

	DestroyQueue(Q);
	return;
}

/////////////////////////////////////////////////////////////////