数算示例程序

顺序字典的二分查找

int BinSearch(SeqDictionary *pdic, KeyType key, int *pos){
	int low,mid,high;
	low = 0; high = pdic->n - 1;
	while(low <= high){ //注意这里的判断
		mid = (low + high) / 2; //注意中间位置
		if(key < pdic->elem[mid].key){
			high = mid - 1; //注意边界变化
		}else if(key > pdic->elem[mid].key){
			low = mid + 1; // 注意边界变化
		}else{
			*pos = mid;
			return true;
		}
	}
	*pos = low; //它“应该在”的位置,用于后续插入
	return false;
}

二叉树

二叉树二叉链表结构定义

#define M 100
struct BinTreeNode
{
	DataType info;                        //数据域
	struct BinTreeNode *llink;      //指向左孩子
	struct BinTreeNode *rlink;     //指向右孩子
};
typedef struct BinTreeNode *PBinTreeNode;

前根遍历二叉树非递归算法

从根开始，沿左子树一直走到末端为止，在走的过程中访问所遇结点，并依次将所遇结点的非空右孩子进栈。当左子树结点全处理完后，从栈顶退出某结点的右孩子，此时该结点的左子树已经遍历完，再按照上述过程遍历结点的右子树，如此重复直到栈空为止。

void PreOrder(PBinTreeNode t)
{
	int top = 0;                                 //栈顶指示器
	PBinTreeNode p, S[M];             //栈中存放各个右子树根结点
	
	p = t;
	do
	{    
		while (p != NULL)
		{
			visit(p->info);                        //访问根结点
			if (p->rlink != NULL)       
			{    S[top++] = p->rlink;    }  //右子树根结点进栈
			p = p->llink;                          //继续搜索p的左子树 
		}
		if (top >= 0)    p = S[--top];          //右子树根结点出栈，转到搜索右子树
	} while (top >= 0)
}

中根遍历二叉树非递归算法

与先根遍历基本类同，只是在沿左分支（左子树）向前搜索过程中将遇到的结点进栈，待遍历完左子树后，从栈顶退出结点并访问，然后再遍历右子树。

void InOrder(PBinTreeNode t)
{   
	int top=0;                            //栈顶指示器
	PBinTreeNode p, S[M];      //控制栈
	p = t;
	do
	{    
		while (p != NULL)
		{
			S[top++] = p;         //所遇结点p进栈
			p = p->llink;           //继续搜索p的左子树
		}
		if ( top >= 0)
		{    
			p = S[--top];          //出栈，栈顶结点赋p
			visit(p->info);       //访问根结点
			p = p->rlink;         //继续搜索右子树 
		}
	} while ( top >= 0)
}

后根遍历二叉树非递归算法

使用栈实现后根遍历要比先、中根遍历复杂。在后根遍历中，当搜索指针指向某个根结点时，不能马上进行访问，而先要遍历左子树，所以要求根结点进栈保存。当遍历完左子树后，再次搜索到该结点时，还不能进行访问，还要遍历其右子树。所以，需要再次将该结点进栈保存。为了区别同一结点的两次入栈，需要一个特别的标志：1表示该结点首次进栈[遍历左子树前入栈]，2表示第二次进栈[遍历右子树前入栈]。设立两个栈，一个栈s1[M]用于存放结点，一个s2[M]栈用于存放结点进栈标志。

void PostOrder( PBinTreeNode t)
{   int S2[M], top = 0, b;            //结点进栈标志栈
	PBinTreeNode p, S1[M];        //结点栈
　
	p = t;
	do
	{    
		while (p != NULL)
		{
			S1[top] = p;
			S2[top++] = 1;            //p结点首次入栈
			p = p->llink;
		}                                     //遍历左子树
		if (top > 0)
		{  
		   b = S2[--top];
			 p =S1[top];
			 if (b == 1)
			 {  
				S1[top] = p;
				  S2[top++] = 2;        //p结点第二次入栈
				  p = p->rlink;
			 }                                 //遍历p的右子树
			 else if (b == 2)
			 {   
				visit(p->info);       //访问根结点
				  p = NULL;
			 }
		}
	} while (top > 0)
}