滴水逆向联盟

标题: 基于visual Studio2013解决面试题之0206hash表实现 [打印本页]

---

作者: 大灰狼    时间: 2014-8-4 09:10
标题: 基于visual Studio2013解决面试题之0206hash表实现


题目

解决代码及点评[cpp] view plaincopy

• <pre code_snippet_id="110162" snippet_file_name="blog_20131213_1_9736233" class="cpp" name="code"><pre code_snippet_id="110162" snippet_file_name="blog_20131213_1_9736233" class="cpp" name="code"><pre code_snippet_id="110162" snippet_file_name="blog_20131213_1_9736233" class="cpp" name="code"><pre code_snippet_id="110162" snippet_file_name="blog_20131213_1_9736233" name="code" class="cpp">/*
•     hash表，是用hash算法将任意长度的二进制值，映射为较短的固定范围的二进制值
•     在这个例子里，我们简单的使用 %10作为我们的hash算法。
•     对10取模会导致经常的冲突，比如13和23，对10取模之后都是3，这种情况下叫做hash算法的冲突
•     为了解决冲突，需要在一个hash节点上使用链表数据结构来保存冲突的多个数据。
• */  
•   
•   
• #include <iostream>  
• #include <algorithm>  
• #include <vector>  
• #include <memory.h>  
• using namespace std;  
•   
• /*
•     hash表节点
•     由value和next指针构成
•     index只是用来打印，无实际意义
• */  
• template<class T>  
• class Node  
• {  
• public:  
•     T value;        // hash节点值  
•     Node<T> *pNext;   // 冲突的下一个节点  
•     int index;      // 只是打印  
• protected:  
• private:  
• };  
• template<class T>  
• class Hash  
• {  
• public:  
•     Hash();         // 构造函数  
•     ~Hash();        // 析构函数  
•     bool insert(T value);   // 往hash表中插入数据  
•     bool deleteNode(T value);   // 删除节点  
•     Node<T> *FindValue(T value);  // 在hash表中搜索节点  
•     //Node<T> **Top10();  
•     void Print();           // 输出哈希表  
•   
• protected:  
• private:  
•     Node<T> *HashArray[10];   // 定义10个hash节点指针，构成hash简答的hash数据结构  
• };  
•   
• // 构造函数：为数据结构申请内存  
• template<class T>  
• Hash<T>::Hash()  
• {  
•     HashArray[10]=new Node<T>[10];  
•     memset(HashArray, NULL, sizeof(Hash));  
• }  
•   
• // 析构函数，释放内存  
• template<class T>  
• Hash<T>::~Hash()  
• {  
•     delete []HashArray;  
• }  
•   
• // 打印hash表，只是遍历hash数组，输出每个节点的value和index  
• template<class T>  
• void  Hash<T>::Print()  
• {  
•     Node<T> *node;  
•     for(int i=0;i<10;i++)  
•     {  
•         if (HashArray==NULL)  
•         {  
•             continue;  
•         }  
•         node = HashArray;  
•         while(node!=NULL)  
•         {  
•             cout<<node->value<<":"<<node->index<<" ";  
•             node=node->pNext;  
•         }  
•   
•         cout<<endl;  
•     }  
• }  
•   
• /*
•     FindValue：首先通过value%10获得hash的index
•     然后在指定的index上的链表中搜索节点
• */  
• template<class T>  
• Node<T> *Hash<T>::FindValue(T value)  
• {  
•     Node<T> *node;  
•     /* 先判断HashArray，如果是空，则不用搜索了 */  
•     if (HashArray==NULL)  
•     {  
•         return NULL;  
•     }  
•   
•     /* 根据hash算法，这里我们简单对10取模，获取hash下标 */  
•     node = HashArray[value%10];  
•     if (node==NULL)  
•     {  
•         return NULL;  
•     }  
•   
•     /* 在对应坐标的冲突链表中搜索value */  
•     while(node)  
•     {  
•         if (node->value==value)  
•         {  
•             return node;  
•         }  
•         node=node->pNext;  
•     }  
•     return NULL;  
• }  
•   
• /* 插入数据 */  
• template<class T>  
• bool Hash<T>::insert(T value)  
• {  
•     Node<T> *node;  
•     /* 首先判断HashArray，如果为空，则无法插入了 */  
•     if (HashArray==NULL)  
•     {  
•         return false;  
•     }  
•   
•     /* 根据hash算法获得hash index，并判断index是不是为空，
•     如果为空，说明该index下还从来未有数据插入过，
•     那么直接将该输入插入即可 */  
•     if (HashArray[value%10]==NULL)     //判断头数组中有没有  
•     {  
•         /* 构造节点 */  
•         node = new Node<T>;  
•         node->value = value;  
•         node->index = 1;  
•         node->pNext = NULL;  
•   
•         /* 直接插入即可，即赋值 */  
•         HashArray[value%10]=node;  
•         return true;  
•   
•     }  
•   
•     /* 如果该index下不为空，那么说明冲突，也有可能该值以前就已经插入过，通过findvalue去查找下
•        如果能找到说明该值已经在hash表中，index++表明该值被多次插入过 */  
•     if (FindValue(value)!=NULL)  
•     {  
•         FindValue(value)->index++;  
•         return false;  
•     }  
•   
•     /* 如果findValue失败，说明数据没有插入过，那么构造节点 */  
•     node = new Node<T>;    //头插法  
•     node->value = value;  
•     node->index = 1;  
•   
•     /* 以下两句代码将新节点加入到冲突链表的头
•          
•         比如有一个冲突节点如下：
•         -> 13 -> 23 -> NULL
•         这时候加入了33，那么33的位置应该在
•         -> 33 -> 13 -> 23 -> NULL
•     */  
•     node->pNext = HashArray[value%10];  
•     HashArray[value%10]=node;  
•     return true;  
•   
• }  
•   
• /*
•     删除节点
• */  
• template<class T>  
• bool Hash<T>::deleteNode(T value)  
• {  
•     Node<T> *node;  
•     if (HashArray==NULL)  
•     {  
•         return false;  
•     }  
•   
•     // 根据hash算法获取头数组，如果头数组没有，则表明该value不存在  
•     if (HashArray[value%10]==NULL)     //判断头数组中有没有  
•     {  
•         return false;  
•     }  
•   
•     /* 通过FindValue去搜索，看节点是否存在，如果不存在也不用删除了 */  
•     if (FindValue(value)!=NULL)  
•     {  
•         /* 如果存在，那么通过hash算法，获取冲突链表头 */  
•         node = HashArray[value%10];  
•   
•         /* 如果链表头节点就是该value，则删除头节点 */  
•         if (node->value==value)  
•         {  
•             Node<T> *temp = node;  
•             node = node->pNext;  
•             HashArray[value%10] = node;  
•             delete temp;  
•             return true;  
•         }  
•   
•         /* 如果不是在冲突链表头，那么就在冲突链表中，循环的查找吧 */  
•         while(node->pNext!=NULL)  
•         {  
•             // 当找到这个value时  
•             if (node->pNext->value==value)  
•             {  
•                 // 将这个value对应的node在链表里删除  
•                 Node<T> *temp = node->pNext;  
•                 node->pNext=temp->pNext;  
•                 delete temp;  
•                 return true;  
•             }  
•             node=node->pNext;  
•         }  
•         return false;  
•   
•     }  
•     return false;  
•   
•   
• }  
•   
• /* 测试主函数 */  
• int main()  
• {  
•     Hash<int> h;  
•     h.insert(4);  
•     h.insert(34);  
•     h.insert(54);  
•       
•     h.insert(35);  
•     h.insert(8);  
•     h.insert(22);  
•     h.insert(48);  
•     h.insert(9);  
•   
•     h.insert(32);  
•     h.insert(2);  
•     h.insert(3);  
•     h.insert(54);  
•     h.insert(37);  
•     h.insert(8);  
•     h.insert(54);  
•     h.insert(6);  
•     h.insert(9);  
•     h.insert(12);  
•     h.insert(12);  
•     h.insert(23);  
•       
•     h.insert(37);  
•     h.insert(48);  
•     h.insert(54);  
•     h.insert(66);  
•     h.insert(9);  
•     h.insert(12);  
•       
•     h.Print();  
•       
•       
•     system("pause");  
•     return 0;  
• }  
•   
• </pre><br><br></pre></pre></pre>  
  

代码下载及其运行

代码下载地址：http://download.csdn.net/detail/yincheng01/6704519

解压密码：c.itcast.cn

下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：

1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”

2）在下拉框中选择相应项目，项目名和博客编号一致

3）点击“本地Windows调试器”运行

程序运行结果

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2