我是 C 编程的新手,最近才开始学习数据结构和算法。我选择的教材是Data Structures and Algorithm Analysis in C,在第5章介绍了哈希表ADT。这是其四开放寻址版本的一种实现,其中函数 Find 将 Key 和 TableSize 的值传递给 Hash 函数,它将返回散列值作为变量 CurrentPos。以下是函数Hash 和Find:
Index
Hash( ElementType Key, int TableSize )
{
return Key % TableSize;
}
Position
Find(ElementType Key, HashTable H)
{
Position CurrentPos;
int CollisionNum;
CollisionNum = 0;
CurrentPos = Hash(Key, H->TableSize);
while(H->TheCells[CurrentPos].Info != Empty && H->TheCells[CurrentPos].Element != Key)
{
CurrentPos += 2 * ++CollisionNum - 1;
if(CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
}
return CurrentPos;
}
这是标题:
typedef int ElementType;
#ifndef _HashQuad_H
#define _HashQuad_H
typedef unsigned int Index;
typedef Index 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, HashTable H );
HashTable Rehash( HashTable H );
#endif
下面是源文件中的类型定义和结构:
struct HashEntry
{
ElementType Element;
enum KindOfEntry Info;
};
typedef struct HashEntry Cell;
/* Cell *TheCells will be an array of */
/* HashEntry cells, allocated later */
struct HashTbl
{
int TableSize;
Cell *TheCells;
};
H是这样初始化的
HashTable
InitializeTable( int TableSize )
{
HashTable H;
int i;
if( TableSize < MinTableSize )
{
Error( "Table size too small" );
return NULL;
}
/* Allocate table */
H = malloc( sizeof( struct HashTbl ) );
if( H == NULL )
FatalError( "Out of space!!!" );
H->TableSize = NextPrime( TableSize );
/* Allocate array of Cells */
H->TheCells = malloc( sizeof( Cell ) * H->TableSize );
if( H->TheCells == NULL )
FatalError( "Out of space!!!" );
for( i = 0; i < H->TableSize; i++ )
H->TheCells[ i ].Info = Empty;
return H;
}
现在的问题是,这个实现在大多数情况下都能正常工作。它有时确实会遇到崩溃。当它发生时,我尝试进行单元测试,发现在某一轮调用Hash函数后,CurrentPos的值将被分配为一个更大的整数比Hash函数的实际返回值还要大1000+甚至更大。 例如,如果 Key 为 29918,TableSize 为 101,则正确答案是 Hash 返回的值为 22,但赋值后行:
CurrentPos = Hash(Key, H->TableSize);
CurrentPos 的值无缘无故地自行变为 1580。 请注意,使用 rand() 基于函数 time() 的种子随机分配的时间 Key 值小于上限- 整数类型的边界 - 我的意思是不应该有溢出。
我努力靠近 watch 看,但没有其他错误或线索。我很困惑,因为这个错误真的是随机发生的。有没有人熟悉这个?
最佳答案
如果 CollisionNum
变得足够大,则此测试将无法正常工作:
if(CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
因为如果 CurrentPos >= H->TableSize*2
那么在减去 H->TableSize
之后 CurrentPos
仍然会超出范围>.
您应该将其更改为:
while (CurrentPos >= H->TableSize)
CurrentPos -= H->TableSize;
或:
CurrentPos = CurrentPos % H->TableSize;
甚至:
CurrentPos %= H->TableSize;
关于c - 为什么我的变量值会随机变化?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26041268/