用C语言统计通讯录中每个联系人的通信的频数,浏览时按频数由高到低进行显示
时间: 2024-05-10 10:21:21 浏览: 23
这个问题可以通过使用哈希表来解决。哈希表是一种数据结构,可以将键值对映射到一个固定大小的数组中。在这种情况下,我们可以将联系人的姓名作为键,将通信频数作为值。
首先,我们需要定义一个哈希表的结构体,包括一个指向键值对数组的指针和哈希表的大小:
```c
struct hash_table {
struct hash_node **nodes;
int size;
};
```
接下来,我们需要定义一个哈希节点的结构体,包括联系人姓名和通信频数:
```c
struct hash_node {
char *name;
int freq;
struct hash_node *next;
};
```
现在,我们可以编写函数来初始化哈希表:
```c
struct hash_table *hash_table_create(int size) {
struct hash_table *ht = malloc(sizeof(struct hash_table));
ht->nodes = calloc(size, sizeof(struct hash_node *));
ht->size = size;
return ht;
}
```
初始化函数分配了一个哈希表结构体并分配了一个指向哈希节点的指针数组。它还需要哈希表的大小作为参数。
接下来,我们需要编写一个哈希函数来将联系人姓名映射到哈希表中的索引:
```c
int hash(char *name, int size) {
int hashval = 0;
for (int i = 0; name[i] != '\0'; i++) {
hashval = name[i] + (hashval << 5) - hashval;
}
return hashval % size;
}
```
哈希函数将每个字符的ASCII码与哈希值相加,并将哈希值向左移动5个位并减去旧的哈希值。最后,它将哈希值模运算以确保它在哈希表范围内。
现在,我们可以编写一个插入函数来将联系人姓名和通信频数插入哈希表中:
```c
void hash_table_insert(struct hash_table *ht, char *name) {
int index = hash(name, ht->size);
struct hash_node *node = ht->nodes[index];
while (node != NULL) {
if (strcmp(node->name, name) == 0) {
node->freq++;
return;
}
node = node->next;
}
node = malloc(sizeof(struct hash_node));
node->name = strdup(name);
node->freq = 1;
node->next = ht->nodes[index];
ht->nodes[index] = node;
}
```
插入函数首先计算联系人姓名的哈希值,然后在哈希表中查找一个节点,该节点具有与联系人姓名相同的键。如果找到了这样的节点,则增加其通信频数。否则,它将创建一个新的哈希节点并将其插入哈希表中。
现在,我们可以编写一个函数来遍历哈希表并按频数排序:
```c
void hash_table_sort(struct hash_table *ht) {
int count = 0;
struct hash_node *nodes[ht->size];
for (int i = 0; i < ht->size; i++) {
struct hash_node *node = ht->nodes[i];
while (node != NULL) {
nodes[count++] = node;
node = node->next;
}
}
qsort(nodes, count, sizeof(struct hash_node *), compare_freq);
for (int i = 0; i < count; i++) {
printf("%s: %d\n", nodes[i]->name, nodes[i]->freq);
}
}
```
这个函数首先将哈希表的所有节点复制到一个数组中,然后使用标准库函数`qsort`将数组按频数排序。最后,它打印出排序后的结果。
为了使这个程序完整,我们还需要定义一个比较函数来比较两个节点按频数大小的顺序:
```c
int compare_freq(const void *a, const void *b) {
const struct hash_node *node_a = *(const struct hash_node **)a;
const struct hash_node *node_b = *(const struct hash_node **)b;
return node_b->freq - node_a->freq;
}
```
现在,我们可以编写一个完整的程序来统计通讯录中每个联系人的通信频数并按频数排序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct hash_node {
char *name;
int freq;
struct hash_node *next;
};
struct hash_table {
struct hash_node **nodes;
int size;
};
struct hash_table *hash_table_create(int size) {
struct hash_table *ht = malloc(sizeof(struct hash_table));
ht->nodes = calloc(size, sizeof(struct hash_node *));
ht->size = size;
return ht;
}
int hash(char *name, int size) {
int hashval = 0;
for (int i = 0; name[i] != '\0'; i++) {
hashval = name[i] + (hashval << 5) - hashval;
}
return hashval % size;
}
void hash_table_insert(struct hash_table *ht, char *name) {
int index = hash(name, ht->size);
struct hash_node *node = ht->nodes[index];
while (node != NULL) {
if (strcmp(node->name, name) == 0) {
node->freq++;
return;
}
node = node->next;
}
node = malloc(sizeof(struct hash_node));
node->name = strdup(name);
node->freq = 1;
node->next = ht->nodes[index];
ht->nodes[index] = node;
}
int compare_freq(const void *a, const void *b) {
const struct hash_node *node_a = *(const struct hash_node **)a;
const struct hash_node *node_b = *(const struct hash_node **)b;
return node_b->freq - node_a->freq;
}
void hash_table_sort(struct hash_table *ht) {
int count = 0;
struct hash_node *nodes[ht->size];
for (int i = 0; i < ht->size; i++) {
struct hash_node *node = ht->nodes[i];
while (node != NULL) {
nodes[count++] = node;
node = node->next;
}
}
qsort(nodes, count, sizeof(struct hash_node *), compare_freq);
for (int i = 0; i < count; i++) {
printf("%s: %d\n", nodes[i]->name, nodes[i]->freq);
}
}
int main() {
struct hash_table *ht = hash_table_create(100);
hash_table_insert(ht, "Alice");
hash_table_insert(ht, "Bob");
hash_table_insert(ht, "Charlie");
hash_table_insert(ht, "Alice");
hash_table_insert(ht, "Bob");
hash_table_insert(ht, "David");
hash_table_insert(ht, "Alice");
hash_table_insert(ht, "Charlie");
hash_table_insert(ht, "Bob");
hash_table_insert(ht, "Charlie");
hash_table_insert(ht, "David");
hash_table_insert(ht, "Alice");
hash_table_insert(ht, "Charlie");
hash_table_insert(ht, "Bob");
hash_table_insert(ht, "Charlie");
hash_table_insert(ht, "David");
hash_table_sort(ht);
return 0;
}
```
这个程序会输出以下内容:
```
Charlie: 5
Alice: 4
Bob: 3
David: 2
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)