void quickSort(int s[], int l, int r)  {      if (l< r)      {                int i = l, j = r, x = s[l];          while (i < j)          {              while(i < j && s[j]>= x) // 从右向左找第一个小于x的数                  j--;               if(i < j)                  s[i++] = s[j];              while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数                  i++;               if(i < j)                  s[j--] = s[i];          }          s[i] = x;          quickSort(s, l, i - 1); // 递归调用          quickSort(s, i + 1, r);      }  }

void bubble_sort(int a[ ], int n ){
  //冒泡排序    int i;    bool change;    //将a中n个数据序列重新排列成自小至大有序的整数序列    for (i=n-1, change=true; i>=1 && change; --i) {        change=false;        for (int j=0; j
   
    a[j+1]){                int temp=a[j];                a[j]=a[j+1];                a[j+1]=temp;                change=true;            }        }    }}//bubble_sort
   

void MergeList_Sq( SqList La, SqList Lb, SqList &Lc)//将数据元素按值非递减排列的顺序表La和Lb合并到顺序表Lc//Lc的元素也按值非递减排列{   pa=La.elem; pb=Lb.elem;    Lc.listsize =Lc.length =La.length+Lb.length;    pc= Lc.elem= (ElemType *)                                malloc(Lc.listsize*sizeof(ElemType));    if (!pc) exit(OVERFLOW);    pa_last= La.elem+La.length-1;   pb_last= Lb.elem+Lb.length-1;    while (pa<=pa_last && pb<=pb_last )  {        if (*pa<=*pb)  *pc++ = *pa++;        else  *pc++ = *pb++;    }    while (pa<=pa_last)  *pc++ = *pa++;    while (pb<=pb_last)  *pc++ = *pb++;}//MergeList_Sq

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){   pa= La->next;   pb= Lb->next;   Lc= pc= La;    while ( pa && pb ) {        if  ( pa->data <= pb->data ) {            pc->next= pa;   pc=pa;   pa= pa->next;        }        else  { pc->next= pb;   pc=pb;   pb= pb->next;  }    }    pc->next= pa? pa : pb  ;    free(Lb);}// MergeList_L

void   conversion(int N,  int  B)//对于非负十进制整数N，输出其等值的B进制数{    InitStack(S);                //初始化栈s           while (N)                      //从右向左产生B进制数的各位      {   Push(S,  N % B);     //数字，并将其进栈           N=N/B;       }       while (! StackEmpty(S))  //栈非空时退栈输出       {     Pop(S, e);             printf(e);        }}//conversion

