code01.cpp

常见算法的代码包

//===============================ATOI=============================

int atoi(const char *str)
{
	char isNeg = 0;
	int n = 0;
	assert(str != NULL);
	while(*str == ' ')
	{
		str++;
	}
	if(*str == '-')
	{
		str++; 
		isNeg = 1;
	}
	while((*str >= '0') && (*str <= '9'))
	{
		n = n * 10 + (*str++) - '0';
	}
	return isNeg ? -n : n;
}

//===============================ATOF=============================

double atof(const char* str) 
{ 
    double val = 0.0;
    double power = 1.0; 
    int sign = 0; 
    assert(NULL != str); 
    while (*str == ' ') 
    { 
        str++; 
    } 
    sign = (*str == '-') ? -1 : 1; 
    if ('-' == *str || '+' == *str) 
    { 
        str++; 
    } 
    while ((*str >= '0') && (*str <= '9')) 
    { 
        val = val * 10.0 + (*str++) - '0'; 
    } 
    if ('.' == *str) 
    { 
        str++; 
    } 
    while ((*str >= '0') && (*str <= '9')) 
    { 
        val = val * 10.0 + (*str++) - '0'; 
        power *= 10; 
    } 
    return sign*val/power; 
}

//===============================ITOA=============================

void itoa(int n, char *str)
{
	char *start = str;
	char isNeg = 0;
	char c;
	if(n < 0)
	{
		n *= -1;
		isNeg = 1;
	}
	do
	{
		*str++ = n % 10 + '0';
		n /= 10;
	}while(n);
	if(isNeg)
	{
		*str++ = '-';
	}
	*str-- = '\0';
	while(start < str)
	{
		c = *start;
		*start++ = *str;
		*str-- = c;
	}
}

//===========返回T在S中第POS个字符之后的位置(非KMP法)==================

