数据结构实践——用哈希法组织关键字

简介: 本文是针对[数据结构基础系列(8):查找]中第11课时[哈希表——散列结构]和第12课时[哈希表的运算]的实践项目。【项目 - 用哈希法组织关键字】 已知一个关键字序列为if、while、for、case、do、break、else、struct、union、int、double、float、char、long、bool,共15个字符串,哈希函数H(key)为关键字的第

本文是针对[数据结构基础系列(8):查找]中第11课时[哈希表——散列结构]和第12课时[哈希表的运算]的实践项目。

【项目 - 用哈希法组织关键字】
已知一个关键字序列为if、while、for、case、do、break、else、struct、union、int、double、float、char、long、bool,共15个字符串,哈希函数H(key)为关键字的第一个字母在字母表中的序号,哈希表的表长为26。
(1)若处理冲突的方法采用线性探测法,请设计算法,输出每个关键字对应的H(key),输出哈希表,并求成功情况下的平均查找长度。

[参考解答]

#include <stdio.h>
#include <string.h>
#define N 15
#define M 26
int H(char *s)
{
    return ((*s-'a'+1)%M);
}

int main()
{
    char *s[N]= {"if", "while", "for", "case", "do", "break", "else", "struct", "union", "int", "double", "float", "char", "long", "bool"};
    int i, j, k;
    char HT[M][10];
    int Det[M];   //存放探测次数
    for(i=0; i<M; i++)
    {
        HT[i][0]='\0';
        Det[i]=0;
    }
    printf("字符串 key\tH(key)\n");
    printf("------------------------\n");
    for(i=0; i<N; i++)
    {
        j=H(s[i]);  //求哈希值
        printf("%s\t\t%d\n", s[i],j);
        k=0;   //探测次数初值
        while(1)
        {
            k++;    //累加探测次数
            if(HT[j][0]=='\0')   //当不冲突时,直接放到该处
            {
                strcpy(HT[j], s[i]);
                break;
            }
            else    //冲突时,采用线性探查法求下一个地址
            {
                j=(j+1)%M;
            }
        }
        Det[j]=k;
    }
    printf("---------------------\n");
    printf("哈希表\n");
    printf("位置\t字符串\t探查次数\n");
    printf("---------------------\n");
    for(i=0; i<M; i++)
        printf("%d\t%s\t%d\n", i, HT[i], Det[i]);
    printf("---------------------\n");
    k=0;
    for(i=0; i<M; i++)
        k+=Det[i];
    printf("查找成功情况下的平均查找长度 %f\n", 1.0*k/N);
    return 0;
}

(2)若处理冲突的方法采用链地址法,请设计算法,输出哈希表,并计算成功情况和不成功情况下的平均查找长度。

[参考解答]

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define N 15
#define M 26
typedef struct node   //定义哈希链表的节点类型
{
    char *key;
    struct node *next;
} LNode;

typedef struct
{
    LNode *link;
} HTType;

int H(char *s)   //实现哈希函数
{
    return ((*s-'a'+1)%M);
}

//构造哈希表
void Hash(char *s[], HTType HT[])
{
    int i, j;
    LNode *q;
    for(i=0; i<M; i++)   //哈希表置初值
        HT[i].link=NULL;
    for(i=0; i<N; i++)   //存储每一个关键字
    {
        q=(LNode*)malloc(sizeof(LNode));   //创建新节点
        q->key = (char*)malloc(sizeof(strlen(s[i])+1));
        strcpy(q->key, s[i]);
        q->next=NULL;
        j=H(s[i]);    //求哈希值
        if(HT[j].link==NULL)   //不冲突,直接加入
            HT[j].link=q;
        else        //冲突时,采用前插法插入
        {
            q->next = HT[j].link;
            HT[j].link=q;
        }
    }
}

//输出哈希表
void DispHT(HTType HT[])
{
    int i;
    LNode *p;
    printf("哈希表\n");
    printf("位置\t关键字序列\n");
    printf("---------------------\n");
    for(i=0; i<M; i++)
    {
        printf(" %d\t", i);
        p=HT[i].link;
        while(p!=NULL)
        {
            printf("%s ", p->key);
            p=p->next;
        }
        printf("\n");
    }
    printf("---------------------\n");
}

//求查找成功情况下的平均查找长度
double SearchLength1(char *s[], HTType HT[])
{
    int i, k, count = 0;
    LNode *p;
    for(i=0; i<N; i++)
    {
        k=0;
        p=HT[H(s[i])].link;
        while(p!=NULL)
        {
            k++;   //p!=NULL,进入循环就要做一次查找
            if(strcmp(p->key, s[i])==0)   //若找到,则退出
                break;
            p=p->next;
        }
        count+=k;
    }
    return 1.0*count/N;   //成功情况仅有N种
}

//求查找不成功情况下的平均查找长度
double SearchLength2(HTType HT[])
{
    int i, k, count = 0;  //count为各种情况下不成功的总次数
    LNode *p;
    for(i=0; i<M; i++)
    {
        k=0;
        p=HT[i].link;
        while(p!=NULL)
        {
            k++;
            p=p->next;
        }
        count+=k;
    }
    return 1.0*count/M;   //不成功时,在表长为M的每个位置上均可能发生
}
int main()
{
    HTType HT[M];
    char *s[N]= {"if", "while", "for", "case", "do", "break", "else", "struct", "union", "int", "double", "float", "char", "long", "bool"};
    Hash(s, HT);
    DispHT(HT);
    printf("查找成功情况下的平均查找长度 %f\n", SearchLength1(s, HT));
    printf("查找不成功情况下的平均查找长度 %f\n", SearchLength2(HT));
    return 0;
}
目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
141 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
算法 C++
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
51 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
47 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
43 10
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
43 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
46 10
|
1月前
|
存储 算法 C++
【C++数据结构——查找】顺序查找(头歌实践教学平台习题)【合集】
若查找的关键字k=5,则SeqSearch函数输出是3,6,2,10,1,8,5,并返回值7。若查找的关键字为k=15,则函数输出是3,6,2,10,1,8,5,7,4,9,并返回值0。假设顺序表中R的关键字依次是3,6,2,10,1,8,5,7,4,9,(第一行是输入的一组原始关键字数据,第二行是要查找的关键字)顺序查找算法中要依次输出与k所比较的关键字,用空格分隔开。本关任务:实现顺序查找的算法。开始你的任务吧,祝你成功!
35 8
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
37 7

热门文章

最新文章