数据结构与算法的查找算法

Question

对于给定的一组m个整数，采用直接定址法构造散列函数，采用线性探测法处理冲突，构造散列表，并实现对任意数的查找。用C语言实现

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

要实现一个散列表，采用直接定址法构造散列函数，并使用线性探测法来处理冲突，以下是一个基本的C语言实现示例：

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

#define TABLE_SIZE 100  // 散列表的大小

// 散列表元素结构体
typedef struct {
    int key;    // 键
    int value;  // 值
} HashItem;

// 散列表结构体
typedef struct {
    HashItem* items[TABLE_SIZE];  // 散列表数组
} HashTable;

// 初始化散列表
void initHashTable(HashTable* hashTable) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        hashTable->items[i] = NULL;
    }
}

// 直接定址法构造散列函数
int hashFunction(int key) {
    return key % TABLE_SIZE;  // 简单使用模运算构造散列函数
}

// 线性探测法处理冲突
int linearProbing(int hashValue, HashTable* hashTable) {
    int index = hashValue;
    while (hashTable->items[index] != NULL && hashTable->items[index]->key != -1) {
        index = (index + 1) % TABLE_SIZE;  // 线性探测，直到找到空位或已删除位置
    }
    return index;
}

// 插入元素到散列表
void insert(HashTable* hashTable, int key, int value) {
    int index = hashFunction(key);
    if (hashTable->items[index] == NULL) {
        hashTable->items[index] = (HashItem*)malloc(sizeof(HashItem));
        hashTable->items[index]->key = key;
        hashTable->items[index]->value = value;
    } else {
        index = linearProbing(index, hashTable);
        hashTable->items[index] = (HashItem*)malloc(sizeof(HashItem));
        hashTable->items[index]->key = key;
        hashTable->items[index]->value = value;
    }
}

// 查找散列表中的元素
int search(HashTable* hashTable, int key) {
    int index = hashFunction(key);
    while (hashTable->items[index] != NULL) {
        if (hashTable->items[index]->key == key) {
            return hashTable->items[index]->value;  // 找到元素，返回值
        }
        index = (index + 1) % TABLE_SIZE;  // 线性探测，直到找到空位
    }
    return -1;  // 未找到元素，返回-1
}

// 释放散列表内存
void freeHashTable(HashTable* hashTable) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        if (hashTable->items[i] != NULL) {
            free(hashTable->items[i]);
            hashTable->items[i] = NULL;
        }
    }
}

int main() {
    HashTable hashTable;
    initHashTable(&hashTable);

    // 插入一些元素
    insert(&hashTable, 10, 100);
    insert(&hashTable, 20, 200);
    insert(&hashTable, 30, 300);

    // 查找元素
    int value = search(&hashTable, 20);
    if (value != -1) {
        printf("Found value: %d\n", value);
    } else {
        printf("Value not found.\n");
    }

    // 释放散列表
    freeHashTable(&hashTable);

    return 0;
}

以上代码实现了一个简单的散列表，其中包括初始化散列表、直接定址法构造散列函数、线性探测法处理冲突、插入元素、查找元素以及释放散列表内存的功能。

相关的参考资料如下：

1. C语言哈希查找算法详解[^1^]
2. 数据结构（查找）part4散列表[^2^]
3. 数据结构基础——哈希表（散列表）查找算法[^3^]
4. 开放定址法——线性探测(Linear Probing)[^4^]
5. 数据结构—— 构造散列函数的六种方法[^5^]
6. 《数据结构-C语言实现散列表(Hash)》[^6^]
7. 哈希表(Hash table) [散列表] C语言简单实现[^7^]
8. 哈希查找算法 - C语言中文网[^8^]
9. 散列表，这一篇就够了，线性探测_散列表线性探测法[^10^]
10. (c语言)散列表(开放定址法-平方探测法)基本操作集[^12^]