20386053
- 浏览: 461380 次
-
文章分类
最新评论
哈希表应用
本文转自：哈希表的应用(C++实现)
问题描述：设计哈希表实现电话号码查询系统，实现下列功能：
(1) 假定每个记录有下列数据项：电话号码、用户名、地址。
(2) 一是从数据文件old.txt(自己现行建好)中读入各项记录，二是由系统随机产生各记录，并且把记录保存到new.txt文件中以及显示到屏幕上，记录条数不要少于30，然后分别以电话号码和用户名为关键字建立哈希表。
(3) 分别采用伪随机探测再散列法和再哈希法解决冲突。
(4) 查找并显示给定电话号码的记录；查找并显示给定用户名的记录。
(5) 将没有查找的结果保存到结果文件Out.txt中，显示查找结果前，要有提示语句。
(1) 假定每个记录有下列数据项：电话号码、用户名、地址。
(2) 一是从数据文件old.txt(自己现行建好)中读入各项记录，二是由系统随机产生各记录，并且把记录保存到new.txt文件中以及显示到屏幕上，记录条数不要少于30，然后分别以电话号码和用户名为关键字建立哈希表。
(3) 分别采用伪随机探测再散列法和再哈希法解决冲突。
(4) 查找并显示给定电话号码的记录；查找并显示给定用户名的记录。
(5) 将没有查找的结果保存到结果文件Out.txt中，显示查找结果前，要有提示语句。
代码：
// MyHashTable.cpp : 定义控制台应用程序的入口点。
////设计哈希表实现电话号码查询系统
//说明：一是从文件old.txt中读取的数据自己在程序运行前建立，
// 二是由系统随机生成数据，在程序运行由随机数产生器生成，并且将产生的记录保存到 new.txt文件。
//存在的问题：使用随机产生的文件，在显示时出现乱码
#include "stdafx.h"
#include<fstream>//文件流
#include<iostream>
#include <string>
using namespace std;
const int D[] = {3,5,8,11,13,14,19,21};//预定再随机数
const int HASH_MAXSIZE = 50;//哈希表长度
//记录信息类型
class DataInfo
{
public:
DataInfo();//默认构造函数
friend ostream& operator<<(ostream& out, const DataInfo& dataInfo); //重载输出操作符
//friend class HashTable;
//private:
string name;//姓名
string phone;//电话号码
string address;//地址
char sign;//冲突的标志位，'1'表示冲突，'0'表示无冲突
};
DataInfo::DataInfo():name(""), phone(""), address(""), sign('0')
{
}
ostream& operator<<(ostream& out, const DataInfo& dataInfo) //重载输出操作符
{
cout << "姓名：" << dataInfo.name << " 电话：" << dataInfo.phone
<< " 地址：" << dataInfo.address << endl;
return out;
}
//存放记录的哈希表类型
class HashTable
{
public:
HashTable();//默认构造函数
~HashTable();//析构函数
int Random(int key, int i);// 伪随机数探测再散列法处理冲突
void Hashname(DataInfo *dataInfo);//以名字为关键字建立哈希表
int Rehash(int key, string str);// 再哈希法处理冲突 注意处理冲突还有链地址法等
void Hashphone(DataInfo *dataInfo);//以电话为关键字建立哈希表
void Hash(char *fname, int n);// 建立哈希表
//fname 是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式
int Findname(string name);// 根据姓名查找哈希表中的记录对应的关键码
int Findphone(string phone);// 根据电话查找哈希表中的记录对应的关键码
void Outhash(int key);// 输出哈希表中关键字码对应的一条记录
void Outfile(string name, int key);// 在没有找到时输出未找到的记录
void Rafile();// 随机生成文件，并将文件保存在 new.txt文档中
void WriteToOldTxt();//在运行前先写入数据
//private:
DataInfo *value[HASH_MAXSIZE];
int length;//哈希表长度
};
HashTable::HashTable():length(0)//默认构造函数
{
//memset(value, NULL, HASH_MAXSIZE*sizeof(DataInfo*));
for (int i=0; i<HASH_MAXSIZE; i++)
{
value[i] = new DataInfo();
}
}
HashTable::~HashTable()//析构函数
{
delete[] *value;
}
void HashTable::WriteToOldTxt()
{
ofstream openfile("old.txt");
if (openfile.fail())
{
cout << "文件打开错误！" << endl;
exit(1);
}
string oldname;
string oldphone;
string oldaddress;
for (int i=0; i<30; i++)
{
cout << "请输入第" << i+1 << "条记录:" << endl;
cin >> oldname ;
cin >> oldphone;
cin >> oldaddress;
openfile << oldname << " " << oldphone << " " << oldaddress << "," << endl;
}
openfile.close();
}
int HashTable::Random(int key, int i)// 伪随机数探测再散列法处理冲突
{//key是冲突时的哈希表关键码，i是冲突的次数，N是哈希表长度
//成功处理冲突返回新的关键码，未进行冲突处理则返回-1
int h;
if(value[key]->sign == '1')//有冲突
{
h = (key + D[i]) % HASH_MAXSIZE;
return h;
}
return -1;
}
void HashTable::Hashname(DataInfo *dataInfo)//以名字为关键字建立哈希表
{//利用除留取余法建立以名字为关键字建立的哈希函数，在发生冲突时调用Random函数处理冲突
int i = 0;
int key = 0;
for (int t=0; dataInfo->name[t]!='\0'; t++)
{
key = key + dataInfo->name[t];
}
key = key % 42;
while(value[key]->sign == '1')//有冲突
{
key = Random(key, i++);//处理冲突
}
if(key == -1) exit(1);//无冲突
length++;//当前数据个数加
value[key]->name = dataInfo->name;
value[key]->address = dataInfo->address;
value[key]->phone = dataInfo->phone;
value[key]->sign = '1';//表示该位置有值
//cout << value[key]->name << " " << value[key]->phone << " " << value[key]->address << endl;
}
int HashTable::Rehash(int key, string str)// 再哈希法处理冲突
{//再哈希时使用的是折叠法建立哈希函数
int h;
int num1 = (str[0] - '0') * 1000 + (str[1] - '0') * 100 + (str[2] - '0') * 10 + (str[3] - '0');
int num2 = (str[4] - '0') * 1000 + (str[5] - '0') * 100 + (str[6] - '0') * 10 + (str[7] - '0');
int num3 = (str[8] - '0') * 100 + (str[9] - '0') * 10 + (str[10] - '0');
h = num1 + num2 + num3;
h = (h + key) % HASH_MAXSIZE;
return h;
}
void HashTable::Hashphone(DataInfo *dataInfo)//以电话为关键字建立哈希表
{//利用除留取余法建立以电话为关键字建立的哈希函数，在发生冲突时调用Rehash函数处理冲突
int key = 0;
int t;
for(t=0; dataInfo->phone[t] != '\0'; t++)
{
key = key + dataInfo->phone[t];
}
key = key % 42;
while(value[key]->sign == '1')//有冲突
{
key = Rehash(key, dataInfo->phone);
}
length++;//当前数据个数加
value[key]->name = dataInfo->name;
value[key]->address = dataInfo->address;
value[key]->phone = dataInfo->phone;
value[key]->sign = '1';//表示该位置有值
}
void HashTable::Outfile(string name, int key)//在没有找到时输出未找到的记录
{
ofstream fout;
if((key == -1)||(value[key]->sign == '0'))//判断哈希表中没有记录
{
fout.open("out.txt",ios::app);//打开文件
if(fout.fail())
{
cout << "文件打开失败!" << endl;
exit(1);
}
fout << name << endl;//将名字写入文件,有个问题，每次写入的时候总是将原来的内容替换了
fout.close();
}
}
void HashTable::Outhash(int key)//输出哈希表中关键字码对应的记录
{
if((key==-1)||(value[key]->sign=='0'))
cout << "没有找到这条记录！" << endl;
else
{
for(unsigned int i=0; value[key]->name[i]!='\0'; i++)
{
cout << value[key]->name[i];
}
for(unsigned int i=0; i<10; i++)
{
cout << " ";
}
cout << value[key]->phone;
for(int i=0; i<10; i++)
{
cout << " ";
}
cout << value[key]->address << endl;
}
}
void HashTable::Rafile()//随机生成文件，并将文件保存在new.txt文档中
{
ofstream fout;
fout.open("new.txt");//打开文件，等待写入
if(fout.fail())
{
cout << "文件打开失败！" << endl;
exit(1);
}
for(int j=0; j<30; j++)
{
string name = "";
for(int i=0; i<20; i++)//随机生成长个字的名字
{
name += rand() % 26 + 'a';//名字是由个字母组成
}
fout << name << " ";//将名字写入文件
string phone = "";
for(int i=0; i<11; i++)//随机生成长位的电话号码
{
phone += rand() % 10 + '0';//电话号码是纯数字
}
fout << phone << " ";//将电话号码写入文件
string address = "";
for(int i=0; i<29; i++)//随机生成长个字的名字
{
address += rand() % 26 + 'a';//地址是由个字母组成
}
address += ',';
fout << address << endl;//将地址写入文件
}
fout.close();
}
void HashTable::Hash(char *fname, int n)//建立哈希表
//fname是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式
//函数输入数据，并根据选择调用Hashname或Hashphone函数进行哈希表的建立
{
ifstream fin;
int i;
fin.open(fname);//读文件流对象
if(fin.fail())
{
cout << "文件打开失败！" << endl;
exit(1);
}
while(!fin.eof())//按行读入数据
{
DataInfo *dataInfo = new DataInfo();
char* str = new char[100];
fin.getline(str, 100, '\n');//读取一行数据
if(str[0] == '*')//判断数据结束
{
break;
}
i = 0;//记录字符串数组的下标
//a-z:97-122 A-Z:65-90
//本程序的姓名和地址都使用小写字母
while((str[i] < 97) || (str[i] > 122))//读入名字
{
i++;
}
for(; str[i]!=' '; i++)
{
dataInfo->name += str[i];
}
while(str[i] == ' ')
{
i++;
}
for(int j=0; str[i]!=' '; j++,i++)//读入电话号码
{
dataInfo->phone += str[i];
}
while(str[i] == ' ')
{
i++;
}
for(int j=0; str[i]!=','; j++,i++)//读入地址
{
dataInfo->address += str[i];
}
if(n == 1)
{
Hashname(dataInfo);
}
else
{
Hashphone(dataInfo);//以电话为关键字
}
delete []str;
delete dataInfo;
}
fin.close();
}
int HashTable::Findname(string name)//根据姓名查找哈希表中的记录对应的关键码
{
int i = 0;
int j = 1;
int t;
int key = 0;
for(key=0, t=0; name[t] != '\0'; t++)
{
key = key + name[t];
}
key = key % 42;
while((value[key]->sign == '1') && (value[key]->name != name))
{
key = Random(key, i++);
j++;
if(j >= length) return -1;
}
return key;
}
int HashTable::Findphone(string phone)//根据电话查找哈希表中的记录对应的关键码
{
int key = 0;
int t;
for(t=0; phone[t] != '\0' ; t++)
{
key = key + phone[t];
}
key = key % 42;
int j = 1;
while((value[key]->sign == '1') && (value[key]->phone != phone))
{
key = Rehash(key, phone);
j++;
if(j >= length)
{
return -1;
}
}
return key;
}
void main()
{
//WriteToOldTxt();
int k;
int ch;
char *Fname;
HashTable *ht = new HashTable;
while(1)
{
system("cls");//cls命令清除屏幕上所有的文字
cout << "欢迎使用本系统！" << endl << endl;
cout << "请选择数据" << endl;
cout << "1.使用已有数据文件" << endl;
cout << "2.随机生成数据文件" << endl;
cout << "0.结束" << endl;
cout << "输入相应序号选择功能：";
cin >> k;
switch(k)
{
case 0:
return;
case 1:
Fname = "old.txt";//从数据文件old.txt(自己现行建好)中读入各项记录
break;
case 2:
ht->Rafile();
Fname = "new.txt";//由系统随机产生各记录，并且把记录保存到new.txt文件中
break;
default:
cout << "输入序号有误，退出程序。" << endl;
return;
}
do
{
system("cls");
cout << " 请选择查找方式" << endl;
cout << "1.通过姓名查找" << endl;
cout << "2.通过电话查找" << endl;
cout << "输入相应序号选择功能：";
cin >> ch;
if((ch != 1) && (ch != 2))
cout << "输入序号有误！" << endl;
}while((ch != 1) && (ch != 2));
ht->Hash(Fname, ch);
while(ch == 1)
{
int choice;
cout << endl << "请选择功能" << endl;
cout << "1.输入姓名查找数据" << endl;
cout << "2.显示哈希表" << endl;
cout << "0.退出"<<endl;
cout << "输入相应序号选择功能：";
cin >> choice;
switch(choice)
{
case 1:
{//注意此处应该加上大括号
int key1;
string name;
cout << "请输入姓名：";
cin >> name;
key1 = ht->Findname(name);
ht->Outfile(name, key1);
ht->Outhash(key1);
}
break;
case 2:
{
for(int i=0; i<HASH_MAXSIZE; i++)
{
if(ht->value[i]->sign!='0')
{
ht->Outhash(i);
}
}
}
break;
default:
cout << endl << "您的输入有误！" << endl;
}
if(choice == 0)
{
return;
}
}
while(ch == 2)
{
int choice;
cout << endl << "请选择功能" << endl;
cout << "1.输入电话查找数据" << endl;
cout << "2.显示哈希表"<<endl;
cout << "0.退出"<<endl;
cout << "输入相应序号选择功能：";
cin >> choice;
switch(choice)
{
case 1:
{
int key2;
string phone;
cout << "请输入11位的电话号码：";
do
{
cin >> phone;
if(phone.length() != 11)
{
cout << "电话号码应为11位！\n请重新输入：";
}
}while(phone.length() != 11);
key2 = ht->Findphone(phone);
ht->Outfile(phone, key2);
ht->Outhash(key2);
}
break;
case 2:
{
for(int i=0; i<HASH_MAXSIZE; i++)
{
if(ht->value[i]->sign != '0')
{
ht->Outhash(i);
}
}
}
break;
default:
cout << endl << "您的输入有误！" << endl;
}
if(choice == 0)
{
return;
}
}
while((ch != 1) && (ch != 2))
{
cout << "您的输入有误！请输入相应需要选择功能：";
}
}
system("pause");
}
分享到：
发表评论
相关推荐
哈希表应用 设计哈希表实现图书查找系统，完成相应的建表和查表程序。从键盘输入各图书相关信息，分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个；构造合适的哈希函数。 （1）记录由外部输入。 （2...
大数据哈希表应用主要关注如何在分布式系统中实现哈希表，处理大规模数据的快速查找、更新和删除操作。 大数据哈希表通常需要水平扩展，通过分布数据到多个哈希表实例中以避免单点瓶颈。在分布式哈希表中，节点会...
int H1(char *key) { int temp[10]; long k,d=0,e; int c,f,g; while(*key) d+=*key++; d*=d; e=d; for(c=0;d!=0;c++) { d/=10; } g=c; for(f=c;f>=0;f--) { temp[--g]=e; e/=10;...}
以上就是关于C++ STL中的哈希表及其应用的基本知识，它在很多场景下提供了高效的数据处理能力，是C++编程中不可或缺的一部分。通过理解和熟练掌握这些概念和用法，能有效提升程序的效率和可读性。
在哈希表的简单应用中，我们通常会关注以下几个方面： 1. **哈希函数**：哈希函数是哈希表的核心，它负责将输入（键）转换为数组的索引。一个好的哈希函数应该尽量让不同的键产生不同的哈希值，以减少冲突。常见的...
设计散列表实现手机号码查找系统，对手机号码进行Hash。...（4）输入手机号码，对该手机号码进行哈希查找，显示散列的次数，若号码存在，则显示号码对应的人名、性别以及邮件地址，否则提示该号码不存在
1. 提高检索速度：哈希表可以提高数据检索速度，提高应用程序的性能。 2. 节省存储空间：哈希表可以节省存储空间，减少存储成本。 3. 实现关联数组：哈希表可以实现关联数组，提高数据处理效率。 哈希表的构造方法...
4. **通讯录实现**：将哈希表应用于通讯录，意味着键可能是联系人的名字，而值可能是联系人信息（如电话号码、地址等）。这种应用要求哈希函数能够处理字符串，字符串的哈希函数通常需要考虑每个字符的贡献。 5. **...
电话本的添加、查找和删除操作是哈希表应用的经典场景。 **哈希表的基本概念：** 1. **哈希函数**：这是哈希表的核心，它将输入（如电话本中的姓名）转换为数组索引，使得数据可以快速存取。一个好的哈希函数应该...
在这个简单的应用实例中，我们将探讨如何在C#环境下使用哈希表，并通过Visual Studio 2010进行开发。 哈希表的基本工作原理是通过一个哈希函数将键转化为数组的下标，这个过程称为哈希化。理想的哈希函数能够确保...
然而，实际应用中，哈希表的性能受到冲突率的影响，冲突过多可能导致性能退化至接近O(n)。 了解并熟练掌握哈希表的构造方法，不仅能够提高程序的运行效率，还能帮助解决许多实际问题，如数据库索引、缓存系统、数据...
在实际应用中，通常会根据预期的数据规模动态调整哈希表的大小，以确保负载因子（已存元素数量/数组大小）保持在一个合理的范围内，以平衡空间和时间效率。 四、哈希表的查找 查找操作是哈希表的主要功能之一。对于...
总结一下，哈希表赎金信问题是C语言面试中考察哈希表应用的经典案例，通过解决这个问题，可以展示对数据结构、算法和C语言编程技巧的掌握程度。理解和熟练运用哈希表不仅对于面试，对于实际的软件开发工作也有着深远...
哈希表是一种高效的数据结构，它通过特定的函数——哈希函数，将任意大小的键（key）映射到一个固定大小的数组中，从而实现快速查找、插入和删除操作。在“数据结构哈希表设计实验报告”中，我们可能会涉及到以下几...
在这个"哈希表源代码"压缩包中，我们可以期待找到实现哈希表的源代码，这对于理解哈希表的工作原理以及在实际编程中应用哈希表非常有帮助。 哈希表的基本概念： 1. 键值对：哈希表由一系列键值对组成，每个键对应...
哈希表，也被称为散列表，是计算机科学中一种非常重要的数据结构，它提供了...无论是编程语言的内置数据结构，如Python的dict或Java的HashMap，还是在数据库系统、缓存机制等应用场景中，哈希表都是不可或缺的一部分。
### 哈希表及其应用 #### 一、定义与基本原理 哈希表是一种高效的数据结构，用于存储键值对数据。它通过一个特定的函数（哈希函数）将键映射到一个固定的范围内，进而定位到具体的存储位置。哈希表的主要优势在于...
5. **哈希表的应用**：哈希表广泛应用于数据库索引、缓存系统、编程语言的字典结构（如Python的字典、JavaScript的对象）、集合和映射等场景。 6. **具体实现代码**：哈希表的实现通常涉及到以下步骤： - 初始化...
电话号码查询系统是哈希表应用的经典场景，尤其适合处理大量的查询操作。 首先，理解哈希表的核心概念至关重要。哈希函数是将输入（通常是一个字符串，如电话号码）转换为数组索引的函数。理想的哈希函数能够均匀...