哈希链表操作大全实现

╰半夏微凉° 2022-05-15 13:24 188阅读 0赞

**哈希链表 操作大全 实现**

**//------------------------------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;  
\}**