精华内容
下载资源
问答
  • 这道题要求给定关键字序列使用哈希映射函数,并运用线性探测再散列法构造关键字序列哈希表,并求出查找成功的平均查找长度。 这道题还是比较简单,没有复杂的数据结构要求和算法,只要哈希算法比较了解,...

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

    解题思路:

    这道题要求对给定关键字序列使用哈希映射函数,并运用线性探测再散列法构造该关键字序列的哈希表,并求出查找成功的平均查找长度。
    这道题还是比较简单,没有复杂的数据结构要求和算法,只要对哈希算法比较了解,知道线性探测再散列法,这道题就比较简单了。
    具体操作见代码,代码中有部分注释。

    题解代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define DATANUM 8
    #define HASHTABLENUM 11
    
    typedef struct HashTableNode{
        int data;
        int flag;
    }HashTable;
    
    int HashFunctionAlgorithm(int data){//哈希映射函数
        return (3*data)%11;
    }
    
    HashTable *CreateHashTableNode(int data, int flag){//新建哈希表节点
        HashTable *p;
        p = (HashTable*)malloc(sizeof(HashTable));
        p->data = data;
        p->flag = flag;
        return p;
    }
    
    void GetHashTable(HashTable *HT[], int dataList[]){//构建哈希表
        int position,flag;
        for(int i=0;i<8;i++){
            flag = 1;
            position = HashFunctionAlgorithm(dataList[i]);
            while(HT[position]!=NULL){
                position++;
                flag++;
            }
            HT[position] = CreateHashTableNode(dataList[i], flag);
        }
    }
    
    void PutOutAverageSearchLength(HashTable *HT[]){//计算ASL并输出
        int ASL=0;
        for(int i=0;i<11; i++){
            if(HT[i]!=NULL){
                ASL += HT[i]->flag;
            }
        }
        ASL = ASL/8;
        printf("%d\n",ASL);
    }
    
    int main(){
        int dataList[DATANUM] = {22,41,53,46,30,13,01,67};//数据列表储存了题中给出的未处理数据
        HashTable *HT[HASHTABLENUM] = {NULL};//由11个哈希节点构成的哈希表
        GetHashTable(HT,dataList);
        PutOutAverageSearchLength(HT);
    }
    
    
    展开全文
  • 构造哈希表(耿8.12)

    千次阅读 2018-05-24 16:38:05
    试在0-10的散列地址空间中,编写程序,对关键字序列 (22,41,53 46,30,13,01,67)构造哈希表,并求等概率情况下查找成功的平均查找长度。Input无Output输出等概率情况下查找成功的平均查找长度。Sample Input 无...

    Description

    选取哈希函数H(k)=(3k)%11,用线性探测再散列法处理冲突。试在0-10的散列地址空间中,编写程序,对关键字序列 (22,41,53 46,30,13,01,67)构造哈希表,并求等概率情况下查找成功的平均查找长度。

    Input

    Output

    输出等概率情况下查找成功的平均查找长度。

    • Sample Input 
    • Sample Output
      2
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node{
        int ori;
        int after;
    }*Hash[11];
    
    int data[8]={22,41,53,46,30,13,01,67};
    
    void change()
    {
        int i;
        int temp,flag;
        for(i=0;i<8;i++)
        {
            flag = 1;
            temp = (3 * data[i]) % 11;
            while(Hash[temp] != NULL)
            {
                ++temp;
                ++flag;
            }
            Hash[temp] = (struct Node *)malloc(sizeof(struct Node));//又忘了写QAQ
            Hash[temp] -> ori = data[i];
            Hash[temp] -> after = flag;
        }
    }
    
    void print()
    {
        int i;
        int sum=0;
        for(i=0;i<=10;i++)
        {
            if(Hash[i]!=NULL)
            {
                sum += Hash[i]->after;
            }
        }
        printf("%d\n",sum/8);
    }
    int main()
    {
        change();
        print();
        return 0;
    }
    

    展开全文
  • 编程实现:构造哈希表:在地址空间为0~12,以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...

    题目描述:

        设哈希函数为H(key)=i/2,其中i为关键字中的第一个字母在字母表中的序号,处理冲突使用线性探测法。编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。

    实现代码:

    typedef struct HashTable{
    	char data[4];
    	int count;    //记录比较次数
    }HashTable;
    void createHash(HashTable H[], int n){
    	int key, i,d,key_new;
    	char ch[9][4] = { { "Jan" }, { "Feb" }, { "Apr" }, { "May" }, { "Jun" }, { "Jul" }, { "Aug" }, { "Sep" }, { "Oct" } };
    	for (int j = 0; j < n; j++){     //哈希表的初始化
    		H[j].data[0] = ' ';    //首字符为‘ ’代表空
    		H[j].count = 0;
    	}
    	for (int j = 0; j < 9; j++){
    		i = ch[j][0] - 'A' + 1;
    		key = i / 2;
    		if (H[key].data[0] == ' '){
    			H[key].count = 1;
    			strcpy(H[key].data, ch[j]);
    		}
    		else       //使用线性探测法解决冲突
    		{
    			d = 1;  //增量
    			key_new = (key + d) % n;
    			while (H[key_new].data[0]!=' ')
    			{
    				d++;
    				key_new = (key + d) % n;
    			}
    			strcpy(H[key_new].data, ch[j]);
    			H[key_new].count = d+1;
    		}
    	}
    }
    float succLength(HashTable H[], int n){
    	int num = 0, sum = 0;
    	float ASL;
    	for (int i = 0; i < n; i++){
    		if (H[i].data[0] != ' '){
    			sum += H[i].count;
    			num++;                  //记录哈希表中实际存在多少个值
    		}
    	}
    	ASL = (float)sum / num;
    	return ASL;
    }
    float unsuccLength(HashTable H[], int n){
    	int sum = 0, num = 0,k;
    	float ASL;
    	for (int i = 0; i < n; i++){
    		num = 1;
    		if (H[i].data[0] != ' '){
    			k = (i + 1) % n;
    			num++;                          //num记录哈希表中每个序号查找不成功的次数
    			while (H[k].data[0] != ' '){
    				num++;  
    				k = (k + 1) % n;
    			}
    		}
    		sum += num;
    	}
    	ASL = (float)sum / n;
    	return ASL;
    }
    
    int main(){
    	HashTable H[13];
    	float ASL_succ, ASL_unsucc;
    	createHash(H, 13);
    	ASL_succ = succLength(H, 13);
    	ASL_unsucc = unsuccLength(H, 13);
    	printf("查找成功的平均查找长度:%.2f\n", ASL_succ);
    	printf("查找不成功的平均查找长度:%.2f", ASL_unsucc);
    
    	system("pause");
    	return 0;
    }
    

    结果输出:

    展开全文
  • 哈希表的查找和算法

    2011-04-19 22:30:17
    数据结构的一道题目: 设有一组关键字{12,11,35,25,22,58},采用哈希函数:H(key)=key%6,采用开放 ...构造哈希表。 解法: 依题,m=11,二次探测再哈希的下一地址计算公式为 d1=H(key), d2=(d1+i*i)%m,...
    数据结构的一道题目:

    设有一组关键字{12,11,35,25,22,58},采用哈希函数:H(key)=key%6,采用开放
    地址法的二次探测再哈希方法解决冲突,试在0~10的哈希地址空间中对该关键字序列
    构造哈希表。

    解法:
    依题,m=11,二次探测再哈希的下一地址计算公式为
    d1=H(key),
    d2=(d1+i*i)%m,
    d3=(d1-i*i)%m
    其中(i=1,2,3,...)
    则有:
    H(12)=12%6=0
    H(11)=11%6=5
    H(35)=35%6=5(冲突)
    H(35)=(5+1*1)%11=6
    H(25)=25%6=1
    H(22)=22%6=4
    H(58)=58%6=4(冲突)
    H(58)=(4+1*1)%11=5(冲突)
    H(58)=(4-1*1)%11=3

    [b]对应的构造算法实现:[/b]


    #include<iostream>
    using namespace std;

    void CrtHash(int a[],int val,int n1,int n2)
    {
    int temp=val%n1; //没有冲突
    if(a[temp]==0){a[temp]=val;return;}
    else //发生冲突
    {
    int temp1;
    for(int j=1;;++j)
    {
    temp1=(temp+j*j)%n2;
    if(a[temp1]==0){a[temp1]=val;return;}

    temp1=(temp-j*j)%n2;
    if(a[temp1]==0){a[temp1]=val;return;}
    }
    }
    }

    int main()
    {
    int KEY[6]={12,11,35,25,22,58};
    int hashtable[11];
    memset(hashtable,0,sizeof(hashtable));

    for(int i=0;i<6;++i)
    {
    CrtHash(hashtable,KEY[i],6,11);
    }
    for(int i=0;i<11;++i)
    {
    cout<<hashtable[i]<<" ";
    }
    return 0;
    }
    展开全文
  • 哈希表查找不成功的ASL问题

    千次阅读 多人点赞 2017-10-24 23:07:31
    哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来: ...在地址空间为0~16的散列区中,以下关键字序列构造两个哈希表: {Jan, Feb, Mar, Apr, May, June,
  • SCAU 8622 哈希查找

    2020-05-21 16:05:46
    输入的关键字序列构造哈希表,哈希表长度为length,求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。 #include"malloc.h" / ...
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: ...在地址空间为0~16的散列区中,以下关键字序列构造两个哈希表: {Jan, Feb, Mar, Apr, May, June,
  • 做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: ...在地址空间为0~16的散列区中,以下关键字序列构造两个哈希表: {Jan, Feb, Mar, Apr, May, June, J...
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结...在地址空间为0~16的散列区中,以下关键字序列构造两个哈希表: {Jan, Feb, Mar, Apr, May, June, J
  • 输入的关键字序列构造哈希表,哈希表长度为length, 求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。*/ #include"malloc.h...
  • 输入的关键字序列构造哈希表,哈希表长度为length,求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。 #include"malloc.h" / ...
  • 在地址空间为0~16的散列区中,以下关键字序列构造两个哈希表:{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} 哈希函数:H(x)=i/2,i为首字母在字母表中的序号。(等概率的情况下) (1) 用...
  • 希哈查找函数

    2011-12-07 23:44:31
    使用哈希函数:H(k)=3*k...试输入的关键字序列构造哈希表,哈希表长度为length,求等概率情况下查找成功的平均查找长度,并设计构造哈希表的完整的算法。本题给出部分代码,请补全Hash函数和解决冲突的collison函数。
  • 设哈希函数H(K)=3Kmod11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和...
  • 链式地址&线性探测的平均查找长度

    千次阅读 2020-08-15 21:59:15
    题目:已知关键字序列为:(75,33,52,41,12,88,66,27),哈希表长为10,哈希函数为:H(k)=kmod7,解决冲突用线性探测再散列法,要求构造哈希表,求出等概率下查找成功的平均查找长度。 1、首先计算该...
  • 通过下图可以看到散列表我们还没有涉及,今天我们就来散列表(哈希表)进行学习实践。 图片来源于《算法》 一、基本概念 散列技术,不需要比较和递归。通过记录存储位置和它的关键字之间建立一个确定的对应...
  • 4. (共15分)设哈希表长为m=13,散列函数为H(k)=k mod 11,关键字序列为5,7,16,12,11,21,31,51,17,81;试求:散列后的表中关键字分布(假定解决冲突的方法为线性探测再散列法);求平均查找长度ASL;计算...
  • 09-007键树的结构特点、哈希表的定义、哈希表构造方法 09-008哈希表的查找与删除操作、处理冲突的方法 10-001排序的定义、直接插入排序、冒泡排序、快速排序 10-002堆排序、多关键字的排序、基数排序、排序时间...
  • 数据结构实验

    2012-04-13 09:55:47
    DeleteHash( ):删除哈希表中某一关键字 PrintHash ( ):打印输出哈希表 四、思考与提高 如何利用二分查找算法在一个有序表中插入一个元素x,并保持表的有序性? 实验7:至少三种排序算法的程序实现 (第十六周...
  • 数据结构课程设计

    2014-06-03 13:26:05
    24、设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),输入一组关键字序列,根据线性探测再散列解决冲突的方法建立哈希表的存储结构,显示哈希表,任意输入关键字,判断是否在哈希表中。 排序 以下问题要求统一在一个...
  • 南理工初试试题

    2015-09-08 09:48:55
    6.设哈希表长为14,哈希函数是H(key)=key,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为26的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是 A) 8 B) 3 C)2 D)9 7.在一个单链表中,若要...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
  • 7.4 方法引用:方法引用提供了一个很有用的语义来直接访问类或者实例的已经存在的方法或者构造方法, 结合Lambda表达式,方法引用使语法结构紧凑简明。不需要复杂的引用。 详情移步:...
  • 实例035 使用嵌套循环在控制台上输出九九乘法 实例036 用while循环计算1+1/2!+1/3!…1/20! 实例037 for循环输出空心的菱形 实例038 foreach循环优于for循环 实例039 终止循环体 实例040 循环体的过滤器 实例...
  • 实例035 使用嵌套循环在控制台上输出九九乘法 实例036 用while循环计算1+1/2!+1/3!…1/20! 实例037 for循环输出空心的菱形 实例038 foreach循环优于for循环 实例039 终止循环体 实例040 循环体的过滤器 实例...
  • 实例035 使用嵌套循环在控制台上输出九九乘法 实例036 用while循环计算1+1/2!+1/3!…1/20! 实例037 for循环输出空心的菱形 实例038 foreach循环优于for循环 实例039 终止循环体 实例040 循环体的过滤器 实例...

空空如也

空空如也

1 2 3
收藏数 44
精华内容 17
关键字:

对关键字序列构造哈希表