?? cmxbtree.cpp
字號:
if( pGreaterThan )
{
//if( pSearchDataLeaf->pDataCont[1]->pData )
if( pSearchDataLeaf->pDataCont[1] )
*pGreaterThan = pSearchDataLeaf->pDataCont[1]->pData;
else
{
if( pSearchDataLeaf->pNext )
{
pSearchDataLeaf2 = pSearchDataLeaf->pNext;
*pGreaterThan = pSearchDataLeaf2->pDataCont[0]->pData;
}
else *pGreaterThan = NULL;
}
}
}
else
{
if( pLessThan )
*pLessThan = pSearchDataLeaf->pDataCont[i-1]->pData;
if( pGreaterThan )
{
if( i+1 < BTREE_DEGREE && pSearchDataLeaf->pDataCont[i+1])
*pGreaterThan = pSearchDataLeaf->pDataCont[i+1]->pData;
else
{
if( pSearchDataLeaf->pNext )
{
pSearchDataLeaf2 = pSearchDataLeaf->pNext;
*pGreaterThan = pSearchDataLeaf2->pDataCont[0]->pData;
}
else *pGreaterThan = NULL;
}
}
}
}
pRet = pSearchResult->pData;
if( pSK )
pSK->m_pSearchResult = pSearchResult->pNext;
return pRet;
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetNextKey( SEARCH_KEY *pSK )
{
if( pSK == NULL ) return NULL;
if( pSK->m_GetKey.m_pProv == NULL ) return NULL;
if( pSK->m_GetKey.m_DataCont == NULL)
{
if( (pSK->m_GetKey.m_nDataElemIndex < BTREE_DEGREE) &&
(pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex] != NULL )
)
{
pSK->m_GetKey.m_DataCont =
pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
return pSK->m_GetKey.m_DataCont->pData;
}
else
{
pSK->m_GetKey.m_nDataElemIndex --;
pSK->m_GetKey.m_DataCont =
pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
return GetNextKey( &(pSK->m_GetKey) );
}
}
else
return GetNextKey( &(pSK->m_GetKey) );
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetPrevKey( SEARCH_KEY *pSK )
{
if( pSK == NULL ) return NULL;
if( pSK->m_GetKey.m_pProv == NULL ) return NULL;
if( pSK->m_GetKey.m_DataCont == NULL)
{
if( pSK->m_GetKey.m_nDataElemIndex > 0)
{
pSK->m_GetKey.m_nDataElemIndex --;
pSK->m_GetKey.m_DataCont =
pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
return pSK->m_GetKey.m_DataCont->pData;
}
else
{
pSK->m_GetKey.m_DataCont =
pSK->m_GetKey.m_pProv->pDataCont[pSK->m_GetKey.m_nDataElemIndex];
return GetPrevKey( &(pSK->m_GetKey) );
}
}
else
return GetPrevKey( &(pSK->m_GetKey) );
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::SearchNextKey( SEARCH_KEY *pSK )
{
if( pSK == NULL ) return NULL;
RECTYPE* pRet;
if( !pSK->m_pSearchResult ) return NULL;
pRet = pSK->m_pSearchResult->pData;
pSK->m_pSearchResult = pSK->m_pSearchResult->pNext;
return pRet;
}
template <class RECTYPE>
int CMXBTree<RECTYPE>::DeleteKey( SEARCH_KEY *pSK, RECTYPE * pRec )
{
if( pRec == NULL || pSK == NULL ) return 1;
if( pSK->m_pSearchResultOrig == NULL ) return 1;
if( pSK->m_pSearchDataLeaf == NULL ) return 1;
DATA_CONTAINER *p = pSK->m_pSearchResultOrig, *q ;
while( p && p->pData != pRec )
p = p->pNext;
if( p == NULL ) return 1;
if( p->pProv == NULL && p->pNext == NULL) //只有一個元素
{
RECTYPE key = *pRec;
return DeleteKey( key );
return 1;
}
else
if( p->pProv == NULL )
{
/*
int i;
for( i = 0; i < BTREE_DEGREE; i++ )
{
if( p == pSK->m_pSearchDataLeaf->pDataCont[i] )
break;
}
if( i == BTREE_DEGREE ) return 1;
*/
if( p != pSK->m_pSearchResultOrig ) return 1;
p = p->pNext;
*(pSK->m_pSearchResultOrig->pData) = *(p->pData);
if( p == pSK->m_pSearchResult )
pSK->m_pSearchResult = pSK->m_pSearchResultOrig;
}
q = p->pProv;
q->pNext = p->pNext;
q = p->pNext;
if( q ) q->pProv = p->pProv;
DeleteRecType( p->pData );
DeleteDataContainer( p );
return 0;
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetFirstKey( GET_KEY * pGK )
{
if( pGK == NULL ) return NULL;
memset( pGK, 0, sizeof(GET_KEY) );
if( MakeDataList() < 0 ) return NULL;
pGK->m_nDataElemIndex = 0;
pGK->m_pProv = m_pDataLeafList;
if( ! pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex] ) return NULL;
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetLastKey( GET_KEY * pGK )
{
if( pGK == NULL ) return NULL;
memset( pGK, 0, sizeof(GET_KEY) );
if( MakeDataList() < 0 ) return NULL;
pGK->m_pProv = m_pDataLeafListTail;
int i;
for( i = BTREE_DEGREE - 1; i >= 0; i -- )
{
if( pGK->m_pProv->pDataCont[i] )
break;
}
if( i < 0 ) return NULL;
pGK->m_nDataElemIndex = i;
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetNextKey( GET_KEY * pGK, bool bGetDup )
{
if( m_bMadeList == false ) return NULL;
if( pGK == NULL ) return NULL;
if( !pGK->m_pProv ) return NULL;
if( pGK->m_DataCont && bGetDup )
{
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
if( (pGK->m_nDataElemIndex+1 < BTREE_DEGREE) && pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex+1] ) //本數據葉還有元素可返回
{
pGK->m_nDataElemIndex++;
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
else
{
pGK->m_pProv = pGK->m_pProv->pNext;
if( pGK->m_pProv )
{
pGK->m_nDataElemIndex = 0;
if( pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex] )
{
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
else
return NULL;
}
else
return NULL;
}
}
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::GetPrevKey( GET_KEY * pGK, bool bGetDup )
{
if( m_bMadeList == false ) return NULL;
if( pGK == NULL ) return NULL;
if( !pGK->m_pProv ) return NULL;
if( pGK->m_DataCont && bGetDup )
{
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
if( pGK->m_nDataElemIndex - 1 >= 0 ) //本數據葉還有元素可返回
{
pGK->m_nDataElemIndex --;
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
else
{
pGK->m_pProv = pGK->m_pProv->pProv;
if( pGK->m_pProv )
{
int i;
for( i = BTREE_DEGREE - 1; i >= 0; i -- )
{
if( pGK->m_pProv->pDataCont[i] )
break;
}
if( i < 0 ) return NULL;
pGK->m_nDataElemIndex = i;
pGK->m_DataCont = pGK->m_pProv->pDataCont[pGK->m_nDataElemIndex];
RECTYPE* pRet = pGK->m_DataCont->pData;
pGK->m_DataCont = pGK->m_DataCont->pNext;
return pRet;
}
else
return NULL;
}
}
template <class RECTYPE>
int CMXBTree<RECTYPE>::SubMakeDataList( BTREE_INDEX_LEAF *pSearchIndexLeaf )
{
if ( !pSearchIndexLeaf ) return -1; //無效的索引葉指針？BTREE 錯誤
if( pSearchIndexLeaf->cPointerType == DATA_LEAF_POINTER ) //下面就是數據葉
{
if( pSearchIndexLeaf->pLeafLeft ) //最左的指針有效
{
if( m_pDataLeafList == NULL)
{ //隊列還沒有開始建立
m_pDataLeafList = (BTREE_DATA_LEAF *) pSearchIndexLeaf->pLeafLeft;
m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->pLeafLeft;
m_pProv->pProv = NULL;
m_pProv->pNext = NULL;
}
else
{ //隊列已經建立了
m_pProv->pNext = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
m_pProv->pNext->pProv = m_pProv;
m_pProv = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
m_pProv->pNext = NULL;
}
}
//一個一個地對索引葉下面的數據葉建立鏈表
int i;
for( i = 0; i < BTREE_DEGREE; i ++ )
{
if( pSearchIndexLeaf->IndexKeys[i].pKey )
{
if( m_pDataLeafList == NULL)
{
m_pDataLeafList = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
m_pProv->pNext = NULL;
m_pProv->pProv = NULL;
}
else
{
m_pProv->pNext = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
m_pProv->pNext->pProv = m_pProv;
m_pProv = (BTREE_DATA_LEAF *) pSearchIndexLeaf->IndexKeys[i].pKeyRight;
m_pProv->pNext = NULL;
}
}
else break;
}
}
else
if( pSearchIndexLeaf->cPointerType == INDEX_LEAF_POINTER ) //下面還是索引葉
{
//對最左的兒子第歸
if( SubMakeDataList((BTREE_INDEX_LEAF *)pSearchIndexLeaf->pLeafLeft) < -1 )
return -1;
//對其他兒子第歸
int i;
for( i = 0; i < BTREE_DEGREE; i ++ )
{
if( pSearchIndexLeaf->IndexKeys[i].pKey )
{
if( SubMakeDataList((BTREE_INDEX_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight) < -1 )
return -1;
}
else break;
}
}
else return -1;
return 0;
}
//把整棵樹鏟除
//也是用第歸
template <class RECTYPE>
int CMXBTree<RECTYPE>::SubDestroyTree( BTREE_INDEX_LEAF *pSearchIndexLeaf )
{
if ( !pSearchIndexLeaf ) return -1;
int i,j;
if( pSearchIndexLeaf->cPointerType == DATA_LEAF_POINTER ) //下面已經是數據葉
{
if( pSearchIndexLeaf->pLeafLeft ) //最左的指針有效
{
BTREE_DATA_LEAF *pTmp = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
for( i = 0; i < BTREE_DEGREE; i++ )
{
if( pTmp->pDataCont[i] )
DeleteDataContainerTrain( pTmp->pDataCont[i] );
else break;
}
DeleteDataLeaf( pTmp );
}
for( i = 0; i < BTREE_DEGREE; i ++ )
{
if( pSearchIndexLeaf->IndexKeys[i].pKey )
{
BTREE_DATA_LEAF *pTmp = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight;
for( j = 0; j < BTREE_DEGREE; j++ )
{
if( pTmp->pDataCont[j] )
DeleteDataContainerTrain( pTmp->pDataCont[j] );
else break;
}
DeleteDataLeaf( pTmp );
}
else break;
}
DeleteIndexLeaf( pSearchIndexLeaf );
}
else
if( pSearchIndexLeaf->cPointerType == INDEX_LEAF_POINTER )
{
if( SubDestroyTree((BTREE_INDEX_LEAF *)pSearchIndexLeaf->pLeafLeft) < -1 )
return -1;
int i;
for( i = 0; i < BTREE_DEGREE; i ++ )
{
if( pSearchIndexLeaf->IndexKeys[i].pKey )
{
if( SubDestroyTree((BTREE_INDEX_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight) < -1 )
return -1;
}
else break;
}
DeleteIndexLeaf( pSearchIndexLeaf );
}
else return -1;
return 0;
}
#endif
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -