哈希链表 操作大全 实现

哈希链表 操作大全 实现

//------------------------------Struct.h----------------------

#define MAX 100

struct ElemStruct
{
char str[MAX];
char info[MAX];
ElemStruct *next;
};

struct TableStruct
{
ElemStruct *link;
};

//-------------------------------HashTable.h--------------------

#include "stdafx.h"
#include "Struct.h"
#include<cstring>

template <class DataType>
class HashTable
{
private:
int hashFunc(const DataType &obj)
{
int sum = 0;
for(int i=0;i<strlen(obj.str);i++)
sum += (int)obj.str[i];
return sum%size;
}
TableStruct *table;
int size;

public:
HashTable(int s)
{
size = s;
table = (TableStruct*)malloc(sizeof(TableStruct)*size);;
for(int i = 0;i<getSize();i++)
table[i].link = NULL;
}

int getSize()
{
return size;
}

int find(const DataType &key)
{
int location = hashFunc(key);
if( location < 0 || location> getSize())
return -1;
else if(table[location].link==NULL)
return 0;
else
{
DataType *p = table[location].link;
while(p != NULL)
{
if(!strcmp(key.str,p->str))
return 1;
p = p->next;
}
return 0;
}
}

int insert(const DataType &newObject)
{
int location = hashFunc(newObject);
if(location < 0 || location> getSize())
return -1;
else
{
int flag = find(newObject);
if(flag==1)
return 0;
else if(flag==0)
{
DataType *p1 = (DataType*)malloc(sizeof(DataType));
strcpy_s(p1->str,newObject.str);
strcpy_s(p1->info,newObject.info);
p1->next = table[location].link;
table[location].link = p1;
return 1;
}
}
}

int remove(DataType &removeObject)
{
int location = hashFunc(removeObject);
if( location < 0 || location> getSize())
return -1;
else
{
DataType *p,*q;
p=q= table[location].link;
while(p != NULL)
{
if(!strcmp(p->str,removeObject.str))
{
if(p==q)
{
table[location].link = p->next;
}
else
{
q->next = p->next;
}
return 1;
}
q = p;
p = p->next;
}
return 0;
}
}

int update(DataType &updateObject)
{
int location = hashFunc(updateObject);
if( location < 0 || location> getSize())
return -1;
else
{
DataType *p = table[location].link;
while(p != NULL)
{
if(!strcmp(p->str,updateObject.str))
{
//关键字不能更新，只能更新其信息
strcpy_s(p->info,updateObject.info);
return 1;
}
p = p->next;
}
return 0;
}
}

void makeEmpty()
{
for(int i = 0;i<getSize();i++)
table[i].link = NULL;
}
};

//---------------------主函数-------------------------

// 散列表实现.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include"HashTable.h"
#include<iostream>
using namespace std;

const int SIZE = 199;

int _tmain(int argc, _TCHAR* argv[])
{
HashTable<ElemStruct> ht(SIZE);
cout<<"---------------------请选择需要进行的操作-----------------------"<<endl;
cout<<"------插入哈希链表(I/i)-------"<<endl;
cout<<"------查找哈希链表(S/s)-------"<<endl;
cout<<"------移除哈希元素(R/r)-------"<<endl;
cout<<"------更新哈希元素(U/u)------"<<endl;
cout<<"------清空哈希链表(C/c)------"<<endl;
cout<<"------退出操作(E/e)------------"<<endl;
char cmd;
cin>>cmd;
while(1)
{
if(cmd=='I'||cmd=='i')
{
cout<<"请输入需要插入的这些元素，以0结束："<<endl;
ElemStruct myStruct;
while(1)
{
cout<<"输入关键字：";
cin>>myStruct.str;
if(!strcmp(myStruct.str,"0"))
break;
cout<<"输入信息：";
cin>>myStruct.info;
myStruct.next = NULL;
int flag = ht.insert(myStruct);
if(flag == -1)
cout<<"哈希散列值非法，此元素非法！"<<endl;
else if(flag == 0)
cout<<"此元素已存在！"<<endl;
else if(flag == 1)
cout<<"插入成功！"<<endl;
}
}
else if(cmd=='S'||cmd=='s')
{
cout<<"请输入需要查询的这些元素，以0结束："<<endl;
ElemStruct myStruct;
while(1)
{
cout<<"输入关键字：";
cin>>myStruct.str;
if(!strcmp(myStruct.str,"0"))
break;
myStruct.next = NULL;
int flag = ht.find(myStruct);
if(flag == -1)
cout<<"哈希散列值非法，此元素非法！"<<endl;
else if(flag == 0)
cout<<"此元素不存在！"<<endl;
else if(flag == 1)
cout<<"查询成功！"<<endl;
}
}
else if(cmd=='R'||cmd=='r')
{
cout<<"请输入需要移除的这些元素，以0结束："<<endl;
ElemStruct myStruct;
while(1)
{
cout<<"输入关键字：";
cin>>myStruct.str;
if(!strcmp(myStruct.str,"0"))
break;
myStruct.next = NULL;
int flag = ht.remove(myStruct);
if(flag == -1)
cout<<"哈希散列值非法，此元素非法！"<<endl;
else if(flag == 0)
cout<<"此元素不存在！"<<endl;
else if(flag == 1)
cout<<"移除成功！"<<endl;
}
}
else if(cmd=='U'||cmd=='u')
{
cout<<"请输入需要更新的这些元素，以0结束："<<endl;
ElemStruct myStruct;
while(1)
{
cout<<"输入需要更新的元素的关键字：";
cin>>myStruct.str;
if(!strcmp(myStruct.str,"0"))
break;
cout<<"输入需要更新的信息：";
cin>>myStruct.info;
myStruct.next = NULL;
int flag = ht.update(myStruct);
if(flag == -1)
cout<<"哈希散列值非法，此元素非法！"<<endl;
else if(flag == 0)
cout<<"此元素不存在！"<<endl;
else if(flag == 1)
cout<<"更新成功！"<<endl;
}
}
else if(cmd=='C'||cmd=='c')
{
cout<<"如果清空，所有元素都将不存在了！确定要清空(Y/y)？"<<endl;
char cmd1;
cin>>cmd1;
if(cmd1=='Y'||cmd1=='y')
ht.makeEmpty();
cout<<"清空成功！"<<endl;
}
else if(cmd=='E'||cmd=='e')
break;
else
{
cout<<"命令不正确，请重新输入！"<<endl;
}
cout<<"---------------------请选择需要进行的操作-----------------------"<<endl;
cin>>cmd;
}
system("pause");
return 0;
}