功能概述：

1. 每个记录有下列数据项：电话号码、用户名、地址
2. 分别以电话号码和用户名为关键字建立散列表
3. 各使用两种处理冲突的方法（平方探测法、拉链法）
4. 计算查找成功及失败的平均查找长度（ASL）

c语言源码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdbool.h>
#include <math.h>

#define MAX_RECORDS 100
#define PHONE_LEN 20 
#define NAME_LEN 50 
#define ADDR_LEN 100 
 
// 数据结构定义 
typedef struct {
    char phone[PHONE_LEN];
    char name[NAME_LEN];
    char address[ADDR_LEN];
} PhoneRecord;
 
// 平方探测法哈希表 
typedef struct {
    PhoneRecord* entries;
    bool* occupied;
    int size;
} QuadHashTable;
 
// 分离链表法节点 
typedef struct ChainNode {
    PhoneRecord record;
    struct ChainNode* next;
} ChainNode;
 
typedef struct {
    ChainNode** buckets;
    int size;
} ChainHashTable;

// 哈希函数实现 
unsigned int phone_hash(const char* phone, int size) {
    unsigned int H = atoi(phone + 7);
    return H % size;
}
 
unsigned int name_hash(const char* name, int size) {
    unsigned int H = 0;     // 散列函数值，初始化为0 
    while (*name != '\0')    // 位移映射 
        H = (H << 5) + *name++;

    return H % size;
}
 
// 去除末尾换行符处理工具 
void trim_newline(char* str) {
    int len = strlen(str);
    if (len > 0 && str[len-1] == '\n') {
        str[len-1] = '\0';
    }
}
 
// 平方探测法操作 
QuadHashTable* create_quad_table(int size) {
    QuadHashTable* qt = malloc(sizeof(QuadHashTable));
    qt->entries = calloc(size, sizeof(PhoneRecord));
    qt->occupied = calloc(size, sizeof(bool));
    qt->size = size;

    return qt;
}

int quadratic_insert(QuadHashTable* qt, PhoneRecord rec, bool is_phone_key) {
    unsigned int index = is_phone_key ? 
        phone_hash(rec.phone,  qt->size) : 
        name_hash(rec.name,  qt->size);
 
    for (int i = 0; i < qt->size; i++) {
        int step;
        if (i == 0) {
            step = 0; // 初始位置 
        } else {
            int k = (i + 1) / 2;      // 计算k值 
            step = (i % 2 == 1) ? (k * k) : -(k * k); // 交替加减 
        }
        // 处理负数索引并计算探测位置 
        int probe = (index + step + qt->size) % qt->size; 
 
        if (!qt->occupied[probe]) {
            qt->entries[probe] = rec;
            qt->occupied[probe] = true;

            return i + 1; // 返回探测次数 
        }
    }
    return -1; // 表已满 
}
 
PhoneRecord* quadratic_search(QuadHashTable* qt, const char* key, bool is_phone_key, int* probes) {
    unsigned int index = is_phone_key ? 
        phone_hash(key, qt->size) : 
        name_hash(key, qt->size);
 
    for (int i = 0; i < qt->size; i++) {
        (*probes)++;
        int step;
        if (i == 0) {
            step = 0;
        } else {
            int k = (i + 1) / 2;
            step = (i % 2 == 1) ? (k * k) : -(k * k);
        }
        int pos = (index + step + qt->size) % qt->size; // 处理负数 
 
        if (!qt->occupied[pos]) return NULL; // 未找到 
        if ((is_phone_key && strcmp(qt->entries[pos].phone, key) == 0) ||
            (!is_phone_key && strcmp(qt->entries[pos].name, key) == 0)) {
            return &qt->entries[pos]; // 找到记录 
        }
    }
    return NULL; // 遍历完所有位置 
}
 
// 分离链表法操作 
ChainHashTable* create_chain_table(int size) {
    ChainHashTable* ct = malloc(sizeof(ChainHashTable));
    ct->buckets = calloc(size, sizeof(ChainNode*));
    ct->size = size;

    return ct;
}
 
