哈希表实现的电话簿查询系统线性探测法解决冲突c语言，实验小结

哈希表是一种重要的数据结构，用于实现快速查找。在电话簿查询系统中，哈希表可用于存储电话号码和对应的联系人姓名等信息。本次实验中，我们采用了线性探测法解决哈希表中的冲突问题。

线性探测法是指当哈希表中某个槽已经被占用时，继续往后探测，直到找到一个空槽为止。我们可以通过一个叫做“探测长度”的变量来记录需要探测的距离，以免陷入死循环。

在实现哈希表时，我们需要考虑以下几个问题：

1. 哈希函数的设计：哈希函数决定了元素在哈希表中的位置。一个好的哈希函数需要满足以下几个条件：均匀性、高效性、容易实现。

2. 哈希表的大小：哈希表的大小需要根据实际情况进行调整，通常需要考虑数据规模和内存限制等因素。

3. 冲突解决方法：哈希表中可能会存在冲突，我们需要采用合适的方法解决。

在本次实验中，我们使用了C语言实现了一个简单的电话簿查询系统。具体实现过程如下：

1. 定义了一个哈希表结构体，包含了哈希表的大小、元素个数、哈希函数和数据数组等信息。

2. 实现了一个简单的哈希函数，将字符串转换为一个整数作为哈希值。

3. 采用线性探测法解决了哈希表中的冲突问题。

4. 实现了插入、删除和查找等操作。

5. 最后，我们对实验进行了测试，并得出了一些结论。例如，随着哈希表大小的增加，查询时间逐渐减少，但空间占用也会增加。

总的来说，本次实验让我们更加深入地理解了哈希表和线性探测法，并提高了我们的编程能力。

相关问题

设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 显示哈希表，哈希表保存到文件中。测试数据：取某个单位电话号码簿中的30 个记录。c语言实现

以下是实现该功能的 C 语言代码：

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

// 定义记录结构体
typedef struct Record {
    char phone[12];     // 电话号码
    char username[20];  // 用户名
    char address[50];   // 住址
} Record;

// 定义哈希表结构体
typedef struct HashTable {
    int size;           // 哈希表大小
    Record* records;    // 记录数组
    int* status;        // 记录状态（0表示空，1表示已删除，2表示有记录）
} HashTable;

// 哈希函数：除留取余数法
int hash(char* key, int size) {
    int sum = 0;
    for (int i = 0; i < strlen(key); i++) {
        sum += key[i];
    }
    return sum % size;
}

// 初始化哈希表
void initHashTable(HashTable* ht, int size) {
    ht->size = size;
    ht->records = (Record*) malloc(size * sizeof(Record));
    ht->status = (int*) calloc(size, sizeof(int));
}

// 插入记录
void insertRecord(HashTable* ht, Record record) {
    int index = hash(record.username, ht->size);  // 计算关键字的哈希值
    int i = 0;
    while (i < ht->size && ht->status[index] != 0 && strcmp(ht->records[index].username, record.username) != 0) {
        // 线性探测法解决冲突
        index = (index + 1) % ht->size;
        i++;
    }
    if (ht->status[index] != 2) {
        // 如果该位置为空或已删除，则插入记录
        ht->records[index] = record;
        ht->status[index] = 2;
        printf("Insert record successfully!\n");
    } else {
        printf("Insert record failed! The username already exists.\n");
    }
}

// 查找记录
void searchRecord(HashTable* ht, char* username) {
    int index = hash(username, ht->size);  // 计算关键字的哈希值
    int i = 0;
    while (i < ht->size && ht->status[index] != 0) {
        if (ht->status[index] == 2 && strcmp(ht->records[index].username, username) == 0) {
            // 如果该位置有记录且用户名匹配，则找到了记录
            printf("Phone: %s\n", ht->records[index].phone);
            printf("Username: %s\n", ht->records[index].username);
            printf("Address: %s\n", ht->records[index].address);
            return;
        }
        index = (index + 1) % ht->size;
        i++;
    }
    printf("Search record failed! The username doesn't exist.\n");
}

// 删除记录
void deleteRecord(HashTable* ht, char* username) {
    int index = hash(username, ht->size);  // 计算关键字的哈希值
    int i = 0;
    while (i < ht->size && ht->status[index] != 0) {
        if (ht->status[index] == 2 && strcmp(ht->records[index].username, username) == 0) {
            // 如果该位置有记录且用户名匹配，则删除记录
            ht->status[index] = 1;
            printf("Delete record successfully!\n");
            return;
        }
        index = (index + 1) % ht->size;
        i++;
    }
    printf("Delete record failed! The username doesn't exist.\n");
}

// 显示哈希表
void displayHashTable(HashTable* ht) {
    printf("Hash Table:\n");
    printf("%-15s %-20s %-50s\n", "Phone", "Username", "Address");
    for (int i = 0; i < ht->size; i++) {
        if (ht->status[i] == 2) {
            printf("%-15s %-20s %-50s\n", ht->records[i].phone, ht->records[i].username, ht->records[i].address);
        } else {
            printf("%-15s %-20s %-50s\n", "-", "-", "-");
        }
    }
}

// 保存哈希表到文件中
void saveHashTable(HashTable* ht, char* filename) {
    FILE* fp = fopen(filename, "wb");
    fwrite(&(ht->size), sizeof(int), 1, fp);
    fwrite(ht->records, sizeof(Record), ht->size, fp);
    fwrite(ht->status, sizeof(int), ht->size, fp);
    fclose(fp);
    printf("Save hash table to file successfully!\n");
}

// 从文件中读取哈希表
void loadHashTable(HashTable* ht, char* filename) {
    FILE* fp = fopen(filename, "rb");
    fread(&(ht->size), sizeof(int), 1, fp);
    ht->records = (Record*) malloc(ht->size * sizeof(Record));
    ht->status = (int*) malloc(ht->size * sizeof(int));
    fread(ht->records, sizeof(Record), ht->size, fp);
    fread(ht->status, sizeof(int), ht->size, fp);
    fclose(fp);
    printf("Load hash table from file successfully!\n");
}

int main() {
    HashTable ht;
    initHashTable(&ht, 50);  // 初始化哈希表，大小为50

    // 从键盘输入各记录
    Record record;
    for (int i = 0; i < 30; i++) {
        printf("Record %d:\n", i + 1);
        printf("Phone: ");
        scanf("%s", record.phone);
        printf("Username: ");
        scanf("%s", record.username);
        printf("Address: ");
        scanf("%s", record.address);
        insertRecord(&ht, record);  // 插入记录到哈希表中
    }

    displayHashTable(&ht);  // 显示哈希表

    char filename[20] = "hash_table.bin";
    saveHashTable(&ht, filename);  // 保存哈希表到文件中

    char username[20];
    printf("Enter username to search: ");
    scanf("%s", username);
    searchRecord(&ht, username);  // 查找记录

    printf("Enter username to delete: ");
    scanf("%s", username);
    deleteRecord(&ht, username);  // 删除记录

    displayHashTable(&ht);  // 显示哈希表

    loadHashTable(&ht, filename);  // 从文件中读取哈希表

    displayHashTable(&ht);  // 显示哈希表

    return 0;
}

注意事项：

1. 本代码中的哈希函数采用除留取余数法，可以根据实际需求选择其他哈希函数。
2. 本代码中的记录结构体只包含电话号码、用户名和住址，可以根据实际需求添加其他数据项。
3. 本代码中的哈希表采用线性探测法解决冲突，可以根据实际需求选择其他冲突解决方法。
4. 本代码中的哈希表保存到文件中时采用二进制形式，可以根据实际需求选择其他保存方式。