C程序查找数组中常见元素

下面是查找数组中常见元素的使用攻略：

1. 程序介绍

本程序的功能是，在一个给定的整型数组中，查找出出现次数最多的若干个元素。

2. 环境要求

本程序使用 C 语言编写，需要在计算机上安装 C 编译器才能运行。常用的 C 编译器有 GCC、Clang、Visual Studio 等。此外，程序需要在控制台（命令行）下运行。

3. 程序结构

程序的主要流程分为以下几个步骤：

读入数组；
统计元素个数；
找出出现次数最多的若干个元素；
输出结果。

4. 读入数组

程序首先需要读入一个整型数组。数组的大小可以在程序中定义，也可以从用户处输入。下面是一个例子：

// 定义数组大小
#define MAX_SIZE 100

// 读入数组
int arr[MAX_SIZE];
int n; // 数组实际大小
printf("请输入数组大小（不超过 %d）：", MAX_SIZE);
scanf("%d", &n);
printf("请输入数组元素：");
for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
}

5. 统计元素个数

程序需要统计每个元素在数组中出现的次数。可以使用一个哈希表（或桶）来存储每个元素以及对应的出现次数。下面是一个例子：

// 哈希表（桶）
#define HASH_SIZE 100000
int hash[HASH_SIZE] = {0};

// 统计元素个数
for (int i = 0; i < n; i++) {
    int key = arr[i];
    hash[key]++;
}

6. 找出出现次数最多的若干个元素

程序需要找到出现次数最多的若干个元素。可以使用一个最小堆来存储出现次数最多的元素。具体实现是，遍历哈希表，将元素和对应的出现次数添加到最小堆中。如果最小堆的大小超过需要输出的元素个数，就弹出堆顶元素。最后最小堆中剩余的元素就是出现次数最多的若干个元素。下面是一个例子：

// 最小堆
typedef struct {
    int key;
    int value;
} HeapNode;
#define HEAP_SIZE 100
HeapNode heap[HEAP_SIZE];
int heapSize = 0;

// 添加元素到最小堆中
void addToHeap(int key, int value) {
    if (heapSize < HEAP_SIZE) {
        heap[heapSize].key = key;
        heap[heapSize].value = value;
        heapSize++;
        // 维护堆结构
        int i = heapSize - 1;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p].value > heap[i].value) {
                // 交换节点
                HeapNode tmp = heap[p];
                heap[p] = heap[i];
                heap[i] = tmp;
                i = p;
            } else {
                break;
            }
        }
    } else if (value > heap[0].value) {
        // 比堆顶元素大，替换掉堆顶元素
        heap[0].key = key;
        heap[0].value = value;
        // 维护堆结构
        int i = 0;
        while (i < heapSize) {
            int l = i * 2 + 1;
            int r = i * 2 + 2;
            int min = i;
            if (l < heapSize && heap[l].value < heap[min].value) {
                min = l;
            }
            if (r < heapSize && heap[r].value < heap[min].value) {
                min = r;
            }
            if (min != i) {
                // 交换节点
                HeapNode tmp = heap[i];
                heap[i] = heap[min];
                heap[min] = tmp;
                i = min;
            } else {
                break;
            }
        }
    }
}

// 遍历哈希表，添加元素到最小堆中
void traverseHash() {
    for (int i = 0; i < HASH_SIZE; i++) {
        if (hash[i] > 0) {
            addToHeap(i, hash[i]);
        }
    }
}

7. 输出结果

程序最后需要输出出现次数最多的若干个元素以及它们在数组中的位置。下面是一个例子：

// 输出结果
printf("出现次数最多的元素：\n");
while (heapSize > 0) {
    HeapNode node = heap[0];
    printf("%d(%d次)：", node.key, node.value);
    for (int i = 0; i < n; i++) {
        if (arr[i] == node.key) {
            printf("%d ", i);
        }
    }
    printf("\n");
    // 弹出堆顶元素
    heapSize--;
    if (heapSize > 0) {
        heap[0] = heap[heapSize];
        // 维护堆结构
        int i = 0;
        while (i < heapSize) {
            int l = i * 2 + 1;
            int r = i * 2 + 2;
            int min = i;
            if (l < heapSize && heap[l].value < heap[min].value) {
                min = l;
            }
            if (r < heapSize && heap[r].value < heap[min].value) {
                min = r;
            }
            if (min != i) {
                // 交换节点
                HeapNode tmp = heap[i];
                heap[i] = heap[min];
                heap[min] = tmp;
                i = min;
            } else {
                break;
            }
        }
    }
}

8. 示例说明

下面是两个示例说明，展示程序如何使用。

示例 1

假设我们要查找以下数组中出现次数最多的元素：

3, 2, 4, 1, 5, 5, 5, 5, 1, 2, 2, 1, 1, 4, 5, 6, 2, 3

我们可以使用如下代码运行程序：

// 读入数组
int arr[] = {3, 2, 4, 1, 5, 5, 5, 5, 1, 2, 2, 1, 1, 4, 5, 6, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);

// 统计元素个数
for (int i = 0; i < n; i++) {
    int key = arr[i];
    hash[key]++;
}

// 找出出现次数最多的若干个元素
traverseHash();

// 输出结果
// 出现次数最多的元素：
// 1(5次)：3 8 11 12 13 
// 2(4次)：1 9 10 16 
// 5(4次)：4 5 6 7 
// 4(2次)：2 14 
// 3(2次)：0 17 
// 6(1次)：15

程序输出了出现次数最多的若干个元素以及它们在数组中的位置。

示例 2

假设我们要查找用户输入的数组中出现次数最多的元素，我们可以使用如下代码：

// 读入数组
#define MAX_SIZE 100
int arr[MAX_SIZE];
int n;
printf("请输入数组大小（不超过 %d）：", MAX_SIZE);
scanf("%d", &n);
printf("请输入数组元素：");
for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
}

// 统计元素个数
for (int i = 0; i < n; i++) {
    int key = arr[i];
    hash[key]++;
}

// 找出出现次数最多的若干个元素
traverseHash();

// 输出结果
// 出现次数最多的元素：
// ...

程序会提示用户输入数组的大小以及元素，然后输出出现次数最多的若干个元素以及它们在数组中的位置。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C程序查找数组中常见元素 - Python技术站

C程序 查找数组中常见元素