#include "stdafx.h"

 #include <iostream>

 #include <exception>

 using namespace std;

 /*散列表查找实现

 散列表如果没有冲突,查找效率就非常高的.时间复杂度是O(1);但是实际应用中,冲突是不可避免的.

 那么散列表的平均查找长度取决于

 1.散列函数是否均匀.

 2.处理冲突的方法.

 3.散列表的装填因子.a = 填入表中的记录个数 / 散列表的长度.当a越大,产生冲突的可能性就越大.

 用空间来换取时间

 */

 const int success = ;

 const int unSuccess =  ;

 const int hashSize = ;

 const int nullKey = -;

 const int ok = ;

 typedef struct

 {

     int *elem;

     int count;

 }HashTable;

 int m = ;

 /*初始化散列表*/

 int InitHashTable(HashTable *H)

 {

     int i ;

     m = hashSize;

     H->count = m;

     H->elem = (int *)malloc(sizeof(int));

     for(int i = ;i!=m;++i)

         H->elem[i]=nullKey; //所有元素初始化

     return ok;

 }

 /*散列函数*/

 int Hash(int key)

 {

     return key%m; //除留余数法

 }

 /*插入关键字进散列表*/

 void InsertHash(HashTable *H,int key)

 {

     int addr = Hash(key);

     while(H->elem[addr]!=nullKey)

     {

         addr = (addr+)%m;

     }

     H->elem[addr] = key;

 }

 /*散列表查找关键字*/

 int SearchHash(HashTable H,int key,int *addr)

 {

     *addr = Hash(key);

     while(H.elem[*addr]!=key)

     {

         *addr=(*addr+)%m;

         if(H.elem[*addr] == nullKey|| *addr ==Hash(key))

         {

             return unSuccess;

         }

     }

     return success;

 }

 int _tmain(int argc, _TCHAR* argv[])

 { 

     return  ;

 }