首页 > 其他分享 >线性探测法的查找函数 整型关键字的散列映射

线性探测法的查找函数 整型关键字的散列映射

时间:2023-12-15 13:12:59浏览次数:26  
标签:映射 idx 位置 flag 查找 整型 哈希 散列 循环

一、 实验目的

掌握哈希表

二、  实验内容

实验题目

线性探测法的查找函数

整型关键字的散列映射

 

 

三、   设计文档

 1.

 

 

 

2.

 

 

 

四、   源程序

  1.

 Position Find( HashTable H, ElementType Key )

{

    int flag=0;

    Position p,q;

    p=Hash(Key,H->TableSize);

    q=Hash(Key,H->TableSize);

    while(H->Cells[p].Data!=Key&&H->Cells[p].Info!=Empty)

    {

        flag++;

        if(flag==MAXTABLESIZE)

        {

            return ERROR;

        }

        p=(q+flag)%H->TableSize;

    }

    return p;

}

 

2.

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n,p,k;

    cin>>n>>p;

    int a[p+10]={0};

    int flag=0;

    while(n--){

        cin>>k;

        int idx=k%p;

        while(a[idx]!=0){

            if(a[idx]==k) break;

            idx++;

            if(idx==p){

                idx=0;

            }

        }

      a[idx]=k;

        if(flag!=0) cout<<" ";

        flag=1;

        cout<<idx;

    }

    return 0;

}

 

 

 

五、  个人体会(此部分与拼题a上主观题提交应一致)

 1.实验中遇到的问题


循环条件是什么?

如果第一次计算哈希值有重复的,怎么找到?

 

2.问题的解决


循环条件检查H->Cells[p].Data!=Key和 H->Cells[p].Info!=Empty;

线性探测法,用flag追增,如果过了长度(q+flag)%H->TableSize

 

3.实验设计思路


初始化: 初始化两个位置 p和 q,它们都通过相同的哈希函数计算得出。

循环查找: 进入一个循环,检查哈希表在位置 p 的元素是否与给定的键 Key 匹配。如果不匹配,并且该位置不是空的(即该位置有数据),则继续查找。

冲突处理: 如果在给定的位置没有找到键,并且该位置不是空的,那么算法会尝试在哈希表中寻找下一个可能的位置。这是通过计算 (q + flag) % H->TableSize 来实现的,其中 flag 是一个计数器,用于记录已经查找过的位置数量。如果 flag 达到了 MAXTABLESIZE,那么查找失败,返回错误代码。

返回结果: 如果找到了键,函数返回相应的位置 p。如果没有找到,函数返回一个错误代码。

 

4.实验后的感想


通过本次实验,我深入了解了哈希表查找算法的工作原理和实现细节。我意识到了处理哈希冲突的重要性,以及选择合适的冲突处理方法对算法性能的影响。同时,我也发现了算法中可能存在的问题和改进空间,例如处理哈希冲突时的效率和正确性等方面。

 

1、 实验中遇到的具体问题

 

散列函数的设计?


2、 问题如何解决的

除留余数法是一种简单但有效的散列函数。

 

3. 实验设计思路


输入:

首先,程序接收两个整数输入:n 和 p。其中 n 表示要输入的整数的数量,p 是循环数组的长度。

初始化数组:

程序初始化一个长度为 p+10 的数组 a,并将所有元素初始化为0。这个数组用于存储循环数组的元素。

循环读取整数:

程序进入一个循环,每次循环接收一个整数 k。

处理冲突:

对于每个输入的 k,程序首先计算其在循环数组中的索引 idx。这是通过取 k 对 p 的余数来完成的。

接下来,程序检查 a[idx] 是否为0。如果为0,表示该位置是空的,可以直接将 k 存入该位置。

如果 a[idx] 不为0,表示该位置已经被占用。此时,程序会检查 a[idx] 是否等于 k。如果等于 k,表示找到了位置,可以退出循环并存入 k。

如果 a[idx] 不等于 k,程序将索引增加1,并检查新的索引位置。如果索引超过了 p,则将其重置为0,继续查找。

输出结果:

一旦找到了位置(或者确定没有找到),程序将位置存入数组 a 中,并输出该位置。注意,在输出位置之前,程序检查 flag 是否为0。如果为0,表示需要输出空格。这样做的目的是确保输出是正确的,因为每个整数可能有多个位置。

4.实验后的感想


