3.2 鏈地址法

鏈地址法就是將相應位置上沖突的所有關鍵詞存儲在同一個單鏈表中。

設關鍵字序列為 47 , 7 , 29 , 11 , 16 , 92 , 22 , 8 , 3 , 50 , 37 , 89 , 94 , 21 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 2147,7,29,11,16,92,22,8,3,50,37,89,94,21，散列函數取為h ( k e y ) = k e y m o d ?? 11 h(key) = key \mod 11h(key)=keymod11，用分離鏈接法處理沖突。

表中有9個結點只需1次查找，5個結點需要2次查找，所以查找成功的平均查找次數為：

A S L s = ( 9 + 5 ? 2 ) / 14 ≈ 1.36

參考代碼：

#include

#include

#include

#include

#include

using namespace std;

#define MAXTABLESIZE 10000 //允許開辟的最大散列表長度

#define KEYLENGTH 100 //關鍵字的最大長度

typedef int ElementType;

struct LNode

{

ElementType data;

LNode *next;

};

typedef LNode *PtrToNode;

typedef PtrToNode LinkList;

struct TblNode

{

int tablesize;  //表的最大長度

LinkList heads; //存放散列單元數據的數組

};

typedef struct TblNode *HashTable;

/返回大于n且不超過MAXTABLESIZE的最小素數/

int NextPrime(int n)

{

int p = (n % 2) ? n + 2 : n + 1; //從大于n的下一個奇數開始

int i;

while (p <= MAXTABLESIZE)

{

    for (i = (int)sqrt(p); i > 2; i--)

    {

        if ((p % i) == 0)

            break;

    }

    if (i == 2)

        break; //說明是素數，結束

    else

        p += 2;

}

return p;

}

/創建新的哈希表/

HashTable CreateTable(int table_size)

{

HashTable h = (HashTable)malloc(sizeof(TblNode));

h->tablesize = NextPrime(table_size);

h->heads = (LinkList)malloc(h->tablesize * sizeof(LNode));

//初始化表頭結點

for (int i = 0; i < h->tablesize; i++)

{

    h->heads[i].next = NULL;

}

return h;

}

/查找數據的初始位置/

int Hash(ElementType key, int n)

{

//這里只針對大小寫

return key % 11;

}

/查找元素位置/

LinkList Find(HashTable h, ElementType key)

{

int pos;

pos = Hash(key, h->tablesize); //初始散列位置

LinkList p = h->heads[pos].next; //從鏈表的第一個節點開始

while (p && key != p->data)

{

    p = p->next;

}

return p;

}

/插入新的元素/

bool Insert(HashTable h, ElementType key)

{

LinkList p = Find(h, key); //先查找key是否存在

if (!p)

{

    //關鍵詞未找到，可以插入

    LinkList new_cell = (LinkList)malloc(sizeof(LNode));

    new_cell->data = key;

    int pos = Hash(key, h->tablesize);

    new_cell->next = h->heads[pos].next;

    h->heads[pos].next = new_cell;

    return true;

}

else

{

    cout << "鍵值已存在！" << endl;

    return false;

}

}

/銷毀鏈表/

void DestroyTable(HashTable h)

{

int i;

LinkList p, tmp;

//釋放每個節點

for (i = 0; i < h->tablesize; i++)

{

    p = h->heads[i].next;

    while (p)

    {

        tmp = p->next;

        free(p);

        p = tmp;

    }

}

free(h->heads);

free(h);

}

int main(int argc, char const *argv[])

{

int a[] = {47, 7, 29,29, 11, 16, 92, 22, 8, 3, 50, 37, 89, 94, 21};

int n = 15;

HashTable h = CreateTable(n);

for (int i = 0; i < n; i++)

{

    Insert(h, a[i]); //插入元素

}

for (int i = 0; i < h->tablesize; i++)

{

    LinkList p = h->heads[i].next;

    while (p)

    {

        cout << p->data << " "; //打印哈希表元素

        p = p->next;

    }

    cout << endl;

}

return 0;

}

審核編輯：符乾江