`
lovnet
  • 浏览: 6671809 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

《多任务下的数据结构与算法》一书中的红黑树的测试代码,供读者参考!

阅读更多

以下是《多任务下的数据结构与算法》一书中的红黑树的测试代码,供读者参考!

出书时本想将测试代码放到光盘里去,但认为测试代码写得草率,不够正规,觉得不好意思,就没有放上去。

考虑到读者可能会使用这些代码,先贴一个测试代码供参考,读者要使用的话可以在此测试代码基础上做进一步完善测试用例,增加测试代码,做更充分的测试。由于测试代码量较大,无法全部在博客上贴出,只好先贴一部分。
如果发现有遗漏的用例请贴上来共享给大家参考。

#include <windows.h>
#include <stdio.h>
#include "CapiGlobal.h"
#include "BinTree.h"
#include "RBTree.h"

void DRV_RBTree_Create(INT i);
void DRV_RBTree_Destroy(INT i);
void DRV_RBTree_Insert(INT i);
void DRV_RBTree_Delete(INT i);
void DRV_RBTree_Find(UINT i);

void Test_RBTree()
{
int i;
for ( i = 1; i < 50; i++ )
{
DRV_RBTree_Create(i);
DRV_RBTree_Destroy(i);
DRV_RBTree_Insert(i);
DRV_RBTree_Delete(i);
DRV_RBTree_Find(i);
}
}

void DRV_RBTree_Create(INT i)
{
RBTREE *pTree = NULL;
switch( i )
{
case 1:
pTree = RBTree_Create();
if ( pTree == NULL
|| pTree->pCursor != NULL
|| pTree->pRoot != NULL
|| pTree->uNodeCount != 0 )
{
printf("RBTree_Create() 测试用例1失败\n");
}
break;
default:
break;
}
RBTree_Destroy(pTree, free);
return;
}

void DRV_RBTree_Destroy(INT i)
{
RBTREE *pTree = RBTree_Create();
switch( i )
{
case 1:
RBTree_Destroy(pTree, free);
break;
case 2:
RBTree_Destroy(pTree, NULL);
break;
case 3:
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Destroy(pTree, free);
break;
case 4:
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Destroy(pTree, free);
break;
case 5:
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("18"), StrCompare);
RBTree_Insert(pTree, strdup("19"), StrCompare);
RBTree_Destroy(pTree, free);
break;
default:
break;
}
return;
}

void DRV_RBTree_Insert(INT i)
{
RBTREE *pTree = NULL;
pTree = RBTree_Create();
switch( i )
{
case 1: /* 插入1个节点的情况 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& pTree->pRoot->pLeft == NULL
&& pTree->pRoot->pRight == NULL
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->uNodeCount == 1
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例1, 插入1个节点失败\n");
}
break;
case 2: /* 插入两个节点的情况 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& pTree->pRoot->pRight == NULL
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->uNodeCount == 2
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例2, 插入2个节点失败\n");
}
break;
case 3: /* 插入3个节点的情况 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "22") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 3
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例3, 插入3个节点失败\n");
}
break;
case 4: /* LLr型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("10"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "10") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 4
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例4, LLr型失败\n");
}
break;
case 5: /* LLb型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("10"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "10") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "20") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 3
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例5, LLb型失败\n");
}
break;
case 6: /* LRb型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "17") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "20") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 3
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例6, LRb型失败\n");
}
break;
case 7: /* LRr型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "17") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 4
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例7, LRr型失败\n");
}
break;
case 8: /* LRr型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
RBTree_Insert(pTree, strdup("13"), StrCompare);
RBTree_Insert(pTree, strdup("14"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "17") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "13") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pRight->pData), "14") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->uNodeCount == 6
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例8, LRr型失败\n");
}
break;
case 9: /* LRr型和LLb型复合型*/
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
RBTree_Insert(pTree, strdup("13"), StrCompare);
RBTree_Insert(pTree, strdup("14"), StrCompare);
RBTree_Insert(pTree, strdup("10"), StrCompare);
RBTree_Insert(pTree, strdup("12"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "13") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "14") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "10") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pRight->pData), "12") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pData), "17") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pRight->pData), "22") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->uNodeCount == 8
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例9, LRr型和LLb型复合型失败\n");
}
break;
case 10: /* LLr型和LRb型复合型*/
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("13"), StrCompare);
RBTree_Insert(pTree, strdup("18"), StrCompare);
RBTree_Insert(pTree, strdup("11"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
RBTree_Insert(pTree, strdup("19"), StrCompare);
RBTree_Insert(pTree, strdup("16"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "18") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "17") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "13") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pLeft->pData), "11") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pLeft->pData), "16") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pData), "19") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pRight->pData), "22") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pRight->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->uNodeCount == 9
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例10, LLr型和LRb型复合型失败\n");
}
break;
case 11: /* LRb型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("13"), StrCompare);
RBTree_Insert(pTree, strdup("18"), StrCompare);
RBTree_Insert(pTree, strdup("11"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
RBTree_Insert(pTree, strdup("19"), StrCompare);
RBTree_Insert(pTree, strdup("16"), StrCompare);
RBTree_Insert(pTree, strdup("12"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "18") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "17") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "12") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pLeft->pData), "11") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pLeft->pData), "16") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pData), "19") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pRight->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pRight->pData), "13") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pRight->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pLeft->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->uNodeCount == 10
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例11, LRb型失败\n");
}
break;
case 12: /* RLr型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("25"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "25") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pData), "22") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 4
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例12, RLr型失败\n");
}
break;
case 13: /* RLb型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("25"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "25") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pLeft == NULL
&& pTree->pRoot->pRight->pRight == NULL
&& pTree->uNodeCount == 3
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例13, RLb型失败\n");
}
break;
case 14: /* RRb型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("25"), StrCompare);
RBTree_Insert(pTree, strdup("27"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "25") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "27") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pLeft == NULL
&& pTree->pRoot->pLeft->pRight == NULL
&& pTree->uNodeCount == 3
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例14, RRb型失败\n");
}
break;
case 15: /* RRr型 */
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("25"), StrCompare);
RBTree_Insert(pTree, strdup("27"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "25") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pRight->pData), "27") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pLeft == NULL
&& pTree->pRoot->pLeft->pRight == NULL
&& pTree->uNodeCount == 4
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例15, RRr型失败\n");
}
break;
case 16: /* RRr型和RLb型复合型*/
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("25"), StrCompare);
RBTree_Insert(pTree, strdup("27"), StrCompare);
RBTree_Insert(pTree, strdup("22"), StrCompare);
RBTree_Insert(pTree, strdup("21"), StrCompare);
RBTree_Insert(pTree, strdup("24"), StrCompare);
RBTree_Insert(pTree, strdup("23"), StrCompare);
if ( strcmp((char *)(pTree->pRoot->pData), "22") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pData), "20") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pData), "25") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pRight->pData), "21") == 0
&& strcmp((char *)(pTree->pRoot->pLeft->pLeft->pData), "15") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pLeft->pData), "23") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pLeft->pData), "24") == 0
&& strcmp((char *)(pTree->pRoot->pRight->pRight->pData), "27") == 0
&& pTree->pRoot->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pLeft->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pLeft->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pLeft->pLeft->nMagic == RBTREE_COLOR_RED
&& pTree->pRoot->pRight->pLeft->nMagic == RBTREE_COLOR_BLACK
&& pTree->pRoot->pRight->pRight->nMagic == RBTREE_COLOR_BLACK
&& pTree->uNodeCount == 8
&& pTree->pCursor == NULL )
{
}
else
{
printf("RBTree_Insert() 测试用例16, RRr型和RLb型复合型失败\n");
}
break;
default:
break;
}
BinTree_CheckParent(pTree->pRoot);
if ( pTree->pRoot != NULL )
{
if (pTree->pRoot->pParent != NULL )
{
printf( "Root Node's Parent Node is not NULL\n" );
}
}
RBTree_Destroy(pTree, free);
return;
}


RBTREE * BuildDeleteTestCase()
{
RBTREE *pTree;
pTree = RBTree_Create();
if ( pTree != NULL )
{
BinTree_Insert(&(pTree->pRoot), strdup("50"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("30"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("70"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("20"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("40"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("60"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("90"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("35"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("45"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("32"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("38"), StrCompare, RBTREE_COLOR_RED);
pTree->uNodeCount = 11;
pTree->pCursor = NULL;
}

return pTree;
}


RBTREE * BuildDeleteTestCase4()
{
RBTREE *pTree;
pTree = RBTree_Create();
if ( pTree != NULL )
{
BinTree_Insert(&(pTree->pRoot), strdup("30"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("20"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("40"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("35"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("45"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("32"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("38"), StrCompare, RBTREE_COLOR_RED);
pTree->uNodeCount = 7;
pTree->pCursor = NULL;
}

return pTree;
}

RBTREE * BuildDeleteTestCase5()
{
RBTREE *pTree;
pTree = RBTree_Create();
if ( pTree != NULL )
{
BinTree_Insert(&(pTree->pRoot), strdup("30"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("20"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("40"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("15"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("25"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("22"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("28"), StrCompare, RBTREE_COLOR_RED);
pTree->uNodeCount = 7;
pTree->pCursor = NULL;
}

return pTree;
}

RBTREE * BuildDeleteTestCase2()
{
RBTREE *pTree;
pTree = RBTree_Create();
if ( pTree != NULL )
{
BinTree_Insert(&(pTree->pRoot), strdup("50"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("30"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("70"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("20"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("40"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("60"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("90"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("15"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("25"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("22"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("28"), StrCompare, RBTREE_COLOR_RED);
pTree->uNodeCount = 11;
pTree->pCursor = NULL;
}

return pTree;
}

RBTREE * BuildDeleteTestCase3()
{
RBTREE *pTree;
pTree = RBTree_Create();
if ( pTree != NULL )
{
BinTree_Insert(&(pTree->pRoot), strdup("50"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("30"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("70"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("20"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("40"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("60"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("90"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("10"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("25"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("35"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("45"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("55"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("65"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("80"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("95"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("32"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("38"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("42"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("48"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("62"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("85"), StrCompare, RBTREE_COLOR_RED);
BinTree_Insert(&(pTree->pRoot), strdup("31"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("33"), StrCompare, RBTREE_COLOR_BLACK);
BinTree_Insert(&(pTree->pRoot), strdup("36"), StrCompare, RBTREE_COLOR_RED);
pTree->uNodeCount = 24;
pTree->pCursor = NULL;
}

return pTree;
}

INT ChangeNode(RBTREE *pTree, char *pSrcData, char *pTagData, INT nMagic = -1)
{
RBTREENODE *pNode;


pNode = pTree->pRoot;

while ( pNode != NULL )
{
INT nRet = strcmp((char *)pNode->pData, pSrcData);
if ( nRet < 0 )
{
pNode = pNode->pRight;
}
else if ( nRet > 0 )
{
pNode = pNode->pLeft;
}
else
{
if ( nMagic != -1 )
{
pNode->nMagic = nMagic;
}
free((char *)(pNode->pData));

if ( pTagData != NULL )
{
pNode->pData = (char *)strdup(pTagData);
}
else
{
if ( pNode->pParent != NULL )
{
if ( pNode == pNode->pParent->pLeft )
{
pNode->pParent->pLeft = NULL;
}
else
{
pNode->pParent->pRight = NULL;
}
}
free(pNode);
pTree->uNodeCount -= 1;
}

return 1;

}
}
return 0;
}

INT CompareRBTree(RBTREENODE *pSrcNode, RBTREENODE *pTagNode)
{
if ( pSrcNode == NULL )
{
if ( pTagNode == NULL )
{
return 1;
}

return 0;
}

if ( strcmp((char *)(pSrcNode->pData), (char *)(pTagNode->pData)) == 0
&& pSrcNode->nMagic == pTagNode->nMagic )
{
if ( CompareRBTree(pSrcNode->pLeft, pTagNode->pLeft) == 1 )
{
if ( CompareRBTree(pSrcNode->pRight, pTagNode->pRight) == 1 )
{
return 1;
}
}
return 0;
}
else
{
return 0;
}
}

void DRV_RBTree_Delete(INT i)
{
INT nRet;
BINTREEBASENODE *pNode;
RBTREE *pTree1;
RBTREE *pTree2;
if ( i < 6 )
{
pTree1 = BuildDeleteTestCase();
pTree2 = BuildDeleteTestCase();
}
else if ( i < 20 )
{
pTree1 = BuildDeleteTestCase2();
pTree2 = BuildDeleteTestCase2();
}
else if ( i < 26 )
{
pTree1 = BuildDeleteTestCase3();
pTree2 = BuildDeleteTestCase3();
}
else if ( i < 38 )
{
pTree1 = RBTree_Create();
pTree2 = RBTree_Create();
}
else if ( i < 46 )
{
pTree1 = BuildDeleteTestCase4();
pTree2 = BuildDeleteTestCase4();
}
else
{
pTree1 = BuildDeleteTestCase5();
pTree2 = BuildDeleteTestCase5();
}
switch( i )
{
case 1:

RBTree_Delete(pTree1, "32", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例1,删除红色节点失败\n");
}
break;
case 2: /* Lr-br型 */

RBTree_Delete(pTree1, "32", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "35", "38");
ChangeNode(pTree2, "30", "35");
ChangeNode(pTree2, "20", "30");


if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例2,Lr-br型失败\n");
}
break;
case 3: /* Lr-rb型 */

RBTree_Delete(pTree1, "38", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "30", "32");
ChangeNode(pTree2, "20", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例3,Lr-rb型失败\n");
}
break;
case 4: /* Lr-rr型 */

RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "30", "32");
ChangeNode(pTree2, "20", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例4,Lr-rr型失败\n");
}
break;
case 5: /* Lr-bb型 */

RBTree_Delete(pTree1, "32", StrCompare, free);
RBTree_Delete(pTree1, "38", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "35", NULL);
ChangeNode(pTree2, "45", NULL);

ChangeNode(pTree2, "40", "45", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "30", "40");
ChangeNode(pTree2, "20", "30");

BinTree_Insert(&(pTree2->pRoot), strdup("35"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 8
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例5,Lr-bb型失败\n");
}
break;
case 6: /* Rr-rr型 */

RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "30", "28");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例6,Rr-rr型失败\n");
}
break;
case 7: /* Rr-rb型 */

RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "25", "22");
ChangeNode(pTree2, "30", "25");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例6,Rr-rb型失败\n");
}
break;
case 8: /* Rr-br型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "30", "28");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例8,Rr-br型失败\n");
}
break;
case 9: /* Rr-bb型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "25", NULL);
ChangeNode(pTree2, "15", NULL);
ChangeNode(pTree2, "20", "15", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "30", "20");
ChangeNode(pTree2, "40", "30");
BinTree_Insert(&(pTree2->pRoot), strdup("25"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 8
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例9,Rr-bb型失败\n");
}
break;
case 10: /* Lb-rr型 */

RBTree_Delete(pTree1, "15", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "20", "22");
ChangeNode(pTree2, "15", "20");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例10,Lb-rr型失败\n");
}
break;
case 11: /* Lb-rb型 */

RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "15", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "20", "22");
ChangeNode(pTree2, "15", "20");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例11,Lb-rb型失败\n");
}
break;
case 12: /* Lb-br型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "15", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "25", "28");
ChangeNode(pTree2, "20", "25");
ChangeNode(pTree2, "15", "20");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例12,Lb-br型失败\n");
}
break;
case 13: /* Lb-bb型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "15", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "25", "25", RBTREE_COLOR_RED);
ChangeNode(pTree2, "20", "20", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "15", NULL);
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 8
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例13,Lb-bb型失败\n");
}
break;
case 14: /* Lb-bb型和Rb-bb复合型 */

RBTree_Delete(pTree1, "60", StrCompare, free);

BinTree_RotateRight(pTree2->pRoot, &(pTree2->pRoot));
ChangeNode(pTree2, "60", NULL);
ChangeNode(pTree2, "20", "20",RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "90", "90", RBTREE_COLOR_RED);
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例14,Lb-bb型和Rb-bb复合型失败\n");
}
break;
case 15: /* Rb-bb型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "25", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "25", NULL);
ChangeNode(pTree2, "15", "15",RBTREE_COLOR_RED);
ChangeNode(pTree2, "20", "20", RBTREE_COLOR_BLACK);
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 8
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例15,Rb-bb型失败\n");
}
break;
case 16: /* Rb-rr型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
BinTree_Insert(&(pTree1->pRoot), strdup("55"), StrCompare, RBTREE_COLOR_RED);
pTree1->uNodeCount += 1;
BinTree_Insert(&(pTree1->pRoot), strdup("65"), StrCompare, RBTREE_COLOR_RED);
pTree1->uNodeCount += 1;
RBTree_Delete(pTree1, "90", StrCompare, free);

BinTree_Insert(&(pTree2->pRoot), strdup("55"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
BinTree_Insert(&(pTree2->pRoot), strdup("65"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);

ChangeNode(pTree2, "65", NULL);
ChangeNode(pTree2, "90", "70");
ChangeNode(pTree2, "70", "65");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 10
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例16,Rb-rr型失败\n");
}
break;
case 17: /* Rb-br型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
BinTree_Insert(&(pTree1->pRoot), strdup("65"), StrCompare, RBTREE_COLOR_RED);
pTree1->uNodeCount += 1;
RBTree_Delete(pTree1, "90", StrCompare, free);

BinTree_Insert(&(pTree2->pRoot), strdup("65"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);

ChangeNode(pTree2, "65", NULL);
ChangeNode(pTree2, "70", "65");
ChangeNode(pTree2, "90", "70");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例17,Rb-br型失败\n");
}
break;
case 18: /* Rb-rb型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
BinTree_Insert(&(pTree1->pRoot), strdup("55"), StrCompare, RBTREE_COLOR_RED);
pTree1->uNodeCount += 1;
RBTree_Delete(pTree1, "90", StrCompare, free);

BinTree_Insert(&(pTree2->pRoot), strdup("55"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);

ChangeNode(pTree2, "55", NULL);
ChangeNode(pTree2, "60", "55");
ChangeNode(pTree2, "70", "60");
ChangeNode(pTree2, "90", "70");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 9
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例18,Rb-rb型失败\n");
}
break;
case 19: /* Rb-bb和Rb-rb复合型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "90", StrCompare, free);

ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "28", NULL);

ChangeNode(pTree2, "15", NULL);
ChangeNode(pTree2, "25", NULL);

ChangeNode(pTree2, "20", "15", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "40", "25");
ChangeNode(pTree2, "30", "20");
ChangeNode(pTree2, "50", "30");
ChangeNode(pTree2, "60", "40"); /* 必须从小改到大,此行必须放在70前面,否则先改70的话会查找不到60 */
ChangeNode(pTree2, "70", "50");
ChangeNode(pTree2, "90", "70");
BinTree_Insert(&(pTree2->pRoot), strdup("60"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 8
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例19,Rb-bb和Rb-rb复合型失败\n");
}
break;
case 20: /* Rb-bb型和Lr-rb复合型 */

RBTree_Delete(pTree1, "30", StrCompare, free);

ChangeNode(pTree2, "25", NULL);
ChangeNode(pTree2, "10", "10", RBTREE_COLOR_RED);

ChangeNode(pTree2, "30", "25");
ChangeNode(pTree2, "32", "32", RBTREE_COLOR_BLACK);

pNode = BinTree_FindNode(pTree2->pRoot, "35", StrCompare);
BinTree_RotateRight(pNode, &(pTree2->pRoot));

pNode = BinTree_FindNode(pTree2->pRoot, "40", StrCompare);
BinTree_RotateRight(pNode, &(pTree2->pRoot));

pNode = BinTree_FindNode(pTree2->pRoot, "25", StrCompare);
BinTree_RotateLeft(pNode, &(pTree2->pRoot));


if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例20,Rb-bb和Lr-rb复合型失败\n");
}
break;
case 21: /* A节点为红色的情况 */

RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "36", NULL);

ChangeNode(pTree2, "38", "36", RBTREE_COLOR_RED);
ChangeNode(pTree2, "40", "38");


ChangeNode(pTree2, "36", "36", RBTREE_COLOR_BLACK);

if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例21,A节点为红色型失败\n");
}
break;
case 22: /* A节点为红色的情况 */

RBTree_Delete(pTree1, "70", StrCompare, free);

ChangeNode(pTree2, "62", NULL);

ChangeNode(pTree2, "65", "62", RBTREE_COLOR_RED);
ChangeNode(pTree2, "70", "65");


ChangeNode(pTree2, "62", "62", RBTREE_COLOR_BLACK);

if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例22,A节点为红色型失败\n");
}
break;
case 23: /* Rb-bb型 */

RBTree_Delete(pTree1, "70", StrCompare, free);

ChangeNode(pTree2, "62", NULL);

ChangeNode(pTree2, "65", "62", RBTREE_COLOR_RED);
ChangeNode(pTree2, "70", "65");


ChangeNode(pTree2, "62", "62", RBTREE_COLOR_BLACK);

if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例23,A节点为红色型失败\n");
}
break;
case 24: /* 删除节点的右节点不存在型 */

RBTree_Delete(pTree1, "65", StrCompare, free);

ChangeNode(pTree2, "62", NULL);

ChangeNode(pTree2, "65", "62", RBTREE_COLOR_RED);

ChangeNode(pTree2, "62", "62", RBTREE_COLOR_BLACK);

if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例24,删除节点的右节点不存在型失败\n");
}
break;
case 25: /* 删除节点的左节点不存在型 */

RBTree_Delete(pTree1, "80", StrCompare, free);

ChangeNode(pTree2, "85", NULL);

ChangeNode(pTree2, "80", "85", RBTREE_COLOR_RED);

ChangeNode(pTree2, "85", "85", RBTREE_COLOR_BLACK);

if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 23
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例25,删除节点的左节点不存在型失败\n");
}
break;
case 26:
nRet = RBTree_Delete(pTree1, "20", StrCompare, free);
if ( nRet == CAPI_SUCCESS )
{
printf("测试用例26,空树删除型失败\n");

}
break;
case 27:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
nRet = RBTree_Delete(pTree1, "20", StrCompare, free);
if ( nRet == CAPI_FAILED || pTree1->pRoot != NULL
|| pTree1->uNodeCount != 0 )
{
printf("测试用例27,1个节点删除型失败\n");

}
break;
case 28:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
nRet = RBTree_Delete(pTree1, "10", StrCompare, free);
if ( nRet == CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight != NULL
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->uNodeCount != 1 )
{
printf("测试用例28,1个节点删除型失败\n");

}
break;
case 29:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
nRet = RBTree_Delete(pTree1, "15", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight != NULL
|| pTree1->uNodeCount != 1
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例29,2个节点删除型失败\n");

}
break;

case 30:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
nRet = RBTree_Delete(pTree1, "20", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "15" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight != NULL
|| pTree1->uNodeCount != 1
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例30,2个节点删除型失败\n");

}
break;
case 31:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
nRet = RBTree_Delete(pTree1, "35", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight != NULL
|| pTree1->uNodeCount != 1
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例31,2个节点删除型失败\n");

}
break;
case 32:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
nRet = RBTree_Delete(pTree1, "20", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "35" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight != NULL
|| pTree1->uNodeCount != 1
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例32,2个节点删除型失败\n");

}
break;

case 33:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
nRet = RBTree_Delete(pTree1, "20", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "15" ) != 0
|| strcmp((char *)(pTree1->pRoot->pRight->pData), "35" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight->pLeft != NULL
|| pTree1->uNodeCount != 2
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pRight->nMagic != RBTREE_COLOR_RED )
{
printf("测试用例33,3个节点删除型失败\n");

}
break;

case 34:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
nRet = RBTree_Delete(pTree1, "15", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| strcmp((char *)(pTree1->pRoot->pRight->pData), "35" ) != 0
|| pTree1->pRoot->pLeft != NULL
|| pTree1->pRoot->pRight->pLeft != NULL
|| pTree1->uNodeCount != 2
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pRight->nMagic != RBTREE_COLOR_RED )
{
printf("测试用例34,3个节点删除型失败\n");

}
break;
case 35:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
nRet = RBTree_Delete(pTree1, "35", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| strcmp((char *)(pTree1->pRoot->pLeft->pData), "15" ) != 0
|| pTree1->pRoot->pRight != NULL
|| pTree1->pRoot->pLeft->pRight != NULL
|| pTree1->uNodeCount != 2
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pLeft->nMagic != RBTREE_COLOR_RED )
{
printf("测试用例35,3个节点删除型失败\n");

}
break;
case 36:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
RBTree_Insert(pTree1, strdup("12"), StrCompare);
nRet = RBTree_Delete(pTree1, "12", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| strcmp((char *)(pTree1->pRoot->pLeft->pData), "15" ) != 0
|| strcmp((char *)(pTree1->pRoot->pRight->pData), "35" ) != 0
|| pTree1->pRoot->pRight->pLeft != NULL
|| pTree1->pRoot->pLeft->pLeft != NULL
|| pTree1->uNodeCount != 3
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pLeft->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pRight->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例36,4个节点删除型失败\n");

}
break;
case 37:
RBTree_Insert(pTree1, strdup("20"), StrCompare);
RBTree_Insert(pTree1, strdup("35"), StrCompare);
RBTree_Insert(pTree1, strdup("15"), StrCompare);
RBTree_Insert(pTree1, strdup("12"), StrCompare);
nRet = RBTree_Delete(pTree1, "15", StrCompare, free);
if ( nRet != CAPI_SUCCESS
|| strcmp((char *)(pTree1->pRoot->pData), "20" ) != 0
|| strcmp((char *)(pTree1->pRoot->pLeft->pData), "12" ) != 0
|| strcmp((char *)(pTree1->pRoot->pRight->pData), "35" ) != 0
|| pTree1->pRoot->pRight->pLeft != NULL
|| pTree1->pRoot->pLeft->pLeft != NULL
|| pTree1->uNodeCount != 3
|| pTree1->pRoot->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pLeft->nMagic != RBTREE_COLOR_BLACK
|| pTree1->pRoot->pRight->nMagic != RBTREE_COLOR_BLACK )
{
printf("测试用例37,4个节点删除型失败\n");

}
break;
case 38:
break;
case 39:
break;
case 42: /* Lr-br型 */

RBTree_Delete(pTree1, "32", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "35", "38");
ChangeNode(pTree2, "30", "35");
ChangeNode(pTree2, "20", "30");


if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 5
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例42,Lr-br型失败\n");
}
break;
case 43: /* Lr-rb型 */

RBTree_Delete(pTree1, "38", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "30", "32");
ChangeNode(pTree2, "20", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 5
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例43,Lr-rb型失败\n");
}
break;
case 44: /* Lr-rr型 */

RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "30", "32");
ChangeNode(pTree2, "20", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 6
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例44,Lr-rr型失败\n");
}
break;
case 45: /* Lr-bb型 */

RBTree_Delete(pTree1, "32", StrCompare, free);
RBTree_Delete(pTree1, "38", StrCompare, free);
RBTree_Delete(pTree1, "20", StrCompare, free);

ChangeNode(pTree2, "32", NULL);
ChangeNode(pTree2, "38", NULL);
ChangeNode(pTree2, "35", NULL);
ChangeNode(pTree2, "45", NULL);

ChangeNode(pTree2, "40", "45", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "30", "40");
ChangeNode(pTree2, "20", "30");

BinTree_Insert(&(pTree2->pRoot), strdup("35"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 4
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例45,Lr-bb型失败\n");
}
break;
case 46: /* Rr-rr型 */

RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "30", "28");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 6
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例46,Rr-rr型失败\n");
}
break;
case 47: /* Rr-rb型 */

RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "25", "22");
ChangeNode(pTree2, "30", "25");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 5
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例47,Rr-rb型失败\n");
}
break;
case 48: /* Rr-br型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "30", "28");
ChangeNode(pTree2, "40", "30");
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 5
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例48,Rr-br型失败\n");
}
break;
case 49: /* Rr-bb型 */

RBTree_Delete(pTree1, "22", StrCompare, free);
RBTree_Delete(pTree1, "28", StrCompare, free);
RBTree_Delete(pTree1, "40", StrCompare, free);

ChangeNode(pTree2, "28", NULL);
ChangeNode(pTree2, "22", NULL);
ChangeNode(pTree2, "25", NULL);
ChangeNode(pTree2, "15", NULL);
ChangeNode(pTree2, "20", "15", RBTREE_COLOR_BLACK);
ChangeNode(pTree2, "30", "20");
ChangeNode(pTree2, "40", "30");
BinTree_Insert(&(pTree2->pRoot), strdup("25"), StrCompare, RBTREE_COLOR_RED);
pTree2->uNodeCount += 1;
if ( CompareRBTree(pTree1->pRoot, pTree2->pRoot) == 0
|| pTree1->uNodeCount != 4
|| pTree1->uNodeCount != pTree2->uNodeCount )
{
printf("测试用例49,Rr-bb型失败\n");
}
break;
default:
break;
}
BinTree_CheckParent(pTree1->pRoot);
if ( pTree1->pRoot != NULL )
{
if (pTree1->pRoot->pParent != NULL )
{
printf( "RBTree_Delete Failed.\n Root Node's Parent Node is not NULL\n" );
}
}
RBTree_Destroy(pTree1, free);
RBTree_Destroy(pTree2, free);
return;
}


void DRV_RBTree_Find(UINT i)
{
char *pszTemp;
RBTREE *pTree = RBTree_Create();
RBTree_Insert(pTree, strdup("20"), StrCompare);
RBTree_Insert(pTree, strdup("16"), StrCompare);
RBTree_Insert(pTree, strdup("28"), StrCompare);
RBTree_Insert(pTree, strdup("29"), StrCompare);
RBTree_Insert(pTree, strdup("15"), StrCompare);
RBTree_Insert(pTree, strdup("17"), StrCompare);
RBTree_Insert(pTree, strdup("19"), StrCompare);
switch( i )
{
case 1:
pszTemp = (char *)RBTree_Find(pTree, "20", StrCompare);
if ( strcmp(pszTemp, "20") != 0 )
{
printf("RBTree_Find()测试用例1 失败\n");
}
break;
case 2:
pszTemp = (char *)RBTree_Find(pTree, "28", StrCompare);
if ( strcmp(pszTemp, "28") != 0 )
{
printf("RBTree_Find()测试用例2 失败\n");
}
break;
case 3:
pszTemp = (char *)RBTree_Find(pTree, "16", StrCompare);
if ( strcmp(pszTemp, "16") != 0 )
{
printf("RBTree_Find()测试用例3 失败\n");
}
break;
case 4:
pszTemp = (char *)RBTree_Find(pTree, "29", StrCompare);
if ( strcmp(pszTemp, "29") != 0 )
{
printf("RBTree_Find()测试用例4 失败\n");
}
break;
case 5:
pszTemp = (char *)RBTree_Find(pTree, "15", StrCompare);
if ( strcmp(pszTemp, "15") != 0 )
{
printf("RBTree_Find()测试用例5 失败\n");
}
break;
case 6:
pszTemp = (char *)RBTree_Find(pTree, "17", StrCompare);
if ( strcmp(pszTemp, "17") != 0 )
{
printf("RBTree_Find()测试用例6 失败\n");
}
break;
case 7:
pszTemp = (char *)RBTree_Find(pTree, "19", StrCompare);
if ( strcmp(pszTemp, "19") != 0 )
{
printf("RBTree_Find()测试用例7 失败\n");
}
break;
case 8:
RBTree_Delete(pTree,"17", StrCompare, free);
pszTemp = (char *)RBTree_Find(pTree, "17", StrCompare);
if ( pszTemp != NULL )
{
printf("RBTree_Find()测试用例8 失败\n");
}
break;
case 9:
RBTree_Delete(pTree,"17", StrCompare, free);
RBTree_Delete(pTree,"20", StrCompare, free);
RBTree_Delete(pTree,"16", StrCompare, free);
RBTree_Delete(pTree,"15", StrCompare, free);
RBTree_Delete(pTree,"29", StrCompare, free);

pszTemp = (char *)RBTree_Find(pTree, "28", StrCompare);
if ( strcmp(pszTemp, "28") != 0 )
{
printf("RBTree_Find()测试用例9 失败\n");
}
break;
default:
break;
}
RBTree_Destroy(pTree, free);
return;
}


分享到:
评论

相关推荐

    多任务下的数据结构与算法

    树、红黑树、AV L树和图之外,引进了多任务:还介绍了将任意数据结构容器变成支持多任务 的方法:另外,还增加了复合数据结构和动态数据结构等新内容的介绍。在复合数据结构中不 仅介绍了哈希链表、哈希红黑树、哈希...

    多任务下的数据结构 随书的源代码

    《多任务下的数据结构》随书的源代码。探讨多任务下的常用数据结构的实现,如AVL,红黑树,以及一些复合数据结构,如哈希链表,哈希红黑树。可以作为STL数据结构的多任务扩展。

    算法导论(part1)

    如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被设计成能够清晰简明地描述每一个算法。因此,我们不考虑出错处理和其他需要对读者所用...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    (2)他编著和主编的书发行量超过4500万册,是读者最多的科技作家。我国平均每30人、知识分子每1.5人就拥有1本谭浩强教授编著的书。(3)他和别人合作编著的《BASIC语言》发行了1200万册,创科技书籍发行量的世界...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar )

    (2)他编著和主编的书发行量超过4500万册,是读者最多的科技作家。我国平均每30人、知识分子每1.5人就拥有1本谭浩强教授编著的书。(3)他和别人合作编著的《BASIC语言》发行了1200万册,创科技书籍发行量的世界...

    算法导论(part2)

    如果希望实现这些算法中的任何一个,就会发现,将书中的伪代码翻译成读者熟悉的某种程序设计语言,是一件相当直接的事。伪代码被设计成能够清晰简明地描述每一个算法。因此,我们不考虑出错处理和其他需要对读者所用...

    算法导论中文版

    在有关算法的书中,有一些叙述非常严谨,但不够全面;另一些涉及了大量的题材,但又缺乏严谨性。本书将严谨性和全面性融为一体,深入讨论各类算法,并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章...

    leetcode账号怎么注销-Data-Structures-Algorithms:数据结构算法

    数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者修改数据 数据结构分类 线性结构 数组 栈 队列 链表 哈希表 树结构 二叉树 二分搜索树 AVL 红黑树 Treap Splay 堆 Trie 线段树 K...

    note:learning note 学习笔记

    数据结构与算法 通向高阶前端的必经之路 Linux 基本操作 服务器一般都是 Linux git 等,多去敲命令 windows cmder 虚拟终端 网站架构基本原理 nginx 前端基础 HTML 如何优化 SEO CSS Render Layer Compositing Layer...

    程序员需要经常刷题吗-programmer-competency-matrix:程序员能力矩阵

    树、二项式和斐波那契堆、AVL/红黑树、展开树、跳过列表、尝试等。 2.算法 无法在数组中找到数字的平均值(很难相信,但我面试过这样的候选人) 基本的排序、搜索和数据结构遍历和检索算法 树,图,简单的贪婪和分治...

    leetcode答案-theEmbeddedNewTestament.github.io:theEmbeddedNewTestament.gi

    红黑树 最小生成树 (MST) 按位尝试 数学 滚动平均 泰勒级数 除以常数 带查找表的正弦函数 线性插值 浮点算术 常用STL函数实现 Malloc() 位操作 翻转单色位图 并发 实现自旋锁/互斥锁/信号机 测试和清除 使用互斥体...

    java核心知识点整理.pdf

    25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................

    JAVA核心知识点整理(有效)

    25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................

Global site tag (gtag.js) - Google Analytics