c - 为什么我的变量值会随机变化？

Question

我是 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 看，但没有其他错误或线索。我很困惑，因为这个错误真的是随机发生的。有没有人熟悉这个？

Answer 1

如果 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;