Функция вставки связанного списка C, создающая нежелательную запись в конце
Я пишу простую программу на C и столкнулся с проблемой в моем коде. Я создаю структуру данных круглого связанного списка и заполняю ее данными из текстового файла. Кажется, что все работает просто отлично, за исключением того, что он помещает дополнительную запись в конец связанного списка. Может ли кто-нибудь указать на то, что я делаю неправильно, и предложить решение этой проблемы?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 20
#define MAXLEN 100
//Definition of the structure:
struct list{
char name[SIZE];
int min, max;
struct list *next;
struct list *prev;
};
typedef struct list List;
typedef List *ListPtr;
//Function prototypes
ListPtr getData(ListPtr lst, ListPtr start);
void print(ListPtr start);
Вот мой главный ():
int main()
{
ListPtr lst, start;
lst = (ListPtr) malloc(sizeof(List));
lst->next = NULL;
lst->prev = NULL;
//Gets data from text file
start = getData(lst, start); //Making start to point to the 1st entry
print(start);
system("PAUSE");
return 0;
}
Вот getData():
ListPtr getData(ListPtr lst, ListPtr start){
//For some reason aditional entry is created with system data in it
char arr[MAXLEN];
FILE *data = fopen("data.txt", "r");
//while(fgets(arr, MAXLEN, data)){
strcpy(lst->name, strtok(arr, " "));
lst->min = atoi(strtok(NULL, " "));
lst->max = atoi(strtok(NULL, " "));
lst->next = (ListPtr)malloc(sizeof(List));
lst->next->prev = lst;
lst = lst->next;
}
fclose(data);
start = lst; //start = end of the list
while(lst->prev != NULL)
lst = lst->prev; //goes to the start of the list
start->next = lst;
lst->prev = start;
start = lst;
return start;
}
А вот функция для проверки записей в списке:
void print(ListPtr start){
int i;
for(i = 0; i < 9; i++){
printf("%s %d %d\n", start->name, start->min, start->max);
start = start->next;
}
}
Образец data.txt:
John 10 15
Mike 13 17
Anna 18 23
Я хочу создать этот список круговым способом, чтобы позже я мог случайным образом выбирать из него записи с генерацией большого числа с помощью rand(); и пролистайте список, так как он дает rand () больше случайности. Любая помощь с моей проблемой высоко ценится.
Изменить Изменение строки в getData(); после fclose(data) в start = lst->prev; кажется, решил проблему, но это не кажется правильным. Создает ли это все еще нежелательную запись, и я просто удаляю ее из списка, заставляя ее загрязнять память, или это была просто моя логическая ошибка, и это правильный способ исправить это?
4 ответа
Я советую вам держать заголовок списка в переменной, давайте назовем его заголовком. Вы можете решить свою проблему с помощью:
int getData(ListPtr *head, char *filename){
ListPtr lst;
int count = 0;
char arr[MAXLEN];
FILE *data = fopen(filename, "r");
if (data == NULL)
return -1;
*head = (ListPtr)malloc(sizeof(List));
lst = *head;
while(fgets(arr, MAXLEN, data)){
count++;
strcpy(lst->name, strtok(arr, " "));
lst->min = atoi(strtok(NULL, " "));
lst->max = atoi(strtok(NULL, " "));
if (!feof(data))
{
lst->next = (ListPtr)malloc(sizeof(List));
lst->next->prev = lst;
lst = lst->next;
}
}
fclose(data);
if (count == 0)
{
free(*head);
return -1;
}
lst->next = *head;
(*head)->prev = lst;
return count;
}
Таким образом, в голове у вас будет NULL в случае пустого файла, а функция возвращает -1 в случае ошибок. Когда файл существует и он не пустой, он возвращает количество элементов в списке, а заголовок будет указателем заголовка списка.
Вы должны вызвать эту функцию с помощью:
ListPtr head;
int nEl;
nEl = getData(&head, "data.txt");
Есть несколько проблем дизайна с решением; Я бы порекомендовал немного переосмыслить и переписать.
Как прокомментировал Джим, во-первых, вы создаете пустой узел перед анализом данных. Предположим, ваш файл данных пуст, будет ли тогда список с одним узлом действительным? Еще одна проблема дизайна заключается в том, что вы проходите через все узлы списка в конце построения списка, что очень странно и не требуется.
Сначала решите, хотите ли вы иметь заголовок списка. Это была бы другая структура с указателями на начало и конец списка и, возможно, также с подсчетом узлов, но на самом деле это не был бы сам узел списка. Это может быть то, что вы имели в виду с начальным узлом, который вы создали.
Тем не менее, узел заголовка не является существенным, и вы могли бы вместо этого вернуть NULL из функции getData(), если ни один узел не был прочитан, и вы бы создали все узлы списка внутри этой подпрограммы. Заголовок списка в некоторых отношениях лучше, так как позволяет хранить метаданные списка и позволяет моделировать и различать пустой список (указатель на заголовок списка без узлов) и отсутствие списка (нулевой указатель).
Двусвязный список будет идти по следующему принципу. Напишите функцию createNode() для создания нового узла с данными и next/prev NULL. Голова и хвост могут быть легко соединены, если вам действительно нужно, чтобы они были круглыми.
ListNode* getData()
{
ListNode* head = 0;
ListNode* tail = 0;
const char* data;
while (data = moreData() /* wherever the data comes from */) {
ListNode* node = createNode(data);
if (!head) {
head = node;
}
else
{
node->prev = tail;
tail->next = node;
}
tail = node;
}
return head;
}
1) Как ваш код компилируется? lst не объявлен в вашей функции печати. Как вы обращаетесь к нему в printf? 2) вместо цикла используйте цикл while с условием начала!=NULL
Кажется, что пропускает
lst->next = NULL
в функции getData() сразу после цикла while, в котором вы читаете данные из файла.
Если вам нужен циклический список, вам нужно сделать это вместо того, что я сказал выше:
lst->next = <head of the list>
Править. Я лучше прочитал ваш код, и вы сделали последнее, что я сказал вам в этом фрагменте кода:
start = lst; //start = end of the list
while(lst->prev != NULL)
lst = lst->prev; //goes to the start of the list
start->next = lst;
lst->prev = start;
start = lst;
Проблема в том, что на последней итерации вы создаете новый узел с помощью malloc, но вы ничего не помещаете в него! Вот почему с lst->prev это сработало.