数据结构课程设计——散列文件的插入、删除和查找

前言

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退出系统
*/