如何统计单链表中Rank[4]数组重复的人数？

给定如下C语言单链表节点结构体，每个节点对应一名人员：

struct node
{
  int value;
  int Rank[4];
  struct node *next;
};

需求是统计所有Rank[4]数组完全相同的重复人员数量——即只要两个节点的Rank数组四个元素完全一致，就算作重复，需要把这类重复的人员总数统计出来。

实现思路 #

核心是通过记录每个Rank组合的出现次数，再基于次数计算重复总数：

• 遍历整个单链表，对每个节点的Rank数组生成唯一标识（比如拼接成格式化字符串，或者计算哈希值）
• 用哈希表（键值对结构）存储每个Rank标识对应的出现次数
• 遍历完链表后，遍历哈希表：对于每个出现次数count，若count > 1，则该Rank组合贡献count - 1个重复人员（第一个为基准，后续均为重复项）
• 累加所有这类贡献值，得到最终的重复总数

C语言实现示例 #

下面是基于字符串作为哈希键的实现（仅依赖标准库）：

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

// 哈希表节点定义
typedef struct HashNode {
    char key[32]; // 存储Rank拼接后的字符串，如"1,2,3,4"
    int count;
    struct HashNode *next;
} HashNode;

// 创建新哈希表节点
HashNode* create_hash_node(const char *key) {
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    strcpy(node->key, key);
    node->count = 1;
    node->next = NULL;
    return node;
}

// 简单哈希函数：基于字符串计算哈希值
unsigned int hash(const char *key) {
    unsigned int hash_val = 0;
    while (*key) {
        hash_val = hash_val * 31 + *key++;
    }
    return hash_val % 100; // 哈希表大小设为100，可按需调整
}

// 更新哈希表：存在则计数+1，不存在则插入新节点
void update_hash_table(HashNode **table, const char *key) {
    unsigned int idx = hash(key);
    HashNode *curr = table[idx];
    while (curr) {
        if (strcmp(curr->key, key) == 0) {
            curr->count++;
            return;
        }
        curr = curr->next;
    }
    HashNode *new_node = create_hash_node(key);
    new_node->next = table[idx];
    table[idx] = new_node;
}

// 统计重复人员总数
int count_duplicate_ranks(struct node *head) {
    HashNode *hash_table[100] = {NULL}; // 初始化哈希表
    char key_buf[32];
    struct node *curr = head;
    
    // 遍历链表更新哈希表
    while (curr) {
        snprintf(key_buf, sizeof(key_buf), "%d,%d,%d,%d", 
                 curr->Rank[0], curr->Rank[1], curr->Rank[2], curr->Rank[3]);
        update_hash_table(hash_table, key_buf);
        curr = curr->next;
    }
    
    // 计算重复总数并释放哈希表内存
    int total_duplicates = 0;
    for (int i = 0; i < 100; i++) {
        HashNode *curr_hash = hash_table[i];
        while (curr_hash) {
            if (curr_hash->count > 1) {
                total_duplicates += (curr_hash->count - 1);
            }
            HashNode *temp = curr_hash;
            curr_hash = curr_hash->next;
            free(temp);
        }
    }
    return total_duplicates;
}

// 测试用例
int main() {
    // 构建测试链表
    struct node *n1 = (struct node*)malloc(sizeof(struct node));
    struct node *n2 = (struct node*)malloc(sizeof(struct node));
    struct node *n3 = (struct node*)malloc(sizeof(struct node));
    struct node *n4 = (struct node*)malloc(sizeof(struct node));
    
    n1->Rank[0] = 1; n1->Rank[1] = 2; n1->Rank[2] = 3; n1->Rank[3] = 4;
    n2->Rank[0] = 1; n2->Rank[1] = 2; n2->Rank[2] = 3; n2->Rank[3] = 4;
    n3->Rank[0] = 5; n3->Rank[1] = 6; n3->Rank[2] = 7; n3->Rank[3] = 8;
    n4->Rank[0] = 1; n4->Rank[1] = 2; n4->Rank[2] = 3; n4->Rank[3] = 4;
    
    n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL;
    
    int duplicates = count_duplicate_ranks(n1);
    printf("重复人员总数：%d\n", duplicates); // 预期输出2
    
    // 释放链表内存
    struct node *temp;
    while (n1) {
        temp = n1;
        n1 = n1->next;
        free(temp);
    }
    return 0;
}

补充说明 #

• 哈希表大小可根据实际数据量调整，避免哈希冲突过多影响效率
• 若Rank数组元素范围固定，可采用更高效的哈希方式（比如将四个int组合为64位整数作为键），减少字符串处理开销
• 代码包含完整的内存释放逻辑，避免内存泄漏

内容的提问来源于stack exchange，提问作者Figi