织梦网站更改网站的导航,微博推广文案怎么写,梭子手做鱼网站,大气吉祥公司名字大全一、前言#xff1a; 这是怀化学院的#xff1a;Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究#xff0c;问题基本解决#xff0c;若有bug欢迎下方评论提出意见#xff0c;我会第一时间改进代码#xff0c;谢谢#xff01;) 后面其他编程题只要我写完… 一、前言 这是怀化学院的Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究问题基本解决若有bug欢迎下方评论提出意见我会第一时间改进代码谢谢) 后面其他编程题只要我写完并成功实现会陆续更新记得三连哈哈! 所有答案供参考不是标准答案是博主自己研究的写法。(这一个题书上也有现成的代码重要的是理解它的算法原理!) 二、题目要求如下 (第 1 题) 哈希查找(难度系数75) 哈希查找 标准输入输出 题目描述 实现哈希查找。要求根据给定的哈希函数进行存储并查找相应元素的存储位置。本题目使用的哈希函数为除留取余法即H(key)key%m其中m为存储空间冲突处理方法采用开放定址法中的线性探测再散列即Hi(H(key)i)/%m0im-1。 输入 输入包含若干个测试用例第一行为测试用例个数。每个测试用例占3行第一个为元素个数m第二行为m个元素值即需要进行散列存储的元素个数同时也是存储空间个数空间位置从0开始存储第三行为需要查找的元素。 输出 对每一测试用例分别用两行输出第一行输出所有的元素要求按存储地址从0开始输出用空格隔开第二行输出需要查找的元素在数组中的位置即对应数组中的下标。 输入样例 1 5 2 4 1 7 9 7 输出样例 9 1 2 7 4 3 三、代码实现 (代码的做题原理全部在代码注释中若还有疑问也可以翻书关于哈希查找的内容) 补充建议写这到题的同志一定要去了解Java《数据结构》书中的哈希表、哈希函数、以及哈希冲突等等东西不然会有点找不着头脑的感觉 (1)全部放在一个Main类里面去实现该题的所有要求
package com.fs.search01;import java.util.Scanner;public class HashTable {public static void main(String[] args) {Scanner sc new Scanner(System.in);int k sc.nextInt(); //需要测试的总次数while (k0){int msc.nextInt(); //本次测试的元素个数int []data new int[m];int []hashtable new int[m]; //存算出来的每个数字对于的哈希函数值依次放入哈希表里的for(int i0;im;i){data[i]sc.nextInt();//输入各个元素//题目要求采用的是哈希函数是取余法int num0; //这个作用是解决产生的哈希冲突//首先用题目中给的哈希函数除留取余法( H(key)key%m )来计算每个数的哈希函数值//但是要解决哈希冲突的问题就要加一个值// 此处就是解决哈希冲突(采用开放定址法中的线性探测再散列即Hi(H(key)i)/%m0im-1)while(hashtable[(data[i]num)%m]!0){ //这里的作用就是判断当前数算出的哈希值所处的位置在原有的哈希表里是否已经存放了其它与它相等哈希值的数等于0就是代表哈希表当前位置还是初始化的0值num;}//如果前面while满足那就是要换哈希表里的其他位置就要加一个1再取余去算是否在哈希表中还有元素占用了位置若没有就直接放进哈希表对应的位置hashtable[(data[i]num)%m]data[i];}int valuesc.nextInt(); //输入要查的数的值//打印哈希表里从下标0开始的所有元素,和记录它要查的值与哈希表的相等的时候的下标int index 0;for(int j0;jm;j){System.out.print(hashtable[j] );if(hashtable[j]value){indexj; //找到要查找的元素下标}}System.out.println();System.out.print(index);k--;}}
}四、不同情况的代码测试运行结果
1首先是题目中的测试输入样例(最好手打输入测试直接复制可能格式问题导致报错) 2其他测试
