readme.txt

提供了rbtree ttree avltree list hashtable等常用容器的算法,代码经过uclinux + arm44b0平台验证

常用容器


///**
// * @brief 创建节点
// */
//static __INLINE__ size_t avltree_left_height(myavltree_node_t * node)
//{
//	assert(node);
//
//	if(NULL == node->base.left)
//		return 0;
//
//	return ((myavltree_node_t *)(node->base.left))->height;
//}
//
///**
// * @brief 创建节点
// */
//static __INLINE__ size_t avltree_right_height(myavltree_node_t * node)
//{
//	assert(node);
//
//	if(NULL == node->base.right)
//		return 0;
//
//	return ((myavltree_node_t *)(node->base.right))->height;
//}
//
///**
// * @brief 创建节点
// */
//static __INLINE__ size_t avltree_cal_height(myavltree_node_t * node)
//{
//	assert(node);
//
//	{
//		size_t l = avltree_left_height(node);
//		size_t r = avltree_right_height(node);
//
//		assert(l == r || (l + 1)== r || (r + 1) == l);
//
//		return (l > r)?(l + 1):(r + 1);
//	}
//}
//
///**
// * @brief 从node开始回溯,平衡受影响的路径,如果满足平衡条件且父节点没有长高,停止回溯
// */
//static __INLINE__ void avltree_balance(myavltree_t * avl_tree, myavltree_node_t * node)
//{
//	assert(avl_tree && node);
//
//	while(node)
//	{
//		size_t left_height = avltree_left_height(node);
//		size_t right_height = avltree_right_height(node);
//
//		if(left_height > right_height)
//		{
//			if(left_height - right_height <= 1)
//			{
//				/*
//				* 如果高度无变化,回溯调整结束
//				* 如果高度出现变化,则应继续
//				*/
//
//				size_t new_height = left_height + 1;
//
//				/*
//				* 高度可以不变
//				* 或者长高一层,或者变矮一层
//				* 不应出现其它情况
//				*/
//				assert(node->height == new_height || 1 + new_height == node->height ||
//					new_height - 1 == node->height);
//
//
//				if(new_height == node->height)
//				{
//					node->height = new_height;
//					break;
//				}
//				else 
//					node->height = new_height;
//			}
//			else
//			{
//				size_t left_lh = 0;
//				size_t left_rh = 0;
//
//				assert(left_height - right_height == 2);
//
//				/* 根据逻辑,此时左边不可能为空 */
//				assert(node->base.left);
//
//				left_lh = avltree_left_height((myavltree_node_t *)(node->base.left));
//				left_rh = avltree_right_height((myavltree_node_t *)(node->base.left));
//
//				/* 分支必满足avl规则 */
//				assert(((left_lh + 1) == left_rh) || ((left_rh + 1) == left_lh) || left_lh == left_rh);
//
//				/*
//				* 处理左子树比右子树高出两层的情况
//				* 根据树形状的不同,做相应的旋转,并更改parent
//				*/
//				if(left_lh < left_rh)
//				{
//					/*
//					* 情况3: 左子树的右分支比左分支高1层 (可以转化为情况1)
//					*      node               node
//					*      / \                / \
//					*     L   R              C   R
//					*    /\        -->      / \  
//					*   A  C               L   D 
//					*     / \             / \    
//					*    B   D           A   B
//					*/
//
//					/* 根据逻辑,以下条件必然成立 */
//					assert(node->base.left && node->base.left->right);
//
//					/* 作一次旋转,完成转化工作 */
//					__rotate_left((bstree_node_t **)&avl_tree->root, node->base.left->right);
//
//					/*
//					* 重新计算L与C的高度 从图看出A,B,D这三分支是不受旋转影响的
//					* L的高度减1
//					* C的高度加1
//					*/
//					assert(node->base.left);
//					assert(node->base.left->left);
//
//					((myavltree_node_t *)(node->base.left->left))->height --;
//					((myavltree_node_t *)(node->base.left))->height ++;
//
//					assert(avltree_left_height((myavltree_node_t *)(node->base.left->left)) + 1 == ((myavltree_node_t *)(node->base.left->left))->height ||
//						avltree_right_height((myavltree_node_t *)(node->base.left->left)) + 1 == ((myavltree_node_t *)(node->base.left->left))->height);
//					assert(avltree_left_height(((myavltree_node_t *)(node->base.left))) + 1 == ((myavltree_node_t *)(node->base.left))->height ||
//						avltree_right_height(((myavltree_node_t *)(node->base.left))) + 1 == ((myavltree_node_t *)(node->base.left))->height);
//
//					/* 重新计算left_lh与left_rh */
//					left_lh = avltree_left_height((myavltree_node_t *)node->base.left);
//					left_rh = avltree_right_height((myavltree_node_t *)node->base.left);
//				}
//
//				assert(left_lh >= left_rh);
//
//				/*
//				* 情况1:左子树的左分支比右分支高1层
//				*      node               L           
//				*      / \               / \
//				*     L   R             A   node
//				*    /\        -->     / \  / \
//				*   A  C              B   D C  R
//				*  / \
//				* B   D
//				*/
//
//				/*
//				* 情况2: 左子树的左右分支一样高 视同情况1 注意L此时长高了一层
//				*      node                  L
//				*      / \                  /  \
//				*     L   R                A     node
//				*    / \        -->       / \    /  \
//				*   A   C                B   D  C    R
//				*  / \ / \                     / \
//				* B  D E  F                   E   F
//				*/
//
//				/* 做一次旋转即可完成工作 */
//				__rotate_right((bstree_node_t **)&avl_tree->root, node->base.left);
//
//				/* 此时node重新指向L */
//				node = (myavltree_node_t *)node->base.parent;
//
//				assert(node && node->base.right);
//
//				((myavltree_node_t *)(node->base.right))->height = avltree_cal_height((myavltree_node_t *)node->base.right);
//				//if(left_lh == left_rh)
//				node->height = avltree_cal_height(node);
//				//else
//
//				/* 根据逻辑得出,此条件必成立 */
//				assert(node->height == (avltree_left_height(node) + 1) ||
//					node->height == (avltree_right_height(node) + 1) );
//
//				assert(avltree_left_height((myavltree_node_t *)(node->base.right)) + 1 == ((myavltree_node_t *)(node->base.right))->height ||
//					avltree_right_height((myavltree_node_t *)(node->base.right)) + 1 == ((myavltree_node_t *)(node->base.right))->height);
//			}
//		}
//		else/* left_height > right_height 对称的一种情况 */
//		{
//			if(right_height - left_height <= 1)
//			{
//				/*
//				* 如果高度无变化,回溯调整结束
//				* 如果高度出现变化,则应继续
//				*/
//
//				size_t new_height = right_height + 1;
//
//				/*
//				* 高度可以不变
//				* 或者长高一层,或者变矮一层
//				* 不应出现其它情况
//				*/
//				assert(node->height == new_height || 1 + new_height == node->height ||
//					new_height - 1 == node->height);
//
//
//				if(new_height == node->height)
//				{
//					node->height = new_height;
//					break;
//				}
//				else
//					node->height = new_height;
//			}
//			else
//			{
//				size_t right_lh = 0;
//				size_t right_rh = 0;
//
//				assert(right_height - left_height == 2);
//
//				/* 根据逻辑,此时左边不可能为空 */
//				assert(node->base.right);
//
//				right_lh = avltree_left_height((myavltree_node_t *)node->base.right);
//				right_rh = avltree_right_height((myavltree_node_t *)node->base.right);
//
//				/* 分支必满足avl规则 */
//				assert(((right_lh + 1) == right_rh) || ((right_rh + 1) == right_lh) || right_lh == right_rh);
//
//				/*
//				* 处理左子树比右子树高出两层的情况
//				* 根据树形状的不同,做相应的旋转,并更改parent
//				*/
//				if(right_rh < right_lh)
//				{
//					/*
//					* 情况3: 右子树的左分支比右分支高1层 (可以转化为情况1)
//					*      node               node
//					*      / \                / \
//					*     L   R              L   A
//					*         /\        -->     / \  
//					*        A  C               B  R 
//					*       / \                   / \    
//					*      B   D                 D   C