通过这个实验,我深入了解了如何设计和实现一个简单的循环数组查找算法,并了解了冲突处理的重要性。在循环数组中,由于元素是循环排列的,所以可能会出现多个元素哈希到同一个位置的情况,即冲突。如果没有正确的冲突处理机制,那么查找算法的效率会大大降低。在这个实验中,我们通过比较当前位置的元素与输入元素是否相等来判断是否找到了位置。如果找到了位置,则跳出循环并存入输入元素;否则,继续查找下一个位置。这种处理方式可以有效地减少冲突的影响,提高查找效率。

 

 

标签:映射,idx,位置,flag,查找,整型,哈希,散列,循环
From: https://www.cnblogs.com/aixin52129211/p/17903166.html

相关文章

  • 整型关键字的散列映射
    #include<iostream>#include<vector>#define_CRT_SECURE_NO_WARNINGS1usingnamespacestd;intmain(){intn,p;//scanf("%d%d",&n,&p);cin>>n>>p;vector<int>a(p,-1);while(n--){intx;......
  • 虚拟映射的内核栈支持 【ChatGPT】
    https://www.kernel.org/doc/html/v6.6/mm/vmalloced-kernel-stacks.html虚拟映射的内核栈支持作者[email protected]概述这是从引入虚拟映射内核栈功能的代码和原始补丁系列中整理的信息https://lwn.net/Articles/694348/。介绍内核栈溢出通常很难调......
  • 【POJ 2418】Hardwood Species 题解(映射)
    描述阔叶树是一种植物群,具有宽阔的叶子,结出果实或坚果,通常在冬天休眠。美国的温带气候造就了数百种阔叶树种的森林,这些树种具有某些生物特征。例如,虽然橡树、枫树和樱桃都是硬木树,但它们是不同的物种。所有硬木树种加起来占美国树木的40%。另一方面,软木,或针叶树,从拉丁语的意思是......
  • 整型和浮点型是怎么存储的
    先看一段程序:1intmain()2{3intn=9;4float*pFloat=(float*)&n;5printf("n的值为:%d\n",n);//将一个整型值以整型的形式取出来6printf("*pFloat的值为:%f\n",*pFloat);//将一个整型值以浮点型的形式取出来7*pFloat=9.0;//将一个......
  • GPIO映射 【ChatGPT】
    https://www.kernel.org/doc/html/v6.6/driver-api/gpio/board.htmlGPIO映射本文档解释了如何将GPIO分配给特定的设备和功能。请注意,这仅适用于基于新描述符的接口。有关已弃用的基于整数的GPIO接口的描述,请参阅“LegacyGPIOInterfaces”(实际上,使用旧接口无法进行真正的映......
  • MyBatis-Plus 自定义 TypeHandler 映射JSON类型为List
    1在mysql5.7支持json类型,那么在表实体是怎么运用的在mybatis-plus中有相关的handler/***Jackson实现JSON字段类型处理器**@authorhubin*@since2019-08-25*/@Slf4j@MappedTypes({Object.class})@MappedJdbcTypes(JdbcType.VARCHAR)publicclassJackso......
  • C++学习笔记二:变量与数据类型(整型)
    1.int(整型数据):1.1进制的表示:十进制,八进制,16进制,二进制intnumber1=15;//Decimalintnumber2=017;//Octalintnumber3=0x0F;//Hexadecimalintnumber4=0b00001111;//Binary上面几种表示方式都表示15这个数字,用cout输出得到相同的结果 1.2......
  • 动态DMA映射指南 【ChatGPT】
    https://www.kernel.org/doc/html/v6.6/core-api/dma-api-howto.html动态DMA映射指南作者[email protected]@[email protected]本指南旨在向设备驱动程序编写者介绍如何使用DMAAPI,并提供伪代码示例。有关A......
  • 动态DMA映射使用通用设备 【ChatGPT】
    https://www.kernel.org/doc/html/v6.6/core-api/dma-api.html动态DMA映射使用通用设备作者[email protected]本文档描述了DMAAPI。要了解API的更详细介绍(以及实际示例),请参阅动态DMA映射指南。该API分为两部分。第一部分描述了......
  • mapping映射属性
    索引库就类似数据库表,mapping映射就类似表的结构。mapping是对索引库中文档的约束,常见的mapping属性包括:type:字段数据类型,常见的简单类型有:字符串:text(可分词的文本)、keyword(精确值,例如:品牌、国家、ip地址)数值:long、integer、short、byte、double、float、布尔:boolean......