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

以下是基于C语言的实现，使用了文件读写操作来保存哈希表：

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

#define MAX_SIZE 50 // 哈希表最大记录数
#define DEL_FLAG 2 // 记录删除标志
#define EMPTY_FLAG 1 // 记录空标志

typedef struct Record {
    char phone[20]; // 电话号码
    char username[20]; // 用户名
    char address[50]; // 住址
} Record;

typedef struct HashTable {
    Record records[MAX_SIZE]; // 记录数组
    int flags[MAX_SIZE]; // 标志数组，0表示有记录，1表示空，2表示被删除
} HashTable;

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

// 初始化哈希表
void initHashTable(HashTable *table) {
    for (int i = 0; i < MAX_SIZE; i++) {
        table->flags[i] = EMPTY_FLAG; // 初始标志都为1，表示为空
    }
}

// 插入记录
void insertRecord(HashTable *table) {
    Record record;
    printf("请输入电话号码:");
    scanf("%s", record.phone);
    printf("请输入用户名:");
    scanf("%s", record.username);
    printf("请输入住址:");
    scanf("%s", record.address);

    int index = hash(record.username); // 计算哈希值
    int i = 0;
    while (table->flags[index] == 0 && i < MAX_SIZE) { // 如果当前位置有记录，或者循环次数超过哈希表大小，则继续查找
        if (strcmp(table->records[index].username, record.username) == 0) { // 如果用户名已存在，则更新记录
            table->records[index] = record;
            return;
        }
        index = (index + 1) % MAX_SIZE;
        i++;
    }
    if (table->flags[index] == EMPTY_FLAG || table->flags[index] == DEL_FLAG) { // 如果当前位置为空或者被删除，则插入记录
        table->records[index] = record;
        table->flags[index] = 0; // 标记为有记录
    }
}

// 查找记录
int findRecord(HashTable *table, char *username) {
    int index = hash(username);
    int i = 0;
    while (table->flags[index] != EMPTY_FLAG && i < MAX_SIZE) { // 如果当前位置不为空或者循环次数超过哈希表大小，则继续查找
        if (table->flags[index] == 0 && strcmp(table->records[index].username, username) == 0) { // 如果当前位置有记录且用户名匹配，则返回该记录位置
            return index;
        }
        index = (index + 1) % MAX_SIZE;
        i++;
    }
    return -1; // 没有找到
}

// 删除记录
void deleteRecord(HashTable *table, char *username) {
    int index = findRecord(table, username); // 先查找记录
    if (index != -1) { // 如果找到了，标记为被删除
        table->flags[index] = DEL_FLAG;
    }
}

// 显示记录
void showRecord(HashTable *table, char *username) {
    int index = findRecord(table, username); // 先查找记录
    if (index != -1 && table->flags[index] == 0) { // 如果找到了，且当前位置有记录，则输出
        printf("电话号码:%s\n", table->records[index].phone);
        printf("用户名:%s\n", table->records[index].username);
        printf("住址:%s\n", table->records[index].address);
    } else {
        printf("没有找到记录!\n");
    }
}

// 计算平均查找长度
void calcASL(HashTable *table) {
    int sum = 0;
    int count = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        if (table->flags[i] == 0) { // 如果当前位置有记录，则计算查找长度
            int index = hash(table->records[i].username);
            int j = 0;
            while (table->flags[index] != EMPTY_FLAG && j < MAX_SIZE) { // 如果当前位置不为空或者循环次数超过哈希表大小，则继续查找
                if (table->flags[index] == 0 && strcmp(table->records[index].username, table->records[i].username) == 0) { // 如果当前位置有记录且用户名匹配，则计算查找长度
                    sum += j + 1; // 计算查找长度
                    count++; // 计算查找记录数
                    break;
                }
                index = (index + 1) % MAX_SIZE;
                j++;
            }
        }
    }
    if (count > 0) { // 如果查找记录数大于0，则输出平均查找长度
        printf("平均查找长度:%.2f\n", (float)sum / count);
    } else {
        printf("没有记录!\n");
    }
}

// 保存哈希表到文件
void saveHashTable(HashTable *table) {
    FILE *fp = fopen("hash_table.dat", "wb");
    fwrite(table, sizeof(HashTable), 1, fp);
    fclose(fp);
}

// 从文件中读取哈希表
void loadHashTable(HashTable *table) {
    FILE *fp = fopen("hash_table.dat", "rb");
    if (fp) {
        fread(table, sizeof(HashTable), 1, fp);
        fclose(fp);
    }
}

int main() {
    HashTable table;
    initHashTable(&table);
    loadHashTable(&table); // 从文件中读取哈希表

    int choice;
    char username[20];
    do {
        printf("1.插入记录\n");
        printf("2.查找记录\n");
        printf("3.删除记录\n");
        printf("4.显示记录\n");
        printf("5.计算平均查找长度\n");
        printf("6.保存哈希表到文件\n");
        printf("0.退出程序\n");
        printf("请选择:");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                insertRecord(&table);
                break;
            case 2:
                printf("请输入用户名:");
                scanf("%s", username);
                int index = findRecord(&table, username);
                if (index != -1) {
                    printf("查找成功，位置:%d\n", index);
                } else {
                    printf("查找失败!\n");
                }
                break;
            case 3:
                printf("请输入用户名:");
                scanf("%s", username);
                deleteRecord(&table, username);
                break;
            case 4:
                printf("请输入用户名:");
                scanf("%s", username);
                showRecord(&table, username);
                break;
            case 5:
                calcASL(&table);
                break;
            case 6:
                saveHashTable(&table);
                break;
            case 0:
                break;
            default:
                printf("输入错误，请重新选择!\n");
                break;
        }
    } while (choice != 0);

    return 0;
}

注意，为了方便保存哈希表到文件中，结构体中不可以使用指针类型。以上代码中使用了两个数组来分别存储记录和标志，其中标志数组的值为1表示该位置为空，为2表示该位置被删除，为0表示该位置有记录。使用线性探测法解决冲突，即如果当前位置有记录，则继续向后查找直到找到空位置或者被删除位置。计算平均查找长度时，需要遍历整个哈希表，对于每个有记录的位置，都需要重新计算哈希值并查找该记录，因此时间复杂度较高。