时间戳

首页 > 解决方案 > 从带有输出的输入文件创建 C 链表

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

问题描述

您好，我正在 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循环中的前一个节点的情况下，我正在努力添加一个节点。有什么建议么？我的实施不正确吗？如果它更适合链表数据结构，我愿意改变我的方法。谢谢

标签： cfiledata-structures

解决方案

首先，让我们从基础开始，你必须将你读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()程序提供参数的形式。使用它们！不要硬编码文件名——这就是参数的用途。只需将文件名作为第一个参数传递给您的程序并验证您是否有至少 2 个参数（第一个参数始终是程序名称），例如

    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 */
}

您只需传递列表的地址和要添加的单词即可创建节点并将其分配给列表，例如 in 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.

内存使用/错误检查

在您编写的任何动态分配内存的代码中，对于分配的任何内存块，您有 2 个责任：（1）始终保留指向内存块起始地址的指针，（2）它可以在它不存在时被释放更需要。

您必须使用内存错误检查程序来确保您不会尝试访问内存或写入超出/超出分配块的范围，尝试读取或基于未初始化的值进行条件跳转，最后确认释放所有分配的内存。

对于 Linuxvalgrind是正常的选择。每个平台都有类似的内存检查器。它们都易于使用，只需通过它运行您的程序即可。

$ 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)

始终确认您已释放所有已分配的内存并且没有内存错误。

如果您还有其他问题，请仔细查看并告诉我。

推荐阅读