HashTable 解决碰撞（冲突）的方法 —— 分离链接法（separate chaining）

1. ListNode 及 HashTable 的类型声明

声明

typedef int ElementType;

typedef unsigned int Index;

struct ListNode;

typedef struct ListNode* Position;

struct HashTbl;

typedef struct HashTbl* HashTable;

HashTable InitHashTable(int TableSize);

void DestroyHashTable(HashTable H);

Position Find(ElementType Element, HashTable H);

void Insert(ElementType Element, HashTable H);;

ElementType Retrieve(Position P);

定义

struct ListNode{

    ElementType Element;

    Position Next;

};

typedef Position List;

struct HashTbl {

    int TableSize;

    List* TheLists;

};

2. HashTable 的构建

HashTable InitHashTable(int TableSize){

    HashTable H;

    if (TableSize < MinTableSize){

        Error(" ... ");

        return NULL;

    }

    H = (HashTable)malloc(sizeof(struct HashTbl));

    if (!H)

        FatalError("out of space !!!");

    H->TableSize = NextPrime(TableSize);

    H->TheLists = (List*)malloc(sizeof(struct ListNode)*H->TableSize);

    for (int i = 0; i < H->TableSize; ++i){

        H->TheLists[i] = (List)malloc(sizeof(struct ListNode));

        if (!H->TheLists[i])

            FatalError("");

        else

            H->TheLists[i]->Next = NULL;

    }

}

3. 插入新的结点

void Insert(ElementType Key, HashTable H){

    Position Pos, NewCell;

    List L;

    Pos = Find(key, H);

    if (!Pos){

        NewCell = (Position)malloc(sizeof(struct ListNode));

        if (!NewCell)

            FatalError("");

        L = H->TheLists[Hash(Key, H->TableSize)];

        NewCell->Next = L->Next;

                                    // 插入在首部

        NewCell->Element = Key;

        L->Next = NewCell->Next;

    }

}

巴特西

HashTable 解决碰撞（冲突）的方法 —— 分离链接法（separate chaining）

1. ListNode 及 HashTable 的类型声明

2. HashTable 的构建

3. 插入新的结点

最新文章

热门文章