C language learning log 2.19

Linked list ：

A list is a kind of Infrastructure , use Dynamically allocate storage units Storage and distribution . Structure pointer It has been fully used in this field . let me put it another way , A linked list is a Extremely powerful array , He can Define multiple data types in nodes , You can also add as you like , Delete , Insert node .

Create a linked list :

First , First construct a structure , Structures are generally constructed with typedef function , This facilitates the naming of structural variables .

typedef struct _node{
    int value;
    struct _node *next;
}Node;

Then construct the node , Before we construct the nodes, let's take a look at ：

        p = head->next And head->next=p The difference between ：

                p= head->next It means originally head Pointer to next, Assign this to p, It is equivalent to displaying this pointer , namely p Point to next.

                head->next=p It means to change next The direction of ,next Point to p This new node .

The construction nodes are as follows :

Node *p = (Node*)malloc(sizeof(Node));
p->value = number;
p->next = NULL;// Pay attention to the last p The pointer is pointing to next, Convenient for rear connection 

The next step is to build the last pointer of the linked list ：

Node *last = head;// First, let last Point to head, Because the linked list may only have one node 
while(last->head){
    last = last->next;
}

Finally, just connect them .

The whole content is as follows :

typedef struct _node{
    int value;
    struct _node *next;
}Node;
int main(int argc, char const *argv[])
{
    Node *head = NULL;
    int number;
    do{
        scanf("%d",&number);
        if(number !=-1){
            Node *p = (Node*)malloc(sizeof(Node));
            p->next = number;
            p->next = NULL;
            Node *last = head;
            if(last){
                while(last ->next){
                    last = last->next;
                }
                last->next = p;
            }esle{
                head = p;
            }
        }
    }while(number !=-1);
}
            
        

Let's optimize the above , Let's start with a function block , To put the operation of adding nodes into the function block ：

Node* add(Node* head,int number)
{
    Node *p = (Node*)malloc(sizeof(Node));
    p->next = number;
    p->next = NULL;
    Node *last = head;
    if(last){
        while(last ->next){
            last = last->next;
        }
        last->next = p;
    }else{
        head = p;
    }
    return head;
}

Note that this is a The secondary pointer , Because changing the pointer in a function , The pointer in the main function does not change , But if it is to change what the pointer refers to , At this time, the contents of the pointer in the main function will change , We can understand that the function reproduces the same pointer as the main function .

The whole thing is just like this :

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
	int value;
	struct _node *next;
}Node; 
Node* add(Node *head,int number); 
int main(int argc, char *argv[])
{
	Node *head=NULL;
	int number;
	do{
		scanf("%d",&number);
		if(number!=-1){
		head=add(head,number);
		}
	}while(number!=-1);
	printf("%d",head->value);
	return 0;
}
Node* add(Node *head,int number)
{
	Node *p=(Node*)malloc(sizeof(Node));
		p->value=number;
		p->next=NULL; 
		Node *last=head;
		if(last){
			while(last->next){
			last=last->next;
			}
		last->next=p;
		}else{
			head=p;
		}
}

Then we can improve again , Create a new structure _list To represent the whole linked list , It can also be adjusted easily in the future .

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
	int value;
	struct _node *next;
}Node; 
typedef struct _list{
	Node* head;
}List; 
void * add(List *list,int number);
int main(int argc, char *argv[])
{
	List list;
	list.head=NULL;
	int number;
	do{
		scanf("%d",&number);
		if(number!=-1){
	    add(&list,number);
		}
	}while(number!=-1);
	printf("%d",list.head->value);
	return 0;
}
void * add(List *list,int number)
{
	Node *p=(Node*)malloc(sizeof(Node));
		p->value=number;
		p->next=NULL; 
		Node *last=list->head;
		if(last){
			while(last->next){
			last=last->next;
			}
		last->next=p;
		}else{
		list->head=p;
		}
}

There is still room for improvement ,last This pointer always starts from head Loop to the last point to the last , Every new node is added , You have to cycle again , so much trouble . So we need to add one tail The pointer

#include <stdio.h>
#include <stdlib.h>
#include "node.h"
typedef struct _list{
	Node* head;
	Node* tail;
}List; 
void * add(List *list,int number);
int main(int argc, char *argv[])
{
	List list;
	list.head=NULL;
	list.tail=NULL;
	int number;
	do{
		scanf("%d",&number);
		if(number!=-1){
	    add(&list,number);
//		head=add(head,number);
		}
	}while(number!=-1);
	printf("%d",list.tail->value);
	return 0;
}

void * add(List *plist,int number)
{
	Node *p=(Node*)malloc(sizeof(Node));
		p->value=number;
		p->next=NULL; 
		Node *last=list->head;
		if(last){
            last = plist ->tail;
		    last->next=p;
		    plist->tail=p;
		}else{
		    plist->head=p;
		    plist->tail=p;
		}
}

（ The above content is from teacher Weng Kai mooc Lessons learned in the course ）