精华内容
下载资源
问答
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...

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

    函数接口定义:

    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.
    

    ANSWER

    Position Find( HashTable H, ElementType Key ){
    	int maxsize = H->TableSize;//表长
    	int d = 0;//增量序列 
    	Position p = Hash(Key,H->TableSize);//计算哈希值
    	while(1){
    		if(H->Cells[p].Info == Empty || H->Cells[p].Data == Key){//找到空位置或者对应值返回下标
    			return p;
    		}
    		if(d < maxsize-1){
    			d++;
    		}else{
                break;
            }
    		p = (Hash(Key,H->TableSize)+d)%maxsize;
    	}
    	return ERROR;
    }
    
    展开全文
  • 线性探测法查找函数 (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;
    }
    
    展开全文
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...

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

    函数接口定义:

    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.

    AC代码

    Position Find( HashTable H, ElementType Key ){
        int x=Hash(Key,H->TableSize);
        int a=0;
        while(a<H->TableSize){
            if( H->Cells[x].Info==Empty//题目里还给了个Deleted,没有测试点不鸟它了
               ||H->Cells[x].Data == Key){//可不能等于Legitimate
                return x;
            }
            x=(x+1)%H->TableSize;
            a++;
        }
        return ERROR;
    }
    
    展开全文
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ ...

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

    函数接口定义:

    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

    输入样例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.
    #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;
    }
    
    /* 你的代码将被嵌在这里 */
    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;
    }

     

     

    展开全文
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef ...
  • 6-1 线性探测法查找函数 (20 分)

    千次阅读 2019-10-20 15:42:20
    试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ ...
  • 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */ typedef...
  • 习题5.10 线性探测法查找函数 (20分) 代码: Position Find( HashTable H, ElementType Key ) { int index = Hash(Key, H->TableSize), count = 0; while (count != H->TableSize) { if (H->Cells...
  • 6-4 线性探测法查找函数(哈希表)

    千次阅读 2017-12-15 15:52:22
    6-4线性探测法查找函数(20分) 试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE ...
  • 6-4 线性探测法查找函数

    千次阅读 2017-12-15 15:46:05
    试实现线性探测法查找函数。 函数接口定义: Position Find( HashTable H, ElementType Key ); 其中HashTable是开放地址散列表,定义如下: #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */...
  • Position Find( HashTable H, ElementType Key ) {  int a=Key%H-&gt;TableSize;  int cou=0;  while(H-&gt;Cells[a].Info!=Empty&amp;&amp;cou!=H-&...Cells[a].Data==K...
  • 哈希表:线性探测法和链地址法求查找成功与不成功的平均查找
  • 映射函数叫做散列函数,存放记录的数组叫做散列表。 装填因子         关键字个数 / 表长 处理冲突         一般来说冲突不可避免的,只能尽可能地减少冲突的发生。在建立...
  • 采用线性探测法作为冲突处理方法,将数据逐个放入大小为15的数组中。 输出散列表的存储示意图(第一行输出下标,第二行输出横线,第三行输出数据)。 并对其进行查找,输出(找到、找不到时的)查找次数。 2、输入10...
  • NULL 博文链接:https://128kj.iteye.com/blog/1744810
  • 散列函数为:H(key)=key mod 11,处理冲突采用链地址,求在等概率下查找成功和查找不成功的平均查找长度1mod11=1,所以数据1是属于地址1 12mod11=1,所以数据12也是属于地址1(这个数据是数据1指针的另一个新数据...
  • Hash表线性探测处理计算比较成功和失败时的 ASL
  • 它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。 2、散列存储的基本思路  以数据中每个元素的关键字K为自变量,通过散列函数H(k)...
  • 散列表类似于数组,可以把散列表的散列值看成数组的索引值,访问散列表和访问数组元素一样快速,他可以在常数时间内实现查找和插入操作。 由于无法通过散列值知道键的大小,因此散列表无法实现有序性操作。 散列...
  • 散列函数线性探测法处理冲突

    千次阅读 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) 查找成功的平均查找长度:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,919
精华内容 4,367
关键字:

线性探测法的查找函数