int chain_insert(ChainHashTable* ct, PhoneRecord rec, bool is_phone_key) {
    unsigned int index = is_phone_key ?
        phone_hash(rec.phone,  ct->size) :
        name_hash(rec.name,  ct->size);

    ChainNode* newNode = malloc(sizeof(ChainNode));
    newNode->record = rec;
    newNode->next = NULL;

    int depth = 1; // 初始深度为1

    if (!ct->buckets[index]) {
        ct->buckets[index] = newNode;
    } else {
        ChainNode* current = ct->buckets[index];
        while (current->next) {
            current = current->next;
            depth++;
        }
        current->next = newNode;

        depth++; // 实际插入深度为遍历次数+1
    }
    return depth;
}
 
PhoneRecord* chain_search(ChainHashTable* ct, const char* key, bool is_phone_key, int* probes) {
    unsigned int index = is_phone_key ? 
        phone_hash(key, ct->size) : 
        name_hash(key, ct->size);
 
    ChainNode* current = ct->buckets[index];
    while (current) {
        (*probes)++;
        if ((is_phone_key && strcmp(current->record.phone,  key) == 0) ||
            (!is_phone_key && strcmp(current->record.name,  key) == 0)) {
            return &current->record;
        }
        current = current->next;
    }
    return NULL;
}

// 性能统计模块 
typedef struct {
    int total_inserts;  //插入元素个数
    int total_probes;   //查询次数总和
    float asl_unsuccess; // 存储不成功ASL
} PerfMetrics;
 
