“This is the first day of my participation in the Gwen Challenge in November. See details of the event: The last Gwen Challenge in 2021”.

From arrays to lists

The ideal situation is for users to keep adding data, without first specifying how many entries to enter or having the program allocate extra space. This can be done by calling malloc () after each entry is entered to allocate just enough space to store that entry. If you enter three movies, the program calls malloc () three times; If the user enters 300, it will be called 300 times!

For comparison, one way is to call malloc() once to allocate enough space for 300 filem struct requests; The alternative is to call malloc ()300 times to allocate enough space for each file structure request. The former allocates contiguic blocks of memory and requires only a single pointer to the struct variable (film) that points to the ⅰ structure in the allocated block. The simple array notation gives Pointers access to every structure in the block, as shown in the previous code snippet. The problem with the second method is that there is no guarantee that each call to malloc() will allocate a contiguous block of memory. This means that the structure is not necessarily stored consecutively (see Figure 17). Therefore, instead of storing a pointer to 300 blocks in the first method, you need to store 300 Pointers, each pointing to a separately stored structure.

This passage in the book is so good, I put it all in bold!

Every time malloc() is used to allocate space for a new structure, it also allocates space for a new pointer. However, you would need another pointer to track the newly allocated pointer, the pointer to track the new pointer itself, and another pointer to track it, and so on. The underlying problem would need to be solved by redefining the structure to include Pointers to the next structure in each structure. Then, when you create a new structure, you can store the address of that structure in the previous one. In short, the film structure can be defined as follows:

#define TSIZE 45		// The size of the array to store the titles
struct film {
char title [ TSIZE];
int rating;
struct film * next;
};
Copy the code

1.1 An important point

Although structures cannot contain structures of the same type as themselves, they can contain Pointers to structures of the same type. This definition is the basis for defining linked lists, in which each item contains information about where to find the next. Before we look at the code of a linked list, we need to understand a linked list conceptually. Assume that the user enters Modern Times with a level of 10. The program allocates space for the film structure, copies the string Modern Times into the title member of the structure, and sets the rating member to 10. To indicate that there is no other structure following this structure, the program sets the next member pointer to NULL(NULL is a symbolic constant defined in the stdio.h header to represent a NULL pointer). Of course, you also need a ** separate pointer to hold the address of the first structure. This pointer is called a head pointer. The header pointer points to item 1 in the list. ** Figure 17.2 illustrates this structure (whitespace in the title member is compressed to save image space).

Now, assume the user enters a second movie and its rating, such as Midnight in Paris and 8. The program allocates space for the second film structure and stores the address of the new structure in the next member of the first structure (overwriting the NULL previously stored in that member) such that the next pointer in the first structure points to the second structure. The program then copies Midnight in Paris and 8 into the new structure and sets the next member in the second structure to NOLL, indicating that the structure is the last one in the list. Figure 17.3 illustrates these two items.

What a great introduction!

Every time a new movie is added, it is treated the same way. The address of the new structure is stored in the above structure, the new information is stored in the new structure, and the next member in the new structure is set to NULL

Suppose you want to display the list. For each item displayed, you can locate the next item to be displayed based on the address already stored in that item. However, for this scheme to work, a pointer is required to store the address of the first item in the list, because no other item in the list stores the address of the item. This is where the header pointer comes in handy.

Use linked lists

We use code to implement a linked list!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TSIZE 45

struct film
{
    char title[TSIZE];
    int rating;
    struct film *next; // points to the next structure in the list
};

char *s_gets(char *st, int n); // The function returns a pointer to type char

int main(void)
{
    struct film *head = NULL;
    struct film *prev, *current;
    char input[TSIZE];

    puts("Enter first movie title:");
    while(s_gets(input, TSIZE) ! =NULL && input[0] != '\ 0')
    {
        current = (struct film *)malloc(sizeof(struct film));
        if (head == NULL)
            head = current;
        else
            prev->next = current;
        current->next = NULL;
        strcpy(current->title, input);
        puts("Enter your rating <0-10>:");
        scanf("%d", &current->rating);
        while(getchar() ! ='\n')
            continue;
        puts("Enter next movie title (empty line to stop)");
        prev = current;
    }

    /* Displays a list of movies */
    if (head == NULL)
        printf("No data entered. ");
    else
        printf("Here is the movie list: \n");
    current = head;
    while(current ! =NULL)
    {
        printf ("Movie: %s Rating: %d\n",current->title,current -> rating);
        current = current->next ;
    }

    /* Complete the task, free the allocated memory */
    current = head;
    while(current ! =NULL)
    {
        current = head;
        head = current->next;
        free(current);
    }
    printf("Bye! \n");

    return 0;
}

