我无法在C中创建链接列表

Question

基本上，对于我的任务，我需要实现代码来进行霍夫曼编码。为此，我需要将输入作为字符串，然后创建一个字符及其频率列表。当有一个新角色时，我需要创建一个新节点。我试过用C来做，但没有结果。当我尝试打印我的链接列表时，我根本无法获得任何输出。我相信我从一开始就没能创建这个列表。我的C代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct node {
char character;
int frequency;
struct node *next;
}head;
struct node *insert(int frequency, char character) {
struct node *newNode = malloc(sizeof(struct node));
newNode->character = frequency;
newNode->character = character;
return newNode;
}
void create_freq_list(struct node *initial, int str_size, char str[]) {
int i;
struct node *temp;
bool has_node;
for (i = 0; i < str_size; i++) {
temp = initial;
has_node = false;
while (temp->next != NULL) {
if (temp->character == str[i]) {
has_node = true;
temp->frequency++;
}
temp = temp->next;
}
if (has_node == false) {
while (temp->next != NULL) {
temp = temp->next;
if (temp->next == NULL) {
temp->next = insert(0, str[i]);
}
}
}
}
}
int main() {
struct node *temp;
char str[100];
gets_s(str, 100);
create_freq_list(&head, 100, str);
temp = &head;
while (temp->next != NULL) {
printf("'%c' : %d", temp->character, temp->frequency);
temp = temp->next;
}
getch();
exit(0);
}

Answer 1

您的代码中存在多个问题：

• 您对head节点的处理不正确：head应定义为node *，并且应将其地址传递给create_freq_list()
• insert()函数中有一个拼写错误：newNode->character = frequency;
• 您不应该对字符串中超过null终止符的字符进行迭代
• 输出循环不正确：它应该迭代while (head)，而不是while (head->next)。编码后，初始节点被输出，但没有意义，最后一个节点被忽略

这是一个修改后的版本：

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char character;
int frequency;
struct node *next;
};
struct node *insert(int frequency, char character) {
struct node *newNode = malloc(sizeof(struct node));
if (newNode != NULL) {
newNode->frequency = frequency;
newNode->character = character;
}
return newNode;
}
void create_freq_list(struct node **headp, const char str[]) {
for (int i = 0; str[i]; i++) {
struct node **tailp = *headp;
struct node *temp;
while ((temp = *tailp) != NULL) {
if (temp->character == str[i]) {
temp->frequency++;
break;
}
tailp = &temp->next;
}
if (temp == NULL) {
*tailp = insert(1, str[i]);
}
}
}
int main() {
struct node *head = NULL;
char str[100];
gets_s(str, 100);
create_freq_list(&head, str);
for (struct node *temp = head; temp != NULL; temp = temp->next) {
printf("'%c': %dn", temp->character, temp->frequency);
}
getch();
return 0;
}

请注意，使用具有256个元素的数组来计算字符频率要简单得多。

Answer 2

我可以提出一个变体，使用优秀的<sys/queue.h>的宏吗这不是一个标准的include，但每个封装良好的系统都应该有它。好吧，它可能不如手工编码链表那样具有教学意义，但它更安全；-(查看man queue(或man LIST_INIT(以查看功能。

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/queue.h>
typedef LIST_HEAD(listhead, entry) nodes_t;
typedef struct entry {
char character;
int frequency;
LIST_ENTRY(entry) entries;
} node_t;

void insert(nodes_t *list, char character) {
node_t *newNode = malloc(sizeof(node_t));
if (newNode != NULL) {
newNode->frequency = 1;
newNode->character = character;
LIST_INSERT_HEAD(list, newNode, entries);
}
}
node_t *get_node(nodes_t *list, char character) {
node_t *n;
LIST_FOREACH(n, list, entries)
if (n->character == character)
return n;
return NULL;
}
void create_freq_list(nodes_t *list, const char str[]) {
node_t *n;
for (int i = 0; str[i]; i++) {
n = get_node(list, str[i]);
if (n == NULL)
insert(list, str[i]);
else
n->frequency++;
}
}
void print_list(nodes_t *list) {
node_t *n;
LIST_FOREACH(n, list, entries)
printf("'%c': %dn", n->character, n->frequency);
}

int main(int argc, char* argv[]) {
nodes_t list;
if (argc != 2) {
fprintf(stderr, "Usage: %s <string>n", argv[0]);
return -1;
}

LIST_INIT(&list);

create_freq_list(&list, argv[1]);
print_list(&list);

return 0;
}