数据结构课程设计——散列文件的插入、删除和查找
2023-12-27 05:07:20
前言
NEFU，计算机与控制工程学院，基于C/C++的数据结构 ，五个课程设计
环境
操作系统：Windows 10
IDE：Visual Studio Code、Dev C++ 5.11、Code::Blocks
说明
本系列包含以下课程设计的完整源代码，其中迷宫问题就题目要求进行了拓展优化(创新)
ps：想得高分除了将课设本身做得很好外，可以自己拓展创新，同样很容易拿优秀
其他联系方式：
Gitee：@不太聪明的椰羊
B站：@不太聪明的椰羊
ps：一定要注明来意！
一、需求和规格说明
1.1 问题描述
编写函数实现散列文件的插入、删除和查找。
?1.2 说明
（1）初始化散列表；
（2）向散列表中插入一个元素；
（3）从散列表中删除一个元素；
（4）从散列表中查找一个元素。
?散列表通常采用链接法处理冲突；
二、设计
2.1 设计思想
????????散列文件采用链接法处理冲突，本程序散列函数设为H(k)=k%13;
????????把每个单链表的表头指针用一个文件单独存储起来，即散列表头文件Hashhead把所有单链表中的结点用一个文件单独存储，即散列储存文件Hashinfo。
思路如下：
2.2 设计表示（存储结构）
typedef struct INFO
{
int key; //存储关键字
char inf[20]; //存储其他信息
}info;//散列元素
typedef struct FNode
{
info data;//值域,存储待散列的元素
int next;//指向下一个结点的指针域
//存储下一个同义词元素在散列表中的存储位置，即所在节点的位置号
}fnode;//散列储存文件中结点类型
三、解决方案
3.1功能示意图
3.2流程示意图
（一）初始化散列表流程
（二）插入流程
（三）删除流程
（四）查找流程
（五）打印流程
四、调试报告
运行自动创建两个文件
依次输入19 ?a、14 ?b、23 ?c、1 ?d、68 ?e，查看散列表
删除关键字为14和1的元素，查看散列表
查找元素（通过关键字查找）14（已删除）、23
退出系统，重新运行，查看文件是否保存成功
初始化散列文件，打印散列表，查看是否初始化成功
五、代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <windows.h>
#include <conio.h>//getch
using namespace std;
#define N 13
char fhead[9] = "Hashhead";//散列表头文件
char finfo[9] = "Hashinfo";//散列储存文件
typedef struct INFO
{
int key; //存储关键字
char inf[20]; //存储其他信息
}info;//散列元素
typedef struct FNode
{
info data;//值域,存储待散列的元素
int next;//指向下一个结点的指针域
//存储下一个同义词元素在散列表中的存储位置，即所在节点的位置号
}fnode;//散列储存文件中结点类型
void haveHash();//检查是否存在哈希文件
void selectmenu();//主菜单功能选择
void initHashfile();//初始化哈希文件
void insertHashfile();//插入一个元素到哈希文件
void deleteHashfile();//删除一个哈希文件中的元素
void searchHashfile();//查找一个元素在哈希文件中是否存在
int searchHash(info *sr);//查找sr在哈希文件中是否存在
void prtHashfile(int n);//n=0菜单进入打印，n=1功能进入打印
void quit();// 退出系统
const int lhead = sizeof(int);
const int lnode = sizeof(fnode);
void haveHash()//检查是否存在哈希文件
{
int t = 3;
FILE *fp1,*fp2;
fp1 = fopen(fhead, "rb");
fp2 = fopen(finfo, "rb");
if(fp1==NULL||fp2==NULL)
{
fp1 = fopen(fhead, "wb+");
// 读写打开建立一个二进制文件，若文件不存在则建立该文件
fp2 = fopen(finfo, "wb+");
// 文件长度清为零，即该文件内容消失
if (fp1 == NULL || fp2 == NULL)
{
cout << "打开文件失败!";
exit(1); // 异常退出
}
int *head, i;
head = new int[N + 1];//多申请一个表头存被删除的元素在散列储存文件中的位置
//方便利用这些被删除的点的空间
if(head==NULL)
{
cout << "内存申请失败!";
exit(1);//异常退出
}
for (i = 0; i <= N; i++)
{
head[i] = -1;//初始化表头结点没有链其他元素
}
fwrite(head, lhead, N+1, fp1);//存入散列表头文件
delete[] head;//释放空间
fclose(fp1);
fclose(fp2);
cout << "系统中不存在散列文件,已自动创建并初始化" << endl
<< endl;
while (1)
{
printf("\r");
printf("===================>即将进入系统......%ds", t);
Sleep(1000);
t--;
if (t == 0)
{
break;
}
}
}
else
{
cout << "系统中存在散列文件" << endl << endl;
while(1)
{
printf("\r");
printf("===================>即将进入系统......%ds",t);
Sleep(1000);
t--;
if(t==0)
{
break;
}
}
}
fclose(fp1);
fclose(fp2);
}
void selectmenu()//主菜单功能选择
{
int k;
system("cls");
printf("\t╔════════════ 功能列表 ═════════════╗\n");
printf("\t║ ║\n");
printf("\t║ ·1-初始化散列文件 ║\n");
printf("\t║ ║\n");
printf("\t║ ·2-插入一个元素 ║\n");
printf("\t║ ║\n");
printf("\t║ ·3-删除一个元素 ║\n");
printf("\t║ ║\n");
printf("\t║ ·4-查找一个元素 ║\n");
printf("\t║ ║\n");
printf("\t║ ·5-打印散列文件 ║\n");
printf("\t║ ║\n");
printf("\t║ ·0-退出系统 ║\n");
printf("\t║ ║\n");
printf("\t╚════════════════════════════════════╝\n");
cout<<endl<<"\t请选择功能(0~5):";
cin >> k;
switch(k)
{
case 1:system("cls");initHashfile();break;//初始化哈希文件
case 2:system("cls");insertHashfile();break;//插入哈希文件
case 3:system("cls");deleteHashfile();break;//删除哈希文件
case 4:system("cls");searchHashfile();break;//查询哈希文件
case 5:system("cls");prtHashfile(0);break;//打印哈希文件
case 0:system("cls");quit();break;//退出系统
default:cout<<"输入的指令有误，请重新输入！(按任意键继续....)"<<endl;
getch();
selectmenu();
break;
}
}
void initHashfile()//初始化哈希文件
{
system("cls");
char k;
cout << "是否要初始化散列文件?(Y or N):";
cin >> k;
if(k=='y'||k=='Y')
{
FILE *fp1,*fp2;//fP1表头目录，fp2储存
fp1 = fopen(fhead, "wb+");
// 读写打开建立一个二进制文件，若文件不存在则建立该文件
fp2 = fopen(finfo, "wb+");
// 若文件存在则文件长度清为零，即该文件内容会消失,实现初始化
if(fp1==NULL||fp2==NULL)
{
cout<<"打开文件失败!";
exit(1);//异常退出
}
int *head, i;
head = new int[N + 1];//多申请一个表头存被删除的元素在散列储存文件中的位置
//方便利用这些被删除的点的空间
if(head==NULL)
{
cout << "内存申请失败!";
exit(1);//异常退出
}
for (i = 0; i <= N; i++)
{
head[i] = -1;//初始化表头结点没有链其他元素
}
fwrite(head, lhead, N+1, fp1);//存入散列表头文件
delete[] head;//释放空间
fclose(fp1);
fclose(fp2);
cout << endl;
cout << "散列文件初始化完成!"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
else
{
cout << endl;
cout << "取消散列文件初始化!"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
}
void insertHashfile()
{
char ch;
cout << "是否查看散列表?(Y or N)" << endl;
cin >> ch;
cout << endl;
if(ch=='y'||ch=='Y')
{
prtHashfile(1);cout << endl;
}
info r;
cout << "请输入插入元素的关键字:";
cin >> r.key;
cout << "请输入插入元素的信息:";
cin >> r.inf;
if(searchHash(&r)==1)//元素在散列文件中已存在
{
cout << endl;
cout << "该元素在散列文件中已存在,无法插入"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
else
{
FILE *fp1, *fp2;//fP1表头，fp2储存
fp1 = fopen(fhead, "rb+");
// 读写打开一个二进制文件
fp2 = fopen(finfo, "rb+");
if(fp1==NULL||fp2==NULL)
{
cout<<"打开文件失败!";
exit(1);//异常退出
}
fnode fr,p;
int *head, d, loc;
d = r.key % N;//插入元素的散列地址
head = new int[N + 1];//多申请一个空闲表头存被删除的元素在散列储存文件中的位置
//方便利用这些被删除的空闲空间
if(head==NULL)
{
cout << "内存申请失败!";
exit(1);//异常退出
}
fread(head, lhead, N+1, fp1);//读取表头文件
fr.data = r;
fr.next = head[d];//头插法
if(head[N]==-1)//空闲表头为空，没有空闲空间
{
fseek(fp2, 0, 2);//文件指针移到文件尾
loc = ftell(fp2) / lnode;//文件尾结点位置序号
fwrite(&fr, lnode, 1, fp2);//fr结点存入文件尾
head[d] = loc;//表头指向新插入结点
}
else//有空闲空间
{
loc = head[N];//取空闲空间的表头位置
fseek(fp2, loc * lnode, 0);//文件指针移动到空闲链表的首结点
fread(&p, lnode, 1, fp2);//读取这个空闲结点信息
head[N] = p.next;//空闲表头指向下一个空闲结点
fseek(fp2, -lnode,1);//文件指针返回到loc的位置
fwrite(&fr, lnode, 1, fp2);//fr结点存入loc位置
head[d] = loc;//表头指向新插入结点
}
fseek(fp1, 0, 0);//head表头重新存入散列表头文件
fwrite(head, lhead, N + 1, fp1);
delete[] head;
fclose(fp1);
fclose(fp2);
cout << endl;
cout<<"关键字为"<<r.key<<"的元素插入完成!"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
}
void deleteHashfile()
{
char ch;
cout << "是否查看散列表?(Y or N)" << endl;
cin >> ch;
cout << endl;
if(ch=='y'||ch=='Y')
{
prtHashfile(1);cout << endl;
}
info r;
cout << "请输入删除元素的关键字:";
cin >> r.key;
if(searchHash(&r)==0)//元素在散列文件中不存在
{
cout << "该元素在散列文件中不存在,无法删除"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
else
{
FILE *fp1, *fp2; // fP1表头，fp2储存
fp1 = fopen(fhead, "rb+");
// 读写打开一个二进制文件
fp2 = fopen(finfo, "rb+");
if(fp1==NULL||fp2==NULL)
{
cout<<"打开文件失败!";
exit(1);//异常退出
}
fnode p, q;//P为工作结点，q为前驱结点
int *head, d, loc,qloc;
head = new int[N + 1];//多申请一个空闲表头存被删除的元素在散列储存文件中的位置
//方便利用这些被删除的空闲空间
if(head==NULL)
{
cout << "内存申请失败!";
exit(1);//异常退出
}
fread(head, lhead, N+1, fp1);//读取表头文件
d = r.key % N;//插入元素的散列地址
loc = head[d];
while(loc!=-1)
{
fseek(fp2, loc * lnode, 0);//文件指针移动到loc位置
fread(&p, lnode, 1, fp2);//读取loc位置的结点信息
if(p.data.key==r.key)
{
r = p.data;//被删除结点的元素值赋给r
if(loc==head[d])
{//首元结点被删
head[d] = p.next;//表头指向下一个结点
}
else
{
q.next = p.next;//前驱指向删除点的后继
fseek(fp2, qloc * lnode, 0);//文件指针移到删除点的前驱位置
fwrite(&q, lnode, 1, fp2);//更新删除点前驱信息
}
p.next = head[N];
fseek(fp2, loc * lnode, 0); // 文件指针移动到删除点位置
fwrite(&p, lnode, 1, fp2); // 更新删除点信息
head[N] = loc;//空闲表头指向删除点的位置
break;//结束循环查找删除点
}
else
{
qloc = loc;//前驱位置=工作位置
q = p;//前驱结点=工作结点
loc = p.next;//工作位置后移到后继的位置
}
}
fseek(fp1, 0, 0);//head表头重新存入散列表头文件
fwrite(head, lhead, N + 1, fp1);
delete[] head;
fclose(fp1);
fclose(fp2);
cout << endl;
cout<<"关键字为"<<r.key<<"(所含信息为"<<r.inf<<")的元素删除完成!"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
}
void searchHashfile()
{
info sr;
int k;
cout << "请输入查找的关键字:";
cin >> sr.key;
k = searchHash(&sr);
if(k==1)
{
cout << endl;
cout << "关键字为" << sr.key << "的元素在散列文件中存在(所含信息为" << sr.inf << ")"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
else
{
cout << endl;
cout << "关键字为" << sr.key << "的元素在散列文件中不存在"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
}
int searchHash(info *sr)
{
FILE *fp1, *fp2; // fP1表头，fp2储存
fp1 = fopen(fhead, "rb+");
// 读写打开一个二进制文件
fp2 = fopen(finfo, "rb+");
if (fp1 == NULL || fp2 == NULL)
{
cout << "打开文件失败!";
exit(1); // 异常退出
}
fnode p; // P为工作结点，q为前驱结点
int *head, d, loc;
head = new int[N + 1]; // 多申请一个空闲表头存被删除的元素在散列储存文件中的位置
// 方便利用这些被删除的空闲空间
if (head == NULL)
{
cout << "内存申请失败!";
exit(1); // 异常退出
}
fread(head, lhead, N + 1, fp1); // 读取表头文件
d = sr->key % N; // 查找元素的散列地址
loc = head[d];
while (loc != -1)
{
fseek(fp2, loc * lnode, 0); // 文件指针移动到loc位置
fread(&p, lnode, 1, fp2); // 读取loc位置的结点信息
if (p.data.key == sr->key)
{
*sr = p.data; // 被找到结点的元素值赋给r
break; // 结束循环查找元素
}
else
{
loc = p.next; // 工作位置后移到后继的位置
}
}
delete[] head;
fclose(fp1);
fclose(fp2);
if(loc==-1)
return 0;
else
return 1;
}
void prtHashfile(int n)
{
FILE *fp1, *fp2; // fP1表头，fp2储存
fp1 = fopen(fhead, "rb+");
// 读写打开建立一个二进制文件
fp2 = fopen(finfo, "rb+");
if (fp1 == NULL || fp2 == NULL)
{
cout << "打开文件失败!";
exit(1); // 异常退出
}
fnode p; // P为工作结点
int *head, loc, i;
head = new int[N + 1]; // 多申请一个空闲表头存被删除的元素在散列储存文件中的位置
// 方便利用这些被删除的空闲空间
if (head == NULL)
{
cout << "内存申请失败!";
exit(1); // 异常退出
}
fread(head, lhead, N + 1, fp1); // 读取表头文件
for (i = 0; i < N;i++)
{
cout << i << ':';
loc = head[i];
while(loc!=-1)
{
fseek(fp2, loc * lnode, 0); // 文件指针移动到loc位置
fread(&p, lnode, 1, fp2); // 读取loc位置的结点信息
cout << p.data.key << '(' << p.data.inf << ')';
loc = p.next;
if(loc!=-1)
cout << "->";
}
cout << endl;
}
delete[] head;
fclose(fp1);
fclose(fp2);
if(n==0)//菜单进入打印
{
cout << endl;
cout << "散列文件输出完毕"<<endl<<"按任意键返回菜单..." << endl;
getch();
selectmenu();
}
else//功能查看打印
{
cout << "散列表如上" << endl;
cout << endl;
}
}
void quit()//退出系统
{
int t;
t=3;
char ch;
printf("确认退出系统?(Y or N)\n");
cin >> ch;
if(ch=='Y'||ch=='y')
{
system("cls");
printf("**********************\n");
printf("*感谢使用散列文件系统*\n");
printf("**********************\n");
printf("\n\n\n\n");
while(1)
{
printf("\r");
printf("===================>即将退出系统......%ds",t);
Sleep(1000);
t--;
if(t==-1)
{
exit(0);//正常退出
}
}
}
else
selectmenu();
}
int main()
{
haveHash();
selectmenu();
return 0;
}
/*
1.插入元素:
19 a
14 b
23 c
1 d
68 e
输入5打印查看散列表
2.删除元素（通过关键字删除）:
14
1
输入5打印查看散列表
3.查找元素（通过关键字查找）:
14（已删除）
23
4.输入0退出系统，重新运行:
输入5打印查看散列表，查看文件是否保存成功
5.初始化功能:
输入1初始化散列文件
输入5打印查看散列表，查看是否初始化成功
输入0退出系统
*/
文章来源:https://blog.csdn.net/qq_43063612/article/details/135156323
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！