void print_metrics(PerfMetrics* m, const char* title) {
    printf("\n=== %s 性能分析 ===\n", title);
    if (m->total_inserts > 0) {
        printf("查找成功ASL: %.2f\n", (float)m->total_probes/m->total_inserts);
        printf("查找不成功ASL: %.2f\n", m->asl_unsuccess);
    }

}
float calculate_quad_unsuccess(QuadHashTable* qt) {
    int total_probes = 0;
    for (int h = 0; h < qt->size; h++) { // 遍历所有可能的初始哈希值 
        int probes = 0;
        for (int i = 0; i < qt->size; i++) {
            int step;
            if (i == 0) {
                step = 0;
            } else {
                int k = (i + 1) / 2;
                step = (i % 2 == 1) ? (k * k) : -(k * k);
            }
            int pos = (h + step + qt->size) % qt->size; // 处理负数 
            probes++;
            if (!qt->occupied[pos]) break; // 找到空槽 
        }
        total_probes += probes;
    }
    return (float)total_probes / qt->size; // 平均查找长度 
}
float calculate_chain_unsuccess(ChainHashTable* ct) {
    int total_length = 0;
    for (int i = 0; i < ct->size; i++) {
        int length = 0;
        ChainNode* node = ct->buckets[i];
        while (node) {
            length++;
            node = node->next;
        }
        total_length += length;
    }
    return (float)total_length / ct->size;
}
int is_valid_phone_number(const char *phone) {
    if (strlen(phone) != 11) {
        return 0;
    }
    for (int i = 0; i < 11; i++) {
        if (!isdigit(phone[i])) {
            return 0;
        }
    }
    return 1;
}
void clear_input_buffer() {
    int c;
    while ((c = getchar()) != '\n' && c != EOF);
}
int is_empty_or_whitespace(const char *str) {
    while(*str) {
        if(!isspace((unsigned char)*str)) // 检测非空白字符 
            return 0;
        str++;
    }
    return 1;
}
//两端空格处理
void trim_whitespace(char *str) {
    char *start = str;
    char *end = str + strlen(str) - 1;
 
    // 去除头部空白（兼容中文全角空格）
    while (*start && (isspace((unsigned char)*start) || 
                    (unsigned char)*start == 0xA0)) {
        start++;
    }
 
    // 处理全空情况 
    if (start > end) {
        *str = '\0';
        return;
    }
 
    // 去除尾部空白 
    while (end > start && (isspace((unsigned char)*end) ||
                          (unsigned char)*end == 0xA0)) {
        end--;
    }
 
    // 移动处理结果 
    memmove(str, start, end - start + 1);
    str[end - start + 1] = '\0';
}
int get_valid_record_count() {
    char input[16]; // 足够存储100的字符串形式 
    long value;
    char *endptr;
 
    do {
        printf("输入记录数 (1-%d): ", MAX_RECORDS);
        fgets(input, sizeof(input), stdin); // 安全输入 
        
        // 字符转换为long型
        value = strtol(input, &endptr, 10);
        
        // 错误分类处理 
        if (endptr == input) { // 无有效数字 
            printf("错误：请输入数字！\n");
            continue;
        } else if (*endptr != '\n' && *endptr != '\0') { // 包含非数字字符 
            printf("错误：检测到非法字符！\n");
             
            continue;
        } else if (value <= 0 || value > MAX_RECORDS) { // 范围校验 
            printf("错误：请输入1-%d之间的数值！\n", MAX_RECORDS);
            continue;
        }
        
        return (int)value;
    } while (1);
}
// 链表哈希表释放函数 
void free_chain_table(ChainHashTable* ct) {
    if (!ct) return;
    // 遍历所有桶释放链表节点 
    for (int i = 0; i < ct->size; i++) {
        ChainNode* current = ct->buckets[i];
        while (current) {
            ChainNode* temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(ct->buckets);  // 释放桶数组 
    free(ct);           // 释放主结构 
}
int load_from_file(const char* filename, PhoneRecord* records) {
    FILE* fp = fopen(filename, "r");
    if (!fp) {
        printf("无法打开文件 %s\n", filename);
        return -1;
    }

    int count = 0;
    int rcount = 0;
    char line[256];
    while (fgets(line, sizeof(line), fp) && count < MAX_RECORDS) {
        // 分割字段
        char *phone = strtok(line, ",");
        char *name = strtok(NULL, ",");
        char *addr = strtok(NULL, "\n");

        // 验证字段有效性
        if (!phone || !name || !addr) {
            printf("第%d行格式错误，已跳过\n", rcount+1);
            rcount++;
            continue;
        }

        // 处理字符串
        trim_whitespace(phone);
        trim_whitespace(name);
        trim_whitespace(addr);

        if (!is_valid_phone_number(phone)) {
            printf("第%d行电话号码无效：%s\n", rcount+1, phone);
            rcount++;
            continue;
        }

        if (strlen(name) == 0 || strlen(addr) == 0) {
            printf("第%d行姓名或地址为空\n", rcount+1);
            rcount++;
            continue;
        }

        // 存入记录
        strncpy(records[count].phone, phone, PHONE_LEN-1);
        strncpy(records[count].name, name, NAME_LEN-1);
        strncpy(records[count].address, addr, ADDR_LEN-1);
        rcount++;
        count++;
    }

    fclose(fp);
    return count;
}
bool is_prime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}
int find_special_prime(int n) {    //找4k+3的质数
    int m = (int)ceil(n / 0.7);
    while (true) {
        if (is_prime(m) && m % 4 == 3) return m;
        m++;
    }
}
int find_next_prime(int n) {  //大于n的第一个质数
    if (n < 2) return 2;  // 处理n小于2的特殊情况 
    
    int candidate = (n % 2 == 0) ? n + 1 : n + 2;
    while (1) {
        if (is_prime(candidate)) return candidate;
        candidate += 2;  // 仅检查奇数（偶数不可能是质数）
    }
}
// 主程序 
int main() {
    QuadHashTable* qht_phone = NULL;
    QuadHashTable* qht_name = NULL;
    ChainHashTable* cht_phone = NULL;
    ChainHashTable* cht_name = NULL;
 
    PerfMetrics metrics[4] = {0};
    PhoneRecord records[MAX_RECORDS];
    
    printf("电话号码查询系统\n");
    int n;
    printf("是否从文件导入数据？(y/n): ");
    char choice;
    scanf("%c", &choice); 
    while (getchar() != '\n');
    
    if (tolower(choice) == 'y') {
        char filename[256];
        printf("输入文件路径：");
        fgets(filename, sizeof(filename), stdin);
        trim_newline(filename);
        
        n = load_from_file(filename, records);
        if (n <= 0) {
            printf("文件读取失败，转为手动输入\n");
            n = get_valid_record_count();
        } else {
            printf("成功从文件读取%d条记录\n", n);

            const int HASH_SIZE = find_special_prime(n);
            const int C_HASH_SIZE = find_next_prime(n);

            printf("平方法哈希表大小为%d \n",HASH_SIZE);
            printf("拉链哈希表大小为%d \n",C_HASH_SIZE);
            qht_phone = create_quad_table(HASH_SIZE);
            qht_name = create_quad_table(HASH_SIZE);
            cht_phone = create_chain_table(C_HASH_SIZE);
            cht_name = create_chain_table(C_HASH_SIZE);
            // 将文件记录插入哈希表 
            for (int i = 0; i < n; i++) {
                // 插入四个哈希表 
                int probes = quadratic_insert(qht_phone, records[i], true);
                metrics[0].total_probes += probes;
                metrics[0].total_inserts++;
                
                probes = quadratic_insert(qht_name, records[i], false);
                metrics[1].total_probes += probes;
                metrics[1].total_inserts++;
                
                int depth = chain_insert(cht_phone, records[i], true);
                metrics[2].total_probes += depth;
                metrics[2].total_inserts++;
                
                depth = chain_insert(cht_name, records[i], false);
                metrics[3].total_probes += depth;
                metrics[3].total_inserts++;
            }
        }
    } else {
        n = get_valid_record_count();
    }

    // 数据录入 
    if (tolower(choice) != 'y') {
        const int HASH_SIZE = find_special_prime(n);
        const int C_HASH_SIZE = find_next_prime(n);
        
        printf("平方法哈希表大小为%d \n",HASH_SIZE);
        printf("拉链哈希表大小为%d \n",C_HASH_SIZE);
        qht_phone = create_quad_table(HASH_SIZE);
        qht_name = create_quad_table(HASH_SIZE);
        cht_phone = create_chain_table(C_HASH_SIZE);
        cht_name = create_chain_table(C_HASH_SIZE);

        for (int i = 0; i < n; i++) {
            printf("\n记录 %d:\n", i+1);
            
            while (1) {
                printf("电话号码: ");
                fgets(records[i].phone, PHONE_LEN, stdin);
                trim_newline(records[i].phone);
    
                if (is_valid_phone_number(records[i].phone)) {
                    //printf("有效的电话号码: %s\n", records[i].phone);
                    break;
                } else {
                    printf("无效的电话号码，请输入11位数字。\n");
                    continue;
                }
            }
        
            
            do {
                printf("用户名 (最多%d字符): ", NAME_LEN-1);
                fgets(records[i].name, NAME_LEN, stdin);
                
                // 检测输入超长 
                if (strchr(records[i].name, '\n') == NULL) {  //查找是否有回车符
                    clear_input_buffer();
                    printf("输入超过最大长度！请重新输入\n");
                    continue;
                }
                
                trim_newline(records[i].name);  // 移除末尾换行符 
                trim_whitespace(records[i].name); //两端空格处理
                //空输入检测 
                if (strlen(records[i].name) == 0) {
                    printf("错误：用户名不能为空！\n");
                    continue;  // 重新循环 
                }
                
                break;
            } while (1);
            
            do {
                printf("地址 (最多%d字符): ", ADDR_LEN-2);
                fgets(records[i].address, ADDR_LEN, stdin);
                
                // 检测输入超长 
                if (strchr(records[i].address, '\n') == NULL) {
                    clear_input_buffer();
                    printf("输入超过最大长度！请重新输入\n");
                    continue;
                }
                
                trim_newline(records[i].address);  // 移除末尾换行符 
                
                //空输入检测 
                if (is_empty_or_whitespace(records[i].address)) {
                    printf("错误：地址不能为空！\n");
                    continue;  // 重新循环 
                }
                
                break;
            } while (1);
            


            // 插入四个哈希表 
            int probes = quadratic_insert(qht_phone, records[i], true);
            metrics[0].total_probes += probes;
            metrics[0].total_inserts++;
            
            probes = quadratic_insert(qht_name, records[i], false);
            metrics[1].total_probes += probes;
            metrics[1].total_inserts++;
            
            int depth = chain_insert(cht_phone, records[i], true);
            metrics[2].total_probes += depth;
            metrics[2].total_inserts++;
            
            depth = chain_insert(cht_name, records[i], false);
            metrics[3].total_probes += depth;
            metrics[3].total_inserts++;
        }
    }

    // 录入完成后计算ASL不成功
    metrics[0].asl_unsuccess = calculate_quad_unsuccess(qht_phone);  // 电话平方
    metrics[1].asl_unsuccess = calculate_quad_unsuccess(qht_name);   // 姓名平方
    metrics[2].asl_unsuccess = calculate_chain_unsuccess(cht_phone);// 电话链式
    metrics[3].asl_unsuccess = calculate_chain_unsuccess(cht_name); // 姓名链式
    
    // 查询界面
    while(1) {
        printf("\n=== 查询菜单 ===\n");
        printf("1. 按电话号码查询\n");
        printf("2. 按用户名查询\n");
        printf("3. 显示性能分析\n");
        printf("0. 退出系统\n");
        printf("选择操作: ");

        int choice;
        int scan_result = scanf("%d", &choice);
        getchar(); // 清除回车

        // 输入验证增强
        if (scan_result != 1 || choice < 0 || choice > 3) {
            printf("错误：请输入0-3之间的有效数字！\n");
           
            continue;
        }

        if (choice == 0) break;

        if (choice == 3) {
            print_metrics(&metrics[0], "电话平方探测");
            print_metrics(&metrics[1], "姓名平方探测");
            print_metrics(&metrics[2], "电话分离链表");
            print_metrics(&metrics[3], "姓名分离链表");
            continue;
        }

        printf("输入查询内容: ");
        char query[choice == 1 ? PHONE_LEN : NAME_LEN];
        fgets(query, sizeof(query), stdin);
        trim_newline(query);

        // 动态选择查询模式
        int search_methods[2] = {0}; // 存储要使用的查询方法索引
        int method_count = 0;
        
        if (choice == 1) {
            search_methods[0] = 0; // 电话平方探测
            search_methods[1] = 2; // 电话分离链表
            method_count = 2;
        } else if (choice == 2) {
            search_methods[0] = 1; // 姓名平方探测
            search_methods[1] = 3; // 姓名分离链表
            method_count = 2;
        }

        // 执行查询并记录结果
        PhoneRecord* results[4] = {NULL};
        int probes[4] = {0};
        
        for (int i = 0; i < method_count; i++) {
            switch(search_methods[i]) {
                case 0:
                    results[0] = quadratic_search(qht_phone, query, true, &probes[0]);
                    break;
                case 1:
                    results[1] = quadratic_search(qht_name, query, false, &probes[1]);
                    break;
                case 2:
                    results[2] = chain_search(cht_phone, query, true, &probes[2]);
                    break;
                case 3:
                    results[3] = chain_search(cht_name, query, false, &probes[3]);
                    break;
            }
        }

        // 显示结果并更新指标
        printf("\n查询结果：\n");
        const char* methods[] = {
            "电话平方探测", "姓名平方探测",
            "电话分离链表", "姓名分离链表"
        };

        for (int i = 0; i < method_count; i++) {
            int idx = search_methods[i];
            if (results[idx]) {
                printf("[%s] 经过 %d 次探测找到记录：\n 电话：%s\n 姓名：%s\n 地址：%s\n",
                    methods[idx],
                    probes[idx],  // 探测次数显示 
                    results[idx]->phone,
                    results[idx]->name,
                    results[idx]->address);
            } else {
                printf("[%s] 经过 %d 次探测未找到记录\n", 
                    methods[idx], probes[idx]);  // 探测次数显示 
            }
            //metrics[idx].total_searches++;
            //metrics[idx].total_search_probes += probes[idx];
        }
    }

    // 内存释放 
    free(qht_phone->entries);
    free(qht_phone->occupied);
    free(qht_phone);
    
    free(qht_name->entries);
    free(qht_name->occupied);
    free(qht_name);
    
    free_chain_table(cht_phone);
    free_chain_table(cht_name);
 
    return 0;
}