首页 > 其他分享 >数据结构实验---散列表

数据结构实验---散列表

时间:2024-08-02 09:26:28浏览次数:16  
标签:typedef int KeyType 列表 --- 关键字 查找 数据结构

一.实验目的

1.理解散列表的存储结构;

2.掌握常用散列函数构造方法和处理冲突方法;

3.在散列表上实现查找的算法。

二.实验内容

为小于n个关键字设计一个散列表,使得查找成功时平均查找长度<2.0,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放定址法的线性探测法处理冲突。

1.从键盘输入关键字个数n及关键字数据;

2.根据输入的关键字个数及平均查找长度要求,设计散列函数和计算表长;

3.构造散列表;

4.在散列表中进行查找。

三.代码

#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
//顺序表存储结构
typedef struct
{
    KeyType key;  	//关键字(数据项)
    int time;       //探测次数
    } ElemType;
typedef struct
{
    ElemType *elem;  		//数据元素存储空间基址
    int length;         	//查找表的长度
} HashTable;



void inputData(KeyType KeyData[],int n)
{
    printf("请输入%d个关键字:",n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&KeyData[i]);
    }
}



void calcpm(int n,int &p, int &m){
    int i,j;    
    float Snl=2.0; //平均查找长度    
    float a;    
    //求m    
    a=1-1/(2*Snl-1);    
    m=int(n/a)+1;    
    //求p
    for (i = m; i < 2 * m; i++) {    
        for (j = 2; j < i; j++) {    
            if (i % j == 0) {    
                break;    
            }    
        }    
        if (j == i) {    
            p = i;    
            break;    
        }    
    }
}


int hashFunc(KeyType key, int p)
{
    return key % p;
}


int linearProbing(HashTable HT,int addr,int m,int &addri)
{
    int time=1; //探测次数
    if (HT.elem[addr].key == -1){ //不冲突
        addri = addr;
        return time;
    }else{ //处理冲突
        addri = (addr+1)%m;
        while (HT.elem[addri].key != -1 && addri != addr){
            time++;
            addri = (addri+1)%m;
        }
        if (HT.elem[addri].key == -1){
            return time;
        }else{
            addri = -1;
            return -1;
        }
    }
}

void initHashTable(HashTable &HT,int m)
{
    int i;
    HT.elem=(ElemType *)malloc(m*sizeof(ElemType));
    HT.length=m;
    for(i=0; i<HT.length; i++)
    {
        HT.elem[i].key=-1;  //赋初值
        HT.elem[i].time=0;
    }
}

void createHashTable(HashTable &HT,KeyType KeyData[],int n, int p, int m)
{
    int i,addr,addri,time;
    for(i=0; i<n; i++)
    {   
        addr=hashFunc(KeyData[i],p);//求散列地址
        time=linearProbing(HT,addr,m,addri);//处理冲突
        HT.elem[addri].key=KeyData[i];
        HT.elem[addri].time=time;
    }
}


int search(HashTable HT, KeyType key,int p,int m)
{
    int i,addr,addri;

    addr=hashFunc(key,p); //求散列地址

    if (HT.elem[addr].key==key)
        return addr;
    else if(HT.elem[addr].key==-1)
        return -1;
    else
        for(i=1; i<m; i++)
        {
            addri=(addr+i) % m;
            {
                if (HT.elem[addri].key==key)
                    return addri;
                else if (HT.elem[addri].key==-1)
                    return -1;
            }
        }
    return -1;
}

void outputHashTable(HashTable HT)
{
    printf("地址\t关键字\t探测次数\n");
    for(int i=0; i<HT.length; i++){
        if(HT.elem[i].key != -1){
            printf("%d\t%d\t%d\n", i, HT.elem[i].key, HT.elem[i].time);
        }
    }
}

void menu()
{
    int i;
    system("cls");
    printf("\n");
    printf("%50s\n", "散列表的构造和查找\n");
    for (i = 0; i < 80; i++)
        putchar('=');
    putchar('\n');
    printf("             1 输入数据 \n");
    printf("             2 构造散列函数 \n");
    printf("             3 构造散列表\n");
    printf("             4 查看散列表\n");
    printf("             5 散列表查找\n");
    printf("             0 退出\n");
    printf("             \n");
    for (i = 0; i<= 79; i++)
        putchar('=');
    putchar('\n');
    printf("请输入操作序号:");
}


