树tree、动态数组dyArray、hashMap、拼图算法

// // hashStruct.c // dataStruct // // Created by hherima on 14-7-29. // Copyright (c) 2014年 . All rights reserved. // #include "hashStruct.h" #define MAX_HASH_PRIME_ARRAY_NUM 7 /************************************************************************************************** function name: HashGetValue description: the hash arithmetic to get the position of the certain key. parameter: pKey: the exclusive symbol which is related to a data block in hash table. nKeyLength: the key string's length. nTableLength: the hash table's length. return value: the position of the certain key. ***************************************************************************************************/ cp_int32 HashGetValue(cp_int8* pKey,cp_int32 nKeyLength,cp_int32 nTableLength) { cp_uint32 h = 0; cp_uint32 g = 0; if(!pKey || nKeyLength<1 || nTableLength<1) //if the input parameter is invalid, return. { return -1; } while(nKeyLength--) // get each charactor and use it to compute hash value. { h = (h<<4) + *pKey++; g = h & 0xF0000000L; if(g) { h ^= g>>24; } h &= ~g; } return h % nTableLength; } /************************************************************************************************** function name: HashFindOne description: search the position's node of the certain key. parameter: pKey: the exclusive symbol which is related to a data block in hash table. nKeyLength: the key string's length. pTable: the hash table. return value: the node pointer or null. ***************************************************************************************************/ struct Node* HashFindOne(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable)//search { cp_int32 nPos = 0; struct Node* pCur = NULL; //if the input parameter is invalid, return. if(!pTable || !pKey || nKeyLength<1) { return NULL; } nPos = HashGetValue(pKey,nKeyLength,pTable->m_nLength); if(nPos>=0) pCur = pTable->m_ppHead[nPos]; //cur = table->head[hash_get_value(key,key_length,table->length)]; while(pCur) // if has link list, visit all the list to find the right one. { if(pCur->m_nKeyLength == nKeyLength && MEMCMPFUN(pCur->m_pKey,pKey,nKeyLength) == 0) { return pCur; } pCur = pCur->m_pNext; } return NULL; } /************************************************************************************************** function name: HashFindMultkeyredund description: search the node of the certain key, there will be several one. parameter: pKey: the exclusive symbol which is related to several data block in hash table. nKeyLength: the key string's length. pTable: the hash table. pdestArray: the dynamic array which is used to save results and need be initilalized. return value: the node pointer or null. ***************************************************************************************************/ cp_int32 HashFindMultkeyredund(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable,struct DynamicArray *pDestArray) //search ,the key is redundant. { int nResNum = 0; struct Node* pCur = NULL; //if the input parameter is invalid, return. if(!pTable || !pKey || nKeyLength<1 || !pDestArray) { return -1; } pCur = pTable->m_ppHead[HashGetValue(pKey,nKeyLength,pTable->m_nLength)]; while(pCur) //if has link list, visit all the list and find the right one. { if(pCur->m_nKeyLength == nKeyLength && MEMCMPFUN(pCur->m_pKey,pKey,nKeyLength) == 0) { DyArrayAppend(pDestArray, pCur->m_pVal); // put the right one to array. nResNum++; //return cur; } pCur = pCur->m_pNext; } return nResNum; } /************************************************************************************************** function name: hashExpand description: expand the array when it's too small.THIS FUNCTION CAN'T BE USED BECAUSE HASH VALUE IS CHANGED WHEN TABLE LENGTH CHANGED. parameter: pTable: the hash table. nNeed: the needed new size. return value: if succeed,return the true, else, return false. ***************************************************************************************************/ cp_bool HashExpand(struct HashTable * pTable, cp_int32 nNeed) { cp_int32 i; struct Node ** pData = NULL; cp_int32 nAllocSize = 0; cp_int32 nPrime[MAX_HASH_PRIME_ARRAY_NUM] = { 17, //0 37, //1 79, //2 163, //3 331, //4 673, //5 1361 //6 };//The prime table used to be the length of hash table to decrease conflict. //if the input parameter is invalid, return. if(!pTable || nNeed<1) { return CP_FALSE; } //if need, expand to one and half times of original size. if(((pTable->m_nEleNum + nNeed) + ((pTable->m_nEleNum + nNeed)>>1) ) > pTable->m_nLength) { nAllocSize = pTable->m_nLength + (pTable->m_nLength>>1); for(i=0; i<MAX_HASH_PRIME_ARRAY_NUM; i++) //find the nearest one of prime array. { if(nPrime[i] > nAllocSize) { nAllocSize = nPrime[i]; break; } } pData = (struct Node **)REALLOCFUN(pTable->m_ppHead, sizeof(struct Node *) * nAllocSize); if(pData != NULL) { // clear the expanded space. MEMSETFUN(pData+pTable->m_nLength,0,(nAllocSize-pTable->m_nLength)*sizeof(struct Node *)); pTable->m_ppHead = pData; pTable->m_nLength = nAllocSize; } } return ((pTable->m_nEleNum + nNeed) + ((pTable->m_nEleNum + nNeed)>>1) <= pTable->m_nLength) ? CP_TRUE : CP_FALSE; } /************************************************************************************************** function name: HashInsertOne description: insert the node of the certain key. parameter: pKey: the exclusive symbol which is related to a data block in hash table. nKeyLength: the key string's length. pVal: the node pointer of the certain key. pTable: the hash table. return value: none. ***************************************************************************************************/ void HashInsertOne(cp_int8* pKey,cp_int32 nKeyLength,void* pVal,struct HashTable *pTable)//insert { cp_int32 nPos = 0; struct Node** pNode = NULL; struct Node* pTmp = NULL; //if the input parameter is invalid, return. if(!pTable || !pKey || nKeyLength<1) { return ; } //comment it because when it expands, the same key's position changed and the original key position CAN'T be found. /*if((pTable->m_EleNum + 1) + ((pTable->m_EleNum + 1)>>1) > pTable->m_nLength) { HashExpand(pTable, 1); }*/ //compute the hash position. pTable->m_nEleNum++; nPos = HashGetValue(pKey,nKeyLength,pTable->m_nLength); pNode = &pTable->m_ppHead[nPos]; //if this key is NOT exist, insert it. if(HashFindOne(pKey,nKeyLength,pTable) == NULL) { //malloc a new node and set the value. pTmp=(struct Node*)MALLOCFUN(sizeof(struct Node)); MEMSETFUN(pTmp,0,sizeof(struct Node)); pTmp->m_pKey = (char*)MALLOCFUN(nKeyLength+2);//for Unicode, two bytes zero is needed. MEMSETFUN(pTmp->m_pKey,0,nKeyLength+2); MEMCPYFUN(pTmp->m_pKey,pKey,nKeyLength); pTmp->m_nKeyLength = nKeyLength; pTmp->m_pVal = pVal; pTmp->m_pNext=NULL; //if there is a list, then insert to the tail. while(*pNode) { pNode = &((*pNode)->m_pNext); } *pNode = pTmp; } } /************************************************************************************************** function name: HashInsertOneKeyredund description: insert the node of the certain key. parameter: pKey: the symbol which is related to a data block in hash table. nKeyLength: the key string's length. pVal: the node pointer of the certain key. pTable: the hash table. return value: none. ***************************************************************************************************/ void HashInsertOneKeyredund(cp_int8* pKey,cp_int32 nKeyLength,void* pVal,struct HashTable *pTable) //insert,key is redundant. { cp_int32 nPos = 0; str