char *s_gets(char *st, int n)
{
    char *ret_val;
    char *find;

    ret_val = fgets(st, n, stdin);
    if (ret_val)
    {
        find = strchr(st, '\n');
        if (find)
            *find = '\ 0';
        else
            while(getchar() ! ='\n')
                continue;
    }
    returnret_val; C} PS D: Code c structure > CD"D :\Code\C\ structure \"; if ($?) {GCC Demo01. C-o Demo01}; if ($?) {.\ Demo01} Enter first movie title: Roman Holiday Enter your rating <0-10>: 8 Enter next movie title (empty line to stop) Rose Enter your rating <0-10>: 2 Enter next movie title (empty line to stop) Here is the movie list: Movie: Roman Holiday Rating: 8 Movie: Rose Rating: 2Copy the code

The program performs two tasks using linked lists. The first task is to construct a linked list in which to store the data entered by the user. The second task is to display the linked list. The task of displaying a linked list is relatively simple, so let’s discuss it first.

2.1 Program Analysis

2.1.1 Display the linked list

Because of the book to write too good, I directly copy down for everyone’s reference!

The display list starts by setting a pointer to the structure (named current). Since the head pointer already points to the first structure in the list, it can be expressed this way

The current = head;Copy the code

The members of the structure are then accessed using the pointer notation described in the previous section

printf ("Movie: %s Rating: %d\n",current->title,current -> rating);
Copy the code

After printing, the current pointer points to the next structure

current = current->next ;
Copy the code

Once you’ve done this, repeat the process. When displayed to the last item in the list, current will be set to NULL because this is the value of the next member in the last structure of the list

while(current ! =NULL)
    {
        // Pointers can be used to access members of a structure. Members can
        printf ("Movie: %s Rating: %d\n",current->title,current -> rating);
        current = current->next ;
    }
Copy the code

When traversing a linked list, why not just use the head pointer instead of creating a new pointer? Because using head changes the value in head, the program can’t find the start of the list

2.1.2 Creating a Linked List

Creating a linked list involves the following three steps:

(1) Use malloc () to allocate enough space for the structure;

(2) address of storage structure;

(3) Copy the current information to the structure.

There is no need to create a structure, so the program uses a temporary store (an input array) to get the movie name entered by the user. If the user emulated EOF via the keyboard or enters a blank line, the following loop will exit:

while (s gets(input,TSIZE)! = NULL && input [0] ! = ‘\ 0’)

Current :current = (struct film *) malloc(sizeof(struct film));

The address of the first structure in the list should be stored in the pointer variable head. The address of each subsequent structure should be stored in the next member of its predecessor. Therefore, the program needs to know if it is dealing with the first structure. The simplest way is to initialize the head pointer to NULL at the beginning of the program. The program can then use the value of head to determine:

if (head == NULL)	// the first structure
	head = current;
else //subsequent structures
	prev->next = current;

Copy the code

In the above code, the pointer prev points to the last allocated structure. Next, you must set appropriate values for the structure members. In particular, setting the next member to NULL indicates that the current structure is the last structure in the list. Also copy the movie name from the input array into the title member and provide a value to the rating member as shown below:

current->next = NULL;
strcpy (current->title, input) ;
puts ( "Enter your rating <0-10> :");scanf ( "%di",&current->rating) ;
Copy the code

Because s_gets () limits input to tsize-1 characters, it is safe to use strcpy() to copy the string from the input array into the title member.

Finally, prepare for the next input. In particular, set the prev to point to the current structure. Because after the user enters the next movie and the program allocates space for the new structure, the current structure becomes the previous structure of the new structure, the program sets the pointer at the end of the loop like this: prev = current; Is the program running properly? Here is an example of this program in action;

​ Enter first movie title:

​ Spirited Away

​ Enter your rating <0-10>:

​ 9 ​ Enter next movie title (empty line to stop):

​ The Duelists

​ Enter your rating :

​ 8 ​ Enter next movie title (empty line to stop) :

​ Devil Dog: The Mound of Hound ​ Enter your rating <0-10>: ​ 1

​ Enter next movie title (empty line to stop) : ​ Here is the movie list: ​ Movie: Spirited Away Rating: 9 ​ Movie: The Duelists Rating: 8 ​ Movie: Devil Dog: The Mound of Hound Rating: 1 ​ Bye!

2.1.3 Releasing linked lists

In many environments, the memory allocated by malloc () is automatically freed at the end of the program. However, it is best to call malloc() and free() in pairs. Therefore, the program calls the free() function for each allocated structure when it cleans up memory: current = head; while (current ! = NULL) { current = head; head = current->next; free (current) ;

​ }