c - 从带有输出的输入文件创建C链表

Question

您好，我正在C中创建一个链接列表，以打印从名为dict.txt的文本文件中给定的唯一标记。我是C的新手，不确定如何正确地从文件中读取每个单词，将其存储到节点中，然后打印生成的链接列表。下面是我的以下方法，我在add方法中省略了contains方法或其实现。我还不关心这个部分，只想打印给定文本文件中的每个单词。

struct Node{

        char *data;
        struct Node *next;
}

typedef struct Node *node;

Node createNode(){
        Node new;
        new = (Node)malloc(sizeof(struct Node));
        *new.next = NULL;
        return new;
}

void add(Node head, char data){     
        Node temp,p;
        temp = createNode();
        *temp.data = data;
        if(head == NULL) head == temp;
        else{
        p = head;
        while(*p.next != NULL) {
        //TODO contains method to catch duplicates
        p = *p.next;
        }
        *p.next = temp;
        }
        return head;
        }
int main(){
        File *filep;
        filep = fopen("dict.txt", "r");
        Node head = NULL;

        while(fscanf(filep, "%s", word) != EOF){
        int i = 0;
        if (i == 0) Node parent = add(head, word); //add the first word
        else{
        //how should I add the other nodes?
        }
        i++
}

我正在努力添加while循环中给定前一个节点的节点。有什么建议吗？我的实现是否不正确？如果更适合链表数据结构，我愿意改变我的方法。谢谢

Answer 1

首先，让我们从基础知识开始，您必须将word读入一个有效的缓冲区，因此声明一个足够大的缓冲区来保存您的单词（未桥接词典（非医学词典）中最长的单词是29个字符）。不要使用幻数，所以声明一个足够大的常数来创建具有自动存储的缓冲区（不要略过！在缓冲区大小上），例如。

#define MAXC 1024u  /* if you need a constant, define one (or more) */
...
int main (int argc, char **argv) {

    char word[MAXC];        /* buffer to hold each word */

注意使用 main()的形式为程序提供参数。使用它们！不要硬编码文件名——这就是参数的用途。只需将文件名作为第一个参数传递给程序，并验证是否至少有两个参数（第一个参数始终是程序名），例如。

    if (argc < 2) { /* check that at least 2 arguments available */
        fprintf (stderr, "error: insufficient arguments.\n"
                "usage: %s filename\n", argv[0]);
        return 1;
    }

    filep = fopen (argv[1], "r");   /* open file given as 1st argument */

现在验证文件是否已打开以供读取：

    if (!filep) {                   /* validate file is open for reading */
        perror ("fopen-filep");
        return 1;
    }

现在您可以看看如何处理列表添加。首先，您可以自由编写一个 create_node()函数，该函数对于复杂的结构初始化很有帮助，但是对于单个字符串 data，确实不需要。每次调用 addnode()时只需分配一个新节点，然后只需检查它是否是添加的第一个节点（只需将节点地址分配为列表地址），否则，迭代到列表的末尾并将节点添加到列表中以便按顺序插入。
（注意：您可以简单地使用前向链接并消除查找列表结尾的需要——但是您将以相反的顺序结束列表——除非您还保留了指向列表结尾的指针——这是留给您研究的主题）
在查看 addnode()注释之前，如果要为 addnode()中的第一个节点分配，则必须将列表指针的地址传递给 addnode()，因为列表的地址将设置为第一个节点。您也可以返回一个指向所插入节点的指针（也可以将其用作插入成功/失败的指示），并将返回值指定为第一个节点的列表地址（取决于您自己）。但是，当您开始按排序顺序插入或从列表中删除节点时，您同样需要将列表的地址作为参数传递，因为更改第一个节点或删除第一个节点将导致列表地址更改。
考虑到这一点，您的 addnode()可能类似于：

node_t *addnode (node_t **head, char *word)
{
    size_t len = strlen (word);             /* length of word */
    node_t  *node = malloc (sizeof *node),  /* allocate new node */
            *iter = *head;      /* temp iterator for in-order insert */

    if (!node) {                    /* validate EVERY allocation */
        perror ("malloc-node");     /* handle error */
        return NULL;
    }

    node->next = NULL;
    node->data = malloc (len + 1);  /* allocate storage for word */

    if (!node->data) {              /* ditto! */
        free (node);                /* free node - word allocation failed */
        perror ("malloc-node->data");
        return NULL;
    }

    memcpy (node->data, word, len + 1); /* copy with nul-character */

    if (!*head)                     /* are we the first node? */
        return (*head = node);      /* just set *head = node */

    while (iter->next)              /* while next is not NULL */
        iter = iter->next;          /* advance iter to next node */

    return (iter->next = node);     /* new node at end */
}

您只需传递列表地址和要添加的单词，即可创建节点并将节点分配给列表，例如在 main()中，

    while (fscanf (filep, "%s", word) != EOF)   /* read each word */
        addnode (&head, word);                  /* add to list */
    fclose (filep);                 /* close file, done reading */

这就是您的 addnode()在列表中添加节点/单词的简单方法。但是，创建列表的每个程序也应该能够删除列表并 free()分配给列表的所有内存。在删除 victim节点之前，在节点上保存一个指向要删除的节点的指针并前进到下一个节点的简单迭代是关键，例如。

  void free_list (node_t *node)
{
    while (node) {              /* iterate over each node */
        node_t *victim = node;  /* save node to free as victim */
        node = node->next;      /* advance to next before freeing current */
        free (victim->data);    /* free node word */
        free (victim);          /* free node */
    }
}

总而言之，您读取文件中的每个单词并将每个单词添加到列表中的节点可以是：

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

#define MAXC 1024u  /* if you need a constant, define one (or more) */

typedef struct Node {
    char *data;
    struct Node *next;
} node_t;

node_t *addnode (node_t **head, char *word)
{
    size_t len = strlen (word);             /* length of word */
    node_t  *node = malloc (sizeof *node),  /* allocate new node */
            *iter = *head;      /* temp iterator for in-order insert */

    if (!node) {                    /* validate EVERY allocation */
        perror ("malloc-node");     /* handle error */
        return NULL;
    }

    node->next = NULL;
    node->data = malloc (len + 1);  /* allocate storage for word */

    if (!node->data) {              /* ditto! */
        free (node);                /* free node - word allocation failed */
        perror ("malloc-node->data");
        return NULL;
    }

    memcpy (node->data, word, len + 1); /* copy with nul-character */

    if (!*head)                     /* are we the first node? */
        return (*head = node);      /* just set *head = node */

    while (iter->next)              /* while next is not NULL */
        iter = iter->next;          /* advance iter to next node */

    return (iter->next = node);     /* new node at end */
}

void prn_list (node_t *node)
{
    puts ("\nlinked list:\n");

    while (node) {              /* iterate over each node */
        puts (node->data);      /* outputting node->data */
        node = node->next;      /* advance to next node */
    }
}

void free_list (node_t *node)
{
    while (node) {              /* iterate over each node */
        node_t *victim = node;  /* save node to free as victim */
        node = node->next;      /* advance to next before freeing current */
        free (victim->data);    /* free node word */
        free (victim);          /* free node */
    }
}

int main (int argc, char **argv) {

    char word[MAXC];        /* buffer to hold each word */
    FILE *filep;            /* FILE not File */
    node_t *head = NULL;    /* node to beginning of list */

    if (argc < 2) { /* check that at least 2 arguments available */
        fprintf (stderr, "error: insufficient arguments.\n"
                "usage: %s filename\n", argv[0]);
        return 1;
    }

    filep = fopen (argv[1], "r");   /* open file given as 1st argument */
    if (!filep) {                   /* validate file is open for reading */
        perror ("fopen-filep");
        return 1;
    }

    while (fscanf (filep, "%s", word) != EOF)   /* read each word */
        addnode (&head, word);                  /* add to list */
    fclose (filep);                 /* close file, done reading */

    prn_list (head);    /* print list */
    free_list (head);   /* free all allocated memory */
}

（注意：您必须验证每个分配、重新分配和输入，以确保您不会在编写的每个程序中调用未定义的行为，而不仅仅是列出程序）
以上原则一般适用于您将要编写的所有链表程序。如上所述，在如何使用 tail指针通过前向链接或按顺序链接来优化添加节点方面也存在差异，但要添加的信息的基本传递以及节点的分配和数据的存储基本上都将工作相同，而不管如何。
示例输入文件

$ cat ../dat/captnjack.txt
This is a tale
Of Captain Jack Sparrow
A Pirate So Brave
On the Seven Seas.

示例使用/输出

$ ./bin/ll_words ../dat/captnjack.txt

linked list:

This
is
a
tale
Of
Captain
Jack
Sparrow
A
Pirate
So
Brave
On
the
Seven
Seas.

内存使用/错误检查
在动态分配内存的任何代码中，对于任何分配的内存块，您都有两个职责：（1）始终保留指向内存块起始地址的指针，以便（2）在不再需要时可以释放它。
必须使用内存错误检查程序，以确保您不会尝试访问内存或写入超出或超出已分配块的界限，尝试读取未初始化值或将条件跳转基于未初始化值，最后确认您释放了已分配的所有内存。
对于Linux valgrind是正常的选择每个平台都有类似的内存检查程序。它们都很容易使用，只要运行你的程序就可以了。

$ valgrind ./bin/ll_words ../dat/captnjack.txt
==16920== Memcheck, a memory error detector
==16920== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==16920== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==16920== Command: ./bin/ll_words ../dat/captnjack.txt
==16920==

linked list:

This
is
a
tale
Of
Captain
Jack
Sparrow
A
Pirate
So
Brave
On
the
Seven
Seas.
==16920==
==16920== HEAP SUMMARY:
==16920==     in use at exit: 0 bytes in 0 blocks
==16920==   total heap usage: 33 allocs, 33 frees, 884 bytes allocated
==16920==
==16920== All heap blocks were freed -- no leaks are possible
==16920==
==16920== For counts of detected and suppressed errors, rerun with: -v
==16920== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认已释放所有已分配的内存，并且没有内存错误。
再看一遍，如果你还有问题，请告诉我。