int index(char *S, char *T, int pos)
{
	int LS = strlen(S);
	int LT = strlen(T);
	int i = pos;
	int j = 0;
	while(i < LS && j < LT)
	{
		if(S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	if(j == LT)
		return i - LT;
	else
		return -1;
}

//===============================KMP=============================

int next[LEN] = {0};

void getNext(char *T)
{
	int i = 0;
	int j = -1;
	int LT = strlen(T);
	next[0] = -1;
	while( i < LT )
	{
		if( j == -1 || T[i] == T[j] )
		{
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
}

int Index_KMP(char *S, char *T, int pos)
{
	int i = pos;
	int j = 0;
	int LS = strlen(S);
	int LT = strlen(T);
	getNext(T);
	while( i < LS && j < LT )
	{
		if( j == -1 || S[i] == T[j] )
		{
			i++;
			j++;
		}
		else 
			j = next[j];
	}
	if( j == LT ) 
		return ( i - LT);
	else
		return -1;
}

//===============================二叉树=============================

typedef struct BiTNode
{
	int data;
	struct BiTNode *lChild, *rChild;
}BiTNode, *BiTree;

void CreateBiTree(BiTree &T)  //先序建树
{
	int d;
	scanf("%d", &d);
	if (d == 0) 
		T = NULL;
	else
	{
		T = (BiTree)malloc(sizeof(BiTNode));
		if (!T)
			exit(1);
		T->data = d;
		CreateBiTree(T->lChild);
		CreateBiTree(T->rChild);
	}
}

int Depth(BinTreNode *T)  //树高
{
	int dL = 0, dR = 0;
	if(T==NULL) 
		return 0;

	else
	{
		dL = 1 + Depth(T->leftChild);
		dR = 1 + Depth(T->rightChild);
		return dL > dR ? dL : dR;		
	}
}


void PreOrderTraverse(BiTree T, void (*Visit)(int)) //先序递归
{
	if (T)
	{
		Visit(T->data);
		PreOrderTraverse(T->leftChild, Visit);
		PreOrderTraverse(T->rightChild, Visit);
	}
}

void preorder_nonrecursive(Bitree T)         /* 先序非递归 */
{
	initstack(S);
	push(S,T);                            /* 根指针进栈 */
    while( !stackEmpty(S) ) 
	{
		while( getTop(S,p) && p) 
		{                             /* 向左走到尽头 */
			visit(p);             /* 每向前走一步都访问当前结点 */
            push(S,p->lchild);
        }
       	pop(S,p);
        if( !stackEmpty(S) ) 
        {                              /* 向右走一步 */
	 		pop(S, p);
            push(S, p->rchild); 
        }
	}
}

void inorder_recursive(Bitree T)                /* 中序递归*/
{
	if (T) 
	{
		inorder_recursive(T->lchild);       
		visit(T);                        
		inorder_recursive(T->rchild);      
	}
}

void InOrderTraverse(BiTree T, void (*Visit)(int))   //中序非递归
{
	InitStack(S);
	push(S, T);
	while( !StackEmpty(S) )
	{
		while(GetTop(S,p) && p)
			push(S, p->lchild);
		pop(S, p);
		if( !StackEmpty(S) )
		{
			pop(S, p);
			Visit(p->data);
			push(S, p->rchild);
		}
	}
}

//后序非递归

typedef struct 
{
	BTNode *ptr;
	enum {0,1,2} mark;
}PMType;                                              /* 有mark域的结点指针类型 */

void postorder_nonrecursive(BiTree T)                 /* 后续非递归*/
{
	PMType a;
    initstack(S);                                 /* S的元素为PMType类型 */
    push (S, {T,0});                              /* 根结点入栈 */
    while( !stackEmpty(S) )  
    {
		pop(S, a);
		switch( a.mark )
		{
			case 0:
				push(S, {a.ptr,1});                   /* 修改mark域 */
 				if(a.ptr->lchild) 
					push(S, {a.ptr->lchild,0});   /* 访问左子树 */
                break;
            case 1:
                push(S, {a.ptr,2});                   /* 修改mark域 */
                if( a.ptr->rchild ) 
					push(S, {a.ptr->rchild,0});   /* 访问右子树 */
                break;
            case 2:
                visit(a.ptr);                	      /* 访问结点 */
        }
    }
}

//===============================图深度优先遍历=============================

bool visited[MAX];

void DFSTraverse(Graph G)
{
	for( v = 0; v < G.Vexnum; ++v)
		visited[v] = false;
	for( v = 0; v < G.Vexnum; ++v)
	{
		if( !visited[v] )
			DFS(G, v);
	}
}

void DFS(Graph G, int v)
{
	visited[v] = true;
	Visit(v);
	for( w = FirstAdjvex(G, v); w >= 0; w = NextAdjVex(G, v, w) )
	{
		if( !visited[w] )
			DFS(G, w);
	}
}


//===============================图广度优先遍历=============================

void BFSTraverse(Graph G)
{
	for(v = 0; v < G.vexnum; ++v)
		visited[v] = false;
	InitQueue(Q);
	for(v = 0; v < G.vexnum; ++v)
	{
		if(!visited[v])
		{
			visited[v] = true;
			Visit(v);
			EnQueue(Q, v);
			while(!QueueEmpty(Q))
			{
				DeQueue(Q, u);
				for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
				{
					if(!visited[w])
					{
						visited[w] = true;
						Visit(w);
						EnQueue(Q, w);
					}
				}
			}
		}
	}
}

//===============================二分查找=============================

int BinSearch(int key, int *list, int n)
{
	int low = 0;
	int high = n - 1;
	int mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(list[mid] < key)
			low = mid + 1;                  //!!!!!!!!!!!!!!!
		else if(list[mid] > key)
			high = mid - 1;
		else
			return mid;
	}
	return -1;
}

//===============================二叉排序树=============================

BiTree SearchBST(BiTree T, KeyType key)//查找成功，返回该元素指针
{
	if(!T || T->data == key)
		return T;
	else if( key < T->data)
		return SearchBST(T->lChild, key);
	else return SearchBST(T->rChild, key);
}


BiTree InsertTreeNode(BiTree T, int key)
{
	BiTree p = T;
	BiTree s = (BiTree)malloc(sizeof(BiTNode));
	s->data = key;
	s->lChild = s->rChild = NULL;
	if(!T)
	{
		T = s;
	}
	else
	{
		while(1)
		{
			if(key <= p->data)
			{
				if(p->lChild)
				{
					p = p->lChild;
				}
				else
				{
					p->lChild = s;
					break;
				}
			}
			else
			{
				if(p->rChild)
				{
					p = p->rChild;
				}
				else
				{
					p->rChild = s;
					break;
				}
			}
		}
	}
	return T;
}

//删除
/***************************************************************************************
在二叉查找树上删除一个结点时，要考虑三种情况：
	1 若待删除的结点p是叶子结点，则直接删除该结点；
	2 若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；
	3 若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s,用结点s的值代
      替结点p的值，然后删除结点s,结点s必属于上述1、2情况之一。。
***************************************************************************************/
int DeleteNode(BiTree *root, int e)
{
	BiTree p = *root;
	BiTree pp, s, c;
	while(p && p->data != e)
	{
		pp = p;
		if(e < p->data)
			p = p->lChild;
		else
			p = p->rChild;
	}
	if(!p)
		return 0;
	if(p->lChild && p->rChild)  //处理3
	{
		s = p->lChild;
		pp = p;
		while(s->rChild)
		{
			pp = s;
			s = s->rChild;
		}
		p->data = s->data;
		p = s;
	}
	if(p->lChild)              //处理1,2
		c = p->lChild;
	else
		c = p->rChild;
	
	if(p == *root)
		*root = c;
	else if(p == pp->lChild)
		pp->lChild = c;
	else
		pp->rChild = c;
	free(p);
	return 1;
}


BOOL SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)  //查找成功，p指向该元素结点，f指向其父结点
{
	if(!T)
	{
		p = f;
		return FALSE;
	}
	else if(key == T->data)
	{
		p = T;
		return TRUE;
	}
	else if(key < T->data)
		return SearchBST(T->lChild, key, T, p);
	else 
		return SearchBST(T->rChild, key, T, p);
}

BOOL InsertBST(BiTree &T, ElemType e) //不存在e,则插入e并返回True.
{
	if(!SearchBST(T, e, NULL, p)
	{
		s = (BiTree)malloc(sizeof(BitNode));
		s->data = e; s->lchild = s->rchild = NULL;
		if(!p)
			T = s;
		else if(e < p->data)
			p->lchild = s;
		else
			p->rchild = s;
		return True;
	}
	else
		return False;
}