数据结构_散列表(哈希表)_分离链接法


该散列表数据结构主要参考《数据结构与算法分析》,第五章-散列;

有关下一个素数的获取,参考了《算法导论·原书第二版》与《离散数学·原书第五版》的相关内容

相关定义:

散列表:一种用于以常熟平均时间执行插入、删除和查找的技术。
分离链接法:将散列到同一个值的所有元素保留到一个表中(通常是链表)。
素数:除1和自身外,不能被其他任何数整除的整数

散列的文件头_HashSep.h

#ifndef _HashSep_H

struct ListNode;
typedef struct ListNode *Position;
struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable( int TableSize );
void DestroyTable( HashTable H );
Position Find( ElementType Key, HashTable H );
void Insert( ElementType Key, HashTable H );
ElementType Retrieve( Position P );
void Delete( ElementType Key, HashTable H );
HashTable MakeEmpty( HashTable H );
int NextPrime( int N );
int IsPrime( int N );
int ModuloPower( int P, int E, int N );
int Hash( const char *Key, int TableSize );

#endif /* _HashSeq_H */

/* Place in the implementation file */
struct ListNode
{
	ElementType Key;
	Position Next;
};

typedef Position List;
#define MinTableSize ( 10 )
struct HashTbl
{
	int TableSize;
	List *TheLists;
};

主要函数例程_HashSep.c

/* 哈希表相关例程参考《数据结构与算法分析:C语言描述》 P111-P116 */
HashTable InitializeTable( int TableSize )
{
	HashTable H;
	int i;

	if( TableSize < MinTableSize )
	{
		printf( "Table size is too small!!" );
		return NULL;
	}

	H = malloc( sizeof( struct HashTbl ) );
	if( H == NULL )
	{
		printf( "Out of space !!!" );
		exit( 1 );
	}

	H->TableSize = NextPrime( TableSize );
	H->TheLists = malloc( sizeof( List ) * H->TableSize );
	if( H->TheLists == NULL )
	{
		printf( "Out of space !!!" );
		exit( 1 );
	}

	for( i = 0; i < H->TableSize; i++ )
	{
		H->TheLists[ i ] = malloc( sizeof( struct ListNode ) );
		if( H->TheLists[ i ] == NULL )
		{
			printf( "Out of space !!!" );
			exit( 1 );
		}
		else
			H->TheLists[ i ]->Next = NULL;
	}

	return H;
}

/* 求P的E次方 模 N 的值 */
/* 详见《离散数学·原书第五版》 P80-P81 */
int ModuloPower( int P, int E, int N )
{
	int R2 = 1;
	int R,R1;
	while( E != 0 )
	{
		R = E&1;
		E = E >> 1;
		R1 = ( P * P ) % N;
		if( R == 1)
		{
			R2 = ( R2 * P ) % N;
		}
		P = R1;
	}
	return R2;
}

/* 判断 N 是否为一个素数 */
/* 不精确判断,当 N 小于 10000时,出错概率约为 22/10000 */
/*             当 N 为随机选取的512位数,出错概率为 1/(10^20) */
/*             当 N 为随机选取的1024位数,出错概率为 1/(10^41) */
/* 详见《算法导论·原书第二版》 P544-P547 */
int IsPrime( int N )
{
	if( ModuloPower( 2, N - 1, N ) != 1 )
		return 0;
	else
		return 1;
}

/* 获取当前数字的下一个素数 */
int NextPrime( int N )
{
	int i;
	for( i = ++N; ;i++)
	{
		if( IsPrime( i ) )
			return i;
	}
}

Position Find( ElementType Key, HashTable H )
{
	Position P;
	List L;

	L = H->TheLists[ Hash( Key, H->TableSize ) ];
	P = L->Next;
	while( P != NULL && strcmp( P->Key, Key ) )
		P->Next;

	return P;
}

int Hash( const char *Key, int TableSize )
{
	unsigned int HashVal = 0;
	
	while( *Key != '\0' )
		HashVal = ( HashVal << 5 ) + *Key++;

	return HashVal % TableSize;
}

void Insert( ElementType Key, HashTable H )
{
	Position Pos, NewCell;
	List L;

	Pos = Find( Key, H );
	if( Pos == NULL )
	{
		NewCell = malloc( sizeof( struct ListNode ) );
		if( NewCell == NULL )
		{
			printf( "Out of space !!!" );
			exit( 1 );
		}
		else
		{
			L = H->TheLists[ Hash( Key, H->TableSize ) ];
			NewCell->Next = L->Next;
			NewCell->Key = malloc( sizeof( Key ) );
			strcpy( NewCell->Key, Key );
			L->Next = NewCell;
		}
	}
}

调用例子 _HashSep_Main.c

#include 
#include
#include
typedef char * ElementType;
#include "_HashSep.h"
#include "_HashSep.c"

int main()
{
	HashTable H;
	Position P;
	H = InitializeTable( 5000 );
	Insert( "test", H );
	P = Find( "test", H );
	printf( "%s", P->Key );
	return 1;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注