c语言哈希表字典序排序
C语言哈希表字典序排序
哈希表是一种以键值对（key-value）方式存储数据的数据结构，通过
将键值映射成数组下标，从而快速地查找对应的值。
哈希表的查找效
率非常高，可以达到O(1)，而不受数据量变化的影响。
然而，哈希表
在显示其优越性时，也面临着排序的问题。
排序是数据处理中一个非常重要的问题，常见的排序方法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。
这些排序方法，可以
对于数组和链表这样的线性数据结构排序。
对于哈希表这样的非线性
数据结构，如何进行排序呢？下面，我们将介绍如何使用哈希表来实
现字典序排序。
1.哈希表实现字典序排序
哈希表实现字典序排序，主要有两种方法：一种是使用桶排的思想，
另一种是使用STL库函数。
下面，我们将依次讲解。
1.1.桶排思想
桶排思想是对数据分治，将数据划分为若干个桶，每个桶存储一定范
围的数据。
通常，划分的依据有多种，比如元素的大小、元素的个位数、十位数等。
对于实现字典序排序，我们可以使用元素的首字母作为桶排的依据。
具体实现过程如下：
（1）初始化一个哈希表，键是元素的首字母，值是指向一个存储该首字母的所有元素的列表的指针。
（2）遍历待排序的元素列表，将每个元素根据其首字母分别存储在对应的哈希表中。
（3）遍历哈希表，对于每个键值对，将其对应的元素列表按照字典序排序。
（4）遍历哈希表，按照键的字典序输出元素。
下面是代码实现：
```
struct node {
char *s;
node *next;
};
int hash(char *s) {
return s[0] - 'a';
node *bucket[26];
void sort() {
for (int i = 0; i < 26; i++) {
node *p = bucket[i];
while (p) {
node *q = p->next;
while (q) {
if (strcmp(p->s, q->s) > 0) { char *t = p->s;
p->s = q->s;
q->s = t;
}
q = q->next;
}
p = p->next;
}
}
}
void output() {
for (int i = 0; i < 26; i++) {
node *p = bucket[i];
while (p) {
printf("%s ", p->s);
p = p->next;
}
}
printf("\n");
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char *s = (char *) malloc(101);
scanf("%s", s);
int h = hash(s);
node *p = (node *) malloc(sizeof(node)); p->s = s;
p->next = bucket[h];
bucket[h] = p;
}
sort();
output();
return 0;
}
```
1.2.STL库函数
使用STL库函数是一种更加简单的方法，只需要使用哈希表和vector 即可。
具体实现过程如下：
（1）初始化一个哈希表，键是元素的首字母，值是一个vector。
（2）遍历待排序的元素列表，将每个元素根据其首字母分别存储在对应的哈希表中。
（3）遍历哈希表，对于每个键值对，对其对应的vector进行排序。
（4）遍历哈希表，按照键的字典序输出元素。
下面是代码实现：
```
int hash(string s) {
return s[0] - 'a';
}
unordered_map<int, vector<string>> hash_table;
void sort() {
for (auto &p: hash_table) {
sort(p.second.begin(), p.second.end());
}
}
void output() {
for (auto &p: hash_table) {
for (auto s: p.second) {
cout << s << " ";
}
}
cout << endl;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int h = hash(s);
hash_table[h].push_back(s); }
sort();
output();
return 0;
}
```
2.总结
本文介绍了如何使用哈希表来实现字典序排序。
哈希表实现字典序排序，主要有两种方法：一种是使用桶排的思想，另一种是使用STL库函数。
使用哈希表实现字典序排序，可以大大提高排序的效率，让我们在处理较大数据时更加便捷。