//Hash.h #ifndef HASH_H #define HASH_H #define HASH_ARR_SIZE 100 #define FILL -1 #include <stdlib.h> #include <stdio.h> #include <string.h> struct _Node { int iFill; int iValue; struct _Node* pNext; }; typedef _Node Node; typedef struct { Node* pHashArr; int iArrSize; int iSize; }Hash; #endif
//Hash.c #include "Hash.h" Hash* CreateHashArr() { Hash* pHash = (Hash*)malloc( sizeof( Hash ) ); if( !pHash ) return NULL; pHash->iArrSize = HASH_ARR_SIZE; pHash->iSize = 0; pHash->pHashArr = (Node*)malloc( sizeof( Node ) * HASH_ARR_SIZE ); memset( pHash->pHashArr, 0, sizeof( Node ) * HASH_ARR_SIZE ); if( !pHash->pHashArr ) return NULL; return pHash; } int GetIndex( int iValue ) { return iValue % HASH_ARR_SIZE; } Node* CreateNode( int iValue ) { Node* pNode = (Node*)malloc( sizeof( Node ) ); if( !pNode ) return NULL; pNode->iValue = iValue; pNode->pNext = NULL; pNode->iFill = FILL; return pNode; } int DoHash( Hash* pHash, int iValue ) { if( !pHash ) return -1; int iIndex = GetIndex( iValue ); if( (pHash->pHashArr + iIndex)->iFill != FILL ) { (pHash->pHashArr + iIndex)->iFill = FILL; (pHash->pHashArr + iIndex)->iValue = iValue; (pHash->pHashArr + iIndex)->pNext = NULL; pHash->iSize++; } else {//collison Node* pNode = (pHash->pHashArr + iIndex)->pNext; if( !pNode ) { (pHash->pHashArr + iIndex)->pNext = CreateNode( iValue ); return 0; } Node* pPrior = pNode; while( pNode ) { pPrior = pNode; pNode = pNode->pNext; } pNode = CreateNode( iValue ); if( !pNode ) return -1; pPrior->pNext = pNode; pHash->iSize++; } return 0; } Node* HashSearch( Hash* pHash, int iValue ) { if( 0 == pHash->iSize ) return NULL; int iIndex = GetIndex( iValue ); if( (pHash->pHashArr + iIndex)->iFill != FILL ) return NULL; else { if( (pHash->pHashArr + iIndex)->iValue == iValue ) return pHash->pHashArr + iIndex; Node* pNode = (pHash->pHashArr + iIndex)->pNext; Node* pPrior = pNode; while( pNode && pPrior->iValue != iValue ) { pPrior = pNode; pNode = pNode->pNext; } if( pNode->iValue == iValue ) return pNode; } return NULL; } void PrintNode( Node* pNode ) { if( pNode ) printf( "%d ", pNode->iValue ); } int main( int argc, char* argv[] ) { Hash* pHash = CreateHashArr(); if( !pHash ) return -1; DoHash( pHash, 1 ); DoHash( pHash, 300 ); DoHash( pHash, 22 ); DoHash( pHash, 11 ); DoHash( pHash, 99 ); DoHash( pHash, 28 ); DoHash( pHash, 36 ); DoHash( pHash, 23 ); DoHash( pHash, 55 ); DoHash( pHash, 3 ); DoHash( pHash, 7 ); DoHash( pHash, 101 ); PrintNode( HashSearch( pHash, 1 ) ); PrintNode( HashSearch( pHash, 101 )); return 0; }