c - 在链表中存储节点数组

Question

我在链表中​​存储节点数组时遇到问题，每个节点都包含一个固定大小的值数组。我的程序可以编译无错，但是没有输出，不知道为什么。这是我的节点和列表结构函数:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 20

typedef struct NODE Node;
struct NODE
{
char *bucket[SIZE]; 
int count;       
Node *next;
};

  Node *new_node()
{
   Node *curr=malloc(sizeof( Node ));
   curr->count=0;
   curr->next=NULL;
   return curr;
}

void add_node(Node *node,char *x)
{

    node->bucket[node->count] = (char *)malloc( strlen( x ) + 1 );
    strcpy(node->bucket[node->count],x);
    node->count++;
}
typedef struct LIST List;

struct LIST 
{
    Node *top;
};

List *construct() 
{
List *list;

list = malloc( sizeof( List ) );
list->top = NULL;

return list;
}
void insert( List *list, char *new_string )
{
 Node *newNode = new_node();
 Node *curr;

 curr = list->top;
if ( NULL == curr)
{
  curr=newNode;
}
add_node(newNode,new_string);

 }


void print( List *list )
{
  Node *curr = list->top;

  while ( NULL != curr ) 
  {
   for(int i=0;i<curr->count;i++)
   {
    printf( "%s\n", curr->bucket[i]);
   }
    curr = curr->next;
  }
} 

这是我的测试函数:

 int main(int argc, char const *argv[])
 {

   List *list=construct();
   char *ch="a";

   insert(list,ch);
   insert(list,ch);
   insert(list,ch);
   insert(list,ch);
   insert(list,ch);
   print(list);


   return 0;
  }

知道为什么这没有按预期运行吗？

Answer 1

主要问题是您的 insert() 函数。

void insert(List *list, char *new_string)
{
        Node *newNode = new_node();
        Node *curr;

        curr = list->top;
        if (NULL == curr) {
                /* OK. We set curr to newNode, but what happens to curr? */
                curr = newNode; 
        }
        /* String is added to newNode, but what happens to newNode? */
        add_node(newNode, new_string);
}

如果你改为说(你可能想要的):

if (list->top == NULL) {
    list->top = newNode;
}

您将保留第一个 newNode，但放开其余部分。

---

当谈到 add_node() 时，它没有直接的错误。最大的问题是您不检查 node->count 是否为 20。其次，它有一个非常糟糕的名称。命名函数时要小心，否则您的代码将变得很难阅读和维护。

add_node 不 添加节点。名称应该反射(reflect)它的作用。

例如你可以说:
insert 应命名为 add_node，add_node 应命名为 add_string、push_string >、bucket_fill 等。至少这样会好一些。

强制转换malloc也是多余的:

node->bucket[node->count] = (char*)malloc(strlen(str) + 1);

更好(恕我直言):

node->bucket[node->count] = malloc(strlen(str) + 1);

---

添加新节点的方法有很多种。一种方法是循环到最后并添加:

    while (node->next != NULL) {
            node = node->next;
    }
    node->next = new_node();
    bucket_fill(node->next, str);

如果你有一个单独的列表结构，你可以跟踪头部和尾部:

struct list {
    struct node *head;
    struct node *tail;
};

然后是这样的:

void node_add(struct list *list, char *str)
{
        struct node *new_node = node_create();

        bucket_fill(new_node, str);

        if (list->head != NULL) {
                list->tail->next = new_node;
                list->tail = new_node;
        } else {
                list->head = new_node;
                list->tail = new_node;
        }
}

等等等等。

---

查看每个步骤并尝试跟踪节点。

通常不会有struct list 和struct node，但两者都使用node。列表本质上是节点链中的第一个节点。

---

编写链表和一般 C 语言时真正有用的一件事是使用 Valgrind(至少在 Linux 等系统上)。为了使其更有用，您首先需要添加 free_list() 函数来释放内存。

当您使用 malloc 编写函数时，请务必编写一个 free 函数。

然后运行你的程序:

$ valgrind ./my_program

如果您使用 gcc 编译并使用 -ggdb 获取 Valgrind 输出的行号。

那么对您有用的两种情况是确保在退出时释放所有内存。这确保您不会遗漏代码中的任何内容。其次，当您访问未初始化的变量等时，您会收到警告。

---

作为初学者，有两件事要看:

1.) 无泄漏。 “退出时正在使用” 应为 0。

==13476== HEAP SUMMARY:
==13476==     in use at exit: 0 bytes in 0 blocks
==13476==   total heap usage: 43 allocs, 43 frees, 424 bytes allocated
==13476== 
==13476== All heap blocks were freed -- no leaks are possible

2.) 使用未初始化的值:

==12972== Conditional jump or move depends on uninitialised value(s)
==12972==    by 0x8048838: insert (foo.c:120)
==12972==    by 0x804890E: main (foo.c:151)
                                      |
                                      |
                                      +--- Shows file and line-number.

或者:

==12820== Use of uninitialised value of size 4
...

等等。

---

一个典型的免费函数可能是这样的:

void free_bucket(struct node *node)
{
        int i;

        for (i = 0; i < node->count; ++i) {
                free(node->bucket[i]);
        }
}

void free_list(struct node *head)
{
        struct node *tmp_node;

        while (head != NULL) {
                free_bucket(head);
                tmp_node = head;
                head = head->next;
                free(tmp_node);
        }
}