éç¨æåºå¹³è¡¡äºåæ æ¥å£æè¿°
è¿å¥ä»£ç 对ç¨æ·å±è½äºå¤æçäºåæ çæ转æä½ï¼ä¸åºåç¨æ·çæ°æ®ç±»åï¼ä»»ä½æ°
æ®é½å¯ä»¥ç¨æåºå¹³è¡¡äºåæ æ¥åæ¾ãæè¿å¯¹å¹³è¡¡äºåæ è¿è¡äºä¸ç¹ç¹æ©å±ï¼å¨æ ç»æé
é¢å¢å äºä¿æ线è¡éå¢ï¼æéåï¼é¡ºåºçååé¾è¡¨ï¼æ¹ä¾¿ä½¿ç¨è
è½å¤å¿«éæåºéåææ
æ èç¹ã
è¿å¥ä»£ç éè¦ç¨æ·ç´æ¥åä¸çé¨åé½ç¨æ³¨åå½æ°æ¥å®ç°ï¼è®©ä½¿ç¨è
å®å
¨ä¸éè¦äºè§£
æåºå¹³è¡¡äºåæ çæ·»å ãå é¤ææ¥æ¾çè¿ç¨ï¼è½å¤åå°å»çå¼ç使ç¨ãè³äºæ§è½ï¼ææ·»
å è¿300ä¸ä¸ªæ èç¹ä¹åï¼æ é«åªæ22å±ï¼æ¥æ¾ä»»æä¸ä¸ªèç¹æå¤åªéè¦22次å¹é
æä½ã
æ¯HASH表快äºå¾å¤ã
è¿å¥ä»£ç è¿é对vxworksæä½ç³»ç»åäºä¸ç¹ç¹æ©å±ï¼å
¶å®å°±æ¯å¤æä¸ä¸å½åæä½ç³»ç»
æ¯å¦æ¯vxworksï¼å¦ææ¯çè¯å°±å建ä¸ä¸ªäºè¿å¶ä¿¡å·éï¼å¦æä¸æ¯å°±ä»ä¹ä¿¡å·éä¹ä¸å建ã
ç®åæ¤çæ¬æä¾äºå¦ä¸éç¨æ¥å£ï¼
1ãæ°æ®ç»æå®ä¹
1.1ãæ çç»æå®ä¹
typedef struct _AVL_TREE_HEADER
{
TREE_NODE *pTreeHeader;
#ifdef ORDER_LIST_WANTED
TREE_NODE *pListHeader;
TREE_NODE *pListTail;
#endif
unsigned int count; /*AVLæ éçèç¹æ»æ°*/
int (*keyCompare)(TREE_NODE * , TREE_NODE *);
int (*free)(TREE_NODE *);
#if OS==3||OS==4 /*#if OS == VXWORKS || OS == VXWORKS_M*/
SEM_ID sem;
#endif
} tAVLTree;
1.2ãæ èç¹çç»æå®ä¹
typedef struct _AVL_TREE_NODE
{
#ifdef ORDER_LIST_WANTED
struct _AVL_TREE_NODE *prev;
struct _AVL_TREE_NODE *next;
#endif
struct _AVL_TREE_NODE *tree_root;
struct _AVL_TREE_NODE *left_child;
struct _AVL_TREE_NODE *right_child;
int bf; /*平衡å åï¼å½å¹³è¡¡å åçç»å¯¹å¼å¤§äºæçäº2çæ¶å就表示æ ä¸å¹³è¡¡(balance_factor)*/
}TREE_NODE;
2ãéç¨å½æ°æ¥å£å®ä¹
2.1ãavlTreeCreate
å½æ°ååï¼tAVLTree *avlTreeCreate(int *keyCompareFunc,int *freeFunc)
åæ°æè¿°ï¼keyCompareFunc - èç¹å¤§å°æ¯è¾å½æ°çæéï¼æ¤å½æ°éè¦ç¨æ·èªå·±æä¾ï¼
æ¯è¾å½æ°çè¿åå¼åºè¯¥æ¯-1ã0ã1ï¼(*keyCompareFunc)å½æ°æ两个åæ°ï¼
åå«æ¯ä¸¤ä¸ªæ èç¹ï¼å¦æ第äºä¸ªåæ°ææåçæ èç¹çå¼æ¯ç¬¬ä¸ä¸ªçå°ï¼
é£ä¹æ¯è¾å½æ°å°±åºè¯¥è¿å-1ï¼å¦æç¸çå°±æ¯è¿å0ï¼å¦åå°±æ¯1ãå
·ä½çæ¯
è¾è§åç±ç¨æ·æ ¹æ®æåå¨çæ°æ®éé¢çå
³é®åæ¥æå®ï¼å½ç¶ï¼å
³é®åæå¯
è½æå¤ä¸ªï¼ã
freeFunc - (*freeFunc)åªæä¸ä¸ªåæ°ï¼å°±æ¯éè¦éæ¾å
åçèç¹çæ
éï¼å¡«åè¿ä¸ªæ³¨åå½æ°çç®çæ¯ä¸ºäºå®ç°avlTreeDestroyåavlTreeFlush
è¿ä¸¤ä¸ªå½æ°ã
è¿åå¼ ï¼æå - è¿åæåä¸ä¸ªæ çæé
失败 - NULL
å½æ°æè¿°ï¼å建ä¸æ£µç©ºç平衡äºåæ ï¼å¦ææ¯vxworksæä½ç³»ç»çè¯è¿å建ä¸ä¸ªè·æ
ç¸å
³çä¸ä¸ªäºè¿å¶ä¿¡å·éãåå§åæææé为空æéã
2.2ãavlTreeDestroy
å½æ°ååï¼int avlTreeDestroy(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - 1
失败 - 0
å½æ°æè¿°ï¼æ§æ¯ä¸é¢å¹³è¡¡äºåæ ï¼éæ¾æææ èç¹çå
åï¼å¹¶ä¸éæ¾ä¿¡å·éï¼å¦ææ¯
vxworksæä½ç³»ç»çè¯ï¼ï¼éæ¾pTreeææåçäºåæ æå ç¨çå
åã
2.3ãavlTreeFlush
å½æ°ååï¼int avlTreeFlush(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - 1
失败 - 0
å½æ°æè¿°ï¼æ¸
空ä¸é¢å¹³è¡¡äºåæ ï¼éæ¾æææ èç¹çå
åï¼ä½æ¯å¹¶ä¸å é¤å¹³è¡¡äºåæ
2.4ãavlTreeAdd
å½æ°ååï¼int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pInsertNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
pInsertNode - å¾
æå
¥çèç¹çæé
è¿åå¼ ï¼æå - 1
失败 - 0
å½æ°æè¿°ï¼å¾å¹³è¡¡äºåæ ä¸æ·»å ä¸ä¸ªæåèç¹
2.5ãavlTreeDel
å½æ°ååï¼int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pDelNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
pDelNode - å¾
æå
¥çèç¹çæé
è¿åå¼ ï¼æå - 1
失败 - 0
å½æ°æè¿°ï¼ä»å¹³è¡¡äºåæ ä¸å é¤ä¸ä¸ªæ èç¹
2.6ãavlTreeFind
å½æ°ååï¼TREE_NODE *avlTreeFind(tAVLTree *pTree,TREE_NODE *pKeyNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
pKeyNode - å¾
æ¥æ¾çèç¹çå
³é®å
è¿åå¼ ï¼æå - æ¥æ¾å°çèç¹æé
失败 - NULL
å½æ°æè¿°ï¼æ¥æ¾ä¸ä¸ªèç¹
2.7ãavlTreeCount
å½æ°ååï¼int avlTreeCount(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - å½å平衡äºåæ éçèç¹æ»æ°
失败 - 0
å½æ°æè¿°ï¼è·åå½åæ éé¢çæææåèç¹æ»æ°
2.8ãavlTreeFirst
å½æ°ååï¼TREE_NODE *avlTreeFirst(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - å½å平衡äºåæ éé¢çæå°çæåèç¹çæé
失败 - NULLï¼åªææ æ¯ç©ºçæ¶åæä¼è¿åNULL
å½æ°æè¿°ï¼è·åå½å平衡äºåæ éé¢ç¬¬ä¸ä¸ªæåèç¹ï¼å³æå°çæåèç¹
2.9ãavlTreeLast
å½æ°ååï¼TREE_NODE *avlTreeLast(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - å½å平衡äºåæ éé¢çæ大çæåèç¹çæé
失败 - NULLï¼åªææ æ¯ç©ºçæ¶åæä¼è¿åNULL
å½æ°æè¿°ï¼è·åå½å平衡äºåæ éé¢æåä¸ä¸ªæåèç¹ï¼å³æ大çæåèç¹
2.10ãavlTreeNext
å½æ°ååï¼TREE_NODE *avlTreeNext(TREE_NODE *pNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - ä¸ä¸ä¸ªæåèç¹çæé
失败 - NULL
å½æ°æè¿°ï¼è·åå½åèç¹çä¸ä¸ä¸ªèç¹
2.11ãavlTreePrev
å½æ°ååï¼TREE_NODE *avlTreePrev(TREE_NODE *pNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼æå - åä¸ä¸ªæåèç¹çæé
失败 - NULL
å½æ°æè¿°ï¼è·åå½åèç¹çåä¸ä¸ªèç¹
2.12ãAVL_TREE_LOCK
å½æ°ååï¼void AVL_TREE_LOCK(tAVLTree *pTree,int timeout)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
timeout - çå¾
æ¶é´
è¿åå¼ ï¼N/A
å½æ°æè¿°ï¼æ¤å½æ°åªææ¯vxworksç³»ç»æææï¼ç®çæ¯å¯¹æ è¿è¡äºæ¥æä½ï¼é²æ¢
å¤ä»»å¡åæ¶æä½é¾è¡¨ã
2.13ãAVL_TREE_UNLOCK
å½æ°ååï¼void AVL_TREE_UNLOCK(tAVLTree *pTree)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
è¿åå¼ ï¼N/A
å½æ°æè¿°ï¼æ¤å½æ°åªææ¯vxworksç³»ç»æææï¼ç®çæ¯å¯¹æ è¿è¡è§£é¤äºæ¥æä½
2.13ãAVL_TREENODE_FREE
å½æ°ååï¼void AVL_TREENODE_FREE(tAVLTree *pTree,TREE_NODE *pNode)
åæ°æè¿°ï¼pTree - æåä¸æ£µå¹³è¡¡äºåæ çæé
pNode - éè¦éæ¾çèç¹çæé
è¿åå¼ ï¼N/A
å½æ°æè¿°ï¼æ¤å½æ°éæ¾å
åçè¿ç¨éç¨çæ¯æ³¨åçéæ¾å½æ°ï¼éæ¾ä¸ä»
ä»
åªæfreeå½æ°ï¼å¯¹äºä¸äºå¤æçç»æ设计ï¼å¯è½éè¦éæ¾å¤ä¸ª
ä¸åçå
åã
3ãåºç¨ä¸¾ä¾
> typedef struct _testStruct{
> TREE_NODE node; /*æ èç¹çç»æä¸å®è¦æ¾å¨ç¨æ·èªå®ä¹ç»æçæåé¢ï¼æ³¨æ!*/
> int keyA; /*å
³é®åA*/
> int keyB; /*å
³é®åB*/
> int keyC; /*å
³é®åCï¼æ¯æ¹è¯´æ¤ç»ææ3个å
³é®å*/
> int userData[200]; /*ç¨æ·çå®é
æ°æ®åº*/
> }tTestStruct;
>
> int keyCompareFunc(TREE_NODE *p , TREE_NODE *p1)
> {
> tTestStruct *T1=NULL,*T2=NULL;
>
> T1=(tTestStruct *)p;
> T2=(tTestStruct *)p1;
>
> if(T1->keyA < T2->keyA) return 1;
> if(T1->keyA > T2->keyA) return -1;
>
> if(T1->keyB < T2->keyB) return 1;
> if(T1->keyB > T2->keyB) return -1;
>
> if(T1->keyC < T2->keyC) return 1;
> if(T1->keyC > T2->keyC) return -1;
>
> return 0;
> }
>
> int freeFunc(TREE_NODE *pNode)
> {
> free((void *)pNode);
> return 1;
> }
>
> tAVLTree *pTree = NULL;
> int main()
> {
> tTestStruct *pTest = NULL;
> tTestStruct key;
> int count = 0;
> pTree = (tAVLTree *)avlTreeCreate
> (
> (void*)keyCompareFunc ,
> (void *)freeFunc
> );
> if(!pTree)
> {
> printf("\r\n å建平衡äºåæ 失败");
> return 0;
> }
>
> /*æ·»å ä¸ä¸ªèç¹*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct));
> if(!pTest)
> {
> printf("\r\n å建æ èç¹å¤±è´¥");
> return 0;
> }
>
> pTest->keyA = 1;
> pTest->keyB = 2;
> pTest->keyC = 3;
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n å·²ç»åå¨ç¸åèç¹ï¼æ·»å 失败!å
³é®åå®å
¨å¹é
就表示èç¹å®å
¨ç¸å");
> return 1;
> }
>
> /*åæ·»å ä¸ä¸ªèç¹*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct));
> if(!pTest)
> {
> printf("\r\n å建æ èç¹å失败");
> return 0;
> }
>
> pTest->keyA = 1;
> pTest->keyB = 1;
> pTest->keyC = 3; /*第äºæ¬¡æ·»å çèç¹çå
³é®åæ¯è¾å¤§å®¶å¯ä»¥ç®ä¸ç®*/
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n å·²ç»åå¨ç¸åèç¹ï¼æ·»å 失败!å
³é®åå®å
¨å¹é
就表示èç¹å®å
¨ç¸å");
> return 1;
> }
>
> /*éåæåºå¹³è¡¡äºåæ -- ä»å°å°å¤§*/
> pTest = (tTestStruct *)avlTreeFirst(pTree);
> while(pTest)
> {
> /**************************
> *è¿éä½ æ³å¹²åå¹²å
> *å¤çpTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreeNext(pTree);
> }
>
> /*éåæåºå¹³è¡¡äºåæ -- ä»å¤§å°å°*/
> pTest = (tTestStruct *)avlTreeLast(pTree);
> while(pTest)
> {
> /**************************
> *è¿éä½ æ³å¹²åå¹²å
> *å¤çpTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreePrev(pTree);
> }
>
> /*æ¥æ¾æ个èç¹*/
> key->keyA = 1;
> key->keyB = 1;
> key->keyC = 3;
> pTest = (tTestStruct *)avlTreeFind(pTree , (TREE_NODE *)&key);
> if(pTest)
> printf("\r\n è¿éåºè¯¥å¯ä»¥æ¥æ¾å°ä¸æ¡è®°å½ï¼å°±æ¯ç¬¬äºä¸ªæå
¥çèç¹");
>
> /*å é¤ä¸ä¸ªèç¹ï¼æ们就å°ä¸é¢æ¥æ¾å°çèç¹å é¤*/
> if(!avlTreeCount(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n å¦æå é¤å¤±è´¥ï¼åªè½è¯´æä¸ä¸ªé®é¢ï¼æ éé¢ä¸åå¨è¿ä¸ªèç¹");
> return 0;
> }
>
> /*è·åæ çæ»çèç¹æ°*/
> count = avlTreeCount(pTree);
> printf("\r\n ææ³ç°å¨countåºè¯¥çäº1ï¼åææ们å æäºä¸ä¸ªèç¹");
>
> /*æ¸
空æ´æ£µæ */
> avlTreeFlush(pTree);
>
> /*å é¤æ´æ£µæ ï¼å
¶å®ç°å¨åªæä¸é¢è£¸æ äºï¼å 为æ èç¹é½è¢«flushæäº*/
> avlTreeDestroy(pTree);
> pTree = NULL;
>
> return 1
> }
温馨提示:答案为网友推荐,仅供参考