/***************************************************************************
* xcl 2012.2.18 *
* HashTable *
* 说明：本哈希表采用线性散列处理冲突，哈希函数为素数取模运算*
***************************************************************************/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <
iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
#define add_scope 11 //地址范围
int hash(int key) //处理键值
{
return (key*3)%11;
}
typedef int KeyType,ValType,StatusType; //定义类型
//实际数据结构-----------------------------
typedef struct{
KeyType key;
ValType val;
StatusType stat;
}Element;
//实现类------------------------------------
class MyList
{
public:
MyList(int n);
~MyList();
public:
void SetKey(int key,int val);
void DeleteKey(int key);
int SearchKey(int key);
int GetMapSize();
void ShowList();
private:
Element *elem;
int hash_size;
int dataNum;
};
//-----------------------------------------
MyList::MyList(int n)
{
hash_size = n;
elem = new Element();
dataNum = 0;
for(int i=0;i < n;i++)
{
elem.key = 0;
elem.val = 0;
elem.stat = 0;
}
}
//------------------------------------------
MyList::~MyList()
{
delete[] elem;
}
//------------------------------------------
void MyList::SetKey(int key,int val)
{
int pos;
if(hash_size==dataNum)
{
cout << "OverFlow~~~~" <<endl;
}
pos=hash(key);
for(int i=0;i<hash_size;i++)
{
if(elem[pos].stat == 0)
{
elem[pos].key=key;
elem[pos].val=val;
elem[pos].stat=1;
dataNum++;
cout << "KeySet Success! "<<elem[pos].key<<"\t"<<elem[pos].val<<"\t"<<pos <<endl;
return;
}
else
{
pos=(pos+1)%hash_size;
}
}
cout << "Insert Key Failed~~" <<endl;
}
//--------------------------------------------
int MyList::SearchKey(int key)
{
int pos = hash(key);
int stat = elem[pos].stat;
int num=1;
while(stat!=0 ;; num<dataNum)
{
if(elem[pos].key == key)
{
return pos;
}
else
{
pos=(pos+1)%hash_size;
stat=elem[pos].stat;
num++;
}
}
return hash_size; //防止冲突
}
//---------------------------------------------
void MyList::DeleteKey(int key)
{
int pos=SearchKey(key);
if(pos==hash_size)
{
cout << "Cannot found the key! Please check out your insert!" << endl;
}
else
{
elem[pos].key=0;
elem[pos].val=0;
elem[pos].stat=0;
dataNum--;
cout << "Delete Success~~" <<endl;
}
}
//-------------------------------------------------
int MyList::GetMapSize()
{
return dataNum%hash_size;
}
//------------------------------------------------
void MyList::ShowList()
{
if(dataNum == 0)
{
cout<<"The Table is NULL"<<endl;
return;
}
cout << "There are "<< dataNum <<" nums in the HashTable!" << endl;
cout<<"************HashTable****************"<<endl;
cout<<"key value position"<<endl;
for(int i = 0; i<hash_size;i++)
{
if(elem.stat == 0)
continue;
else
cout<<elem.key<<"\t\t"<<elem.val<<"\t\t"<<i <<endl;
}
cout<<"***************************************"<<endl;
}
//获取随即的key与val
www.atcpu.com---------------------------------void GetRdmKey(int *key)
{
srand((unsigned)time(NULL));
for(int i=0;i<6;i++)
{
key=rand()%90+10;
}
}
void GetRdmVal(int *val)
{
srand((unsigned)time(NULL));
for(int i=0;i<6;i++)
{
val=rand()%900+100;
}
}
//---------------------------------------
int main(int argc, char *argv[])
{
char flag;
int inKey,inVal,delKey;
//初始化部分随机数据
int *key,*val;
key=(int*)malloc(6*sizeof(int));
val=(int*)malloc(6*sizeof(int));
GetRdmKey(key);
GetRdmVal(val);
//写入哈西表
MyList *list=new MyList(add_scope);
cout << "Inatiating the HashTable Randomly......" <<endl;
sleep(1);
cout << "Result\t\t Key\tValue\tPosition\t"<<endl;
for(int i=0;i<6;i++)
{
list->SetKey(key,val);
}
do
{
//选择操作项
cout << "\n/*chose the operate*/"<<endl;
cout <<"Q:exit. I:insert. D:delete. Show."<<endl;
cin >>flag;
if(flag=='Q'||flag=='q')
exit(1);
else if(flag=='D'||flag=='d')
{
cout <<"please insert the key you want del:";
cin >> delKey;
list->DeleteKey(delKey);
}
else if(flag=='I'||flag=='i')
{
cout <<"please insert the new Key and new Value:";
cin >> inKey >> inVal;
list->SetKey(inKey,inVal);
}
else if(flag=='S'||flag=='s')
{
system("clear");
list->ShowList();
}
}while(1);
}
以上代码在linux平台下，kdevelop环境中编写，测试通过。
