C语言哈希表

【1】设计数据结构

（1）哈希表由一个结构体HashTable构成

（2）结构体HashTable由两个元素组成。其一为指针数组（链式存储元素）；其二为整型变量（记录元素个数）

（3）指针数组类型为HashNode *（哈希节点指针）

（4）结构体HashNode由数据域和指针域组成。数据域也是一种结构类型变量，指针域为一个同类型指针，为了实现链式存储。

（5）数据域结构体ElemType由关键码以及其他相关信息组成（在此程序里没有添加）

（6）拟定哈希表长度为13

【2】C语言表示数据结构

1 #define   M   13    2 typedef  int  KeyType; 3 typedef  struct  4 { 5     KeyType key;    6     //otherinfo; 7 }ElemType; 8 typedef struct  _Node 9 {10     ElemType  data;     11     _Node     *next;    12 }HashNode;13 typedef struct14 {15     HashNode  *table[M];    16     int  len;                17 }HashTable;

【3】函数设计

    在设计函数之前，让我们先理解一下基本的逻辑：

    哈希表中存储的每个元素都有一个关键码，而每个关键码都可以通过与哈希表的总数取模（当然这个算法可以任意选择）得到一个索引，而索引就是该元素欲存入的“桶”标识。一个循环链表可以形象的理解为一只桶。

    插入函数采用的前插入方式，删除函数就相当于链表的删除操作，关键仅仅在于对指针操作。

    哈希函数可以有多种实现算法，在此采用取模法。

 （1）哈希函数Hash，取模定位。实现代码如下：

1 //hash函数2 int Hash(KeyType k)3 {4     return (k % M);5 }

 （2）初始化哈希表。元素分别置为空。实现代码如下：

