C语言如何统计数组中每个元素出现的次数

创作时间:

作者:

@小白创作中心

C语言如何统计数组中每个元素出现的次数

引用

来源

https://docs.pingcode.com/baike/1286738

在C语言中，统计数组中每个元素出现的次数的核心方法包括：使用嵌套循环、使用哈希表、利用排序与计数。这些方法各有优缺点，适用于不同的场景。其中，利用哈希表的方法在效率和易用性上有明显的优势。

一、使用嵌套循环统计数组中每个元素出现的次数

1. 嵌套循环方法简介

嵌套循环是一种较为直观但效率较低的方法，尤其在数组较大时。它的基本思想是通过两个循环，逐个比较数组中的元素，并记录每个元素出现的次数。

2. 嵌套循环的实现步骤

首先，创建一个数组存储每个元素出现的次数；然后，使用两个嵌套循环遍历原数组，并在内层循环中更新计数数组。

#include <stdio.h>

void countOccurrences(int arr[], int size) {  
    int count[size];  
    for(int i = 0; i < size; i++) {  
        count[i] = -1; // 初始化计数数组  
    }  
    for(int i = 0; i < size; i++) {  
        int counter = 1;  
        for(int j = i + 1; j < size; j++) {  
            if(arr[i] == arr[j]) {  
                counter++;  
                count[j] = 0; // 标记已统计  
            }  
        }  
        if(count[i] != 0) {  
            count[i] = counter;  
        }  
    }  
    for(int i = 0; i < size; i++) {  
        if(count[i] != 0) {  
            printf("%d occurs %d times\n", arr[i], count[i]);  
        }  
    }  
}  

int main() {  
    int arr[] = {1, 2, 3, 2, 1, 3, 1, 1};  
    int size = sizeof(arr) / sizeof(arr[0]);  
    countOccurrences(arr, size);  
    return 0;  
}

二、使用哈希表统计数组中每个元素出现的次数

1. 哈希表方法简介

哈希表是一种高效的数据结构，能够在平均O(1)时间复杂度内完成插入和查找操作。使用哈希表可以显著提高统计数组中每个元素出现次数的效率。

2. 哈希表的实现步骤

使用一个哈希表来存储每个元素及其出现的次数。遍历数组并更新哈希表中的对应计数。

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

#define TABLE_SIZE 128  

typedef struct HashNode {  
    int key;  
    int value;  
    struct HashNode* next;  
} HashNode;  

typedef struct HashTable {  
    HashNode* table[TABLE_SIZE];  
} HashTable;  

unsigned int hash(int key) {  
    return key % TABLE_SIZE;  
}  

HashTable* createTable() {  
    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));  
    for (int i = 0; i < TABLE_SIZE; i++) {  
        hashTable->table[i] = NULL;  
    }  
    return hashTable;  
}  

void insert(HashTable* hashTable, int key) {  
    unsigned int index = hash(key);  
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));  
    newNode->key = key;  
    newNode->value = 1;  
    newNode->next = hashTable->table[index];  
    hashTable->table[index] = newNode;  
}  

void update(HashTable* hashTable, int key) {  
    unsigned int index = hash(key);  
    HashNode* temp = hashTable->table[index];  
    while (temp != NULL) {  
        if (temp->key == key) {  
            temp->value++;  
            return;  
        }  
        temp = temp->next;  
    }  
    insert(hashTable, key);  
}  

void countOccurrences(int arr[], int size) {  
    HashTable* hashTable = createTable();  
    for (int i = 0; i < size; i++) {  
        update(hashTable, arr[i]);  
    }  
    for (int i = 0; i < TABLE_SIZE; i++) {  
        HashNode* temp = hashTable->table[i];  
        while (temp != NULL) {  
            printf("%d occurs %d times\n", temp->key, temp->value);  
            temp = temp->next;  
        }  
    }  
}  

int main() {  
    int arr[] = {1, 2, 3, 2, 1, 3, 1, 1};  
    int size = sizeof(arr) / sizeof(arr[0]);  
    countOccurrences(arr, size);  
    return 0;  
}

三、利用排序与计数统计数组中每个元素出现的次数

1. 排序与计数方法简介

通过先对数组进行排序，然后遍历排序后的数组统计每个元素的出现次数。这种方法的效率取决于排序算法。

2. 排序与计数的实现步骤

首先对数组进行排序，然后遍历排序后的数组，统计每个元素的出现次数并输出。

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

// 比较函数用于qsort  
int compare(const void* a, const void* b) {  
    return (*(int*)a - *(int*)b);  
}  

void countOccurrences(int arr[], int size) {  
    qsort(arr, size, sizeof(int), compare);  
    int count = 1;  
    for(int i = 1; i < size; i++) {  
        if(arr[i] == arr[i - 1]) {  
            count++;  
        } else {  
            printf("%d occurs %d times\n", arr[i - 1], count);  
            count = 1;  
        }  
    }  
    printf("%d occurs %d times\n", arr[size - 1], count); // 打印最后一个元素的计数  
}  

int main() {  
    int arr[] = {1, 2, 3, 2, 1, 3, 1, 1};  
    int size = sizeof(arr) / sizeof(arr[0]);  
    countOccurrences(arr, size);  
    return 0;  
}