Невозможно понять связанный список (c)

Question

Не могу понять, как работает связанный список.

Допустим, у меня есть код

typedef struct trip {
    int id, year, something;
    char name[100], destination[100];
    struct trip *next;                       //X1

}TRIP;                                       //X2
    FILE *fr;
    TRIP *p_a, *p_p;                         //X3
    fr =fopen("list.txt","r");
    int j=0;
    p_p = (TRIP *) malloc(sizeof(TRIP));
    p_a = p_p;
    while ((fscanf(fr,"%d",&p_a->id)), p_a->id>0 )
    {
            fscanf(fr,"%s",&p_a->name);
            fscanf(fr,"%s",&p_a->destination);
            fscanf(fr,"%d",&p_a->year);
            fscanf(fr,"%d",&p_a->something);
            p_a->next = (TRIP *) malloc(sizeof(TRIP));
            p_a = p_a->next;

    }
    p_a->next = NULL;                        //X4
    fclose(fr);
    return p_p;
}

Я не уверен, что делают некоторые строки. Эти строки прокомментированы с x1 x2 x3 x4. Пожалуйста, кто-нибудь может мне это объяснить?

Answer 1

typedef struct trip {                       
    int id, year, something;
    char name[100], destination[100];
    struct trip *next;                   //Define a pointer to a trip struct
                                         //called next. This will hold a
                                         //pointer to the next element in
                                         //the list.

}TRIP;                                   //The name of the typedef statement
                                         //After this you can define a trip 
                                         //without writing 'struct trip' but 
                                         //just 'TRIP'

FILE *fr;
TRIP *p_a, *p_p;                         //Define two pointers to trip structs
fr =fopen("list.txt","r");
int j=0;
p_p = (TRIP *) malloc(sizeof(TRIP));
p_a = p_p;
while ((fscanf(fr,"%d",&p_a->id)), p_a->id>0 )
{
        fscanf(fr,"%s",&p_a->name);
        fscanf(fr,"%s",&p_a->destination);
        fscanf(fr,"%d",&p_a->year);
        fscanf(fr,"%d",&p_a->something);
        p_a->next = (TRIP *) malloc(sizeof(TRIP));
        p_a = p_a->next;

}
p_a->next = NULL;                        //After the last line has been added
                                         //to the list, end the list by making
                                         //the next pointer NULL
fclose(fr);
return p_p;
}

Answer 2

x1: next - указатель на другой экземпляр struct trip.Может помочь картинка:

+-------+------+       +-------+------+       +-------+------+
| stuff | next | ----> | stuff | next | ----> | stuff | next | ----|||
+-------+------+       +-------+------+       +-------+------+

, где stuff - все остальные данные, которые вы храните в этом узле (id, year, something, name, destination).Член next хранит адрес другого узла.

C позволяет объявлять указатели на тип struct в определении этого типа struct:

struct foo {
  ...
  struct foo *fooptr;
  ...
};

Вам не нужно знать размер типа structчтобы создать указатель на него, указатели на все типы struct имеют одинаковый размер и представление.То есть указатель на struct foo имеет тот же размер, что и указатель на struct bar, хотя struct foo и struct bar могут иметь радикально разные определения.

x2: средство typedef позволяет создавать псевдонимы для типов - TRIP - псевдоним для имени типа struct trip.Это полезно, если вы хотите упростить сложный тип или абстрагироваться от деталей реализации (имя * typedef FILE в stdio.h является примером последнего).

x3: эта строка объявляет p_a и p_p как указатели на struct trip.

Answer 3

x1

struct trip * next; // X1

Внутри структуры данных "поездки" он содержит указатель на другую структуру данных поездки.

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

x2

} TRIP; // X2

Это будет (я забыл соответствующее слово) псевдоним структуры. ПОЕЗДКА = поездка.

Так сказать

trip a; // OR
TRIP a;

Действительны ли оба

x3

TRIP * p_a, * p_p; // X3

Это объявление двух переменных, p_a, p_p, типа TRIP * (или trip *, они эквивалентны)

Этот тип является указателем на структуру данных поездки.

x4

p_a-> next = NULL; // Х4

Это выбор элемента в указателе. То есть теперь он устанавливает значение «следующего» элемента в структуре поездки, на которую указывает p_a, равное NULL.

Если бы это было полезно, это было бы эквивалентно

(*p_a).next = NULL