一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度ASLC语言代码

以下是基于线性表、二叉排序树和哈希表不同存储结构实现单词词频统计和单词检索功能的ASLC代码：

## 线性表存储结构

定义一个单词节点结构体，包含单词和出现次数两个变量。定义一个线性表结构体，包含单词节点数组和当前单词节点数两个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
};

struct word_list {
    struct word_node nodes[1000];
    int count;
};

struct word_list wordList;

void word_count(char* filename) {
    FILE* fp = fopen(filename, "r");
    char word[20];
    while (fscanf(fp, "%s", word) != EOF) {
        int exist = 0;
        for (int i = 0; i < wordList.count; i++) {
            if (strcmp(wordList.nodes[i].word, word) == 0) {
                wordList.nodes[i].count++;
                exist = 1;
                break;
            }
        }
        if (!exist) {
            strcpy(wordList.nodes[wordList.count].word, word);
            wordList.nodes[wordList.count].count = 1;
            wordList.count++;
        }
    }
    fclose(fp);
}

int word_search(char* word) {
    for (int i = 0; i < wordList.count; i++) {
        if (strcmp(wordList.nodes[i].word, word) == 0) {
            return wordList.nodes[i].count;
        }
    }
    return 0;
}

## 二叉排序树存储结构

定义一个单词节点结构体，包含单词、出现次数、左右子树节点指针三个变量。定义一个二叉排序树结构体，包含根节点指针一个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
    struct word_node* left;
    struct word_node* right;
};

struct bst {
    struct word_node* root;
};

void bst_insert(struct bst* tree, char* word) {
    if (!tree->root) {
        tree->root = (struct word_node*) malloc(sizeof(struct word_node));
        strcpy(tree->root->word, word);
        tree->root->count = 1;
        tree->root->left = NULL;
        tree->root->right = NULL;
        return;
    }
    struct word_node* node = tree->root;
    while (1) {
        if (strcmp(node->word, word) == 0) {
            node->count++;
            return;
        } else if (strcmp(node->word, word) > 0) {
            if (node->left) {
                node = node->left;
            } else {
                node->left = (struct word_node*) malloc(sizeof(struct word_node));
                strcpy(node->left->word, word);
                node->left->count = 1;
                node->left->left = NULL;
                node->left->right = NULL;
                return;
            }
        } else {
            if (node->right) {
                node = node->right;
            } else {
                node->right = (struct word_node*) malloc(sizeof(struct word_node));
                strcpy(node->right->word, word);
                node->right->count = 1;
                node->right->left = NULL;
                node->right->right = NULL;
                return;
            }
        }
    }
}

void bst_traverse(struct word_node* node) {
    if (!node) {
        return;
    }
    bst_traverse(node->left);
    printf("%s: %d\n", node->word, node->count);
    bst_traverse(node->right);
}

int bst_search(struct word_node* node, char* word) {
    if (!node) {
        return 0;
    }
    if (strcmp(node->word, word) == 0) {
        return node->count;
    } else if (strcmp(node->word, word) > 0) {
        return bst_search(node->left, word);
    } else {
        return bst_search(node->right, word);
    }
}

## 哈希表存储结构

定义一个单词节点结构体，包含单词和出现次数两个变量。定义一个哈希表结构体，包含单词节点指针数组和当前单词节点数两个变量。实现单词词频统计和单词检索功能。

struct word_node {
    char word[20];
    int count;
};

struct hash_table {
    struct word_node* nodes[1000];
    int count;
};

struct hash_table hashTable;

unsigned int hash(char* str) {
    unsigned int hash = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        hash = hash * 31 + str[i];
    }
    return hash % 1000;
}

void hash_insert(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    while (node) {
        if (strcmp(node->word, word) == 0) {
            node->count++;
            return;
        }
        node = node->next;
    }
    struct word_node* newNode = (struct word_node*) malloc(sizeof(struct word_node));
    strcpy(newNode->word, word);
    newNode->count = 1;
    newNode->next = hashTable.nodes[index];
    hashTable.nodes[index] = newNode;
    hashTable.count++;
}

void hash_traverse() {
    for (int i = 0; i < 1000; i++) {
        struct word_node* node = hashTable.nodes[i];
        while (node) {
            printf("%s: %d\n", node->word, node->count);
            node = node->next;
        }
    }
}

int hash_search(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    while (node) {
        if (strcmp(node->word, word) == 0) {
            return node->count;
        }
        node = node->next;
    }
    return 0;
}

计算不同检索策略下的平均查找长度ASLC代码如下：

int linear_search(char* word) {
    for (int i = 0; i < wordList.count; i++) {
        if (strcmp(wordList.nodes[i].word, word) == 0) {
            return i + 1;
        }
    }
    return 0;
}

int bst_average_search_length(struct word_node* node, int depth) {
    if (!node) {
        return 0;
    }
    int leftDepth = bst_average_search_length(node->left, depth + 1);
    int rightDepth = bst_average_search_length(node->right, depth + 1);
    return depth + leftDepth + rightDepth;
}

int hash_average_search_length(char* word) {
    int index = hash(word);
    struct word_node* node = hashTable.nodes[index];
    int count = 0;
    while (node) {
        count++;
        if (strcmp(node->word, word) == 0) {
            return count;
        }
        node = node->next;
    }
    return 0;
}