C 语言二次探测程序

7 Jan 2025 | 7 分钟阅读

在本文中，我们将讨论 C 语言中的二次探测问题。

问题描述

本 C 程序实现了二次探测的哈希表。哈希表是一种使用哈希函数将键映射到值的有序数组。线性探测和二次探测是相似的。区别在于，如果我们尝试将元素插入到一个已经被占用的槽中，我们会检查1^1=1 个元素，2^2=4 个元素，3^2=9 个元素，4^2=16 个元素等等。

问题解决方案

创建一个哈希表或结构数组。
输入一个将存储在哈希表中的键和值。
将生成一个与键对应的索引；每个键都存储在一个特定的数组索引中。
使用生成的索引访问该数组索引中包含的数据。
如果没有数据，则创建一个，添加数据项（键和值），并增加哈希表的大小。
如果数据已存在，则在接下来的项中查找一个空位（必要时循环回）来插入新的数据项。

注意

在这种情况下，我们将使用以下公式进行探测，而不是使用线性探测：

(currentPosition + h) % arraySize => 线性探测

(currentPosition + (h * h)) % arraySize => 二次探测

其中h = 1, 2, 3, 4，依此类推。

使用for 循环访问每个索引处的元素，以显示哈希表的所有元素。
要从哈希表中删除键，我们必须首先确定它的索引，然后如果键匹配则删除它。如果不匹配，我们必须搜索元素，直到找到键或一个没有输入数据的空区域，这表示哈希表中没有数据。
退出。

二次探测程序

让我们举个例子来理解 C 语言中二次探测的用法。

#include <stdio.h>
#include <stdlib.h>

struct item {
    int key;
    int value;
};

struct hashtable_item {
    int flag;
    struct item *data;
};

struct hashtable_item *array;
int size = 0;
int max = 10;

int hashcode(int key) {
    return key % max;
}

void init_array() {
    array = (struct hashtable_item*) malloc(max * sizeof(struct hashtable_item));
    for (int i = 0; i < max; i++) {
        array[i].flag = 0;
        array[i].data = NULL;
    }
}

void insert(int key, int value) {
    int index = hashcode(key);
    int i = index;
    int h = 1;

    struct item *new_item = (struct item*) malloc(sizeof(struct item));
    new_item->key = key;
    new_item->value = value;

    while (array[i].flag == 1) {
        if (array[i].data->key == key) {
            printf("\nThis key is already present in the hash table, updating its value\n");
            array[i].data->value = value;
            return;
        }
        i = (i + (h * h)) % max;
        h++;
        if (i == index) {
            printf("\nHash table is full, cannot add more elements\n");
            return;
        }
    }

    array[i].flag = 1;
    array[i].data = new_item;
    printf("\nKey (%d) has been inserted\n", key);
    size++;
}

void remove_element(int key) {
    int index = hashcode(key);
    int i = index;
    int h = 1;

    while (array[i].flag != 0) {
        if (array[i].flag == 1 && array[i].data->key == key) {
            array[i].flag = 2;
            free(array[i].data);  // Free memory for the removed item
            array[i].data = NULL;
            size--;
            printf("\nKey (%d) has been removed\n", key);
            return;
        }
        i = (i + (h * h)) % max;
        h++;
        if (i == index) {
            break;
        }
    }
    printf("\nKey does not exist\n");
}

void display() {
    for (int i = 0; i < max; i++) {
        if (array[i].flag != 1) {
            printf("\nArray[%d] has no elements\n", i);
        } else {
            printf("\nArray[%d] has elements\n%d (key) and %d (value)\n", i, array[i].data->key, array[i].data->value);
        }
    }
}

int size_of_hashtable() {
    return size;
}

