精华内容
下载资源
问答
  • 数据结构与算法 ~ 查找 ~ 散列查找(哈希~线性探查法和二次探查法) /*search-hash*/ #include<math.h> #include<stdio.h> #include<stdlib.h> void Print(int *a){ int i; printf("\n"); ...

    数据结构与算法 ~ 查找 ~ 散列查找(哈希~线性探查法和二次探查法)

    /*search-hash*/
    #include<math.h>
    #include<stdio.h>
    #include<stdlib.h>
    
    void Print(int *a){
      int i;
      printf("\n");
      for(i=1;i<=a[0];++i)
      	printf("%4d",a[i]);
    }/*Print*/
    
    int formatlist(){
    int e;
    printf("\n====创建哈希表========");
    printf("\n1-线性探查法 ");
    printf("\n2-二次探查法");
    printf("\n0-退出");
    printf("\n请你选择:");
    scanf("%d",&e);
    return e;
    }/*formatlist*/
    
    void hashprint(int *hashtable){
    	int i;
    	/*打印哈希表*/
    	for(i=0;i<19;++i){ 
    		if(hashtable[i]!=-1)
    			printf("\n[%d]=%d",i,hashtable[i]);
    	   }
    }/*hashprint*/
    
    /*构造哈希表*/
    void createhash(int *hashtable,int *collision){
    	int i ,e,hkey,d,k=1;
    	/*哈希表初始化*/
    	for (i=0;i<19;++i)  
    		hashtable[i]=-1; 
    	printf("\n请输入数值(exit for 0):");
    	scanf("%d",&e);
    	while(e!=0&&k<=19){
    		hkey=e%13;
    		d=hkey;i=1;
    		while(hashtable[d]!=-1){ 
    			if (hashtable[d]!=e && i<=collision[0])
    				d=(hkey+collision[i++])%19;
    			else if (hashtable[d]==e){ 
    				printf("数据重复!");
    				k--;
    				break;
    			}else if(i>collision[0]){
    				printf("冲突次数太多!");
    				exit(0);
    			}
    		}/*while*/
    		if (hashtable[d]==-1)  
    			hashtable[d]=e;
    		printf("\n请输入数值(exit for 0):");
    		scanf("%d",&e);
    		k++;
    	}/*while*/
    	if (k>19) 
    		printf("空间满了!");  /*输入的数据超过所分配的空间*/
    }/*createhash*/
    
    /*哈希表中进行查找*/
    int  searchhash(int *hashtable,int *collision,int e){ 
    	int hkey,d,i;
    	hkey=e%13;
    	d=hkey;i=1;
    	while(hashtable[d]!=e && hashtable[d]!=-1 && i<=collision[0])
    		d=(hkey+collision[i++])%19;
    	if (hashtable[d]==e ){
    		printf("\n数据:%d=被找到 , 地址: [%d],t探测次数:%d. ",e,d,i);
    		return 1;
      	}else { 
    		printf("\n数据没有找到.\n");
    		return 0;
    	}
    }/*search*/
    
    /*插入哈希表中*/
    void hashinsert(int *hashtable,int *collision,int e){
    	int i,hkey,d;
    	hkey=e%13;
    	d=hkey;i=1;
    	while(hashtable[d]!=-1){ 
    		if (hashtable[d]!=e && i<=collision[0])
    			d=(hkey+collision[i++])%19;
    		else if(i>collision[0]){
    			printf("冲突次数太多!");
    			exit(0);
    		}
    	}/*while*/
    	if (hashtable[d]==-1){
    		hashtable[d]=e;
    		printf("\n元素被插入!");
    		hashprint(hashtable);
    	}
    }/*createhash*/
    
    int main(){
      int hashtable[19], prode[19],secondprode[19];
      int i,j=1;
      int k=0,e,values;
      /*线形探测再散列增量表初始化*/
      for (i=1;i<=18;++i)  
    	  prode[i]=i;     
      prode[0]=i-1;
      /*二次线形探测再散列增量表初始化*/
      for(i=1;i<=18&&j<=9;++i){ 
    	  secondprode[i]=pow((double)(-1),(i+1)) * pow((double)(j),2);
    	  k++;
    	  if (k==2) { 
    		  j++;k=0;
    	  }
      }
      secondprode[0]=i-1;
      Print(prode);
      Print(secondprode);
      while(1){
       e=formatlist();
       if (e==0) 
    	   break;
       switch(e){
          case 1:{/*用线形探测再散列构造哈希表*/ 
    		  createhash(hashtable,prode);
    		  break;
    			 }
          case 2:{/*用二次线形探测再散列构造哈希表*/
    		  createhash(hashtable,secondprode);
    		  break;
    			 }
          default:printf("your input is error!");
        }/*switch*/
       hashprint(hashtable);
       while(1){
          printf("\n请输入你想查找的数据(exit for -1):");
          scanf("%d",&values);
          if (values==-1) break;
          switch(e){
    	  case 1:
                       if (!searchhash(hashtable,prode,values))   /*哈希表查找*/
                       hashinsert(hashtable,prode,values);      /*查找不成功则插入该元素*/
                       break;
    	  case 2:
                      if (!searchhash(hashtable,secondprode,values))
                      hashinsert(hashtable,secondprode,values);  /*用二次线形探测再散列构造哈希表*/
                      break;
    	  default:
                      printf("你的输入错误!");
      	}/*switch*/
       }/*while*/
    }/*while*/
      system("pause");
     exit(0);
    }/*main*/

    运行结果:

    
       1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18
       1  -1   4  -4   9  -9  16 -16  25 -25  36 -36  49 -49  64 -64  81 -81
    ====创建哈希表========
    1-线性探查法
    2-二次探查法
    0-退出
    请你选择:1
    
    请输入数值(exit for 0):26
    
    请输入数值(exit for 0):36
    
    请输入数值(exit for 0):41
    
    请输入数值(exit for 0):38
    
    请输入数值(exit for 0):44
    
    请输入数值(exit for 0):15
    
    请输入数值(exit for 0):68
    
    请输入数值(exit for 0):12
    
    请输入数值(exit for 0):6
    
    请输入数值(exit for 0):51
    
    请输入数值(exit for 0):25
    
    请输入数值(exit for 0):0
    
    [0]=26
    [2]=41
    [3]=15
    [4]=68
    [5]=44
    [6]=6
    [10]=36
    [12]=38
    [13]=12
    [14]=51
    [15]=25
    请输入你想查找的数据(exit for -1):25
    
    数据:25=被找到 , 地址: [15],t探测次数:4.
    请输入你想查找的数据(exit for -1):26
    
    数据:26=被找到 , 地址: [0],t探测次数:1.
    请输入你想查找的数据(exit for -1):41
    
    数据:41=被找到 , 地址: [2],t探测次数:1.
    请输入你想查找的数据(exit for -1):68
    
    数据:68=被找到 , 地址: [4],t探测次数:2.
    请输入你想查找的数据(exit for -1):44
    
    数据:44=被找到 , 地址: [5],t探测次数:1.
    请输入你想查找的数据(exit for -1):6
    
    数据:6=被找到 , 地址: [6],t探测次数:1.
    请输入你想查找的数据(exit for -1):36
    
    数据:36=被找到 , 地址: [10],t探测次数:1.
    请输入你想查找的数据(exit for -1):38
    
    数据:38=被找到 , 地址: [12],t探测次数:1.
    请输入你想查找的数据(exit for -1):12
    
    数据:12=被找到 , 地址: [13],t探测次数:2.
    请输入你想查找的数据(exit for -1):51
    
    数据:51=被找到 , 地址: [14],t探测次数:3.
    请输入你想查找的数据(exit for -1):

     

    展开全文
  • 强行考了二次探查法,一脸蒙蔽 #include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack...

    强行考了二次探查法,一脸蒙蔽

    #include <stdio.h>
    #include <memory.h>
    #include <math.h>
    #include <string>
    #include <vector>
    #include <set>
    #include <stack>
    #include <queue>
    #include <algorithm>
    #include <map>
    
    #define I scanf
    #define OL puts
    #define O printf
    #define F(a,b,c) for(a=b;a<c;a++)
    #define FF(a,b) for(a=0;a<b;a++)
    #define FG(a,b) for(a=b-1;a>=0;a--)
    #define LEN 1010
    #define MAX (1<<30)-1
    #define V vector<int>
    
    typedef long long ll;
    
    using namespace std;
    
    bool isPrime(int x){
        if(x<=1) return 0;
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0) return 0;
        }
        return 1;
    }
    
    int Hash[1000000];
    
    int main(){
    //    freopen("1078.txt","r",stdin);
        int n,i,sz,t;
        I("%d%d",&sz,&n);
        while(!isPrime(sz)) sz++;
        FF(i,n){
            I("%d",&t);
            int p=t%sz;
            if(Hash[p]){
                int step;
                for(step=1;step<sz;step++){
                    p=(t+step*step)%sz;
                    if(!Hash[p]){
                        Hash[p]=1;
                        O("%d",p);
                        break;
                    }
                }
                if(step>=sz) O("-");
            }else{
                O("%d",p);
                Hash[p]=1;
            }
            if(i!=n-1) O(" ");
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/TQCAI/p/8568358.html

    展开全文
  • Sample Input: 4 4 10 6 4 15 Sample Output: 0 1 4 - 题意: 用户输入哈希表长度Tsize和N个待插入元素,将这写元素插入哈希表中,H(key)=key%TSize,如发生冲突,采用正向增加的二次探查法。如果Tsize不是素数,则...

    The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

    Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

    Input Specification:
    Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (≤10^​4) and N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

    Output Specification:
    For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

    Sample Input:

    4 4
    10 6 4 15
    

    Sample Output:

    0 1 4 -
    

    题意:
    用户输入哈希表长度Tsize和N个待插入元素,将这写元素插入哈希表中,H(key)=key%TSize,如发生冲突,采用正向增加的二次探查法。如果Tsize不是素数,则需要重新寻找一个大于等于Tsize的素数。

    思路:
    计算M = a % Tsize,直接用一个hash[M]表示位置是否被使用。产生冲突时,令步长step=1,M = (a + step * step)% Tsize,如果还被占用,step++
    注意:
    如果step自增到Tsize还没有找到插入位置,则这个元素无法被插入哈希表中。

    #include <cstdio>
    #include <cmath>
    const int N = 10010;
    bool hashTable[N] = {false};    //hashTable[i] == false表示i位置没有被占用
    bool isPrime(int n)     //判断n是否为素数
    {
        if(n <= 1) return false;
        int sqr = (int)sqrt(1.0 * n);
        for(int i = 2; i <= sqr; i++)
            if(n % i == 0)
                return false;
        return true;
    }
    
    int main()
    {
        int n, Tsize, a;
        scanf("%d%d", &Tsize, &n);      //用户输入的Tsize和待插入哈希表元素的个数
        while(isPrime(Tsize) == false)  //寻找第一个大于等于Tsize的素数
            Tsize++;
        for(int i = 0; i < n; i++)      //对每一个元素枚举
        {
            scanf("%d", &a);
            int M = a % Tsize;
            if(hashTable[M] == false)   //若M位置未被使用
            {
                hashTable[M] = true;    //标记已使用
                if(i == 0)  printf("%d", M);
                else   printf(" %d", M);
            }
            else
            {
                int step;
                for(step = 1; step < Tsize; step++)     //二次探测法
                {
                    M = (a + step * step) % Tsize;      
                    if(hashTable[M] == false)
                    {
                        hashTable[M] = true;
                        if(i == 0)  printf("%d", M);
                        else   printf(" %d", M);
                        break;      //记得break(找到位置了就要中断循环)
                    }
                }
                if(step >= Tsize)       //找不到插入的地方
                {
                    if(i > 0)
                        printf(" ");
                    printf("-");
                }
    
            }
        }
        return 0;
    }
    
    
    //printf("%d", M);
    //if(i < n - 1)
    //    printf(" ");
    
    
    
    
    
    展开全文
  • 看了题解,才知道原来是需要使用二次探查法: 转自:https://www.liuchuo.net/archives/2297 1.如果当前key%value没被占用,那么就放下; 2.如果key%value被占用了,那么就设置一个step从1到value-1,判断(key...
    1078 Hashing (25 分)

    The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.

    Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

    Input Specification:

    Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (104​​) and N (MSize) which are the user-defined table size and the number of input numbers, respectively. Then Ndistinct positive integers are given in the next line. All the numbers in a line are separated by a space.

    Output Specification:

    For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print "-" instead.

    Sample Input:

    4 4
    10 6 4 15
    

    Sample Output:

    0 1 4 -

     题目大意:向一个Hash表中插入不同的数字,并且给出了一个 TSize ,就是哈希的函数,用输入的数字%TSize,如果TSize不是素数,那么就转化为最近的大于它的素数。

    按输入顺序输出每一个数的位置,从0开始,如果一个数不能插入(也就是存在冲突问题)那么就输出-。

    #include <iostream>
    #include <cmath>
    #include<vector>
    #include <map>
    using namespace std;
    
    bool isPrime(int m){
        int x=sqrt(m)+1;
        for(int i=2;i<x;i++){
            if(m%i==0)return false;
        }
        return true;
    }
    int getPrime(int m){
        for(int i=m+1;;i++){
            if(isPrime(i))return i;
        }
    }
    int main() {
        int m,n;
        cin>>m>>n;
        if(m!=1&&!isPrime(m)){
            m=getPrime(m);
        }
        if(m==1)m=2;
        vector<int> vt(n);
        for(int i=0;i<n;i++){
            cin>>vt[i];
        }
        map<int,int> mp;
        for(int i=0;i<n;i++){//遍历一个,打印一个就可以解决这个顺序问题。
            int x=vt[i]%m;
            if(mp[x]==0){
                cout<<x;
                mp[x]=1;
            }else
                cout<<"-";
            if(i!=n-1)cout<<" ";
        }
    
        return 0;
    }
    View Code

    //第一次在牛客网上提交错误,是因为出现了测试:

    1 1 

    1

    这是1不是素数,应该把1转化为2才对。在pat上提交,最后一个测试点答案错误。牛客网上的通过率只有10%。。。应该是因为我没有用直接将大数内素数求出来的方法。

    看了题解,才知道原来是需要使用二次探查法:

    转自:https://www.liuchuo.net/archives/2297

    1.如果当前key%value没被占用,那么就放下;

    2.如果key%value被占用了,那么就设置一个step从1到value-1,判断(key+step*step)%value是否被占用了,如果未被占用那么就放下;如果都被占用了那么就真的无法放下了。

    我的AC:

    #include <iostream>
    #include <cmath>
    #include<vector>
    #include <map>
    using namespace std;
    
    bool isPrime(int m){
        int x=sqrt(m)+1;
        for(int i=2;i<x;i++){
            if(m%i==0)return false;
        }
        return true;
    }
    int getPrime(int m){
        for(int i=m+1;;i++){
            if(isPrime(i))return i;
        }
    }
    int main() {
        int m,n;
        cin>>m>>n;
        if(m!=1&&!isPrime(m)){
            m=getPrime(m);
        }
        if(m==1)m=2;
        vector<int> vt(n);
        for(int i=0;i<n;i++){
            cin>>vt[i];
        }
        map<int,int> mp;
        for(int i=0;i<n;i++){//遍历一个,打印一个就可以解决这个顺序问题。
            int x=vt[i]%m;
            if(mp[x]==0){
                cout<<x;
                mp[x]=1;
            }else{
                int step=1;
                bool flag=false;
                for(int j=step;j<m;j++){
                    int y=(vt[i]+j*j)%m;
                    if(mp[y]==0){
                        cout<<y;
                        mp[y]=1;
                        flag=true;break;
                    }
                }
                if(!flag)cout<<"-";
            }
    
            if(i!=n-1)cout<<" ";
        }
    
        return 0;
    }

     

    //学习了二次探查法。 

    转载于:https://www.cnblogs.com/BlueBlueSea/p/9689823.html

    展开全文
  • //二次探测 //线性探测 void InitHash(PHash hash, int capacity, PHF); int InsertHash(PHash hash, Value value ); int FindHash(PHash hash, Value value ); int RemoveHash(PHash hash, Value ...
  • 返回 1078Hashing(25分) The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defi...
  • 核心思想 当散列发生冲突时,将原来的值分别……如此进行。如果题目只考虑正向,那么减的就不要考虑。 冲突处理公式 原来的值改变后,模上表长,如果仍然冲突,继续增加,直到增加的值等于表长 ...
  • 二次探查法 #include <iostream> using namespace std; int size, n, hashTable[10100]; bool isprime(int num) { if(num == 1) return false; for(int i = 2; i * i <= num; i++) if(num % i == 0) ...
  • 主要是这个二次探查法,因为第一次做完全不知道题目还有这个意图,我看英文好像就提了一下什么冲突的解决办法。但是不知道啥意思。 scanf("%d",&num); for(int i=0;j<size;i++){ if(v[(num+i*i)%size]==0)...
  • 小白求助:平法探查法:平法探查法也称为二次探查法。在发生地址冲突的时候,依次探查位置d+i,其中i 取1^2,-1^2 ,2^2 ,2^-2......即在发生冲突的地址两端逐步的扩大间隔地探查,其开放定址公式为:d=(HashCode...
  • 哈希散列中的二次探查法

    千次阅读 2018-08-26 21:58:59
    否则step步长从1加到size-1,一次次尝试是否能使index = (key + step * step) % size;所对应的位置没有元素,如果都没有找到就输出“-”,否则就输出这个找到的元素的位置。~~~~ – 注意 是(key + step * step) % .....
  • hash table(开放寻址-二次探查实现的哈希表) #ifndef C11LEARN_HASHQUADRATIC_H #define C11LEARN_HASHQUADRATIC_H #include "HashLiner.h" template<typename T> class HashQuadratic:public HashLiner&...
  • #include &lt;iostream&gt; const int maxn = 10001; bool isprime(int a) { if(a == 1) return false;//素数为大于1且能被除了自身和1整除的数 for(int i = 2; i * i &lt;... retu...
  • } 反思 题目没看懂,不知道Quadratic probing (with positive increments only) is used to solve the collisions是什么意思,所以测试点3一直没有过: Quadratic probing 是指二次探查法,即当 H(a)H(a)H(a)发生...
  • ![图片说明](https://img-ask.csdn.net/upload/201903/30/1553923589_340666.jpg)![图片说明](https://img-ask.csdn.net/upload/201903/30/1553923596_642510.jpg)
  • The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSiz...
  • 题目大意:给出散列表长和要插入的元素,将这些元素按照读入的顺序插入散列表中,其中散列函数为h(key) = key % TSize,解决冲突采用只向正向增加的二次探查法。如果题中给出的TSize不是素数,就取第一个比TSize大...
  • 如果题中给出的TSize不是素数,就取第一个比TSize大的素数作为TSize 分析:先解决size是否为素数,不是素数就要重新赋值的问题 然后根据二次探查法: 如果hashTable里面key % size的下标对应的hashTable为false,...
  • 虽然上文有提到怎么解释的开放地址处理hash冲突,但是当时只是给了个...什么叫平方探测再散列(二次探测再散列); 老师的ppt吧。 给个原始数据如上图。 下面详细解析。 上面的是线性探测再散列。这个简单。

空空如也

空空如也

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

二次探查法