C++字符串数组存哈希表
时间: 2023-08-20 18:12:40 浏览: 55
引用[1]中提到了一种使用数组类型哈希表的方法来存储字符串数组。这种方法利用数组的简单和快捷的特点,将字符串中的每个字符出现的次数存入哈希表中。首先,取第一个字符串,读取其中的每一个字符出现次数,存入哈希表hash中,并以此为参照对象。然后,遍历剩余的字符串,创建另一个哈希表hashOther,记录剩余字符串中字符的出现频率。每次读取后,将其与第一个字符串形成的哈希表相比较,取两者中的最小值,实时更新hash哈希表。这样,最终的hash哈希表中存储了26个字符在所有字符串中出现的最小次数。[1][3]
相关问题
c++哈希表不用类实现怎么代码实现
哈希表的实现依赖于哈希函数的设计,下面是一个简单的示例,使用数组作为哈希表,不使用类的实现方式:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 1000
typedef struct entry {
char *key;
int value;
struct entry *next;
} Entry;
Entry *table[TABLE_SIZE] = { NULL };
unsigned int hash(const char *key) {
unsigned int hash = 0;
for (int i = 0; key[i] != '\0'; i++) {
hash = hash * 31 + key[i];
}
return hash % TABLE_SIZE;
}
void put(const char *key, int value) {
Entry *new_entry = (Entry *) malloc(sizeof(Entry));
new_entry->key = strdup(key);
new_entry->value = value;
unsigned int h = hash(key);
new_entry->next = table[h];
table[h] = new_entry;
}
int get(const char *key) {
unsigned int h = hash(key);
Entry *entry = table[h];
while (entry != NULL) {
if (strcmp(entry->key, key) == 0) {
return entry->value;
}
entry = entry->next;
}
return -1;
}
int main() {
put("apple", 1);
put("banana", 2);
put("cherry", 3);
printf("%d\n", get("apple"));
printf("%d\n", get("banana"));
printf("%d\n", get("cherry"));
return 0;
}
```
这里定义了一个`Entry`结构体,表示哈希表的每个元素,其中包含键(`key`)和值(`value`)。哈希表是一个`Entry`指针数组`table`,其中每个元素是一个指向`Entry`结构体的指针。
哈希函数`hash`使用了经典的字符串哈希函数,将字符串转化为一个哈希值,然后使用取模运算得到哈希表的下标。
`put`函数向哈希表中插入一个元素,首先使用`hash`函数计算出该元素的哈希值,然后创建一个新的`Entry`结构体,将键和值赋值给它,并且将该元素插入到哈希表的链表中,链表使用`next`指针实现。
`get`函数用于查找哈希表中的元素,首先根据键值计算出哈希值作为下标,然后遍历该位置的链表,查找键是否匹配,如果找到则返回对应的值。如果没有找到则返回-1。
上述代码仅仅是一个简单的实现,实际情况中还需要考虑冲突解决、扩容、删除等问题。
字符串去重 C++多种方法
除了使用哈希表和双指针的方法,还可以使用其他方法来实现字符串去重。下面介绍几种常见的方法:
1. 排序去重法
将字符串排序后,遍历字符串中的每个字符,如果该字符不等于前一个字符,则将该字符加入结果字符串中。这种方法的时间复杂度为 O(nlogn),空间复杂度为 O(n)。
代码如下:
```c++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string remove_duplicate_chars(string s) {
sort(s.begin(), s.end());
string result;
for (int i = 0; i < s.size(); i++) {
if (i == 0 || s[i] != s[i-1]) {
result += s[i];
}
}
return result;
}
int main() {
string s = "abcaabbcc";
string result = remove_duplicate_chars(s);
cout << result << endl; // 输出:abc
return 0;
}
```
2. 暴力枚举法
遍历字符串中的每个字符,判断该字符在字符串中是否重复出现,如果没有则将该字符加入结果字符串中。这种方法的时间复杂度为 O(n^2),空间复杂度为 O(n)。
代码如下:
```c++
#include <iostream>
#include <string>
using namespace std;
string remove_duplicate_chars(string s) {
string result;
for (int i = 0; i < s.size(); i++) {
bool found = false;
for (int j = 0; j < i; j++) {
if (s[j] == s[i]) {
found = true;
break;
}
}
if (!found) {
result += s[i];
}
}
return result;
}
int main() {
string s = "abcaabbcc";
string result = remove_duplicate_chars(s);
cout << result << endl; // 输出:abc
return 0;
}
```
3. 位图法
使用一个长度为 256 的布尔型数组,将字符串中每个字符的 ASCII 码作为数组下标,并将对应的数组元素置为 true。这种方法的时间复杂度为 O(n),空间复杂度为 O(1)。
代码如下:
```c++
#include <iostream>
#include <string>
using namespace std;
string remove_duplicate_chars(string s) {
bool bitmap[256] = {false};
string result;
for (int i = 0; i < s.size(); i++) {
int index = (int)s[i];
if (!bitmap[index]) {
bitmap[index] = true;
result += s[i];
}
}
return result;
}
int main() {
string s = "abcaabbcc";
string result = remove_duplicate_chars(s);
cout << result << endl; // 输出:abc
return 0;
}
```
需要注意的是,这种方法只能处理 ASCII 码范围内的字符,无法处理 Unicode 码。