精华内容
下载资源
问答
  • 已知一组关键字为(39,49,54,38,44,28,68,12,06,77),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。  解答:为了减少冲突,通常令装填因子α<l。这里关键字个数n=10,不妨取m=13...

    以下是用线性探测法构造哈希表的一个具体例子:

    已知一组关键字为(39,49,54,38,44,28,68,12,06,77),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
      解答:为了减少冲突,通常令装填因子α<l。这里关键字个数n=10,不妨取m=13,此时α≈0.77,散列表为T[0..12],散列函数为:h(key)=key%13。
         由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
         前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
         当插入第6个关键字28时,其散列地址2(即h(28)=28%13=2)已被关键字54(28和54互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
         当插入第7个关键字68时,其散列地址3已被非同义词28先占用,故将其插入到T[4]中。
         当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。

         类似地,第9个关键字06直接插入T[6]中;而最后一个关键字77插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。

    展开全文
  • 哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小...

    哈希表(线性存储)+ 线性探测法解决哈希冲突:

    将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小素数。这里的长度不会变。

    另外,这里解决哈希冲突采用的线性探测发。

    代码如下:

    #include <stdio.h>
    #define max 50
    #define nuldata -1
    #define deledata -2
    typedef struct{
    	int ino; //哈希编号 
    	int data;//存放数据 
    	int count;//探索次数 
    }hashstable;//哈希表结构体类型 
    
    //向哈希表中插入数据 
    void inserthash(hashstable hash[],int x, int m)//求长度
    {
    	int i;
    	int adr;
    	adr = x%m; //取模求出哈希编号 
    
        //这里是设定了哈希编号的数据data为空或者为删除过的编号(删除过data的值是-2)	
    	if(hash[adr].data == nuldata || hash[adr].data == deledata)
    	{
    		hash[adr].data = x;
    		hash[adr].count++;
    	}
    	else{
    	   i = 0;
    	   do{
    	   	    adr = (adr+1)%m;
    	   	    i++; //i用来求探测数
    			    
                if(i == m) 
                {
                	printf("哈希表已满,插入失败");
                	break;
    			}
    	   }while(hash[adr].data!=nuldata && hash[adr].data!=deledata);
    	   hash[adr].data =x;
    	   hash[adr].count = i;
    	}
    }
    
    //创建哈希表
    void createhash(hashstable hash[], int hs[], int n,int m)//n表示插入的个数,m表示哈希的长度 
    {
    	//初始化 
    	for(int i =0; i<m; i++)
    	{
    		hash[i].ino =i;
    		hash[i].data = nuldata;
    		hash[i].count = 0;
    	}
    	
    	//对每个数插入哈希表中 
    	for(int i =0; i<n; i++)
    	{
    		inserthash(hash,hs[i],m);
    	}
    } 
    
    //查询关键字的位置的哈希信息 
    int  searchhash(hashstable hash[],int m,int k)
    {
    	int adr = k%m;
    	
    	while(hash[adr].data!=nuldata && hash[adr].data!=deledata && hash[adr].data!=k)
    	{
    		adr = (adr+1)%m;
    	}
        if(hash[adr].data == k)  return adr;
        else return -1;
     }  
     
     //删除关键子 
     void delehash(hashstable hash[],int m,int k)
     {
     	int adr;
     	adr = searchhash(hash,m,k); //先查询 
     	
     	if(adr!=-1)
     	{
     		hash[adr].data = deledata;
     		hash[adr].count = 0;
     		printf("操作成功\n");
    	 }
      } 
      
    //输出哈希表的相关信息 
    void showhash(hashstable hash[], int m)
    {
    	
    	printf("哈希表的地址: ");
    	for(int i =0; i<m; i++)
    	{
    		printf("%-4d",i);
    	 } 
    	 printf("\n");
    	 
    	 printf("哈希表关键字: ");
    	 for(int i =0; i<m; i++)
    	 {
    	 	if(hash[i].data==nuldata || hash[i].data == deledata)
    	 	{
    	 		printf("空   ");
    		 }
    		 else  printf("%-4d",hash[i].data);
    	 }
    	 printf("\n");
    	 
    	 printf("探测次数:      ");
    	 for(int i=0; i<m; i++)
    	 {
    		 printf("%-4d",hash[i].count);
    	 }
    }
    
     
    int main()
    {
    	int hs[] ={16,74,60,43,54,90,46,31,29,88,77};
    	int n =11, m = 13;
    	hashstable hash[max];
    	createhash(hash,hs,n,m);
    	showhash(hash,m);
    	printf("\n");
    	
    	
    	int adr = searchhash(hash,m,77);
    	printf("\n查找77的哈希信息:  "); 
    	printf("hs[%d].%d :%d", adr,hash[adr].data,hash[adr].count);
    	printf("\n");
    	
    	
    	printf("\n删除值为77的哈希信息: ");
    	delehash(hash,m,77);
    	printf("\n");
    	showhash(hash,m);
    	
    	
    	printf("\n");
    	printf("\n插入值为50的哈希信息: ");
    	
    	
    	inserthash(hash,50,m);
    	adr = searchhash(hash,m,50);
    	if(adr!=-1)
    	{
    		printf("插入成功!\n"); 
    		printf("插入50的哈希信息:");
    		printf("hs[%d].%d :%d", adr,hash[adr].data,hash[adr].count);
    	}
    	else{
    		printf("插入失败");
    	}
    	
    	printf("\n");
    	printf("\n"); 
    	showhash(hash,m);
    	
    	return 0; 
     } 
    

    程序运行如下:
    在这里插入图片描述

    展开全文
  • //输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表 int SearchHash(HashTable HT[],int key); //输入一个值key,在散列表中查找key位置 其中 HT 表示哈希表, n表示记录数,key要查找的...

    6-3 哈希表的创建及查找(线性探查法) (10分)

    实现哈希表创建及查找算法,哈希函数使用除余法,用线性探测法处理冲突。

    函数接口定义:

    void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表
    int SearchHash(HashTable HT[],int key); //输入一个值key,在散列表中查找key位置
    

    其中 HT 表示哈希表, n表示记录数,key要查找的关键字

    裁判测试程序样例:

    #include<iostream>
    using namespace std;
    
    #define m 16 
    #define NULLKEY 0 //单元为空的标记
    
    struct HashTable{
       int  key;
    };
    
    void CreateHash(HashTable HT[],int n);
    int SearchHash(HashTable HT[],int key);
    
    int main()
    {    int value,key;
        int result;
        int i,j,n;
        HashTable HT[m];
        for(i=0;i<m;i++)
         HT[i].key=0;
        cin >> n;
        if(n>m) return 0;
        CreateHash(HT,n);
        cin >> key;
        result=SearchHash(HT,key);
        if(result!=-1)
            cout << "search success,The key is located in "<< result+1;
        else
            cout << "search failed";
        return 0;
    }
    
    
    /* 请在这里填写答案 */
    

    输入样例:

    12
    19 14 23 1 68 20 84 27 55 11 10 79
    55
    

    输出样例:

    search success,The key is located in 6 
    

    答案样例:

    //输入不大于m的n个不为0(0表示空值)的数,
    //用线性探查法解决冲突构造散列表
    void CreateHash(HashTable HT[], int n) {//创作不易,点个赞吧,新春快乐~
    	int hash_table[m];//创建一个辅助数组 
    	int temp;//存放余数 
    	for(int i=0; i<n; i++)
    		cin >> hash_table[i]; 
    	for(int i=0; i<m; i++)
    		HT[i].key = 0;//初始化HT数组 
    	for(int i=0; i<n; i++) {
    		temp = hash_table[i] % 13;//求余数 
    		if(HT[temp].key==0) {//如果正好有空就放进去 
    			HT[temp].key = hash_table[i];
    		} else { 
    			int flag=0;
    			for(int j=temp+1; j<n; j++) {//从余数位置往后看有没有空余位置 
    				if(HT[j].key==0) {//如果有位置就放进去 
    					HT[j].key = hash_table[i];
    					flag = 1;
    					break;
    				}
    			}
    			if(flag==0) {//如果还是没有位置 
    				for(int j=0; j<temp; j++) {//就从0位置往后找,找到余数位置之前 
    					if(HT[j].key==0) {
    						HT[j].key = hash_table[i];
    						break;
    					}
    				}
    			}
    		}
    	}
    }
    //输入一个值key,在散列表中查找key位置
    int SearchHash(HashTable HT[],int key) {
    	int temp = key % 13;//求余数
    	for(int i=temp; i<m; i++) {//从余数位置往后查 
    		if(HT[i].key == key)
    			return i;
    	}
    	for(int i=0; i<temp; i++) {//从头查到余数位置之前 
    		if(HT[i].key == key)
    			return i;
    	}
    	return -1;
    }
    

    感谢您的阅读,点个赞吧❤⭐
    哔哩哔哩/bilibili:羊卓的杨
    公众号:羊卓的杨

    展开全文
  • 线性探测法解决哈希冲突

    千次阅读 2018-10-10 15:54:41
    线型探测解决哈希冲突的一种方法 */ #include &lt;iostream&gt; #include &lt;ctime&gt; using namespace std; const int INDEXBOX = 10; //哈希表最大元素 const int MAXNUM = 7; ...
    /*
    线型探测法:解决哈希冲突的一种方法
    */
    #include <iostream>
    #include <ctime>
    using namespace std;
    
    const int INDEXBOX = 10;                             //哈希表最大元素
    const int MAXNUM = 7;                                //最大数据个数
    void PrintData(int *data, int n);
    void CreatTable(int *table, int n);
    
    void main()
    {
    	int i, nIndex[INDEXBOX], nData[MAXNUM];
    	srand((unsigned)time(NULL));
    	//设置原始数据值
    	cout << "原始阵列值:\n";
    	for(i = 0; i < MAXNUM; i++)
    	{
    		nData[i] = rand()%20 + 1;
    		cout << "\t" << nData[i];
    	}
    	cout << endl;
    
    	//初始化哈希表
    	for(i = 0; i < INDEXBOX; i++)
    		nIndex[i] = -1;
    
    	//建立哈希表
    	//也即把每个数据值通过哈希法放到哈希表中
    	for(i = 0; i < MAXNUM; i++)
    	{
    		CreatTable(nIndex, nData[i]);                //将每一个数据值放到哈希表中
    		cout << nData[i] << "->";                    //输出单一元素的哈希表位置
    		PrintData(nIndex, INDEXBOX);
    	}
    
    	cout << "完成哈希表\n";
    	PrintData(nIndex, INDEXBOX);
    }
    
    void PrintData(int *data, int n)
    {
    	for(int j = 0; j < n; j++)
    		cout << "\t" << data[j];
    	cout << endl;
    }
    
    void CreatTable(int *table, int n)                   //把数值n放到哈希表table中
    {
        int nTmp;
    	nTmp = n%INDEXBOX;                               //哈希函数中的除留余数法
    	while(1)
    	{
    		if(table[nTmp] == -1)                        //如果数据对应的位置是空的,就直接存入数据
    		{
    			table[nTmp] = n;
    			break;
    		}
    		else
    			nTmp = (nTmp+1)%INDEXBOX;                //否则,循环往后找位置存放
    	}
    }

     

    展开全文
  • //这就是处理哈希冲突线性探测 ht->data[offset].key = key; ht->data[offset]. value = value ; //插入完成以后将该位置置成有效状态 ht->data[offset].stat = Valid; //哈希表有效元素个数+1 ++...
  • 假定选用的散列函数是H(K)= K mod 7,若发生冲突采用线性探查法处理,要求: (1)计算出每一个元素的散列地址并在下图中填写出散列表(写出散列过程)。 (2)求出在查找每一个元素概率相等情况下的平均查找长度...
  •  * 用开放地址法中的线性探查法解决冲突实现哈希表的运算。  */ public class MyHashSearch {  public static final int SIZE = 10;  public static final int NULLKEY = -1;  public sta
  • 已知9名学生的信息,每个学生信息包括编号和姓名。...用线性探测法解决冲突。要求从文本文件中读取学生信息(相邻数据间用空白符分隔,且姓名不含有空白符),建立散列表,然后输入学生编号,查找...
  • 今天我们主要的是用线性探测的方法处理哈希冲突的问题。 线性探测方法的具体实现如下: test.h #pragma once #include &lt;stdio.h&gt; #include &lt;stddef.h&gt; #include &lt;stdlib.h&...
  • //使用线性探测法解决冲突  #include using namespace std; const int NULLKEY = 0; const int ENDFLAG = 0; const int TableSize = 16; const int mod = 13; ...
  • 下面实现基于线性探测解决哈希冲突的哈希表(哈希函数为除留余数)。 1. 哈希表的结构定义   用数组来实现哈希表的结构,哈希函数为除留余数。再用一个变量记录哈希表中的实际元素个数。  哈希表中的元素...
  • 散列函数线性探测处理冲突

    千次阅读 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...
  • 散列函数之线性探测处理冲突

    千次阅读 2020-01-15 11:44:46
    设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测处理冲突。 (1)构建HASH表 (2)分别求查找成功和不成功时的平均查找长度 答案: (1) (2) 查找成功的平均查找长度:...
  • 【题目】已知散列表的地址空间为A[0..10],散列函数H(k)=k mod 11,采用线性探查法处理冲突。将下列数据{24, 15, 38, 46, 79, 82, 52, 39, 85, 143, 231}依次插入到散列表中,请写出散列表的结果,并计算出在等概率...
  • hash线性探测开放定址法解决冲突

    千次阅读 2017-12-29 18:57:13
    一,利用线性探测法构造散列表(用除余法来得出散列地址,用开放地址法解决同义词问题) 题目:已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组...
  • 此代码可以正常运行 #include<...//- - - - -开放地址哈希表的存储表示- - - - - #define m 16 //哈希表的表长 #define NULLKEY 0 //单元为空的标记 struct HashTable{ int key; //.
  • ⑴ 对于给定的一组整数和散列函数,采用线性探测处理冲突构造散列表; ⑵ 设计查找算法,验证查找性能。 #include <stdio.h> int H(int k){ int x; x=k%19;//除留余数 19为最接近表长的素数 return x...
  • 线性探查法的基本思想:在产生散列冲突时,将产生散列冲突的关键字向后存储 当使用了线性探查法之后,整个散列表就被视为一个环形表了 二、图示说明 散列函数为f(k)=k%11。且散列表的当前状态如下图所示 当要...
  • 采用线性探测方法解决冲突

    千次阅读 2015-09-14 15:47:00
    已知一个线性表(38,25,74,63,52,48),假定采用散列函数h(key)=key%7计算散列地址,并散列存储在散列表A[0..6]中,若采用线性探测方法解决冲突,则在该散列表上进行等概率成功查找的平均查找长度为___分析:...
  • else //冲突时,采用线性探查法求下一个地址 { j=(j+1)%M; } } Det[j]=k; } printf("---------------------\n"); printf("哈希表\n"); printf("位置\t字符串\t探查次数\n"); printf("-------------------...
  • 哈希表的线性探查法搜索算法

    千次阅读 2015-04-14 16:06:59
    #include #include using namespace std; const int P = 7; const int DefaultSize = 7; enum KindOfStatus{Active,Empty,Deleted}; class HashTable ... HashTable(const int d,int sz = DefaultSize) {
  • 数据结构作业21复习

    2020-12-13 00:13:59
    search success,The key is located in 6 void CreateHash(HashTable HT[],int n)//输入不大于m的n个不为0(0表示空值)的数,用线性探查法解决冲突构造散列表 { int i,e,t; for(i=0;i;i++) { cin>>e; t=e%...
  •  key`算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。 哈希函数 哈希函数  一般具有如下特点。 相等的  key  产生相等的  哈希值 计算简单方便 哈希值  均匀分布。(若过度集中,则容易使...
  • // 线性探测法解决碰撞问题:当发生碰撞时,线性探测法检查散列表的下一个位置是否为空,如果为空,则将数据存入该位置;如果不为空,则继续检查下一个位置,直到找到一个空的位置为止。 function HashTable(){ ...
  • 散列表         哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。... 一般来说冲突不可避免的,只能尽可能地减少冲突的发生。在建立Has
  • 处理冲突的方法 通常有两类方法处理冲突:开放定址(Open Addressing)法和拉链(Chaining)法。... 1、开放定址法 (1)开放地址法解决冲突的方法 用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查...
  • 处理哈希冲突线性探测

    万次阅读 2016-05-24 15:28:24
    哈希表,是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的...=k2,而f(k1)=f(k2),这种现象称为碰撞(英语:Collision),也叫哈希冲突。 处理哈
  • const int DefaultSize = 100;enum KindofStatus {Active, Empty, Deleted};template&lt;class E, class K&gt;class HashTable { public: HashTable(int d, int sz = DefaultSize); ~HashTable() {...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,721
精华内容 1,488
关键字:

线性探查法解决冲突