数据结构 c/c++索引顺序表查找

数据结构 c/c++索引顺序表查找:

  1. //BlockSearch.h
  2. #ifndef BLOCK_SEARCH
  3. #define BLOCK_SEARCH
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #define ARR_SIZE 100
  7. #pragma pack(push)
  8. #pragma pack(4)
  9. typedef struct
  10. {
  11.     int iStart;
  12.     int iEnd;
  13.     int iMax;
  14. }INode;
  15. typedef struct
  16. {
  17.     int* pArr;
  18.     int iSize;
  19.     INode* pNode;
  20.     int iNodeSize;
  21. }BlockSeq;
  22. #pragma pack(pop)
  23. #endif
[cpp][/cpp] 

  1. //BlockSearch.c
  2. #include “BlockSearch.h”
  3. int BlockSearch( BlockSeq* pBSeq, int iTarget )
  4. {
  5.     if( !pBSeq ||  0 == iTarget )
  6.         return -1;
  7.     int i = 0;
  8.     for( ; i < pBSeq->iNodeSize; i++ )
  9.     {
  10.         if( (pBSeq->pNode + i)->iMax >  iTarget )
  11.             break;
  12.     }
  13.     if( i >= pBSeq->iNodeSize )
  14.         return -1;
  15.     int j;
  16.     int iMaxIndex = ( pBSeq->pNode + i )->iEnd;
  17.     for( j = ( pBSeq->pNode + i )->iStart; j <= iMaxIndex; j++ )
  18.     {
  19.         if( *(pBSeq->pArr + j) == iTarget )
  20.             return j;
  21.     }
  22.     return -2;
  23. }
  24. BlockSeq* CreateBlockSeq()
  25. {
  26.     BlockSeq *pBSeq = (BlockSeq*)malloc( sizeof( BlockSeq ) );
  27.     if( !pBSeq )
  28.         return NULL;
  29.     pBSeq->pArr = (int*)malloc( sizeof( int ) * ARR_SIZE );
  30.     pBSeq->iSize = ARR_SIZE;
  31.     pBSeq->pNode = (INode*)malloc( sizeof( INode ) * 4 );
  32.     pBSeq->iNodeSize = 4;
  33.     int i = 1;
  34.     for( ; i <= 100; i++ )
  35.     {
  36.         *( pBSeq->pArr + i – 1 ) = i;
  37.     }
  38.     pBSeq->pNode->iStart = 0;
  39.     pBSeq->pNode->iMax = 25;
  40.     pBSeq->pNode->iEnd = 24;
  41.     ( pBSeq->pNode + 1 )->iStart = 25;
  42.     ( pBSeq->pNode + 1 )->iMax = 50;
  43.     ( pBSeq->pNode + 1 )->iEnd = 49;
  44.     ( pBSeq->pNode + 2 )->iStart = 50;
  45.     ( pBSeq->pNode + 2 )->iMax = 75;
  46.     ( pBSeq->pNode + 2 )->iEnd = 74;
  47.     ( pBSeq->pNode + 3 )->iStart = 75;
  48.     ( pBSeq->pNode + 3 )->iMax = 100;
  49.     ( pBSeq->pNode + 3 )->iEnd = 99;
  50.     return pBSeq;
  51. }
  52. int main( int argc, char* argv[] )
  53. {
  54.     BlockSeq *pBSeq = CreateBlockSeq();
  55.     printf( “Result is: %d”, BlockSearch( pBSeq, 33 ) );
  56.     puts( “” );
  57.     return 0;
  58. }

标签