数据结构学习，哈希表链地址

各位小伙伴，新年快乐。

哈希表，本质上是数组，而链地址就是存放了链表的数组。

借用哈希函数对某个数进行适当运算求得该数的哈希值，在根据这个哈希值对哈希表进行查找插入删除操作。

假设这是一个哈希表H，容量为5，长度为0；五个指针全部为NULL；

首先我们有一个数：3；假设其求得的哈希值为2，如图所示：

 然后再令3成为这个存放这五个链表的数组中，第三个链表的，第一个结点。

如图所示：

这就是插入，删除也可借鉴单链表的操作。

下面来看怎么实现的

目录

预先要引用的头文件以及宏定义

所使用哈希表的结构

所使用的哈希函数

其基本操作接口

初始化哈希表

销毁哈希表

查找

插入

删除

遍历

一些接口的测试

---

预先要引用的头文件以及宏定义

1.  
   #include<stdio.h>
2.  
   #include<iostream>
3.  
   //
4.  
   //using namespace std;
5.  
    
6.  
   #define TRUE 1
7.  
   #define FALSE 0
8.  
   #define OK 1
9.  
   #define ERROR 0
10.  
    #define OVERFLOW -1
11.  
    #define UNSUCCESS 0
12.  
    #define SUCCESS 1
13.  
    typedef int ElemType;
14.  
    typedef int Status;
15.  
    typedef int KeyType;

所使用哈希表的结构

1.  
   //(链地址)
2.  
   typedef struct {
3.  
   KeyType Key;
4.  
   //这里可以存放其他数据
5.  
   }RecordType, RcdType;
6.  
   typedef struct Node { //其实这个指针就是链表
7.  
   RcdType r;
8.  
   struct Node* next;
9.  
   }Node;
10.  
    typedef struct {
11.  
    Node** rcd; //（指向指针的指针）存放指针的数组
12.  
    int size; //哈希表的容量
13.  
    int count; //当前表中含有的记录个数
14.  
    int(*hash)(KeyType key, int hashSize); //函数指针变量，选取哈希函数
15.  
    }HashTable;

所使用的哈希函数

1.  
   int hash(int key, int hashSize)
2.  
   {//哈希函数，hashSize为地址空间长度（哈希表的容量）
3.  
   return (3 * key) % hashSize;
4.  
   }

哈希函数可以有很多种

1，直接定址法，你这个数是98，那里就到H.rcd[98]里面去，直接。hash = 98

2，除留余数法，hash = 关键字%（某个你中意的数（一般是哈希表的容量））也是我选择的。

3，数字分析法，

4，折叠法，

5，平方取中法，

等。3，4，5大家有兴趣就搜一下，我不会讲。

其基本操作接口

1.  
   Status InitHash(HashTable& H, int size, int(*hash)(KeyType, int)); //初始化哈希表
2.  
   Status DestroyHash(HashTable& H); //销毁哈希表
3.  
   Node* SearchHash(HashTable H, KeyType key); //查找
4.  
   Status InsertHash(HashTable& H, RcdType e); //插入
5.  
   Status DeleteHash(HashTable& H, KeyType key, RcdType& e); //删除
6.  
   void HashTraverse(HashTable H); //遍历

初始化哈希表

1.  
   Status InitHash(HashTable& H, int size, int(*hash)(KeyType, int))
2.  
   {
3.  
   H.rcd = (Node**)malloc(size*sizeof(Node*));
4.  
   if (H.rcd != NULL)
5.  
   {
6.  
   for (int i = 0; i < size; i )
7.  
   {
8.  
   H.rcd[i] = NULL;
9.  
   }
10.  
    H.size = size;
11.  
    H.hash = hash;
12.  
    H.count = 0;
13.  
    return OK;
14.  
    }
15.  
    else
16.  
    {
17.  
    return OVERFLOW;
18.  
    }
19.  
    }

销毁哈希表

1.  
   Status DestroyHash(HashTable& H)
