Создание связанного списка C из входного файла с выводом - PullRequest
Новая
       20

Создание связанного списка C из входного файла с выводом

1 голос
/ 14 марта 2019

Здравствуйте. Я создаю связанный список в C для печати уникальных токенов, данных из текстового файла dict.txt. Я новичок в C и не знаю, как правильно прочитать каждое слово из файла, сохранить его в узле, а затем распечатать получившийся связанный список. Ниже приведены мои следующие методы, я опустил мой метод содержащий или его реализацию в моем методе добавления. Я пока не занимаюсь этой частью, только пытаюсь напечатать каждое слово из данного текстового файла. 

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++
}

Я изо всех сил пытаюсь добавить Node, учитывая предыдущий узел в цикле while. Какие-либо предложения? моя реализация неверна? Я готов изменить свои методы, если это лучше подходит для структуры данных связанного списка. спасибо

Ответы [ 2 ]

2 голосов
/ 14 марта 2019

Во-первых, давайте начнем с основ, вы должны прочитать ваш word в допустимый буфер, поэтому объявите буфер достаточно большой, чтобы вместить ваши слова (самое длинное слово в словаре Unabridged (немедицинском) составляет 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 аргумента (1-й аргумент - это всегда имя программы), например, 

    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.

Использование памяти / проверка ошибок

В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей в отношении любого выделенного блока памяти: (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)

Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.

Посмотрите вещи и дайте мне знать, если у вас есть дополнительные вопросы.

0 голосов
/ 14 марта 2019

Вы, кажется, не используете указатель последовательно.Возможно, вам придется обновить различие между указателем и значением.Это вы должны потренироваться самостоятельно, чтобы убедиться, что вы понимаете концепцию.

Для этой конкретной проблемы:

1) Сначала измените createNode, чтобы создать новый узел и инициализировать данные: 

Node * createNode(char *data) {
    Node *node = (Node *)malloc(sizeof(struct Node));
    node->next = NULL;
    node->data = (char *)malloc(strlen(data));
    strcpy(node->data, data);
    return node;
}

(Обратите внимание, что мы возвращаем указатель. Кроме того, мы выделяем место для хранения данных.)

2) Кроме того, измените add для принятия указателей и возврата указателя 

Node * add(Node *head, char *data) {
    Node *p = NULL;
    Node *temp = createNode(data);
    if (head == NULL) {
        head = temp;
    }
    else {
        p = head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = temp;
    }
    return head;
}

Обратите внимание, что вышеупомянутая функция может обрабатывать пустой список и ни один пустой список, поэтому вашему основному не нужно.

3) В основном: 

int main() {
    File *filep = fopen("dict.txt", "r");
    Node head = NULL;
    char word[256];

    while (fscanf(filep, "%s", word) != EOF) {
        head = add(head, word);
    }
    return 0;
}
...