C语言高效查找并输出重复字符的多种方法119

在C语言编程中，经常会遇到需要查找和输出字符串或数组中重复字符的问题。这个问题看似简单，但其解决方案的效率和优雅程度却体现了程序员的编程功底。本文将深入探讨几种不同的方法来解决这个问题，并对它们的优缺点进行比较，最终提供一种高效且易于理解的实现。

方法一：暴力枚举法

最直观的方法是使用嵌套循环进行暴力枚举。外层循环遍历字符串中的每个字符，内层循环比较该字符与后续字符是否相同。如果相同，则表示找到一个重复字符。这种方法虽然简单易懂，但效率较低，时间复杂度为O(n^2)，其中n是字符串的长度。对于大型字符串，其性能会急剧下降。

代码示例：```c
#include
#include
void find_duplicate_chars_bruteforce(const char *str) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (str[i] == str[j]) {
printf("重复字符: %c", str[i]);
break; // 避免输出同一个字符多次
}
}
}
}
int main() {
char str[] = "programming";
find_duplicate_chars_bruteforce(str);
return 0;
}
```

方法二：使用辅助数组计数

为了提高效率，我们可以使用一个辅助数组来记录每个字符出现的次数。假设只考虑ASCII字符，我们可以创建一个大小为256的整数数组，每个元素对应一个ASCII字符。遍历字符串，对于每个字符，将其对应的数组元素加1。最后，遍历辅助数组，找出计数大于1的字符，即为重复字符。

代码示例：```c
#include
#include
void find_duplicate_chars_counting(const char *str) {
int count[256] = {0};
int len = strlen(str);
for (int i = 0; i < len; i++) {
count[str[i]]++;
}
for (int i = 0; i < 256; i++) {
if (count[i] > 1) {
printf("重复字符: %c (出现次数: %d)", i, count[i]);
}
}
}
int main() {
char str[] = "programming";
find_duplicate_chars_counting(str);
return 0;
}
```

这种方法的时间复杂度为O(n)，其中n是字符串的长度，效率比暴力枚举法高得多。但是，它需要额外的空间来存储辅助数组，空间复杂度为O(1)。如果字符集很大(例如Unicode)，则需要更大的辅助数组，空间消耗会增加。

方法三：使用哈希表(适用于大字符集)

对于包含Unicode字符等大字符集的字符串，使用辅助数组会造成空间浪费。此时，可以使用哈希表来存储字符及其计数。哈希表能够高效地查找和插入元素，其平均时间复杂度为O(1)。

由于C语言标准库没有内置的哈希表实现，我们可以使用第三方库或者自己实现一个简单的哈希表。以下代码使用一个简单的哈希表实现，只适用于较小的字符集。```c
#include
#include
#include
#define TABLE_SIZE 256
typedef struct {
char key;
int count;
} HashEntry;
typedef struct {
HashEntry *table;
int size;
} HashTable;
HashTable *createHashTable() {
HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
ht->table = (HashEntry *)calloc(TABLE_SIZE, sizeof(HashEntry));
ht->size = TABLE_SIZE;
return ht;
}
int hash(char key) {
return key % TABLE_SIZE;
}
void insert(HashTable *ht, char key) {
int index = hash(key);
if (ht->table[index].key == '\0') {
ht->table[index].key = key;
ht->table[index].count = 1;
} else if (ht->table[index].key == key) {
ht->table[index].count++;
}
}

void find_duplicate_chars_hash(const char *str) {
HashTable *ht = createHashTable();
int len = strlen(str);
for (int i = 0; i < len; i++) {
insert(ht, str[i]);
}
for (int i = 0; i < ht->size; i++) {
if (ht->table[i].count > 1) {
printf("重复字符: %c (出现次数: %d)", ht->table[i].key, ht->table[i].count);
}
}
free(ht->table);
free(ht);
}
int main() {
char str[] = "programming";
find_duplicate_chars_hash(str);
return 0;
}
```