精华内容
下载资源
问答
  • 线性探测法的查找函数题目答案思路 题目 答案 Position Find( HashTable H, ElementType Key ) { int i,flag=0; i=Hash(Key,H->TableSize); while(H->Cells[i].Info!=Empty&&H->Cells[i]....

    线性探测法的查找函数

    题目

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    答案

    Position Find( HashTable H, ElementType Key )
    {
    	int i,flag=0;
    	i=Hash(Key,H->TableSize);
    	while(H->Cells[i].Info!=Empty&&H->Cells[i].Data!=Key)
    	{
    		if(i==H->TableSize&&flag==0)
    		{
    			i=0;
    			flag=1;
    		}
    		else if(i==H->TableSize) return ERROR;
    		else i++;
    	}
    	return i;
    }
    

    思路

    在通过Hash函数获取Key的第一位置后,在从这个位置遍历Cell数组,如果第一遍没找到,flag变量赋值1,再给它一次机会(因为它有可能是从中间向后遍历,前面的还没遍历),找到了就返回对应的位置,否则返回ERROR

    展开全文
  • 线性探测法线性探测法中函数是位置i的函数,这相当于当发生冲突的时候,逐个单元甚至回绕查询到一个空单元,也就是说数据都需要放置在这一个表格中,当发生冲突的时候就出发上面的机制,不过这样做,花费的时间是...

    线性探测法:

    线性探测法中函数是位置i的函数,这相当于当发生冲突的时候,逐个单元甚至回绕查询到一个空单元,也就是说数据都需要放置在这一个表格中,当发生冲突的时候就出发上面的机制,不过这样做,花费的时间是相当多的,这样单元会形成一些区域块,其结果称作为一次聚焦,也就是是说经过多次的查找才能找到一个空的单元:

        Hkey(x) = Hkey(n)+ i;

    也就是当出现和n重复的hash值的时候,则需要逐个进行探测,因为可以回绕,所以可以只取一个方向继续查找空单元。不过分析一下可以看出,当表中元素多于一半的话,则需要查找的次数就更多了,这也就不再是一种好办法,耗费了大量的时间。

    平法探测法:

    平法探测法是消除线性探测法聚集问题的一种方法,流行的选择是f(i)= i^2.对于平方探测法,单元被填满,情况要比线性探测法更加严重,一旦表的大小超过一半,表的大小不是素数的时候,有可能在表被填充到一半之前就可能找不到空单元了,因此最多只有一半的空位置用来解决冲突问题。

    平方探测法实现:

    /**
     * Probing table implementation of hash table
     * Note that all "matching" is based on the equals methods
     * @author **********
     *
     */
    public class QuadraticProbingHashTableExec <AnyType>{
    	
    	private static final int DEFAULT_TABLE_SIZE = 101; 
    	private HashEntry<AnyType> [] array;// The array of elements
    	private int occupied; //The number of occupied cells
    	private int theSize; // Current size
    	
    
    	/**
    	 * Constructor the hash table
    	 */
    	public QuadraticProbingHashTableExec(){
    		this(DEFAULT_TABLE_SIZE);
    	}
    	
    	/**
    	 * Construct the hash table
    	 * @param size the approximate initial size
    	 */
    	public QuadraticProbingHashTableExec(int size){
    		allocateArray(size);
    		doClear();
    	}
    	
    	/**
    	 * Insert into the hash table .if the item is
    	 * already present, do nothing.
    	 * @param x is the item to insert
    	 * @return the result of insert
    	 */
    	public boolean insert(AnyType x){
    		
    		//Insert x as active
    		int currentPos = findPos(x);
    		if(isActive(currentPos))
    			return false;
    		
    		if(array[currentPos] == null){
    			++ occupied;
    		}
    		array[currentPos] = new HashEntry<>(x,true);
    		theSize ++;
    		
    		//Rehash : see Section 
    		
    		if(occupied > array.length/2){
    			rehash();
    		}
    		
    		return true;
    	}
    	
    	/**
    	 * Expand the hash table
    	 */
    	private void rehash(){
    		HashEntry<AnyType> [] oldArray = array;
    		
    		//Create a new double-sized ,empty table
    		allocateArray(2 * oldArray.length);
    		occupied = 0;
    		theSize = 0;
    		
    		//Copy the table over
    		for (HashEntry<AnyType> hashEntry : oldArray) {
    			if(hashEntry != null && hashEntry.isActive)
    				insert(hashEntry.element);
    		}
    	}
    	
    	/**
    	 * Method that-performs quadratic probing resolution
    	 * @param x the item to search for
    	 * @return the position where the search terminates.
    	 */
    	private int findPos(AnyType x){
    		int offset = 1;
    		int currentPos = myhash(x);
    		
    		while(array[currentPos] != null &&
    				! array[currentPos].element.equals(x)){
    			currentPos += offset;//Compute the ith probe
    			offset += 2;
    			if(currentPos >= array.length){
    				currentPos -= array.length;
    			}
    		}
    		return currentPos;
    	}
    	
    	public boolean remove(AnyType x){
    		int currentPos = findPos(x);
    		if(isActive(currentPos)){
    			array[currentPos].isActive = false;
    			theSize --;
    			return true;
    		}else{
    			return false;
    		}
    	}
    	
    	/**
    	 * Get current size
    	 * @return the size
    	 */
    	public int size(){
    		return theSize;
    	}
    	
    	/**
    	 * Get length of internal table
    	 * @return the size 
    	 */
    	public int capacity(){
    		return array.length;
    	}
    	
    	/**
    	 * Find an item in the hash table
    	 * @param x the item to search for 
    	 * @return the matching item
    	 */
    	public boolean contains(AnyType x){
    		int currentPos = findPos(x);
    		return isActive(currentPos);
    	}
    	
    	/**
    	 * Return true if currentPos exit and is active
    	 * @param currentPos the result of a call to findPos
    	 * @return true if currentPos is active
    	 */
    	private boolean isActive( int currentPos){
    		return array[currentPos] != null && array[currentPos].isActive;
    	}
    	
    	/**
    	 * Method to obtain the hash code 
    	 * @param x the element
    	 * @return the hash code
    	 */
    	private int myhash(AnyType x){
    		int hashVal = x.hashCode();
    		
    		hashVal %= array.length;
    		if(hashVal < 0){
    			hashVal += array.length;
    		}
    		return hashVal;
    	}
    	
    	/**
    	 * Internal method to allocate array
    	 * @param arraySize arraySize the size of the array
    	 */
    	private void allocateArray(int arraySize){
    		array = new HashEntry[nextPrime(arraySize)];
    		String s = "nusjks";
    		s.hashCode();
    	}
    
    	
    	/**
    	 * Internal method to find a prime number at least as large as n
    	 * @param n the starting number (must be positive)
    	 * @return a prime number larger than or equal to n
    	 */
    	private static int nextPrime(int n){
    		if( n % 2 == 0)
    			n++;
    		for(;!isPrime(n) ; n += 2)
    			;
    		return n;
    	}
    	
    	/**
    	 * Internal method to test if a number is prime
    	 * Not an efficient algorithm
    	 * @param n the number to test
    	 * @return the result of the test
    	 */
    	private static boolean isPrime(int n){
    		if(n == 2 || n == 3)
    			return true;
    		if(n ==1 || n % 2 == 0)
    			return false;
    		for(int i = 3 ; i * i <= n; i += 2){
    			if(n % 2 == 0)
    				return false;
    		}
    		
    		return true;
    	}
    	
    	/**
    	 * Make the hash table empty
    	 */
    	public void makeEmpty(){
    		doClear();
    	}
    
    	private void doClear(){
    		occupied = 0;
    		for (int i = 0; i< array.length ; i ++){
    			array[i] = null;
    		}
    	}
    	
    	
    	/**
    	 * to define a data structure to contains the data 
    	 * @author Zhang tianlong
    	 *
    	 * @param <AnyType>  the type of elements
    	 */
    	private static class HashEntry<AnyType>{
    		
    		public AnyType element; //the elements
    		public boolean isActive;// false if marked deleted
    		/**
    		 * constructor
    		 * @param e 
    		 */
    		public HashEntry(AnyType e){
    			this(e,true);
    		}
    		
    		public HashEntry(AnyType e,boolean i){
    			element = e;
    			isActive = i;
    		}
    	}
    }


    展开全文
  • 线性探测法的查找函数 (20 分)

    千次阅读 2018-12-07 14:57:18
    6-22 线性探测法的查找函数 (20 分) 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /*...

    6-22 线性探测法的查找函数 (20 分)

    试实现线性探测法的查找函数。

    函数接口定义:

    Position Find( HashTable H, ElementType Key );
    

    其中HashTable是开放地址散列表,定义如下:

    #define MAXTABLESIZE 100000  /* 允许开辟的最大散列表长度 */
    typedef int ElementType;     /* 关键词类型用整型 */
    typedef int Index;           /* 散列地址类型 */
    typedef Index Position;      /* 数据所在位置与散列地址是同一类型 */
    /* 散列单元状态类型,分别对应:有合法元素、空单元、有已删除元素 */
    typedef enum { Legitimate, Empty, Deleted } EntryType;
    
    typedef struct HashEntry Cell; /* 散列表单元类型 */
    struct HashEntry{
        ElementType Data; /* 存放元素 */
        EntryType Info;   /* 单元状态 */
    };
    
    typedef struct TblNode *HashTable; /* 散列表类型 */
    struct TblNode {   /* 散列表结点定义 */
        int TableSize; /* 表的最大长度 */
        Cell *Cells;   /* 存放散列单元数据的数组 */
    };
    

    函数Find应根据裁判定义的散列函数Hash( Key, H->TableSize )从散列表H中查到Key的位置并返回。如果Key不存在,则返回线性探测法找到的第一个空单元的位置;若没有空单元,则返回ERROR。

    裁判测试程序样例:

    #include <stdio.h>
    
    #define MAXTABLESIZE 100000  /* 允许开辟的最大散列表长度 */
    typedef int ElementType;     /* 关键词类型用整型 */
    typedef int Index;           /* 散列地址类型 */
    typedef Index Position;      /* 数据所在位置与散列地址是同一类型 */
    /* 散列单元状态类型,分别对应:有合法元素、空单元、有已删除元素 */
    typedef enum { Legitimate, Empty, Deleted } EntryType;
    
    typedef struct HashEntry Cell; /* 散列表单元类型 */
    struct HashEntry{
        ElementType Data; /* 存放元素 */
        EntryType Info;   /* 单元状态 */
    };
    
    typedef struct TblNode *HashTable; /* 散列表类型 */
    struct TblNode {   /* 散列表结点定义 */
        int TableSize; /* 表的最大长度 */
        Cell *Cells;   /* 存放散列单元数据的数组 */
    };
    
    HashTable BuildTable(); /* 裁判实现,细节不表 */
    Position Hash( ElementType Key, int TableSize )
    {
        return (Key % TableSize);
    }
    
    #define ERROR -1
    Position Find( HashTable H, ElementType Key );
    
    int main()
    {
        HashTable H;
        ElementType Key;
        Position P;
    
        H = BuildTable(); 
        scanf("%d", &Key);
        P = Find(H, Key);
        if (P==ERROR)
            printf("ERROR: %d is not found and the table is full.\n", Key);
        else if (H->Cells[P].Info == Legitimate)
            printf("%d is at position %d.\n", Key, P);
        else
            printf("%d is not found.  Position %d is returned.\n", Key, P);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    

    输入样例1:(注:-1表示该位置为空。下同。)

    11
    11 88 21 -1 -1 5 16 7 6 38 10
    38
    输出样例1:

    38 is at position 9.
    输入样例2:

    11
    11 88 21 -1 -1 5 16 7 6 38 10
    41
    输出样例2:

    41 is not found. Position 3 is returned.
    输入样例3:

    11
    11 88 21 3 14 5 16 7 6 38 10
    41
    输出样例3:

    ERROR: 41 is not found and the table is full.

    Position Find( HashTable H, ElementType Key ){
    	Position p0,p;
    	int Cnum=0;//冲突数
    	p=p0=Hash(Key,H->TableSize);
    	while(H->Cells[p].Info!=Empty&&H->Cells[p].Data!=Key){
    		Cnum++;
    		if(Cnum==MAXTABLESIZE){
    			return ERROR;
    		}
    		p=(p0+Cnum)%H->TableSize;		
    	}
    	return p;
    }
    
    展开全文
  • 线性探测法hash

    2016-12-18 19:01:58
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数

    数据结构实验之查找七:线性之哈希表

    Time Limit: 1000MS Memory Limit: 65536KB

    Problem Description

    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。

    Input

    连续输入多组数据,每组输入数据第一行为两个正整数N(N <= 1000)和p(p >= N的最小素数),N是关键字总数,p是hash表长度,第2行给出N个正整数关键字,数字间以空格间隔。

    Output

    输出每个关键字在hash表中的位置,以空格间隔。注意最后一个数字后面不要有空格。

    Example Input

    5 5
    21 21 21 21 21
    4 5
    24 15 61 88
    4 5
    24 39 61 15
    5 5
    24 39 61 15 39

    Example Output

    1 1 1 1 1
    4 0 1 3
    4 0 1 2
    4 0 1 2 0

    Hint

     

    Author

    xam     

    代码:
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int main(){
       // freopen("F://1.txt","r",stdin);
        int n,p,x=1,a,key,i,j;
        int h1[10005];   ///用于标记是否出现
        int t[10005];   ///用作线性探测方法处理冲突
        t[0]=0;
        for(i=1;i<1000;i++){
            t[i]=i;
        }
        while(~scanf("%d %d",&n,&p)){
            int ans;
            memset(h1,-1,sizeof(h1));
            for(i=0;i<n;i++){
                scanf("%d",&key);
                ans=0;
                j=0;
                while(1){
                    a=(key%p+t[j])%p;
                    if(h1[a]==-1){
                        h1[a]=key;
                        ans=a;
                        break;
                    }
                    else if(h1[a]==key){
                        ans=a;
                        break;
                    }
                    j++;
                }
                printf("%d",ans);
                if(i<n-1)
                    printf(" ");
            }
            printf("\n");
        }
        return 0;
    }
    




    革命尚未成功!
    展开全文
  • 散列函数线性探测法处理冲突

    千次阅读 2018-07-07 01:34:39
    散列函数线性探测法处理冲突: #include &amp;amp;lt;iostream&amp;amp;gt; using namespace std; typedef int KeyType; typedef int InfoType; struct done { KeyType key; InfoType otherinfo; }HT[20...
  • 从键盘输入各记录,以用户名为关键字建立哈希表, 哈希函数用除留取余数法构造, 采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 并计算查找长度, 哈希表保存到文件中。 测试数据: 取自己...
  • 哈希之线性探测法

    2018-12-07 17:25:00
    根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数据,每组输入...
  • 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ ...
  • 哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小...
  • 对于给定的一组整数和散列函数,分别采用线性探测法和拉链法处理冲突构造散列表,并在这两种方法构建的散列表中查找整数K,比较两种方法的时间和空间性能。
  • 散列(2)线性探测法和双重散列法

    万次阅读 2015-04-22 17:08:16
    我们依靠空的存储空间解决冲突:设计表长M大于元素数目N,开放地址法,最简单的开放地址法是线性探测法:初始化该符号表的实现将元素保存到大小是元素个数两倍的散列表中。void HashTableInit(in
  • 哈希表:线性探测法和链地址法求查找成功与不成功的平均查找
  • 哈希表-线性探测法/链地址法

    千次阅读 2018-10-27 13:34:48
    1.线性探测法 eg.假设散列表的长度是13,三列函数为H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。分别画出用线性探测法和拉链法解决冲突时构造的哈希表,并求...
  • 散列函数之线性探测法处理冲突

    千次阅读 2020-01-15 11:44:46
    设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。 (1)构建HASH表 (2)分别求查找成功和不成功时的平均查找长度 答案: (1) (2) 查找成功的平均查找长度:...
  • 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...
  • 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ ...
  • 用拉链法和线性探测法解决哈希冲突 转自:http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
  • 这里分享下基于拉链法、线性探测法实现的散列表。 本博客代码示例均来自:算法 Algorithmes Forth Edition [美] Robert Sedgewick Kevin Wayne 著 谢路云译 一、拉链法 package com.cmh.algorithm; import edu....
  • 利用线性探测法构造哈希表

    千次阅读 2016-08-30 17:07:29
    利用线性探测法构造哈希表  已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。  解答:为了减少冲突,通常令装填因子α 由...
  • 在最近对散列表的学习中,以线性探测法处理的散列表的删除操作让我无所适从,从网上、考研参考书等等各方面查找到的资料也都不尽人意,因此写写博客,希望能够给同样无所适从的朋友一点思路。 我主要针对机械工业...
  • 基于线性探测法的散列表

    千次阅读 2015-08-13 07:04:32
    //基于线性探测法的散列表 //使用线性探测解决键冲突问题,核心思想就是利用数组空位,当使用 //哈希函数计算出数组索引后,开始检测该索引位置是否已经被使用,如 //果已经使用,则索引向后递增(如果超出数组索引...
  • 6-4 线性探测法的查找函数

    千次阅读 2017-12-15 15:46:05
    试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */...
  • 6-4 线性探测法的查找函数(哈希表)

    千次阅读 2017-12-15 15:52:22
    6-4线性探测法的查找函数(20分) 试实现线性探测法的查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE ...
  • 1知识点:除留余数法定义hash函数+线性探测法解决hash冲突数据结构实验之查找七:线性之哈希表 Time Limit: 1000MS Memory Limit: 65536KBProblem Description 根据给定的一系列整数关键字和素数p,用除留余数法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,800
精华内容 6,720
关键字:

线性探测法