2.  
   {
3.  
   if (H.rcd != NULL)
4.  
   {
5.  
   Node* np, * nt;
6.  
   for (int i = 0; i < H.size; i )
7.  
   {
8.  
   np = H.rcd[i];
9.  
   while (np != NULL)
10.  
    {
11.  
    nt = np;
12.  
    np = np->next;
13.  
    free(nt);
14.  
    }
15.  
    }
16.  
    H.size = 0;
17.  
    H.count = 0;
18.  
    H.hash = NULL;
19.  
    return OK;
20.  
    }
21.  
    else
22.  
    {
23.  
    return OVERFLOW;
24.  
    }
25.  
    }

查找

1.  
   Node* SearchHash(HashTable H, KeyType key)
2.  
   {
3.  
   int p = H.hash(key, H.size);
4.  
   Node* np;
5.  
   for (np = H.rcd[p]; np != NULL; np = np->next)
6.  
   {
7.  
   if (np->r.Key == key)return np;
8.  
   }
9.  
   return NULL;
10.  
    }

插入

1.  
   Status InsertHash(HashTable& H, RcdType e)
2.  
   {
3.  
   int p;
4.  
   Node* np;
5.  
   np = SearchHash(H, e.Key);
6.  
   if (np == NULL)
7.  
   {
8.  
   p = H.hash(e.Key, H.size);
9.  
   np = (Node*)malloc(sizeof(Node));
10.  
    if (np != NULL)
11.  
    {
12.  
    np->r = e;
13.  
    np->next = H.rcd[p];
14.  
    H.rcd[p] = np;
15.  
    H.count ;
16.  
    return OK;
17.  
    }
18.  
    else
19.  
    {
20.  
    return OVERFLOW;
21.  
    }
22.  
    }
23.  
    else
24.  
    {
25.  
    return ERROR;
26.  
    }
27.  
    }

删除

1.  
   Status DeleteHash(HashTable& H, KeyType key, RcdType& e)
2.  
   {
3.  
   Node* n;
4.  
   n = SearchHash(H, key);
5.  
   if (n != NULL)
6.  
   {
7.  
   int p = H.hash(key, H.size);
8.  
   Node* np, * nq;
9.  
   np = H.rcd[p];
10.  
    nq = NULL;
11.  
    while (np != NULL)
12.  
    {
13.  
    if (np->r.Key != key)
14.  
    {
15.  
    nq = np;
16.  
    np = np->next;
17.  
    }
18.  
    else
19.  
    {
20.  
    e = np->r;
21.  
    if (nq == NULL)//表头
22.  
    {
23.  
    H.rcd[p] = np->next;
24.  
    }
25.  
    else//不是表头
26.  
    {
27.  
    nq->next = np->next;
28.  
    }
29.  
    break;
30.  
    }
31.  
    }
32.  
    H.count--;
33.  
    free(np);
34.  
    return OK;
35.  
    }
36.  
    else
37.  
    {
38.  
    return ERROR;
39.  
    }
40.  
    }

遍历

1.  
   void HashTraverse(HashTable H)
2.  
   {
3.  
   if (H.rcd != NULL)
4.  
   {
5.  
   Node* np, * nq;
6.  
   for (int i = 0; i < H.size; i )
7.  
   {
8.  
   np = H.rcd[i];
9.  
   if (np == NULL)
10.  
    {
11.  
    printf(" #");
12.  
    }
13.  
    else
14.  
    {
15.  
    while (np)
16.  
    {
17.  
    printf("=", np->r.Key);
18.  
    np = np->next;
19.  
    }
20.  
    }
21.  
    printf("\n");
22.  
    }
23.  
    }
24.  
    }

一些接口的测试

1.  
   int main()
2.  
   {
3.  
   HashTable H;
4.  
   InitHash(H, 10, hash);
5.  
   for (int i = 0; i < 12; i )
6.  
   {
7.  
   RcdType e;
8.  
   e.Key = i;
9.  
   InsertHash(H, e);
10.  
    }
11.  
    HashTraverse(H);
12.  
    RcdType e1;
13.  
    DeleteHash(H, 9, e1);
14.  
    printf("被删数据%d\n", e1.Key);
15.  
    HashTraverse(H);
16.  
    DestroyHash(H);
17.  
    }

 其实想想看，如果他不是链表，是棵B树呢！！！，存放B树的数组，哈哈哈哈哈哈。

这篇好文章是转载于：学新通技术网