-
2017-12-15 16:55:04
介绍了符号表的组织形式有线性组织(重插入简洁性,轻索引性能),排序组织(插入操作耗时,重索引性能),哈希表映射(以空间换取时间)。那么如下便介绍了符号表的链表实现方式和哈希表实现方式,分别对应线性组织和哈希表映射两种方式,至于排序组织方式的实现其实只需要一个动态扩展数组便可以实现,较为简单不作讨论。网上关于符号表的实现代码有很多,没有必要重复造轮子,其中个人觉得实现最好的是erhuoxifu博主的两篇文章,代码质量很高,故而在他的代码基础上做一些讨论分析。
1. 符号表的List链表形式实现
首先来看下接口函数的设置 list.h#ifndef _LIST_H_ #define _LIST_H_ /* *链表实现最大的优点便是动态插入的性能很好,故而显然每个符号表项(这里称为元素项)的具体实现方式 *采用链接节点的形式最好,这样既能实现动态扩展(不盲目扩展空间),又可以很好地实现链表关联 *所以这里分为两层结构,分别定义元素项的节点和管理链表的组织信息头结构体 */ typedef struct ListNode { char* key; void* value; struct ListNode* pre; struct ListNode* next; } ListNode; typedef struct List { struct ListNode* head_node; struct ListNode* tail_node; unsigned long uiNodeLength; } List; typedef struct List* pList; /* *如果是用C++编译器编译,那么接口函数为了可以被用在C语言中,声明采用C语言的函数修饰规则, **否则链接过程中可能会找不到正确的函数名 */ #ifdef __cplusplus extern "C" { #endif pList List_new( void ); /* *这里需要讨论的问题是,元素项节点结构体中存放着指向符号名key、元素值value的指针,那么在释放时 *符号名Key的空间释放我们是可以理解的,那么元素值value是否也需要在这里释放呢? *思考了一下,觉得还是不应该在List_free中释放具体的元素项的value指针,有两点考虑 *1.不符合“谁制造,谁负责”的原则,这样容易出现模块之间功能界限模糊 *2.元素项中存放具体元素值时,因为不知道元素值的类型,而采用通用指针void*,那么显然在不知道元素值类 *型的情况下,是无法正确释放该元素值所占用的空间的,虽然让用户自己负责自己的值空间的分配和释放确实容易 *出现忘记释放的情况,但是如果将该工作转移到symbol_list库中来实现,工作量和难度都会增加不少, *故而基于以上考虑,放弃在List_free和List_remove中对具体元素项的值空间的释放 */ void List_free( pList oList ); int List_getLength( pList oList ); /* *这里要讨论的是List_put如何遇到要存储元素已经存在,该如何面对,是更新,还是不更新? *我们知道在有些用户使用性友好的库中,这种插入操作有时是和replace混用的,但这要求库的设计者对 *库的使用场景足够熟悉,才能做出这种果断的融合操作的 *显然出于功能界限尽可能清晰的原则考虑,这里我还是认为不应该出现put插入和replace替换混用 */ int List_put( pList oList, const char* pcKey, const void* pvValue ); /* *和上面List_put同样的道理,既然是replace替换,所以就应该是要替换的元素已经存在在List中, *不应该增加:如果要替换的元素此前不存在,那么便将该元素项作为新插入项插入List中这种功能组合的设计 */ void* List_replace( pList oList, const char* pcKey, const void* pvValue ); int List_contains( pList oList, const char* pcKey ); /* *出于功能安全的角度考虑,库传出来给用户的值尽可能应该是传值、传bool这类的直接量,而不应该传出 *元素项指针,链表组织信息(如头结点地址)这类敏感的信息的指针 *所以这里的List_get应该完成的操作是根据给定的符号名来给出元素项具体值空间,前面又说道了List库 *是不对具体的元素值空间负责的,所以这里只能传出值空间首地址,让程序上层调用者来负责那些指针安全操作的 *内容,List库的原则应该是自己产生的指针信息绝对不外泄 */ void* List_get( pList oList, const char* pcKey ); /*参考上面关于List_free的描述*/ void* List_remove( pList oList, const char* pcKey ); /* *给List链表设计一个类似于lambda函数遍历操作的接口,结合了lambda函数+迭代器的原则, *功能目标是在List链表中将所有元素项调用传递的pfApply函数指针指向的函数调用一遍 */ void List_map( pList oList, void (*pfApply)(const char* pcKey, const void* pvValue, void* pvExtra), const void* pvExtra ); #ifdef __cplusplus } #endif #endif //end of _LIST_H_
来看下具体的链表接口函数实现,我对原代码进行了一点更改,采用双向链表以加速删除这类操作的性能
list.cpp#include "list.h" //“”意味着优先在当前目录下搜索库 #include <stdio.h> //<>意味着按照#include环境变量设置的绝对路径进行搜索 #include <stdlib.h> #include <assert.h> #include <string.h> /* * Use calloc to allocate the memory, * because it will initialize all memory bits to zero. * calloc函数相比于malloc函数最大的不同便是初始化操作,前者带有分配空间全部清空的操作 */ static void* MyAlloc ( unsigned long size ) { void* tmp; tmp = ( void* ) calloc ( size, sizeof ( char ) ); assert( tmp ); return tmp; } pList List_new( void ) { return (pList)MyAlloc(sizeof(List)); } void List_free( pList oList ) { assert( oList ); ListNode* temp = oList->head_node; while ( temp ) { oList->head_node = oList->head_node->next; if ( temp->key ) free( temp->key ); //if ( temp->value ) //value的释放不应该由List内部来实现,应该遵循着谁制造,谁负责的逻辑 // free( temp->value ); free( temp ); temp = oList->head_node; } free( oList ); oList = NULL; } int List_getLength( pList oList ) { return oList->uiNodeLength; } /* *static修饰本函数仅限于本文件list.cpp内部使用,之所以加这一个函数是为了内部其他函数方便获取具体元素 *的指针信息,从而方便操作,但是该函数显然是不能向外部开放的 */ static ListNode* List_getKey( pList oList, const char* pcKey ) { assert( oList ); assert( pcKey ); if (strlen(pcKey) == 0) return NULL; if ( oList->uiNodeLength == 0) return NULL; ListNode* temp = oList->head_node; while (temp) { if( strcmp( pcKey, temp->key) == 0) return temp; temp = temp->next; } return NULL; } //插入元素项,如果元素项存在,那就意味着本次插入不成功,返回0,成功返回1 int List_put( pList oList, const char* pcKey, const void* pvValue ) { assert( oList ); assert( pcKey ); assert( pvValue); if ( strlen( pcKey) == 0) return 0; if ( List_getKey( oList, pcKey) ) return 0; else { ListNode* new_node = (ListNode*)MyAlloc( sizeof(ListNode) ); assert( new_node ); char* key = (char*)MyAlloc( strlen(pcKey) + 1); if (key == NULL) { free( new_node); return 0; } new_node->key = key; strcpy( new_node->key, pcKey ); new_node->value = (void*)pvValue; if (oList->uiNodeLength == 0) { oList->head_node = new_node; oList->tail_node = new_node; new_node->pre = NULL; new_node->next = NULL; oList->uiNodeLength = 1; return 1; } else { new_node->pre = oList->tail_node; new_node->next = NULL; oList->tail_node->next = new_node; oList->tail_node = new_node; oList->uiNodeLength += 1; return 1; } } } //根据给定的元素符号名查找该元素是否存在,如果存在返回1,否则返回0 int List_contains( pList oList, const char* pcKey ) { assert( oList ); assert( pcKey ); if ( List_getKey( oList, pcKey) ) return 1; else return 0; } //元素替换接口函数的实现,替换的前提是必须列表中存在这样的元素 void* List_replace( pList oList, const char* pcKey, const void* pvValue ) { assert( oList ); assert( pcKey ); ListNode* tempListNode = List_getKey( oList, pcKey ); if (tempListNode == NULL) return NULL; else { void* tempP = tempListNode->value; tempListNode->value = (void*) pvValue; return tempP; } } //根据具体元素的符号名查找元素项,但是显然不能返回该元素项的指针,而只能返回值空间的首地址, void* List_get( pList oList, const char* pcKey ) { assert( oList ); assert( pcKey ); if (strlen(pcKey) == 0) return NULL; else { ListNode* temp = List_getKey( oList, pcKey ); return temp ? temp->value : NULL; } } //删除指定符号名的元素项,并返回元素原值 void* List_remove( pList oList, const char* pcKey ) { assert( oList ); assert( pcKey ); if ( strlen(pcKey) == 0) return NULL; else { ListNode* temp = List_getKey( oList, pcKey ); void* tempValue = NULL; if (temp) { if ((temp != oList->tail_node) && (temp != oList->head_node)) { temp->pre->next = temp->next; temp->next->pre = temp->pre; } else if (temp == oList->head_node ) { if (oList->uiNodeLength == 1) { oList->head_node = NULL; oList->tail_node = NULL; } else { oList->head_node = temp->next; temp->next->pre = NULL; } } else //if (temp == oList->tail_node ) { if (oList->uiNodeLength == 1) { oList->head_node = NULL; oList->tail_node = NULL; } else { oList->tail_node = temp->pre; temp->pre->next = NULL; } } tempValue = temp->value; free(temp->key); //free(temp->value); free(temp); oList->uiNodeLength -= 1; } return tempValue; } } void List_map( pList oList, void (*pfApply)(const char* pcKey, const void* pvValue, void* pvExtra), const void* pvExtra ) { assert( oList ); assert( pvExtra ); assert( pfApply ); ListNode* temp = oList->head_node; while (temp) { assert( temp->key ); assert( temp->value ); pfApply( temp->key, temp->value, (void*)pvExtra); temp = temp->next; } return; }
2. 符号表的hash-table形式实现
首先来看下接口函数的设置 hash-table.h#ifndef _HASH_TABLE_H_ #define _HASH_TABLE_H_ /*建立三级结构,分别是具体元素项、哈希单位置链、符号表,因为符号表机制采用的是诸侯鼎力的机制 *为了因对哈希冲突,本程序实现的是同一哈希key值处用链表串联来解决,而非传统的顺移方案 */ /*建立hash-table中的元项实现,因为每个元素项的哈希索引值可能存在冲突,所以应该在元素节点中保留 *插入冲突节点的可能性,这便是引入struct ListNode* next的原因 */ typedef struct ListNode { char* key; void* value; struct ListNode* next; }ListNode; /*声明该链的组织信息*/ typedef struct ListAssociation { struct ListNode* head_node; struct ListNode* tail_node; unsigned long uiNodeLength; //指明该链长度 }ListAssociation; typedef struct HashTable { struct ListAssociation** bucketTable;//子表的索引入口 unsigned long uiBindingsCount; //保存该hash-table所有有效子表的数目 unsigned long uiBucketCount; //保存当前哈希表内含的子表数目的上限 } HashTable; typedef struct HashTable* HashTable_t; #ifdef __cplusplus extern "C" { #endif /*初始化哈希表,根据给定的容量设置BucketCount,初始化BucketCount个listAssocation*指针信息*/ HashTable_t HashTable_new( void ); void HashTable_free( HashTable_t oHashTable ); int HashTable_getLength( HashTable_t oHashTable ); /* *往指定哈希表插入新元素,和讨论符号表的List实现时一样,既然是插入新元素,那么如果不是新元素 *那么显然插入新元素是不存在,即插入新元素和更改元素的功能严格分离 */ int HashTable_put ( HashTable_t oHashTable, const char* pcKey, const void* pvValue); void* HashTable_get( HashTable_t oHashTable, const char* pcKey ); /*将哈希表原有的元素项的值替换成新值pvValue,并返回旧值,如果该元素项不存在,则返回NULL*/ void* HashTable_replace( HashTable_t oHashTable, const char* pcKey, const void* pvValue); /*在哈希表中,给定元素的符号名,删除该指定元素项*/ void* HashTable_remove( HashTable_t oHashTable, cosnt char* pcKey); void HashTable_map( HashTable_t oHashTable, void (*pfApply)( const char* pcKey, const void* pvValue, void* pvExtra), const void* pvExtra );
hash-table.cpp
#include "hash-table.h" #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define ARRAY_SIZE 3 static const unsigned long kBucketCount[ARRAY_SIZE] = {1024, 2048, 666666}; static int giBucketCountIndex = 0; static void* MyAlloc( unsigned long size ); /* *给定一个符号表组名称,和当前要查找的元素符号名key --pcKey,因为同样的符号名可能存在哈希冲突,故而应该 *返回的是一个单向链表的表头或链表信息节点 */ static ListAssociation* HashTable_getListAssociation ( HashTable_t oHashTable, const char* pcKey ); /*给定一个冲突链条,在其中查找具体的元素节点*/ static ListNode* ListAssociation_getListNode ( const ListAssociation* pListAssociation, const char* pcKey ); /*在哈希表中直接查找到具体元素项的首地址,注意static修饰符,该函数是该文件的内部函数,纯粹是为了方便 *其他函数的实现,对外部并不可见,之所以提到最前面给出函数声明,是因为该库要兼容C,所以才会有这些操作 */ static ListNode* HashTable_getListNode( HashTable_t oHashTable, const char* pcKey ); /*非覆盖版插入操作,即插入和更新绝对不混用*/ static int ListAssociation_put( ListAssociation* pListAssociation, const char* pcKey, const void* pvValue ); /*hash-table扩展操作,如果当前哈希表容量不足,则由1024->2048->666666递增,递增成功,则返回1,否则返回0*/ static int Rehash( HashTable_t oHashTable ); static int ListAssociation_put_help_rehash( ListAssociation* pListAssociation, ListNode* pListNode ); /*获取当前哈希表的容量所处级别*/ static int GetBucketSizeIndex( unsigned long uiBucketCounts ); /*很简单的hash函数,该步操作返回的哈希映射后的下标*/ int HashTable_hash( const char* pcKey, int iBucketCount ) { int i; unsigned int uiHash = 0U; assert( pcKey != NULL); for (i=0; pcKey[i] != '\0'; i++) { uiHash = uiHash * 66666 + (unsigned int)pcKey[i]; } return (int)( uiHash % (unsigned int)iBucketCount ); } HashTable_t HashTable_new( void ) { HashTable_t temp = (HashTable_t) MyAlloc( sizeof(HashTable) ); if(temp) { struct ListAssociation ** pListAssociation = NULL; temp->uiBucketCount = kBucketCount[0]; //初始将hash_table初始化为1024个节点 pListAssociation = (ListAssociation**) MyAlloc(temp->uiBucketCount * sizeof( ListAssociation* ) ); if (pListAssociation == NULL) { free(temp); return NULL; } temp->bucketTable = pListAssociation; } return temp; } void HashTable_free( HashTable_t oHashTable ) { assert( oHashTable ); unsigned long uiBucketCount = oHashTable->uiBucketCount; //遍历删除子表的内容 struct ListAssociation* pListAssociation = NULL; for (int i = 0; i<uiBucketCount; i++ ) { pListAssociation = oHashTable->bucketTable[i]; if( NULL == pListAssociation ) continue; ListNode* temp = pListAssociation->head_node; while (temp) { pListAssociation->head_node = pListAssociation->head_node->next; if (temp->key) { free( temp->value ); free( temp->key ); } free(temp); } free( pListAssociation); pListAssociation = NULL; } free( oHashTable->bucketTable ); free( oHashTable ); oHashTable = NULL; } int HashTable_getLength( HashTable_t oHashTable ) { return oHashTable->uiBindingsCount; } int HashTable_put ( HashTable_t oHashTable, const char* pcKey, const void* pvValue) { assert( oHashTable ); assert( pcKey ); assert( pvValue ); assert( oHashTable->uiBucketCount ); //确保当前哈希表的子表数目不为0 if (0 == strlen( pcKey) ) return 0; if (oHashTable->uiBucketCount < kBucketCount[ARRAY_SIZE-1] ) { if (oHashTable->uiBindingsCount >= oHashTable->uiBucketCount ) { if( Rehash(ohashTable) == 0) return 0; } } ListAssociation* pListAssociation = HashTable_getListAssociation( oHashTable, pcKey ); if (NULL == pListAssociation ) { pListAssociation = ( ListAssociation* ) MyAlloc( sizeof(ListAssociation) ); if (pListAssociation == NULL ) return 0; oHashTable->bucketTable[HashTable_hash( pcKey, oHashTable->uiBucketCount)] = pListAssociation; } if (ListAssociation_put( pListAssociation, pcKey, pvValue) ) { oHashTable->uiBindingsCount = oHashTable->uiBindingsCount + 1; return 1; } return 0; } int HashTable_contains( HashTable_t oHashTable, const char* pcKey ) { assert( oHashTable ); assert( pcKey ); if(HashTable_getListNode( oHashTable, pcKey) ) return 1; else return 0; } void* HashTable_get( HashTable_t oHashTable, const char* pcKey ) { assert( oHashTable ); assert( pcKey ); ListNode* pListNode = HashTable_getListNode( oHashTable, pcKey ); if(pListNode) return pListNode->value; return NULL; } //对哈希表中所有元素进行遍历操作,操作函数为pfApply指定的函数指针 void HashTable_map( HashTable_t oHashTable, void (*pfApply)( const char* pcKey, const void* pvValue, void* pvExtra), const void* pvExtra ) { assert( oHashTable ); assert( pfApply ); assert( pvExtra ); unsigned long uiBucketCount = oHashTable->uiBucketCount; int i = 0; if ( HashTable_getLength( oHashTable) == 0) return; for ( i = 0; i< uiBucketCount; i++) { ListAssociation* pListAssociation = oHashTable->bucketTable[i]; if (pListAssociation == NULL) continue; ListNode* pListNode = pListAssociation->head_node; while (pListNode) { assert( pListNode->key); assert( pListNode->value); pfApply( pListNode->key, pListNode->value, (void*)pvExtra ); pListNode = pListNode->next; } } return; } //将哈希表原有的元素项的值替换成新值pvValue,并返回旧值,如果该元素项不存在,则返回NULL void* HashTable_replace( HashTable_t oHashTable, const char* pcKey, const void* pvValue) { assert( oHashTable ); assert( pcKey ); void* value = NULL; ListNode* pListNode = HashTable_getListNode( oHashTable, pcKey); if ( pListNode ) { value = pListNode->value; pListNode->value = (void*)pvValue; } return value; } //在哈希表中,给定元素的符号名,删除该指定元素项 void* HashTable_remove( HashTable_t oHashTable, cosnt char* pcKey) { assert( oHashTable ); assert( pcKey ); ListAssociation* pListAssociation = HashTable_getListAssociation( oHashTable, pcKey); if (pListAssociation == NULL) return NULL; void* value = NULL; ListNode* temp = pListAssociation->head_node; ListNode* pre_node = NULL; //如果哈希后得到位置处没有有效信息,则可以直接返回 if (temp = NULL) return NULL; //如果哈希后位置处有信息,则需要遍历该处的具体链表,查找到匹配的”符号名“ //1. 链表首项就是要查找的元素项,则需要额外处理,因为涉及到pListAssociation->head_node等组织信息的更新 if( strcmp(pcKey, temp->key) == 0) { value = temp->value; pListAssociation->head_node = temp->next; free(temp->value); free(temp->key); free(temp); pListAssociation->uiNodeLength = pListAssociation->uiNodeLength - 1; oHashTable->uiBindingsCount = oHashTable->uiBindingsCount - 1; return value; } while (1) { pre_node = temp; temp = temp->next; if (temp == NULL) return NULL; if ( strcmp(pcKey, temp->key) == 0 ) { pre_node->next = temp->next; //链条串起来不能断 if ( temp == pListAssociation->tail_node ) pListAssociation->tail_node = pre_node; value = temp->value; free( temp->key ); free( temp->value); free( temp ); pListAssociation->uiNodeLength = pListAssociation->uiNodeLength - 1; oHashTable->uiBindingsCount = oHashTable->uiBindingsCount - 1; return value; } } return NULL; } static void* MyAlloc( unsigned long size ) { void* temp = (void*) malloc( size*sizeof(char) ); assert(temp); return temp; } //给定元素项的“符号名”,返回哈希后该元素项在哈希表中下表位置 static ListAssociation* HashTable_getListAssociation( HashTable_t oHashTable, const char* pcKey) { assert( oHashTable); assert( pcKey); if ( strlen(pcKey) == 0) return NULL; int iHash_key = -1; iHash_key = HashTable_hash( pcKey, oHashTable->uiBucketCount ); assert( iHash_key >= 0); return oHashTable->bucketTable[iHash_key]; } //应对哈希冲突,如果同样的哈希值处存在多个元素项,则采用链表方式组织,故而针对具体的符号名需要二次操作 //1. 将符号名哈希后得到下标位置; 2.在下标位置上遍历链表进一步找到匹配的符号名项 static ListNode* ListAssociation_getListNode( const ListAssociation* pListAssociation, const char* pcKey) { assert( pListAssociation ); assert( pcKey ); if (strlen(pcKey) == 0) return NULL; ListNode* pListNode = pListAssociation->head_node; while ( pListNode ) { if ( strcmp( pcKey, pListNode->key ) == 0 ) return pListNode; pListNode = pListNode->next; } return NULL; } //在具体哈希值链条上插入元素,如果该元素原先存在,则直接返回0;如果不存在则新建项,并插入链表中,并返回1 static int ListAssociation_put( ListAssociation* pListAssociation, const char* pcKey, const void* pvValue ) { assert( pListAssociation ); assert( pcKey ); assert( pvValue ); if (ListAssociation_getListNode( pListAssociation, pcKey )) return 0; else { ListNode* new_node = (ListNode*)MyAlloc( sizeof(ListNode) ); assert(new_node); char* key = (char*)MyAlloc( strlen( pcKey) + 1); if (key == NULL) { free(new_node); return 0; } new_node->key = key; strcpy( new_node->key, pcKey ); new_node->value = (void*)pvValue; if ( pListAssociation->uiNodeLength == 0) { pListAssociation->head_node = new_node; pListAssociation->tail_node = new_node; pListAssociation->uiNodeLength = 1; return 1; } else { pListAssociation->tail_node->next = new_node; pListAssociation->tail_node = new_node; pListAssociation->uiNodeLength += 1; return 1; } } } static ListNode* HashTable_getListNode( HashTable_t oHashTable, const char* pcKey) { assert( oHashTable ); assert( pcKey ); if (strlen(pcKey) == 0) return NULL; ListAssociation* pListAssociation = NULL; if (HashTable_getLength( oHashTable) == 0) return NULL; pListAssociation = HashTable_getListAssociation( oHashTable, pcKey); if (pListAssociation == NULL) return NULL; return ListAssociation_getListNode( pListAssociation, pcKey); } static int Rehash( HashTable_t oHashTable ) { assert( oHashTable ); assert( oHashTable->uiBindingsCount >= oHashTable->uiBucketCount ); giBucketCountIndex = GetBucketSizeIndex( oHashTable->uiBucketCount ); assert( giBucketCountIndex >= 0); if ((ARRAY_SIZE-1) == giBucketCountIndex ) return 1; giBucketCountIndex++; unsigned long uiBucketCounts = kBucketCount[giBucketCountIndex]; struct ListAssociation** pNewListAssociation = NULL; pNewListAssociation = ( ListAssocaition**)MyAlloc( uiBucketCounts * sizeof( ListAssocaition*) ); if (pNewListAssociation == NULL) return 0; //将原先哈希表中的内容进行整体搬迁,由于并无时间序上的要求,故而搬迁时对于不同节点的先入先出顺序并无特殊要求 unsigned long uiOldBucketCount = oHashTable->uiBucketCount; unsigned long i = 0; for( ; i < uiOldBucketCount; i++ ) { struct ListAssociation* pOldListAssociation = NULL; pOldListAssociation = oHashTable->bucketTable[i]; if ( pOldListAssociation == NULL ) continue; ListNode* pTempListNode = pOldListAssociation->head_node; while ( pTempListNode ) { int iHash_key = -1; iHash_key = HashTable_hash( pTempListNode->key, uiBucketCounts ); assert( iHash_key >= 0 ); ListAssocaition* pListAssociation = pNewListAssociation[iHash_key]; if ( pListAssociation == NULL) { pListAssociation = (ListAssocaition*)MyAlloc( sizeof(ListAssocaition) ); if (pListAssociation == NULL) return 0; pNewListAssociation[iHash_key] = pListAssociation; } pOldListAssociation->head_node = pOldListAssociation->head_node->next; if (ListAssociation_put_help_rehash( pListAssociation, pTempListNode ) == 0) return 0; pTempListNode = pOldListAssociation->head_node; } free( pOldListAssociation ); pOldListAssociation = NULL; } free( oHashTable->bucketTable ); //将哈希表的新的组织信息更新 oHashTable->bucketTable = pNewListAssociation; oHashTable->uiBucketCount = uiBucketCounts; //oHashTable->uiBindingsCount代表当前有效链表数目,不变 return 1; } //该函数时配合rehash函数的,出于的目的主要是重复利用原有的元素项,而不需要重新分配 static int ListAssociation_put_help_rehash( ListAssocaition* pListAssociation, ListNode* pListNode ) { assert( pListAssociation ); assert( pListNode ); assert( pListAssociation->uiNodeLength >= 0 ); //如果该链表已经存在该同符号名元素项,则返回 if ( ListAssociation_getListNode( pListAssociation, pListNode->key) ) return 0; else { //如果链表是空,则 if (pListAssociation->uiNodeLength == 0) { pListAssociation->head_node = pListNode; pListAssociation->tail_node = pListNode; pListAssociation->tail_node->next = NULL; pListAssociation->uiNodeLength = 1; return 1; } else { pListAssociation->tail_node->next = pListNode; pListAssociation->tail_node = pListNode; pListNode->next = NULL; pListAssociation->uiNodeLength += 1; return 1; } } } static int GetBucketSizeIndex( unsigned long uiBucketCounts ) { int i = 0; for ( i=0; i < ARRAY_SIZE; i++) { if (uiBucketCounts == kBucketCount[i]) { giBucketCountIndex = i; return giBucketCountIndex; } } return -1; }
更多相关内容 -
C语言设计哈希表实现图书查找
2020-10-26 20:19:01C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成... -
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。c语言课设
2022-01-02 12:51:24设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希... -
C语言基于哈希表实现通讯录
2020-08-27 23:58:11主要为大家详细介绍了C语言基于哈希表实现通讯录,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
哈希表实现通讯录
2018-01-23 12:11:22(1)每个人的信息至少包括姓名,...(2)假设人名为汉语拼音全拼形式,待插入哈希表的长度为你所在班级的人数。哈希函数用除留余数法构造,采用链地址法或二次探测再散列法解决冲突。 (3)完成菜单设计。操作有必要的提示。 -
《数据结构课程设计》设计哈希表实现电话号码查找系统
2022-06-02 17:57:36问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法... -
C语言基于哈希表实现通讯录.doc
2021-08-20 18:36:33C语言基于哈希表实现通讯录--附源码 -
C++ 实现哈希表的实例
2020-08-29 13:58:28主要介绍了C++ 实现哈希表的实例的相关资料,这里使用C++实现哈希表的实例帮助大家彻底理解哈希表的原理,需要的朋友可以参考下 -
150-链式哈希表实现
2022-05-05 00:41:38C++、Java无序关联容器底层采用链式哈希表实现。 为什么不采用线性探测哈希表? 如果采用线性探测哈希表,缺陷是: 2、发生哈希冲突时,需要从当前发生哈希冲突的位置向后不断的去找,找到第一个空闲的位置把元素...C++、Java无序关联容器底层采用链式哈希表实现。
为什么不采用线性探测哈希表?
如果采用线性探测哈希表,缺陷是:-
2、发生哈希冲突时,需要从当前发生哈希冲突的位置向后不断的去找,找到第一个空闲的位置把元素放上,这个过程的时间复杂度就趋近于O(n)了,存储变慢了,查询和删除也变慢,哈希冲突的发生越严重,就越靠近O(n)的时间复杂度,这个时间复杂度能否优化?哈希冲突是无法避免的,但是发生哈希冲突以后,在进行增删查的时候,能不能把时间效率提高一点,不让它趋近于O(n)的时间复杂度呢?不能,因为它是一个线性表,是数组,得环形遍历,趋近于O(n),按一个位置一个位置找,找的越多,时间复杂度就靠近O(n),这个是无法优化的,因为只有这么一个数组的结构。这个问题在线性哈希表中,无法优化,但是在链式哈希表中是可以优化的!
-
2、在多核盛行的情况下,非常方便的使用并发程序(多线程,多进程),在多线程环境中,有线程安全的问题,**多个线程能不能同时在一个数组中进行数据的增删查呢?肯定是不可以的!!!**在C++的所有容器都不是线程安全的,所以我们必须添加线程的互斥操作,互斥锁,读写锁,自旋锁,然后在多线程下对容器的添加修改删除做互斥操作,保证这些容器在多线程环境下操作它都是一个原子操作。同样的,线性哈希表作为一个数组,没有办法去一边修改一边查询的,或者一边删除一边查询。
-
很明显,在线性哈希表中,往数组增加一个元素,又要通过除留余数法计算哈希值,发生哈希冲突了,又要遍历数组找到一个空闲的位置放,这么多的操作能是一个原子操作吗?肯定不能是一个原子操作,这步骤太多了。
-
在多线程环境中,线性探测所用到的基于数组实现的哈希表只能给全局的表用互斥锁来保证哈希表的原子操作,保证线程安全。
-
(因为线性探测只有一个数组,得把整个数组锁起来,也就是说,多个线程,对同1个数组操作,如果多个线程对这个数组添加的元素是不在同一个位置上的,理论来说,应该可以并发运行,实际上不能让他们并发,因为有可能多个线程,你要放在3位置,我要放在4位置,然后3和4位置原本已经有元素了,你和我就都发生哈希冲突了,都要向后找第一个空闲的位置,如果我和你同时找到了1号位置,如果我和你都认为1号位置是空闲,都放元素进去,后放的那个元素把先放的元素给覆盖掉了,这就有问题了!!!)
-
所以,我们给整个哈希表加锁了,要么你先操作,要么我先操作。(不具备并发能力)
但是,链式哈希表在多线程环境下可以采用分段的锁,既保证了线程安全,又有一定的并发量,提高了效率。
当然,我们库里的无序关联容器并没有实现多线程环境中的线程安全问题,也就是并没有去加锁,但是毫不妨碍当我们真真正正想实现一个线程安全,运行在多线程环境下的一个基于哈希表实现的无序关联容器,我们在代码上就可以通过分段锁来实现!链式哈希表
1、增加元素
我们要把下面这一行数据放到链式哈希表中:
我们使用的哈希函数还是除留余数法。解决哈希冲突的方法是链地址法
除留余数法为了解决哈希冲突,建议所采用的数组的元素个数是素数个, 除了1和自己,不会被其他数字整除 ,尽量避免余数产生冲突这个哈希表的下标是0-6,和线性哈希表一样,只不过现在这个是竖着放的,12%7=5,把12放在数组下标是5的位置
链式哈希表在解决哈希冲突时,就不向后遍历探测了,而是在这个桶里边生成一个数据结构:链表
这个链表的节点存储的是元素值和next指针,把发生哈希冲突的元素都串在一个链表上
18%7=4,把18串在下标为4的桶的链表上
21%7=0 把21放在0号位置
24%7=3 把24放在3号位置
以此类推。
链式哈希表,一维数组是没有变的,每个元素是一个桶,但是这个桶存储的是链表发生哈希冲突的时候,不会像线性哈希表那样往其他桶跑,通过哈希函数算出在哪个桶,就是在哪个桶,这个桶放的是链表,采用尾插或者头插把这个元素插进链表里。
2、元素搜索
- 如果你要搜索21的话,先通过哈希函数-除留余数法,21%7=0,我们就去0号桶里查。
- 当这个链式哈希表里的每个桶的链表比较长时,链表搜索花费的时间就大,节点越多,时间复杂度就趋近于O(n)
- 当然,我们也不会放任这种情况的。链式哈希表也有装载因子。已占用桶的个数如果达到占总的桶个数的0.75,哈希表就要进行扩容了。
3、删除元素
- 先搜,搜到再删除;
- 先拿原始的数据模上7,得出余数,知道在哪个桶放,这个操作时间复杂度是O(1);
- 然后在这个桶里的链表去找到这个元素的节点,然后删除这个节点。
这个链式哈希表不能出现这种情况:
- 其他的桶都是空的,然后其中一个桶的链表特别特别长,好像都挤到一个桶里去了,这说明选择的哈希函数不好或者自己创建的哈希函数太差了,没有办法把原始的数据通过哈希函数的映射离散开来。
- 我们需要的哈希函数是尽量把数据离散开,散列结果越离散越好,就可以均匀的分配在桶中 。
- 所以,我们一般把除留余数法,桶的个数取成素数,这样才会让散列的结果产生最少的冲突,所有的数据不会集中在一个或者几个桶中,而是离散开来,提高了整体哈希表的效率。
链式哈希表的增删查时间复杂度: 无限趋近于O(1) ,因为哈希冲突的存在。
4、链式哈希表的优化
优化1:链表转化为红黑树
红黑树每个节点占用的内存要比链表大,因为里面存储的信息更多。优化2:使用分段式锁,并发操作
在多线程环境中,我们在每个桶添加一把锁就可以保证线程安全,(分段锁),每把锁控制各自桶的链表的多线程下的并发操作就可以了。
不同桶里的链表可以并发操作。同一个桶里的链表不能并发操作,因为有锁。
5、链式哈希表代码
注意:- swap只是交换了两个vector的成员变量,并没有交换堆内存和表数据;
- vector中的成员变量都是指针;
- 比如说一个容器是从内存池取出的内存进行管理,一个容器是普通的释放内存free方法。这样就不能简单的成员变量交换了。
#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std; //链式哈希表 class HashTable { public: HashTable(int size = primes_[0], double loadFactor = 0.75)//构造函数 : useBucketNum_(0) , loadFactor_(loadFactor) , primeIdx_(0) { if (size != primes_[0]) { //调整素数 for (; primeIdx_ < PRIME_SIZE; primeIdx_++) { if (primes_[primeIdx_] >= size) break; } if (primeIdx_ == PRIME_SIZE) { primeIdx_--; } } table_.resize(primes_[primeIdx_]); } public: //增加元素 不能重复插入key void insert(int key) { //判断扩容 double factor = useBucketNum_ * 1.0 / table_.size(); cout << "factor:" << factor << endl; if (factor > loadFactor_) { expand(); } int idx = key % table_.size();//O(1) if (table_[idx].empty()) //只需要在桶里面放第一个元素时进行++; { useBucketNum_++; table_[idx].emplace_front(key);//头插法 } else //原来这个桶后面就有元素,我们要实现不能重复插入key { //使用全局的::find泛型算法,而不是调用自己的成员方法find,要去重 auto it = ::find(table_[idx].begin(), table_[idx].end(), key);//O(n) if (it == table_[idx].end()) { //key不存在 table_[idx].emplace_front(key); } } } //删除元素 void erase(int key) { int idx = key % table_.size();//O(1) // 如果链表节点过长:如果散列结果比较集中(散列函数有问题!!!) // 如果散列结果比较离散,链表长度一般不会过长,因为有装载因子 auto it = ::find(table_[idx].begin(), table_[idx].end(), key);//O(n) if (it != table_[idx].end()) { table_[idx].erase(it); //删完之后看桶是不是空的 if (table_[idx].empty()) { useBucketNum_--; } } } //搜索元素 bool find(int key) { int idx = key % table_.size();//O(1) auto it = ::find(table_[idx].begin(), table_[idx].end(), key); return it != table_[idx].end(); } private: //扩容函数 void expand() { if (primeIdx_ + 1 == PRIME_SIZE) { throw "hashtable can not expand anymore!"; } primeIdx_++; useBucketNum_ = 0; vector<list<int>> oldTable; //swap会不会效率很低??? //swap效率是非常高的,因为它只是交换了两个容器的成员变量,没有交换堆内存和表数据 table_.swap(oldTable);//table成了空的内容,oldtable存储旧的哈希表内容 table_.resize(primes_[primeIdx_]);//扩容 for (auto list : oldTable) { for (auto key : list)//能进来这个for循环说明这个链表是有数据的 { int idx = key % table_.size(); if (table_[idx].empty()) { useBucketNum_++; //只需要在桶里面放第一个元素时进行++; } table_[idx].emplace_front(key); } } } private: vector<list<int>> table_;//哈希表的数据结构 int useBucketNum_;//记录已使用的桶的个数 double loadFactor_;//记录哈希表装载因子 static const int PRIME_SIZE = 10;//素数表的大小 static int primes_[PRIME_SIZE];//素数表 int primeIdx_;//当前使用的素数下标 }; int HashTable::primes_[PRIME_SIZE] = { 3, 7, 23, 47, 97, 251, 443, 911, 1471, 42773 }; int main() { HashTable htable; htable.insert(21); htable.insert(32); htable.insert(14); htable.insert(15); htable.insert(22); htable.insert(67); cout << htable.find(67) << endl; htable.erase(67); cout << htable.find(67) << endl; return 0; }
-
-
哈希表实现
2013-05-05 23:33:16哈希表实现,对初学者很有用。 //这个hash实现,解决key冲突的方法是链开地址法 //如下图所示 /* ------ 0 | ptr-|--->hash_node[0]->hash_node[1] ------ 1 | | ------ 2 | | ------ 3 | ptr-|--->hash_node[0... -
python 哈希表实现简单python字典代码实例
2020-09-18 14:44:45主要介绍了python 哈希表实现简单python字典代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 -
哈希表的c语言实现1
2019-03-01 16:29:42哈希表的哈希取余法和链表地址法来实现哈希表的基本操作。。。 -
哈希表实现电话号码查询系统方案.doc
2021-09-25 18:16:44哈希表实现电话号码查询系统方案.doc -
哈希表的实现
2018-12-21 10:31:25hash表的简单实现 数据结构初学 对于这里希望留下一些资源 期待大家批评指正 -
哈希表底层实现
2021-01-20 13:46:03哈希表使用数组作为主干,实现查找,插入,删除元素的时间复杂度为O(1)。 哈希表(key,value) 就是把Key通过一个固定的算法函数既哈希函数转换成一个整型数字,然后将该数字对数组长度进行取余,取余结果就当作数组... -
哈希表实现号码查询
2011-12-26 11:40:52简单利用哈希表实现电话号码的查询,我们学校数据结构的课程设计。 -
哈希表实现电话号码查找系统
2020-06-05 13:48:01设计任务 设计哈希表实现电话号码查找系统 设每个记录有下列数据项:电话号码、用户名、地址 从键盘输入个记录,分别以电话号码和用户名为关键字建立不同的哈希表 采用线性探测再散列的方法解决冲突 查找并显示给定...设计任务
设计哈希表实现电话号码查找系统
- 设每个记录有下列数据项:电话号码、用户名、地址
- 从键盘输入个记录,分别以电话号码和用户名为关键字建立不同的哈希表
- 采用线性探测再散列的方法解决冲突
- 查找并显示给定电话号码的记录
- 查找并显示给定用户名的记录
主要算法功能
主要4个功能:
- 创建链表
- 查询(通过名字/电话)
- 显示
- 退出
以下是简易流程图:
代码
为了让主代码main.c看起来更加清晰,我把功能函数集成在一个头文件中hash.h。
代码里用不大好的英文注释,能懂9行
main.c文件
#include"hash.h" int main() { char s[20]; int n,Fn; int num;//contact number Bridge head;//include namehash table and phonehash table while(1) { Menu(); printf("Enter:"); scanf("%d",&n); switch(n) { case 1: printf("Enter number of contacts:"); scanf("%d",&num); Fn=Fprime(num);//get next prime head=Create(num);//creat link Clean(); break; case 2: Query(head,Fn); Clean(); break; case 3: ShowAll(head,Fn);//print all contacts Clean(); break; case 4: printf("\nThank you for using my software!\n"); return 0; } } }
hash.h文件
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #define MAXNUMBER 100000 typedef struct node { char name[8]; char phone[12]; char adress[50]; int state; struct node *next; }contnode; typedef struct { contnode *Hn;//head node of name contnode *Hp;//head node of phone }Bridge; void Menu() { printf("\n----------Menu----------\n\n"); printf(" 1.Create contacts\n"); printf(" 2.Query contacts\n"); printf(" 3.Show all contacts\n"); printf(" 4.Exit\n"); printf("------------------------\n"); } void Clean()//clear window { printf("\nClear window? (Y/N)\t"); getchar();//filter \n if(getchar()=='Y') system("cls"); } void ShowAll(Bridge h,int n)//show all contacts { contnode *p=h.Hp; printf("\nName\tPhone\t\tAdress"); printf("\n--------------------------------------\n"); while(n--) { if(p->state==1) printf("%s\t%s\t%s\n",p->name,p->phone,p->adress); p=p->next; } } int Fprime(int n)//find next prime { int i,p=(n%2)?n+2:n+1; while(p<=MAXNUMBER) { for(i=(int)sqrt(p);i>2;i--) if(!(p%i)) break; if(i==2) break; else p+=2; } return p; } contnode* CreatTable(int num)//insert tail & init { contnode *p,*q,*h; q=p=h=(contnode*)malloc(sizeof(contnode)); h->state=0; while(num--) { p=(contnode*)malloc(sizeof(contnode)); strcpy(p->name,"\0"); strcpy(p->adress,"\0"); strcpy(p->phone,"\0"); p->state=0; q->next=p; q=p; } p->next=NULL; free(p); free(q); return h; } int Ghashn(char *key,int num)//get hash name number { unsigned int h=0; while(*key!='\0') h=(h<<5)+*key++; return h%num; } int Ghashp(char *key,int num)//get hash phone number { int i; int sum=0; for(i=6;i<=10;i++) sum=sum*10+key[i]-'0'; return sum%num; } void HashTable(char *name,char *phone,char *adress,contnode *h,int flag,int size)//create table { int seat; contnode *p=h; if(flag) seat=Ghashp(phone,size); else seat=Ghashn(name,size); while(seat&&seat--)//Go to the designated location p=p->next; while(p->state!=0)//Linear Probing(if state==1 ,find the next one) { if(p->next==NULL) { p=h; continue; } p=p->next; } strcpy(p->name,name); strcpy(p->adress,adress); strcpy(p->phone,phone); p->state=1; } void show(contnode *n)//print the contact { printf("\nName\tPhone\t\tAdress"); printf("\n--------------------------------------\n"); printf("%s\t%s\t%s\n",n->name,n->phone,n->adress); } void FindSeat(contnode *h,int size,int flag)//find seat of number { char key[15]; int seat,bseat,f=1; contnode *p=h; printf("\nEnter key:"); scanf("%s",key); if(flag) seat=Ghashp(key,size);//find table number of phone else seat=Ghashn(key,size);//find table number of name bseat=seat; while(seat>0&&--seat) p=p->next; if(flag) while(strcmp(p->phone,key)!=0) { if(p->next==NULL)//If to the end back to the head { f=1; p=h; } if(f) bseat++; if(bseat>=size)//If steps are larger than size return { printf("\nSorry,not found!\n"); return; } p=p->next; } else while(strcmp(p->name,key)!=0) { if(p->next==NULL) { f=1; p=h; } if(f) bseat++; if(bseat>=size) { printf("\nSorry,not found!\n"); return; } p=p->next; } show(p);//print node } Bridge Create(int num) { int i; contnode *Hp,*Hn; Bridge h; char name[8],adress[20],phone[12]; Hp=CreatTable(Fprime(num));//get head node Hn=CreatTable(Fprime(num)); for(i=0;i<num;i++) { printf("\n%dst contact:",i+1); printf("\nEnter name:"); scanf("%s",name); printf("Enter phone:"); scanf("%s",phone); printf("Enter adress:"); scanf("%s",adress); HashTable(name,phone,adress,Hn,0,Fprime(num));//create hashtable by name HashTable(name,phone,adress,Hp,1,Fprime(num));//create hashtable by phone } h.Hn=Hn; h.Hp=Hp; return h; } void Query(Bridge head,int size) { int n; printf("\n-------Choose way-------\n"); printf("1.By Name\n"); printf("2.By Phone\n"); printf("------------------------\n"); printf("Enter:"); scanf("%d",&n); switch(n) { case 1:FindSeat(head.Hn,size,0); break; case 2:FindSeat(head.Hp,size,1); break; } }
-
哈希表实现通讯录的设计与实现
2022-03-15 19:36:57设计哈希表存储,设计并实现通讯录查找系统。 【实验要求】 (1)每个员工记录有下列数据项:电话号码、用户名、地址,可以适当再增加数据项;员工数据保存在employee.txt文件里。 (2)从employee.txt文件读取数据...【实验目的】
为某个单位建立一个员工通讯录管理系统,可以方便查询每一个员工的电话与地址。设计哈希表存储,设计并实现通讯录查找系统。
【实验要求】
(1)每个员工记录有下列数据项:电话号码、用户名、地址,可以适当再增加数据项;员工数据保存在employee.txt文件里。
(2)从employee.txt文件读取数据,分别以用户名、电话号码为关键字建立哈希表;
(3)哈希函数采用除留余数法,解决冲突采用二次探测再散列法;
(4)对通讯录进行添加、删除、修改、浏览、查找等操作,每进行一项操作后将内存中的数据写入到文件中。
(5)记录操作者的操作内容和当地时间并记录到当前文件夹下的Log.dat文件中(为方便查看,博主用的Log.txt文件)。【主要功能】
(1)从文件employee.txt输入数据,初始化
(2)添加一个员工数据
(3)查找员工
(4)按姓名或电话号码定位员工,返回数据的地址
(5)删除一个员工
(6)保存内存中的数据到文件中
(7)按姓名查找员工
(8)按电话号码查找员工
(9)显示所有员工的数据
(10)显示指定员工数据
(11)更改员工数据
(12)更改员工的指定数据
(13)显示原员工信息和新员工信息,判断是否修改
(14)菜单显示
(15)获得系统时间,记录日志时使用
(16)将操作日志保存到文件Log.dat中【参考程序】
header.h
/***************************************************************** * 版权所有(C)2022 浅笑醉红楼 * * 文件名称:header.h * 内容摘要:哈希表的基本操作 * 其他说明:无 * 当前版本:1.0 * 作者:浅笑醉红楼 ****************************************************************/ /*------------------头文件引用------------------*/ #include <stdio.h> #include <string.h> #include <stdlib.h> /*------------------头文件引用------------------*/ /**************************相关宏定义**************************/ #define Hashsize 50/*哈希表长*/ #define DELEFLAG -1/*删除标志*/ /**************************相关宏定义**************************/ /************************相关结构体定义************************/ typedef struct{ char add[50];/*员工地址*/ long int num;/*员工电话号码*/ char name[10];/*员工姓名*/ int key;/*关键字*/ } Datatype; typedef struct{ Datatype data;/*数据域*/ int times;/*比较次数*/ }HashTable[Hashsize]; /************************相关结构体定义************************/ /*----------------------------------------函数的声明----------------------------------------*/ void CreatHash(HashTable ht, Datatype items[], int n); /*创建Hash表*/ int HashInsert(HashTable ht, Datatype x); /*哈希表插入*/ int HashDelete(HashTable ht, Datatype x); /*哈希表删除*/ int HashSearch(HashTable ht, Datatype x); /*哈希表查找*/ int Collision(int d); /*线性探测处理冲突*/ int Collision2(int d, int i); /*平方探测处理冲突*/ int HashFunc(int num); /*除留余数法构造哈希函数*/ int Getkey(Datatype x); /*直接定址法获取名字的哈希地址*/ int Getkeyn(Datatype x); /*直接定址法获取电话号码的哈希地址*/ /*----------------------------------------函数的声明----------------------------------------*/ /** * @brief 创建哈希表 * @param ht:哈希表 items:关键字序列 n:关键字个数 * @retval 无 */ void CreatHash(HashTable ht, Datatype items[], int n) /*创建哈希表*/ { int i; for(i = 0; i < Hashsize; i++)/*初始化哈希表*/ { ht[i].data.key = 0; ht[i].times = 0; } for(i = 0; i < n; i++) { HashInsert(ht, items[i]);/*依次向哈希表中插入元素*/ } } /** * @brief 哈希表插入 * @param ht:哈希表 x:插入数据元素 * @retval 插入成功,返回1 */ int HashInsert(HashTable ht, Datatype x) /*哈希表插入*/ { int addr; addr = HashSearch(ht, x);/*在哈希表中查找*/ if(addr > 0)/*找到,不必插入*/ { return 0; } ht[-addr].data = x;/*没有找到,则插入*//*-addr是因为上面返回的是-addr,故这儿是-addr(哈希地址不能为负)*/ ht[-addr].times = 1; ht[-addr].data.key = 1; return 1; } /** * @brief 哈希表的删除 * @param ht:哈希表 x:删除数据元素 * @retval 成功返回1,失败返回0 */ int HashDelete(HashTable ht, Datatype x)/*哈希表的删除*/ { int addr; addr = HashSearch(ht, x);/*查找数据元素*/ if(addr >= 0)/*找到,打上删除标记*/ { ht[addr].data.key = -1;/*删除*/ return 1;/*删除成功返回1*/ } return 0;/*删除失败返回0*/ } /** * @brief 哈希表的查找 * @param ht:哈希表 x:查找元素 * @retval 查找成功返回addr,失败返回-addr */ int HashSearch(HashTable ht, Datatype x)/*哈希表的查找*/ { int addr; x.key = Getkey(x);/*获取键值*/ addr = HashFunc(x.key);/*获得哈希地址*/ x.key = 1; while(ht[addr].data.key != 0 && ht[addr].data.key != x.key)/*地址不为空或循环回到原点未找到查找元素,则冲突*/ { addr = Collision(addr);/*没找到,处理冲突*/ } if(ht[addr].data.key == x.key) { return addr;/*查找成功*/ } else { return -addr;/*查找失败*/ } } /** * @brief 线性探测处理冲突 * @param d:探查位置 * @retval 返回空闲的位置 */ int Collision(int d)/*线性探测处理冲突*/ { return(d + 1) % Hashsize;/*返回哈希地址*/ } /** * @brief 平方探测处理冲突 * @param d:探查位置 i:探测次数 * @retval 返回空闲的位置 */ int Collision2(int d, int i)/*平方探测处理冲突*/ { return (int)(d + pow(-1, i - 1) * i * i) % Hashsize;/*返回哈希地址*/ } /** * @brief 除留余数法构造哈希函数 * @param key:关键字 * @retval 返回余数为散列地址 */ int HashFunc(int key)/*除留余数法构造哈希函数*/ { return key % Hashsize;/*模为50取余*/ } /** * @brief 直接定址法获取名字的哈希地址 * @param x:哈希地址 * @retval 返回名字哈希地址 */ int Getkey(Datatype x)/*直接定址法获取名字的哈希地址*/ { int i, key = 0; for (i = 0; i< 10; i++) { key = key + x.name[i];/*以数据元素关键字k本身或它的线性函数作为它的哈希地址*/ } key = -key; return key; } /** * @brief 直接定址法获取名字的哈希地址 * @param x:哈希地址 * @retval 返回电话号码哈希地址 */ int Getkeyn(Datatype x)/*直接定址法获取电话号码的哈希地址*/ { int key = 0; long int z = x.num; while (z != 0) { key = key + z % 10;/*以数据元素关键字k本身或它的线性函数作为它的哈希地址*/ z = z / 10; } return key; }
hash.c
/************************************************ * 版权所有(C) 2022 浅笑醉红楼 * * 文件名称:hash.cpp * 内容摘要:实现通讯录的显示、增加、查找、删除、修改等功能 * 其他说明:无 * 当前版本:1.0 * 作者:浅笑醉红楼 *************************************************/ /*------------------头文件引用------------------*/ #include <stdio.h> #include <string.h> #include <stdlib.h> #include "header.h" #include <conio.h> /*------------------头文件引用------------------*/ /*----------------------------------------函数的声明----------------------------------------*/ void Displaymanu(HashTable ht, int n); /*主菜单*/ void SJXR(HashTable ht); /*数据写入*/ int SJDQ(HashTable ht); /*数据读取*/ void add(HashTable ht, int n); /*数据增加*/ void Delet(HashTable ht, int n); /*数据删减*/ void change(HashTable ht, int n); /*数据修改*/ int Search(HashTable ht, int n); /*数据查找*/ void display(HashTable ht, int n); /*显示所有员工数据*/ void fanhui(HashTable ht, int n); /*退出函数*/ /*----------------------------------------函数的声明----------------------------------------*/ void main() /*主函数*/ { HashTable ht; int n; n = SJDQ(ht); Displaymanu(ht, n); } void Displaymanu(HashTable ht, int n)/*主菜单*/ { int choose; FILE* fp1;/*定义操作日志记录文件*/ fp1 = fopen("Log.txt", "a");/*打开日志记录文本文件(“a”打开或新建一个文本文件,只允许在文件末尾追写,即只能增加不能删除)*/ if (fp1 == NULL)/*打开文件失败*/ { printf("打开文件出错!"); } system("cls");/*清屏操作*/ SJDQ(ht);/*员工数据读取*/ /*-----------------------------人机交互-----------------------------*/ printf("********************************************************\n"); printf("* 菜单 *\n"); printf("*1、增加员工信息 2、删除员工信息 *\n"); printf("*3、修改员工信息 4、查找员工信息 *\n"); printf("*5、打印所有员工信息 6、退出程序 *\n"); printf("********************************************************"); /*-----------------------------人机交互-----------------------------*/ printf("\n请输入序号来进行下一步操作:"); scanf_s("%d", &choose);/*键盘输入功能选择*/ switch(choose)/*功能选择*/ { case 1: /*增加*/ fprintf(fp1, "【%s】 %s %s\t\n", __DATE__, __TIME__, "增加员工信息");/*日志文件输出*/ printf("【%s】 %s %s\t\n", __DATE__, __TIME__, "增加员工信息"); add(ht, n); break; case 2: /*删除*/ fprintf(fp1, "【%s】 %s %s\t\n", __DATE__, __TIME__, "员工删除");/*日志文件输出*/ printf("【%s】 %s %s\t\n", __DATE__, __TIME__, "员工删除"); Delet(ht, n); break; case 3: /*修改*/ fprintf(fp1, "【%s】 %s %s\t\n", __DATE__, __TIME__, "修改员工信息");/*日志文件输出*/ printf("【%s】 %s %s\t\n", __DATE__, __TIME__, "修改员工信息"); change(ht, n); break; case 4: /*查找*/ fprintf(fp1, "【%s】 %s %s\t\n", __DATE__, __TIME__, "查找员工信息");/*日志文件输出*/ printf("【%s】 %s %s\t\n", __DATE__, __TIME__, "查找员工信息"); Search(ht, n); break; case 5: /*显示*/ fprintf(fp1, "【%s】 %s %s\t\n", __DATE__, __TIME__, "打印所有员工信息");/*日志文件输出*/ printf("【%s】 %s %s\t\n", __DATE__, __TIME__, "打印所有员工信息"); fclose(fp1); display(ht, n); /*哈希显示函数*/ break; case 6: /*退出*/ exit (0); } Displaymanu(ht, n); /*主菜单*/ } /** * @brief 数据读取 * @param ht:哈希表 * @retval 返回文件读取个数 */ int SJDQ(HashTable ht)/*数据读取*/ { Datatype Hl[Hashsize];/*定义哈希表长度*/ int n = 0; FILE* fp; /*定义员工信息文本文件*/ fp = fopen("employee.txt", "r");/*打开文本文件*/ if(fp == NULL)/*打开文件失败*/ { printf("文件打开失败"); return -1; } while(fscanf(fp, "%s %d %s", &Hl[n].name, &Hl[n].num, &Hl[n].add) == 3)/*读取文本数据*/ { n++; } fclose(fp);/*关闭文件*/ CreatHash(ht, Hl, n);/*根据关键字个数n创建哈希表*/ return n; } /** * @brief 员工数据增加 * @param ht:哈希表 n:增加员工个数 * @retval 无 */ void add(HashTable ht, int n)/*数据增加*/ { Datatype x; int addr, i; printf("请输入增加员工信息:\n"); printf("请依次输入姓名,电话,地址:\n"); scanf_s("%s %d %s", &x.name,10, &x.num, &x.add,50); addr = HashSearch(ht, x);/*在哈希表中查找*/ if(addr < 0)/*没找到,则插入*/ { i = HashInsert(ht, x);/*哈希插入*/ printf("*****员工信息增加成功!*****\n"); } else { printf("已有数据,请重新输入\n");/*找到,不必插入*/ add(ht, n);/*再次调用数据增加函数*/ } SJXR(ht);/*数据写入*/ fanhui(ht, n);/*退出此段程序*/ } /** * @brief 员工信息的删除 * @param ht:哈希表 n:删除位置 * @retval 无 */ void Delet(HashTable ht, int n)/*数据删除*/ { Datatype x; int i; printf("请输入删除员工姓名:\n"); scanf_s("%s", &x.name,10);/*键盘输入删除员工姓名*/ i = HashDelete(ht, x);/*查找删除元素,并把删除结果赋值于i*/ if(i == 1)/*哈希删除函数删除元素成功返回1*/ { printf("*****员工信息删除成功!*****\n"); } else { printf("没有找到员工数据,请重新输入\n"); Delet(ht, n);/*再次调用删除函数*/ } SJXR(ht);/*数据写入*/ fanhui(ht, n);/*退出此段程序*/ } /** * @brief 员工信息的修改 * @param ht:哈希表 n:修改位置 * @retval 无 */ void change(HashTable ht, int n)/*数据修改*/ { int addr = -1; int i, m; Datatype x; printf("请输入查找联系人的方式:\n1、姓名\n2、电话号码\n输入除1、2外任意正数返回主菜单\n"); scanf_s("%d", &m); if(m == 1) { printf("请输入查找姓名:\n"); scanf_s("%s", &x.name,10); x.key = Getkey(x);/*获取哈希表键为Key的键值*/ addr = HashFunc(x.key);/*获得哈希地址*/ x.key = 1; while(ht[addr].data.key != 0 && ht[addr].data.key != x.key) { addr = Collision2(addr,i);/*没找到,处理冲突*/ } if(strcmp(ht[addr].data.name, x.name) == 0)/*两个字符串相同,返回0*/ { printf("找到员工信息:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); printf("请输入修改后员工信息:\n"); scanf_s("%s %d %s", &ht[addr].data.name,10, &ht[addr].data.num, &ht[addr].data.add,50);/*键盘输入员工修改信息*/ printf("修改后员工信息为:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); SJXR(ht);/*数据写入*/ } else { printf("未找到该员工,请重新输入。\n"); change(ht, n);/*调用修改函数*/ } } if(m == 2) { printf("请输入查找电话号码:\n"); scanf_s("%d", &x.num);/*键盘输入查找的电话号码*/ for(i = 0; i < Hashsize; i++) { if(ht[i].data.num == x.num) { addr = i; } } if(addr == -1) { printf("未找到该号码,请重新输入\n"); change(ht,n); } if(ht[addr].data.num == x.num) { printf("找到信息:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); printf("请输入修改后信息:\n"); scanf_s("%s %d %s", &ht[addr].data.name,10, &ht[addr].data.num, &ht[addr].data.add,50); printf("修改后信息为:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); SJXR(ht);/*数据写入*/ } } fanhui(ht, n); } /** * @brief 员工信息的查找 * @param ht:哈希表 n:查找位置 * @retval 无 */ int Search(HashTable ht, int n)/*数据查找*/ { int i, z, addr = -1; Datatype x; printf("请输入查找方式:\n1、姓名\n2、电话号码\n输入除1、2外任意正数返回主菜单\n"); scanf_s("%d", &z); switch (z) { case 1: printf("请输入查找员工姓名:"); scanf_s("%s", &x.name,10); x.key = Getkey(x);/*获取哈希表键为Key的键值*/ addr = HashFunc(x.key);/*获得哈希地址*/ x.key = 1; while(ht[addr].data.key != 0 && ht[addr].data.key != x.key) { addr = Collision2(addr,i);/*没找到,处理冲突*/ } if(strcmp(ht[addr].data.name, x.name) == 0)/*对比输入员工信息和文本信息,一致返回0*/ { printf("找到信息:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); } else { printf("未找到该员工,请重新输入。"); Search(ht, n); } break; case 2: printf("请输入查找电话号码:"); scanf_s("%d", &x.num); for (i = 0; i < Hashsize; i++) { if (ht[i].data.num == x.num) { addr = i; } } if (addr == -1) { printf("未找到该号码,请重新输入。"); Search(ht, n); } if (ht[addr].data.num == x.num) { printf("找到信息:%s %d %s\n", ht[addr].data.name, ht[addr].data.num, ht[addr].data.add); } break; } fanhui(ht, n); } /** * @brief 员工信息数据写入 * @param ht:哈希表 * @retval 无 */ void SJXR(HashTable ht)/*数据写入*/ { FILE *fp;/*定义员工信息储存文件*/ int i; fp = fopen("employee.txt", "w");/*打开文本文件*/ if (fp == NULL) { printf("打开文件出错!"); } for (i = 0; i < Hashsize; i++) { if (ht[i].data.key >0) { fprintf(fp, "%s %d %s\n",ht[i].data.name ,ht[i].data.num, ht[i].data.add); } } printf("*****操作成功*****\n"); fclose(fp);/*关闭文件*/ } /** * @brief 打印所有员工信息 * @param ht:哈希表 n:员工个数 * @retval 无 */ void display(HashTable ht, int n)/*显示所有员工数据*/ { int i; printf("所有数据为:\n"); for(i = 0; i < Hashsize; i++)/*依次访问哈希表中员工数据,并显示*/ { if(ht[i].data.key == 1)/*从哈希表数据域的第一个开始*/ { printf("%s %d %s\n", ht[i].data.name, ht[i].data.num, ht[i].data.add); } } fanhui(ht, n); } /** * @brief 子程序退出函数 * @param ht:哈希表 n:键盘读入正数 * @retval 无 */ void fanhui(HashTable ht, int n)/*退出函数*/ { int A; while(1) { printf("**请输入任意正数返回目录**\n"); scanf_s("%d", &A); if(A>0) { Displaymanu(ht, n);/*返回主菜单*/ break; } else { printf("不是正数,请重新输入正数:"); scanf_s("%d",&A); if (A > 0) { Displaymanu(ht, n);/*返回主菜单*/ break; } } } }
效果图
-
OpenDHT:C ++ 14分布式哈希表实现-C/C++开发
2021-05-26 22:28:48OpenDHT轻量级的C ++ 14分布式哈希表实现。 OpenDHT提供了易于使用的分布式内存数据存储。 网络中的每个节点都可以将值读取和写入存储。 值是分布式的OpenDHT轻量级的C ++ 14分布式哈希表实现。 OpenDHT提供了易于... -
C语言基于哈希表的电话簿
2020-12-23 19:41:30C语言基于哈希表的电话簿 -
哈希表实现学生学籍管理
2010-05-29 00:23:25哈希表查找,使用哈希表实现学生学籍管理====================== -
C++哈希表实现.zip
2021-08-20 14:55:54C++实现哈希表 -
基于哈希表的图书馆管理系统(数据结构)
2022-05-26 20:05:54主要用到数据结构中的哈希表,使用文件IO的操作设计了一个图书管理系统,系统分为分有一个主界面和多个子界面,实现后的效果可以界面切换自如,子界面中设计有学生入口以及老师入口,分别模拟不同的操作,功能都是... -
数据结构课程设计 学生信息管理系统哈希表学号 姓名查询
2022-02-10 16:53:302.按照学号字段建一个哈希表,实现按学号进行查找 务必用哈希结构实现 3.按照姓名字段构建哈希表结构,实现姓名的模糊查询。姓名取中文姓氏作为哈希地址 4.排序 实现多关键字排序 5.分别使用堆排和快排显示成绩前10... -
C语言项目 电话查询系统 哈希表实现(项目要求 + 运行界面 + 代码分析 + 完整代码)
2021-12-18 20:00:181. 设每个记录有以下数据项:用户名、电话、地址 2. 从键盘输入各个记录,以电话号码为关键字建立哈希表 3. 能够增加、修改、删除给定电话号码的相关记录 -
C/C++哈希表实现电话号码查询系统
2009-12-10 22:36:24用C++语言写的程序,在VC下运行的文件。其中.cpp是源文件,建立工程时还要把old.txt添加到工程中去,方可顺利运行。