结构设计"/>
数据结构设计
目录
一、哈希表词频统计
1.环境
2.语言
3.功能
4.源代码
二、职工电话号码查询系统
1.环境
2.语言
3.功能
4.源代码
一、哈希表词频统计
1.环境
vs code
2.语言
c++
3.功能
一篇英文文章(单词个数不超过1000个)存储在一个文本文件中，请设计程序，完成以下功能:
(1)从文件中读取英文单词(不区分大小写)，过滤掉所有的标点，统计文章中各单词出现的次数。
(2)单词查找:
用哈希表作为查找表(自行设计哈希函数)，分别实现基于线性探测法的单词查找和基于链地址法的单词查找，并分别计算其ASL。
(3)单词插入:
若查找失败，向哈希表中插入该单词。
4.源代码
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
#include<windows.h>
#include<conio.h>
#include<cmath>
#include<time.h>
#include<stdlib.h>
using namespace std;//常量的定义
const int MaxSize = 1000; //文章单词最大容量
const char* file = "D:\\下载2\\English.txt"; //待检索文件
int sum; //单词总数// 词频顺序存储结构--线性探测法
struct WordFrequency
{ //词频string word; //单词int frequency; //频率int key; //关键码
}WF[MaxSize];typedef WordFrequency datatype; //为数据类型定义一个新的名字//词频链式存储结构--链地址法
struct Node
{datatype data; //数据域Node* next; //指针域
};//读取文件函数声明
int StatisticalWord(string word); //统计文章词频
void StatisticsData(); //数据统计
int WordTransitionKey(string word); //将单词转换为唯一关键码//Hash函数声明
void HashMenu(); //哈希表菜单
void OpenHashLocateMenu(); //线性探测法哈希查找菜单
void OpenHashLocate(); //线性探测法哈希查找
void LinkHashLocate(); //链地址法哈希查找
void LinkHashWordLocateMenu(); //线性探测法哈希查找菜单void MajorMenu(); //主菜单//统计文章词频,把字符添加到结构体数组中
int StatisticalWord(string word)
{for (int i=0; i<MaxSize; i++) {if (WF[i].word == word) { WF[i].frequency++; //词频++return i; //退出函数} }//单词如果不重复，添加到哈希表中 WF[sum].word = word; //添加单词WF[sum].frequency = 1; //词频置为一WF[sum].key = WordTransitionKey(word); //添加关键码sum++; //单词总数++return 0;
}//将单词转换为关键字--随机数法
int WordTransitionKey(string word)
{int a[23] = {0,2,3,5,7,11,13,17,19,23,27,29,31,37,41,47,51,67,87,101,111,113,117};//用随机数法 int sumkey = 0;for (int i = 0; i < int(word.size()); i++) {sumkey += int(word[i]); //每个字符的ASCLL值相加}sumkey += int('a') * a[int(word.size())];//用a的ASCLL*一个随机的素数 return sumkey;
}//读取文件，并进行词频统计
void StatisticsData()
{system("cls"); //清屏ifstream fin; //文件读操作，存储设备读取到内存中fin.open(file); //关联文件filechar ch; //用于获取字符 string word; //用于存放单词int count = 0, min; //count用于标记单词个数，min用于标记最小的单词for (int i = 0; fin.get(ch); i++) { //读取文件内容，并去除符号if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {if (word == "\0") //word为空，放入第一个字母word = ch;elseword += ch; //word不为空，拼接字母组成单词} else {if (word != "\0") { //判断之前的word里面是否有单词count++; //有单词，总数++if (count>MaxSize) {cout << "文章单词超出统计上限，系统已退出" << endl;fin.close(); //关闭文件exit(0); //退出程序system("pause"); //暂停}StatisticalWord(word); //存放到结构体数组里面--哈希数组 } word = "\0"; //重置word，用于存放新单词} } fin.close(); //关闭文件
}//线性探测法哈希表类
class HashTable
{
public:HashTable(); //构造函数，初始化空散列表~HashTable() {}; //删除函数int Insert(datatype a); //插入int Search(string word); //查找datatype Get(int a);void Print(); //输出
private:int H(int k); //哈希函数(散列函数)datatype ht[MaxSize]; //散列表
};//初始化散列函数
HashTable::HashTable()
{for (int i = 0; i < MaxSize; i++) {ht[i].key = 0; //关键码初始化ht[i].word = "";ht[i].frequency = 0; // 0表示该散列单元为空}
}//哈希函数，除留余数法
int HashTable::H(int k)
{return k % MaxSize;
}//输出函数
void HashTable::Print()
{system("cls"); //清屏cout << "单词总数为：" << sum << endl;for (int i = 0; i < sum; i++) {cout << "单词："<<WF[i].word << "\t" <<"词频："<<WF[i].frequency << endl;}system("pause"); //暂停
}//查找函数
int HashTable::Search(string word)
{int key = WordTransitionKey(word); //将单词转化为关键码int i = H(key); //计算散列地址，设置比较的起始位置while (ht[i].key != 0) {if (ht[i].word == word)return i; //查找成功elsei = (i + 1) % MaxSize; //向后探测一个位置} return 0; //查找失败
}//插入函数
int HashTable::Insert(datatype f_word_key)
{int key = WordTransitionKey(f_word_key.word);//将单词转化为关键码int i = H(key); //计算散列地址，设置比较的起始位置while (ht[i].key != 0) { //寻找空的散列单元i = (i + 1) % MaxSize; //向后探测一个位置}ht[i].key = key; //关键码赋值ht[i].word = f_word_key.word; //单词赋值ht[i].frequency = f_word_key.frequency; //词频赋值return i; //返回插入位置
}//获取单词以及频率
datatype HashTable::Get(int a)
{return ht[a];
}//链地址法哈希表类
class HashTableLink
{public:HashTableLink(); //构造函数，初始化散列表~HashTableLink(); //删除函数，释放同义词子表结点int Insert(datatype fword); //插入Node* Search(string word); //查找void Print(); //输出private:int H(int k); //散列函数Node* ht[MaxSize]; //开散列表
};//构造函数
HashTableLink::HashTableLink()
{for (int i = 0; i < MaxSize; i++)ht[i] = NULL; //链式存储结构指针置空
}//析构函数，释放空间
HashTableLink :: ~HashTableLink()
{Node* p = NULL, * q = NULL;for (int i = 0; i < MaxSize; i++){p = ht[i];q = p; //用来储存pwhile (p != NULL){ //p非空p = p->next; //p后移delete q; //删除qq = p;} //while}
}//除留余数法-散列函数
int HashTableLink::H(int k)
{return k % MaxSize;
}//输出到屏幕
void HashTableLink::Print()
{system("cls"); //清屏cout << "单词总数为：" << sum << endl;for (int i = 0; i < sum; i++) {cout << "单词："<<WF[i].word << "\t" <<"词频："<<WF[i].frequency<< endl;}system("pause"); //暂停
}//链地址查找函数
Node* HashTableLink::Search(string word)
{int k = WordTransitionKey(word); //转化为关键码int j = H(k); //计算散列地址Node* p = ht[j]; //指针p初始化while (p != NULL){ //p非空if (p->data.word == word)return p; //已找到返回指针elsep = p->next; //p后移} //whilereturn NULL; //未找到返回空指针
}//插入函数(前插法)--链地址
int HashTableLink::Insert(datatype fword)
{int k = WordTransitionKey(fword.word); //转化为关键码fword.key = k; //给关键码赋值int j = H(k); //计算散列地址Node* p = Search(fword.word); //调用查找函数if (p != NULL) //p非空，表示该内容已经插入过了return -1; //已存在元素k，无法插入 else { //p为空，表示该内容未插入p = new Node; //生成新节点p->data.key = fword.key; //关键码赋值p->data.frequency = fword.frequency; //词频赋值p->data.word = fword.word; //单词赋值p->next = ht[j]; //新节点插入ht[j]ht[j] = p; //更新节点return 1; //插入成功标志 }
}//哈希表菜单
void HashMenu()
{while(true){system("cls"); //清屏cout << "*******************基于哈希表的英文单词词频统计和检索系统*******************" << endl;cout << "1.线性探测法哈希查找" << endl;cout << "2.链地址法哈希查找" << endl;cout << "3.返回上一级" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n){case 1 : OpenHashLocate(); //线性探测法哈希查找break;case 2 : LinkHashLocate(); //链地址法哈希查找break;case 3 : return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause");} }return;
}//线性探测法哈希查找菜单
void OpenHashLocateMenu()
{HashTable HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表中double a = (double)sum / MaxSize; //装填因子system("cls"); //清屏cout << "*******************基于哈希表的英文单词词频统计和检索系统*******************" << endl;cout << "---线性探测单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;int i = HT.Search(word); //获取散列地址if (i) //查找成功的ASL {cout << "此单词为：" << HT.Get(i).word << endl;cout << "此单词的词频：" << HT.Get(i).frequency << endl;double ans=(double)(1 + (1.00)/ (1 - a)) / 2; printf("查找成功时ASL=%.2lf\n",ans);}else//查找失败，把单词加入到哈希表当中 ，并输出失败的ASL {WF[sum].word=word;WF[sum].frequency=1;WF[sum].key=WordTransitionKey(word);HT.Insert(WF[sum]);sum++;cout << "查找失败" << endl;double ans=(double)(1+1/pow(1-a,2))/2;printf("查找失败时ASL=%.2lf\n",ans);}system("pause");
}//线性探测法哈希查找
void OpenHashLocate()
{HashTable HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表中while(true){system("cls"); cout << "*******************基于哈希表的英文单词的词频统计和检索系统*******************" << endl;cout << "---基于线性探测法的哈希查找---" << endl;cout << "1.词频统计" << endl;cout << "2.单词查找" << endl;cout << "3.返回上一级" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n){case 1 : HT.Print(); //词频统计break;case 2 : OpenHashLocateMenu(); //线性探测法的哈希查找菜单break;case 3 :return;default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause");} }
}//链地址法哈希查找
void LinkHashLocate()
{HashTableLink HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表while(true){system("cls"); //清屏cout << "*******************基于哈希表的英文单词词频统计和检索系统*******************" << endl;cout << "---基于链地址法的哈希查找---" << endl;cout << "1.词频统计" << endl;cout << "2.单词查找" << endl;cout << "3.返回上一级" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n){case 1: HT.Print(); //词频统计break;case 2:LinkHashWordLocateMenu(); //单词查找菜单break;case 3: return; //退出函数default: cout << "输入的不是有效符号，请重新输入" << endl; system("pause");} }
}//链地址法哈希查找菜单
void LinkHashWordLocateMenu()
{HashTableLink HT;for (int i = 0; i < sum; i++)HT.Insert(WF[i]); //把数据插入到哈希表double a= (double)sum / MaxSize;//散列表的装填因子system("cls");cout << "*******************基于哈希表的英文单词词频统计和检索系统*******************" << endl;cout << "---链地址单词查找---" << endl;cout << "请输入要查找的单词：";string word;cin >> word;HT.Search(word);Node* p = HT.Search(word); //返回目标指针if (p != NULL) {cout << "此单词为：" << p->data.word << endl;cout << "此单词的词频：" << p->data.frequency<< endl;double ans=1+(double)(a)/2;printf("查找成功时ASL=%.2lf\n", ans);} //ifelse{WF[sum].word=word;WF[sum].frequency=1;WF[sum].key=WordTransitionKey(word);HT.Insert(WF[sum]);sum++;cout << "查找失败" << endl;double e=2.718281;double ans=(double)(a+pow(e,-a)); printf("查找失败时ASL=%.2lf\n",ans);}system("pause"); //暂停
}
//主菜单
void MajorMenu()
{while (true) {cout << "*******************基于哈希表的英文单词词频统计和检索系统*******************" << endl;cout << "---菜单---" << endl;cout << "1.基于哈希表的查找" << endl;cout << "2.退出系统" << endl;cout << "请按相应的数字键进行选择：" << endl;int n;cin >> n;switch (n) {case 1:HashMenu();break;case 2:cout << "系统已退出" << endl;return;default:cout << "输入的不是有效符号，请重新输入" << endl;system("cls"); //清屏system("pause"); //暂停} }
}
//主函数
int main()
{ifstream fin;fin.open(file);//获取文件English.txt if (!fin.is_open()) {cout << "EngLish.txt文件不存在，请检查文件名或者目录下文件是否存在..." << endl;system("pause");return 0;} else {cout << "EngLish.txt文件加载中..." << endl;Sleep(1000);//延时函数，延时1秒} StatisticsData(); //数据统计MajorMenu();//主菜单return 0;
}二、职工电话号码查询系统
1.环境
vs code
2.语言
c++
3.功能
设计散列表，实现职工电话号码查询系统，要求:
(1) 每个记录包括下列内容:
(电话号码(11位) 、工号(5位) 、姓名、性别、院系名)总记录数不少于300条。
(2)从文件中读入各记录，分别以电话号码和用户名为关键字建立散列表(散列函数要求使用除留余数法，采用开放定址法处理冲突)
(3)查找并显示给定电话号码的记录，并输出查找长度。
(4)查找并显示给定用户名的记录(若有同名记录,则输出全部同名用户信息)，并输出查找长度。
(5) 从文件读入各记录，以工号为关键字建立散列表(散列函数要求使用除留余数法，采用链地址法处理冲突)。
(6) 查找并显示给定院系的所有职工信息。
4.源代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int MAXSIZE=300;
int n;//读入数据数
typedef struct
{string tel;//电话string num;//工号string name;//姓名string sex;//性别string col;//院系
}Hash;typedef Hash Elemtype;//重新定义一个类型 typedef struct LNode
{Elemtype data;LNode *next;
}*LinkList;Hash ht[MAXSIZE];//定义结构体线性表 //初始化单链表
void InitList(LinkList h[MAXSIZE])
{for(int i=0;i<MAXSIZE;i++){h[i]=new LNode;h[i]->next=NULL;}
}//初始化线性表
void init()
{n=0;return ;
} //将文件中的数据逐条读入顺序表L中
void ReadData(Hash ht[])
{int i=0;init(); //初始化顺序表ifstream infile("D:\\下载2\\edg.txt"); //以输入的方式（读文件的方式）打开文件d:\book.txtwhile(!infile.eof()) //只要文件没读完，就读一行数据到顺序表L中的第i个分量中{infile>>ht[i].tel; infile>>ht[i].num; infile>>ht[i].name;infile>>ht[i].sex;infile>>ht[i].col;i++;}n=i; //修改顺序表的长度infile.close (); //关闭文件
} int H(int x)//除留余数法
{return x%MAXSIZE;
}int KEY(string x)//求关键字
{int a[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};//减少冲突 int ans=0;for(int i=0;i<x.size();i++)ans+=int(x[i]);return (a[x.size()]*ans+MAXSIZE)%MAXSIZE;
}void name_create(int op)//开放寻址法电话号码/姓名建表
{Hash a[MAXSIZE];int ans=0;for(int i=0;i<n;i++){int key;if(op==1)key=H(KEY(ht[i].tel));else if(op==2)key=H(abs(KEY(ht[i].name)));int f=key;while(a[key].name!="")//如果当前有冲突，向下一个继续探测 {key++;if(key==MAXSIZE-1) key=0;if(f==key) break;//再次探测这个位置，跳出循环 }a[key]=ht[i]; //插入哈希表中，也就是将结构体数组赋值 } cout<<"输出开放寻址法所建的哈希表:"<<endl;for(int i=0;i<MAXSIZE;i++){if(a[i].name!=""){cout<<a[i].tel<<" "<<a[i].num<<" "<<a[i].name<<" "<<a[i].sex<<" "<<a[i].col<<endl;}}cout<<endl;return ;
} void tel_search()//按电话号码查找
{cout<<"请输入一个电话号码：";string x;cin>>x;cout<<endl;int ans=0;int p=0; for(int i=0;i<n;i++){if(ht[i].tel==x){p++;//设置访问标志 cout<<ht[i].tel<<" "<<ht[i].num<<" "<<ht[i].name<<" "<<ht[i].sex<<" "<<ht[i].col<<endl;}ans++;//继续查找，长度+1if(p) break; //如果查到，退出循环 }if(p)cout<<"查找长度为："<<ans<<endl;else cout<<"未查找到该用户！"<<endl;return ;
} void name_search()
{cout<<"请输入一个姓名：";string x;cin>>x;cout<<endl;int ans=0;int p=0;int q=0;for(int i=n-1;i>=0;i--){if(ht[i].name==x){q=i;break;}} for(int i=0;i<n;i++){if(ht[i].name==x){p++;//设置访问标志 cout<<ht[i].tel<<" "<<ht[i].num<<" "<<ht[i].name<<" "<<ht[i].sex<<" "<<ht[i].col<<endl;}}if(p)cout<<"查找长度为："<<q+1<<endl;else cout<<"未查找到该用户！"<<endl;return ;
}void num_create()//基于链地址法工号创建哈希表
{LinkList h[MAXSIZE];InitList(h);int ans=0;for(int i=0;i<n;i++){int key=H(KEY(ht[i].num));LinkList p=new LNode;p=h[abs(key)];while(p->next!=NULL) p=p->next;//让p指向尾节点 ，用尾插法 建表 LinkList q=new LNode;q->data.name=ht[i].name;//复制姓名 q->data.col=ht[i].col;//复制学院 q->data.num=ht[i].num;//复制工号 q->data.sex=ht[i].sex;//复制性别 q->data.tel=ht[i].tel;//复制电话 p->next=q;//尾插发 q->next=NULL;//将表尾置空 }cout<<"输出链地址法建表职工信息："<<endl;for(int i=0;i<MAXSIZE;i++){LinkList p=new LNode;if(h[i]->next==NULL) continue;else {p=h[i]->next;while(p){cout<<p->data.col<<" "<<p->data.name<<" "<<p->data.num<<" "<<p->data.sex<<" "<<p->data.tel<<endl;p=p->next;}}}return ;
}void query()//输出给定院系职工信息
{cout<<"请输入一个院系:";string op;cin>>op;cout<<"该院系所有的职工为:"<<endl;for(int i=0;i<n;i++){if(ht[i].col==op){cout<<ht[i].tel<<" "<<ht[i].num<<" "<<ht[i].name<<" "<<ht[i].sex<<" "<<ht[i].col<<endl;}}return ;
} void menu()
{cout<<"***********欢迎使用职工电话号码查询系统*************"<<endl;cout<<"***********1.开放寻址法以电话建立哈希表*************"<<endl;cout<<"***********2.开放寻址法以姓名建立哈希表*************"<<endl;cout<<"***********3.查询电话号码记录并输出长度*************"<<endl;cout<<"***********4.查找用户名并且输出查找长度*************"<<endl;cout<<"***********5.链地址法以工号来建立哈希表*************"<<endl;cout<<"***********6.查找显示给定院系的职工信息*************"<<endl;
}int main()
{ReadData(ht);//读取信息 while(1){menu();int op;cout<<"请输入一个序号："; cin>>op;puts("");//换行 switch(op){case 1:name_create(op); break;case 2:name_create(op);break;case 3:tel_search();break;case 4:name_search();break;case 5:num_create();break;case 6:query();break;default:printf("序号错误！");break;}}return 0;
}更多推荐
数据结构设计
发布评论