3.2 鏈地址法

鏈地址法就是將相應(yīng)位置上沖突的所有關(guān)鍵詞存儲在同一個單鏈表中。

設(shè)關(guān)鍵字序列為 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，散列函數(shù)取為h ( k e y ) = k e y m o d ?? 11 h(key) = key \mod 11h(key)=keymod11，用分離鏈接法處理沖突。

表中有9個結(jié)點(diǎn)只需1次查找，5個結(jié)點(diǎn)需要2次查找，所以查找成功的平均查找次數(shù)為：

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

參考代碼：

#include

#include

#include

#include

#include

using namespace std;

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

#define KEYLENGTH 100 //關(guān)鍵字的最大長度

typedef int ElementType;

struct LNode

{

ElementType data;

LNode *next;

};

typedef LNode *PtrToNode;

typedef PtrToNode LinkList;

struct TblNode

{

int tablesize;  //表的最大長度

LinkList heads; //存放散列單元數(shù)據(jù)的數(shù)組

};

typedef struct TblNode *HashTable;

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

int NextPrime(int n)

{

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

int i;

while (p <= MAXTABLESIZE)

{

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

    {

        if ((p % i) == 0)

            break;

    }

    if (i == 2)

        break; //說明是素數(shù)，結(jié)束

    else

        p += 2;

}

return p;

}

/創(chuàng)建新的哈希表/

HashTable CreateTable(int table_size)

{

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

h->tablesize = NextPrime(table_size);

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

//初始化表頭結(jié)點(diǎn)

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

{

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

}

return h;

}

/查找數(shù)據(jù)的初始位置/

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; //從鏈表的第一個節(jié)點(diǎn)開始

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

{

    p = p->next;

}

return p;

}

/插入新的元素/

bool Insert(HashTable h, ElementType key)

{

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

if (!p)

{

    //關(guān)鍵詞未找到，可以插入

    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;

//釋放每個節(jié)點(diǎn)

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;

}

審核編輯：符乾江