int main()
{
    HashTable HT;
    KeyType KeyData[50];  //存放关键字数据

    int choice,n,m,p,addr;
    KeyType key;

    while (1)
    {
        menu();
        scanf("%d", &choice);
        getchar();  /*接收回车键*/
        switch(choice)
        {
        case 1:
            printf("请输入关键字个数:");
            scanf("%d",&n);
            inputData(KeyData,n);
            break;
        case 2:
            calcpm(n,p,m);
            printf("p=%d,m=%d\n",p,m);
            printf("成功构造散列函数.\n");
            break;
        case 3:
            initHashTable(HT,m);
            createHashTable(HT,KeyData,n,p,m);
            printf("成功构造散列表.\n");
            break;
        case 4:
            printf("散列表:\n");
            outputHashTable(HT);
            printf("\n");
            break;
        case 5:
            printf("请输入要查找的关键字:");
                scanf("%d", &key);
                addr = search(HT, key, p, m);
                if(addr == -1){
                    printf("未找到关键字:%d\n", key);
                }else{
                    printf("已找到关键字:%d,地址为%d,探测次数为%d\n", key, addr, HT.elem[addr].time);
                }
                break;
        case 0:
            exit(0);
            break;
        default:
            printf("\n输入错误!");
            break;
        }
        system("pause");
    }
    return 1;
}

标签:typedef,int,KeyType,列表,---,关键字,查找,数据结构
From: https://blog.csdn.net/2301_79235379/article/details/140863518

相关文章

  • 连载|浅谈红队中的权限维持(六)-Linux 主机后门与Linux 隐藏文件
    本文来源无问社区,更多实战内容,渗透思路可前往查看http://www.wwlib.cn/index.php/artread/artid/11584.html0x01Linux主机后门1、添加用户一句话添加用户useraddtest;echo-e"123456n123456n"|passwdtest或者使用openssluseradd-popensslpasswd-1-salt'salt'12......
  • 字符串相关函数、二维数组-
    目录strcpy--字符串复制函数strcat--字符串拼接函数strcmp--字符串对比函数字符串相关函数:二维数组初始化:strcpy--字符串复制函数char*strcpy(char*dest,constchar*src);功能:  将src中字符串拷贝到dest中 用法: strcpy(dest,src);//dest是一个字......
  • Linux系统编程-临时文件
    临时文件:1、如何不冲突  2、及时销毁创建临时文件有两种方法:1、tmpnam  2、tmpfiletmpnam函数tmpnam的用法为一个临时文件创建一个名字。该方法创建临时文件,需要两步:1、产生文件名字   2、创建文件。所以从并发的角度,可能有两个用户获取同一个文件名字,因此......
  • easyui-datebox 只显示月份选择,默认开启月份,隐藏日期选择框
    如果你使用​​easyui-datebox​​​并希望隐藏日期选择框,只显示月份选择,可以通过一些自定义代码来实现。虽然EasyUI没有直接提供这种功能,但可以通过自定义​​formatter​​​和​​parser​​​方法,以及修改​​onShowPanel​​事件来实现这个功能。以下是一个详......
  • 在 VS Code 中 - 有没有办法以通常的“(env_name)”样式显示自动激活的环境?
    我的自动环境激活工作正常,它只是在终端中看起来很难看(参见屏幕截图)-有人知道如何更改它吗?我想将它放在括号中,并在下一个命令之前有一个空格:)任何非常感谢提示!这是我可以在VSCode端更改的内容,还是它是bash脚本,还是这是预期的行为而我无法更改它?很不幸,......
  • August 1st, Java Study Notes,static&non-static method
    IfollowedthevideoandrecordedsomeofitMostoftheideasarealreadyinthecomments,andtoputitbluntly,theyarethetranslatedwordspublicclassdog{publicintweight;//dog没有一个固定的weight,所以我们不使用static定义weight//定......
  • Hive学习第九天--函数的用法
    1.1 Hive窗口函数普通的聚合函数每组(Groupby)只返回一个值,而开窗函数则可为窗口中的每行都返回一个值。简单理解,就是对查询的结果多出一列,这一列可以是聚合值,也可以是排序值。开窗函数一般就是说的是over()函数,其窗口是由一个OVER子句定义的多行记录开窗函数一般分为两......
  • HT-018 Div3 构造 题解 [ 黄 ] [ 数学 ] [ 结论 ]
    构造:结论题,gcy数竞大佬tql%%%orz。结论先放结论:如果\(x\bmod4=2\),那么\(x\)无法被表示为\(a^2-b^2\)的形式;除此之外的其他数都可以。证明对\(a^2-b^2\)因式分解,得\(x=(a+b)(a-b)\)。当\(x\bmod2=1\)时包含\(x\bmod4=1\)和\(x\bmod4=3\)的情况。......
  • Seurat-SCTransform与harmony整合学习
    目录基础介绍SCTransform与harmony联合代码测试1)报错解决2)SCTransform标准化3)harmony去批次基础介绍源于Rtips:Seurat之SCTransform方法原理(qq.com)Seurat对象在经过SCTransform处理后会增加一个SCT的Assay,里面的scaled.data就是经过scale之后的pearsonresidual值......
  • 【愚公系列】《短视频生成与剪辑实战》005-使用 Midjourney 进行 Al 绘图
    ......