快速排序
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<i; ++j){
if(a[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十进制转B进制
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);
}
}//conversionHanoi塔问题
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。1posStrLength(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
KMP算法
int KMP(string str,int slen,string ptr,int plen,vector<int> next){
int i=0,j=0;
while(i<slen&&j<plen){
if(str[i]==ptr[j]){
i++;j++;
}else{
if(j==0)
i++;
else
j= next[j-1]+1;
}
}
return (j== plen)?(i-plen):-1;
}//KMP
vector<int> calNext(string str){
int size=str.size(),i=0,k=-1,end=size-1;//k=next[i]
vector<int> next(size,-1);
while (i<end){
while (k!=-1&&str[k]!=str[i])
k=next[k];
k++;
i++;
next[i]=k;
}
return next;
}
vector<int> calNextval(string str){
int size=str.size(),i=0,k=-1,end=size-1;//k=next[i]
vector<int> nextval(size,-1);
while (i<end){
while (k!=-1&&str[k]!=str[i])
k=nextval[k];
k++;
i++;
if(str[k]==str[i])
nextval[i]=nextval[k];
else
nextval[i]=k;
}
return nextval;
}
二叉树先序遍历算法
//递归
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大的数
思路：快速排序。
主要思想是找一个“轴”节点，将数列交换变成两部分，一部分全都小于等于“轴”。另一部分全都大于等于“轴”，然后对两部分 递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的“较大”那一部分的数的个数j正好是n，不也就完成了在 N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果j>n，则最大的n个数肯定在这j个数中，则问题变成在这j 个数中找出n个最大的数；否则如果j
// Find the max subarray no more than K
int best_cumulative_sum(vector<int> array,int K){
set<int> 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);
}
}//HeapSort
void HeapAdjust(HeapType &H, int s, int m){
rc=H.r[s];
for (j=2*s;j<=m;j*=2) {
if (j<m && H.r[j].key < H.r[j+1].key)
j++;
if (rc.key > 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