1 void InitHash(HashTable &ht)2 {3     ht.len=0;4     for(int i=0;i

 （3）插入元素InsertHashTable（HashTable &ht,ElemType  x）。引用传入哈希表对象，传入关键字。实现代码如下：

1 /* 2 *插入函数 3 */ 4 void InsertHashTable(HashTable &ht,ElemType x) 5 { 6     //判断是否存在 7     int pos=SearchHash(ht,x); 8     if(pos == -1) 9     {10         cout<<"已存在"<
     
      data=x;             16     //头部插入法17     s->next =ht.table[pos];  18     ht.table[pos]=s;19     //重置长度                 20     ht.len+=1;21 }
     

 （4）在插入之前，我们先要确定关键字映射的索引。函数SearchHash实现这个需求。实现代码如下：

1 //查询关键码的pos 2 int SearchHash(HashTable &ht,ElemType x) 3 { 4     /* 5     *初始化 6     */ 7     //首先定位 8     int pos=Hash(x.key); 9     HashNode *p=ht.table[pos];10     /*11     *循环遍历节点12     */13     while(p != NULL && p->data.key != x.key)14     {15         p=p->next;16     }17     /*18     *处理结果19     */20     //没找到21     if(p == NULL)22     {23         return pos;24     }25     //找到26     else27     {28         return -1;29     }30 }

（5）在实现了添加元素之后，我们相应地考虑到删除元素。删除元素的前提是要找到元素所被存储的节点。于此函数Search实现该功能。返回欲删除元素的指针。实现代码如下：

1 HashNode *Search(HashTable &ht,ElemType x) 2 { 3     /* 4     *初始化 5     */ 6     //定位 7     int pos=Hash(x.key); 8     HashNode *p=ht.table[pos]; 9     /*10     *循环11     */12     while(p != NULL && p->data.key !=x.key)13     {14         p=p->next;15     }16     /*17     *结果处理18     */19     return p;20 }

 （6）删除函数RemoveHash(HashTable &ht,ElemType x)设计思想：

    A.调用Hash函数确定元素的索引

    B.依据索引定位元素链表的起点（即就是确定从那个指针数组索引进行遍历）

    C.备用指针

    D.循环遍历

    E.结果处理。具体实现代码如下：

1 void RemoveHash(HashTable &ht,ElemType x) 2 { 3     /* 4     *初始化 5     */ 6     int pos=Hash(x.key); 7     HashNode *q=ht.table[pos]; 8     HashNode *p=NULL;       //备用指针 9     /*10     *循环遍历11     */12     while(q != NULL && q->data.key != x.key)13     {14         p=q;15         q=q->next;16     }17     /*18     *结果处理19     */20     //找到的是第一个结点21     if(p == NULL && q != NULL)22     {23         ht.table[pos]=q->next;24         ht.len-=1;25         delete q;26     }27     //找到的是其他节点包括最后一个28     if(p != NULL && q != NULL)29     {30         p->next=q->next;31         ht.len-=1;32         delete q;33     }34 35 }

【4】测试程序以及源程序代码

1 #include 
     
        2 #include 
      
         3 using namespace std;  4   5 //数据结构  6 #define   M   13        //hash表的大小  7 typedef  int  KeyType;  //关键字类型定义  8   9 //储存元素类型(结构体代表数据库的一行(即就是一个完整的个体)) 10 typedef  struct  11 { 12     KeyType key;   //关键码类型：一般比如学号，身份证号 13      //otherinfo; 14 } ElemType; 15  16 //链表节点类型 17 typedef struct  _Node 18 { 19     ElemType  data;      //元素变量 20     _Node*    next;      //指向下一个的指针 21 } HashNode; 22  23 //hash表结构 24 typedef struct 25 { 26     HashNode* table[M];    //节点指针(相当于链表头结点) 27     int  len;              //大小 28 } HashTable; 29  30 /* 31 *初始化hash 32 */ 33 void InitHash(HashTable &ht) 34 { 35     ht.len = 0; 36     for (int i = 0; i < M; ++i) 37     { 38         ht.table[i] = NULL;     //置空 39     } 40 } 41  42 //hash函数 43 int Hash(KeyType k) 44 { 45     return (k % M); 46 } 47  48 //查询关键码的pos是否存在 49 int SearchHash(HashTable &ht, ElemType x) 50 { 51     /* 52     *初始化 53     */ 54     //首先定位 55     int pos = Hash(x.key); 56     HashNode *p = ht.table[pos]; 57     /* 58     *循环遍历节点 59     */ 60     while (p != NULL && p->data.key != x.key) 61     { 62         p = p->next; 63     } 64     /* 65     *处理结果 66     */ 67     //没找到 68     if (NULL == p) 69         return pos; 70  71    return -1; 72 } 73 /* 74 *插入函数 75 */ 76 void InsertHashTable(HashTable &ht, ElemType x) 77 { 78     //判断是否存在 79     int pos = SearchHash(ht, x); 80     if (-1 == pos) 81     { 82         cout << "已存在" << endl; 83         return; 84     } 85     //不存在的前提下：new一个新的节点 86     HashNode *s = new HashNode(); 87     s->data = x;              88     //头部插入法 89     s->next = ht.table[pos];   90     ht.table[pos] = s; 91     //重置长度                  92     ht.len += 1; 93 } 94 /* 95 *查询某元素的指针 96 */ 97 HashNode *Search(HashTable &ht, ElemType x) 98 { 99     /*100     *初始化101     */102     //定位103     int pos = Hash(x.key);104     HashNode *p = ht.table[pos];105     /*106     *循环107     */108     while (p != NULL && p->data.key != x.key)109     {110         p = p->next;111     }112     /*113     *结果处理114     */115     return p;116 }117 /*118 *删除元素119 */120 void RemoveHash(HashTable &ht, ElemType x)121 {122     /*123     *初始化124     */125     int pos = Hash(x.key);126     HashNode *q = ht.table[pos];127     HashNode *p = NULL;       //备用指针128     /*129     *循环遍历130     */131     while (q != NULL && q->data.key != x.key)132     {133         p = q;134         q = q->next;135     }136     /*137     *结果处理138     */139     //找到的是第一个结点140     if (NULL == p && q != NULL)141     {142         ht.table[pos] = q->next;143         ht.len -= 1;144         delete q;145     }146     //找到的是其他节点包括最后一个147     if (p != NULL && q != NULL)148     {149         p->next = q->next;150         ht.len -= 1;151         delete q;152     }153 }154 155 void main()156 {157     cout << __FILE__ << endl;158     cout << __LINE__ << endl;159     cout << __TIME__ << endl;160 161     ElemType ar[11] = {
    1, 14, 27, 12, 40, 34, 53, 65, 78, 9, 5,};162     HashNode *p = NULL;163     ElemType x;164     HashTable ht;165 166     InitHash(ht);167     for (int i = 0; i < 11; ++i)168     {169         InsertHashTable(ht, ar[i]);170     }171     cout << "请输入查找关键码并以-1结束" << endl;172     while (cin>>x.key, x.key != -1)173     {174         p = Search(ht, x);175         if (NULL == p)176         {177             cout << "无此数据" << endl;178         }179         else180         {181             cout << "关键码地址："<< p << "  " << "关键码值：" << p->data.key << endl;182         }183     }184     cout <<"请输入删除的关键码" <
       
        >x.key, x.key != -1)186     {187         RemoveHash(ht, x);188     }189 }
       
      
     

【5】Demo总结

完成一个简单的程序之前，首先整理思路，把基本的逻辑思路想清楚，再开始一步一步地策划，一点一点的处理相应的功能需求，一次一次的重审自己的设计思路。

在所有的步骤大概都设计好以后，着手书写代码，实现相应地模块，或者说函数，进而完成整个程序。

最后测试自己的代码，是否达到了预期地要求，是否可以扩充，有没有多余的代码等。

本次程序学到了循环链表的基本操作以及哈希表的原理。

 

Good Good Study, Day Day Up.

顺序  选择  循环  坚持