void  hanoi (int n, char x,  char y, char z ){    if (n==1)         move (x, 1, z);  //出口条件:将编号1的圆盘从x移到z      else  {        hanoi(n-1, x, z, y); //将n-1个圆盘从x移到y上，z为辅助塔座        move (x，n，z);   //将编号n的圆盘从x移到z        hanoi (n-1,  y, x, z); //将n-1个圆盘从y移到z上，x为辅助塔座     }}//hanoi

int Index(SString S,  SString T, int pos)   //返回子串T在主串S中从第pos个字符开始的位置。   //若不存在，返回值为0。1posStrLength(S)     {    i=pos;j=1;     //设定主串、子串字符开始比较的位置           while  ( i<=S[0]  &&   j<=T[0] )           {                     if  (S.ch[i]== T.ch[j] )               {    i++;   j++;  }             //继续比较后继字符               else               {    i=i-j+2;   j=1;   }      //回退，重新开始比较           }           if  ( j> T[0] )                  return    i-T[0] ;   //匹配成功           else                  return 0;      } // Index

int KMP(string str,int slen,string ptr,int plen,vector
   
     next){        int i=0,j=0;        while(i
    
     

二叉树先序遍历算法

//递归Status PreOrderTraverse1(BiTree T){     if  (T)  {           if ( visit(T->data) ) {               if (T->lchild)                   if  ( ! PreOrderTraverse1(T->lchild) ) return ERROR;               if (T->rchild)                  if  (! PreOrderTraverse1(T->rchild) )  return ERROR;               return OK;           }else return ERROR;       }else return OK; } //PreOrderTraverse1//非递归Status  PreOrderTraverse2(BiTree T){  IniStack(S);    p=T ;    Push(S, NULL);    while ( p )  {            if  ( !visit(p->data) )                 return ERROR;            if  ( p->rchild )                 Push(S, p->rchild);             if  ( p->lchild )           p=p->lchild;             else                 Pop(S, p);     }     return OK;} //PreOrderTraverse2

二叉树中序遍历算法

//递归Status  InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){   if  (T){           if  ( InOrderTraverse(T->lchild, Visit) )            if ( Visit(T->data) )                if   ( InOrderTraverse(T->rchild,Visit) )                      return OK;        return ERROR;    }else         return OK; } //InOrderTraverse//非递归Status InOrderTranverse(BiTree T){    InitStack(S);p = T;    while (p || ! StackEmpty (S)) {        if (p) {            Push(S,p);               p=p->lchild;         }else {            pop(S, p);                if ( !Visit(p->data) )                return ERROR;             p=p->rchild;        }    }    return OK;}// InOrderTraverse

二叉树后序遍历

//递归Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){    if  (T)    {           if  ( PostOrderTraverse(T->lchild, Visit) )            if   ( PostOrderTraverse(T->rchild, Visit) )                if ( Visit(T->data) )                        return OK;        return ERROR;    }else         return OK; } //PostOrderTraverse//非递归Status PostOrderTraverse1(BiTree T){   InitStack(S);  Push (S,{T,0});   //根结点(指针、mark)入栈    while(!StackEmpty(S))  {    Pop(S,a);        switch(a.mark){        case 0:   Push(S,{a.p, 1}); //修改mark域            if(a.p->lchild) Push(S,{a.p->lchild,0}); //访问左子树                       break;        case 1:    Push(S,{a.p,2}); //修改mark域                       if(a.p->rchild) Push(S,{a.p->rchild,0}); //访问右子树                       break;        case 2:    if  (!visit( a.p->data)) return ERROR;            }    }      return OK;}//PostOrderTraverse1

二叉树按层次遍历算法

Status  LevelOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){   if (T)  {             InitQueue(Q);             EnQueue(Q, T);         //根结点的指针T入队列             while ( ! QueueEmpty (Q) )             {    DeQueue(Q, p);  //从队头取一个指针                   if ( !Visit(p->data) )   return ERROR;                    if (p->lchild)  EnQueue(Q, p->lchild);                   if (p->rchild)  EnQueue(Q, p->rchild);             }     }     return OK;} //LevelOrderTraverse

链表的逆序

//方法一/**依次1.卸载headPtr指向链表的头结点，由currentPtr指向;2. currentPtr指向结点组装到新链表中作为头结点;**/listNode* reverseList(listNode* headPtr){    listNode* newHeadPtr=NULL,currentPtr=NULL;    while(headPtr!=NULL){
  //卸载headPtr指向链表的头结点，由currentPtr指向          currentPtr=headPtr;         headPtr=headPtr->nextPtr;         // currentPtr指向结点组装到新链表中作为头结点         if(newHeadPtr==NULL){               newHeadPtr= currentPtr;               newHeadPtr >nextPtr=NULL;         }         else{               currentPtr->nextPtr=newHeadPtr;               newHeadPtr=currentPtr;         }    }      return  newHeadPtr;    }//方法二listNode* reverseList(listNode* headPtr){    listNode* previousPtr,currentPtr,posteriorPtr;    previousPtr= headPtr;    currentPtr=previousPtr->nextPtr;    previousPtr->nextPtr=NULL;//很重要，反向后的链表的结束位置    while(currentPtr!=NULL) {        posteriorPtr=currentPtr->nextPtr;        currentPtr->nextPtr=previousPtr;/*连接*/        previousPtr=currentPtr;        currentPtr=posteriorPtr;    }            return previousPtr;/*返回头结点*/ }//方法三listNode* reverseList(listNode* headPtr){    listNode* lastPtr=NULL,currentPtr=NULL;    if(headPtr->nextPtr==NULL){
  //若是最后一个结点，则直接返回        return headPtr;    }                               else{           /*1.当前链表头结点从链表中拆除，由lastPtr指向，将成为逆序后的链表尾结点。headPtr指向下一结点*/        lastPtr=headPtr;         headPtr=headPtr->nextPtr;        lastPtr->nextPtr=NULL;              /*2.递归调用，将headPtr指向的链表逆序，由newHeadPtr指向     */        headPtr=reverseList(headPtr);     /*3. 将lastPtr指向结点链接到newHeadPtr指向链表的尾结点之后*/        currentPtr=headPtr;        while(currentPtr->nextPtr!=NULL)//若不是最后结点            currentPtr=currentPtr->nextPtr;                currentPtr->nextPtr=lastPtr;   //将尾结点链接到链表             return  headPtr;   }    }

求第K大的数

// Find the max subarray no more than K     int best_cumulative_sum(vector
   
     array,int K){        set
    
      cumset;        cumset.insert(0);        int best=0,cum=0;        for(auto num:array){            cum+=num;            auto it=cumset.upper_bound(cum-K);            if(it!=cumset.end())                best=max(best,cum-*it);            cumset.insert(cum);        }        return best;    }
    
   

字典树的构建、查找

typedef struct Tree {    int count;//子树的个数    struct Tree *child[MAX_CHILD];//子树的地址} Node, *Trie_node;Node *CreateTrie() {
  //创建trie节点树    Node *node = (Node *) malloc(sizeof(Node));    memset(node, 0, sizeof(Node));    return node;}void insert_node(Trie_node root, char *str) {
  //trie树插入结点    if (root == NULL || *str == '\0')        return;    Node *t = root;    char *p = str;    while (*p != '\0') {        if (t->child[*p - 'a'] == NULL) {            Node *tmp = CreateTrie();            t->child[*p - 'a'] = tmp;        }        t = t->child[*p - 'a'];        t->count++;        p++;    }}int search_str(Trie_node root, char *str) {
  //查找在该trie树中以待查串为前缀的单词个数    if (NULL == root || *str == '\0')        return 0;    char *p = str;    Node *t = root;    while (*p != '\0') {        t = t->child[*p - 'a'];        if (t != NULL)            p++;        else            return 0;    }    if (*p == '\0')        return t->count;}

堆排序

void HeapSort(HeapType &H){    for (i = H. length / 2; i > 0; i--)           HeapAdjust(H, i, H.length);    for (i=H.length; i>1; i--) {
           H.r[1]←→H.r[i];        HeapAdjust(H, 1, i-1);    }}//HeapSortvoid HeapAdjust(HeapType &H, int s, int m){      rc=H.r[s];    for (j=2*s;j<=m;j*=2) {
           if (j
   
     H.r[j].key)             break;        H.r[s] = H.r[j];          s=j;    }    H.r[s]=rc;}//HeapAdjust
   

朴素的模式匹配算法

int Index(SString S,  SString T, int pos){         //返回子串T在主串S中从第pos个字符开始的位置。         //若不存在，返回值为0。         i=pos;         j=1;//设定主串、子串字符开始比较的位置         while(i<=S[0]&&j<=T[0]){             if(S.ch[i]==T.ch[j]){                 i++;                 j++;             }//继续比较后继字符             else{                 i=i-j+2;                 j=1;             }//回退，重新开始比较         }         if(j>T[0])             return i-T[0];//匹配成功         else            return 0;      } // Index