int main() {
    int choice, key, value, n, c;

    init_array();

    do {
        printf("Implementation of Hash Table in C with Quadratic Probing.\n\n");
        printf("MENU-:\n1.Insert item in the Hash table\n2.Remove item from the Hash table\n3.Check the size of Hash table\n4.Display Hash table\n5.Exit\n\nPlease enter your choice-:");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Inserting element in Hash table\nEnter key and value:\t");
                scanf("%d %d", &key, &value);
                insert(key, value);
                break;

            case 2:
                printf("Deleting in Hash table\nEnter the key to delete:");
                scanf("%d", &key);
                remove_element(key);
                break;

            case 3:
                n = size_of_hashtable();
                printf("Size of Hash table is:%d\n", n);
                break;

            case 4:
                display();
                break;

            case 5:
                printf("Exiting...\n");
                break;

            default:
                printf("Wrong Input\n");
        }

        if (choice != 5) {
            printf("\nDo you want to continue? (Press 1 for yes):");
            scanf("%d", &c);
        } else {
            c = 0;
        }

    } while (c == 1);

    // Free allocated memory
    for (int i = 0; i < max; i++) {
        if (array[i].flag == 1) {
            free(array[i].data);
        }
    }
    free(array);

    return 0;
}

输出

运行时测试用例

1. Inserting and Displaying Elements
Implementation of Hash Table in C with Quadratic Probing.

MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25

Key (5) has been inserted

Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 15 225

Key (15) has been inserted

Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 4
Array[0] has no elements
Array[1] has no elements
Array[2] has no elements
Array[3] has no elements
Array[4] has no elements
Array[5] has elements
5 (key) and 25 (value)
Array[6] has no elements
Array[7] has no elements
Array[8] has no elements
Array[9] has elements
15 (key) and 225 (value)

Do you want to continue? (Press 1 for yes): 0
2. removing an element
Implementation of Hash Table in C with Quadratic Probing.

MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25

Key (5) has been inserted

Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 2
Deleting in Hash table
Enter the key to delete: 5

Key (5) has been removed

Do you want to continue? (Press 1 for yes): 0

3. Checking Hash Table Size
Implementation of Hash Table in C with Quadratic Probing.

MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 5 25

Key (5) has been inserted

Do you want to continue? (Press 1 for yes): 1
MENU-:
1.Insert item in the Hash table
2.Remove item from the Hash table
3.Check the size of Hash table
4.Display Hash table
5.Exit

Please enter your choice-: 1
Inserting element in Hash table
Enter key and value: 15 225

Key (15) has been inserted

Do you want to continue? (Press 1 for yes): 1
MENU-:
1. Insert item in the Hash table
2. Remove item from the Hash table
3. Check the size of Hash table
4. Display Hash table
5. Exit

Please enter your choice-: 3
Size of Hash table is: 2

Do you want to continue? (Press 1 for yes): 0

说明

在此示例中，程序定义了两个结构：struct hashtable_item 用于表示哈希表中的对象，struct item 用于存储键值对。Array，哈希表指针，size 用于跟踪条目数量，以及 max 用于哈希表大小，都是全局变量的示例。
hashcode 函数通过对键执行模运算来确定哈希索引。此索引决定了项在哈希表数组中的位置。
init_array 函数初始化了哈希表数组。所有标志都设置为0（表示空槽），数据指针设置为NULL。
insert 操作增加了哈希表的库存。哈希函数用于确定索引，二次探测（按 h 的平方值递增）用于查找开放槽。如果槽是空的，则插入一个新项。如果键已存在，则更新该值。如果哈希表已满，则显示适当的消息。
remove_element 函数使用该函数从哈希表中删除内容。它使用哈希函数来确定索引，并使用二次探测来确定键的位置。如果找到键，则通过更改size、更改flag和释放内存来删除对象。如果表已满或键不存在，则显示适当的通知。
display 函数通过遍历哈希表数组来检查每个槽是否有元素，然后进行打印。如果存在元素，则打印其键和值。
size_of_hashtable 函数返回哈希表的当前大小（当前存储的元素数量）。
主函数使用init_array 初始化哈希表。用户会看到一个包含添加和删除项、检查大小、查看哈希表和退出选项的菜单。根据用户的选择，在运行相关函数后，用户可以选择继续或退出。内存为项分配空间，并在用户退出后释放数组。

下一主题C 语言编程测试

C 语言二次探测程序

问题描述

问题解决方案

二次探测程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言二次探测程序

问题描述

问题解决方案

二次探测程序

相关帖子

C 语言 2048 游戏

C 语言 Enum

C 语言左因子分解程序

C 语言单利息计算程序

C 语言嵌入 Lua

使用栈进行表达式求值的 C 语言程序

C 语言众数程序

使用 C 语言求解指数函数 (ex) 的泰勒级数

C 语言行主序和列主序程序

C 语言 FCFS 调度程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器