introduction

When storing a large wave number , We usually use arrays , But arrays sometimes seem inflexible , For example, the following example :

There is a list of numbers that have been sorted 2,3,5,8,9 ,10

If we want to insert into the array 6 This element , Need to 8 All subsequent elements move back one bit

 

This operation is obviously time-consuming , If you use a linked list, it will be much faster . So what is a linked list ? Please see the figure below :

At this time, if necessary 8 Add one in front 6, Then just change it like the figure below , Instead of moving each number back as you did at the beginning .

Thinking about linked list

In order to realize the data structure of linked list , We need to use pointers and malloc Such a function .

be careful : malloc The return value of the function is void * type , We need to cast it  

use malloc The header file needs to be called <stdlib.h>

Why do we use such a complicated way to store types  ?

Because according to the previous method , We must know exactly the number of variables needed in advance , That is, we have to define all the variables . If you define it now 100 Variables , In fact, you need 101 Variables , Then you have to modify this program .

And with malloc function , We can apply for space according to the actual situation during the operation of the program .

Linked list node structure  

Each node consists of two parts . The left part is used to store specific values , Then you can use an integer variable ; The right part needs to store the address of the next point , It can be realized by pointer ( Also known as a successor pointer ).

Here we define a structure type to store this node :
struct node { int date; struct node* next; };
 

Because the type of the next node is also struct node , So the type of our pointer must also be struct node * type . 

Create linked list  

1

first , We need a head pointer head Point to the beginning of the linked list . When the linked list has not been established, the header pointer head Empty ( It can also be understood to point to an empty node ).
struct node* head; head = NULL; // The header pointer is initially null
2

Now? , Let's create the first node , And use temporary pointer p Point to this node
struct node* p; // Apply for a space dynamically , Used to store a node , And use temporary pointer p Point to this node p = (struct
node*)malloc(sizeof(struct node));
Next, set the left half and right half of the new node respectively
scanf("%d", &a); p->date = a; // Store data to the current node date In domain p->next = NULL;
// Set the subsequent pointer of the current node to null , That is, the next node of the current node is empty
Let's set the header pointer and the of the newly created node *next Point to null . The function of head pointer is to facilitate traversing the whole linked list from scratch
if (head == NULL) head = p; // If this is the first node created , Then point the header pointer to this node else q->next = p;
// If it is not the first node created , Then the subsequent pointer of the previous node points to the current node
If it is the first node created , Then point the header pointer to this node  

 

  If it is not the first node created , Then the successor node of the previous node points to the current node .

Finally, the pointer q It also points to the current node , Because the pointer will be temporarily changed later p Will point to the newly created node .
q = p; // Pointer q Also point to the current node
 
#include <stdio.h> #include <stdlib.h> // Here, a structure is created to represent the node type of the linked list struct node {
int date; struct node* next; }; int main() { struct node* head, * p, * q =
NULL, * t; int i, n, a; scanf("%d", &n); head = NULL; // The header pointer is initialized to null for (i = 1; i
<= n; i++) { scanf("%d", &a); // Apply for a space dynamically , Used to store a node , And use temporary pointer p Point to this node p = (struct
node*)malloc(sizeof(struct node)); p->date = a; p->next = NULL;
// Set the subsequent pointer of the current node to null , That is, the next node is empty if (head == NULL) head = p;
// If this is the first node created , Then point the head pointer to this point else q->next = p;// If it is not the first node created , Then the successor node of the previous node points to the current node q
= p; // Pointer q It also points to the current node } // Output all numbers in the linked list t = head; while (t != NULL) { printf("%d ",
t->date); t = t->next; // Continue to the next node } }
design sketch

 

Implement insert operation  

First, use a temporary pointer t Start traversing from the head of the linked list
t = head; // Start traversing from the head of the linked list
  Wait until the pointer t Value ratio of the next node of 6 When I was old , take 6 Put it in the middle .

Namely t -> next -> date greater than 6 Insert when

code implementation
scanf("%d", &a); // Number of inserts to be read in t = head; // Start traversing from the head of the linked list while (t != NULL) { if
(t->next->date > a || t->next->next == NULL) {
// Insert if the current node is the last node or the value of the next node is greater than the value to be inserted p = (struct node*)malloc(sizeof(struct
node)); // Apply for a space , To store new nodes p->date = a; p->next =
t->next;// The subsequent pointer of the new node points to the node pointed to by the subsequent pointer of the current node t->next = p; // The subsequent pointer of the current node points to the new node break;
// Exit loop after insertion } t = t->next; // Continue to the next node }
Complete code  

design sketch :

 
#include <stdio.h> #include <stdlib.h> // Here, a structure is created to represent the node type of the linked list struct node {
int date; struct node* next; }; int main() { struct node* head, * p, * q =
NULL, * t; int i, n, a; scanf("%d", &n); head = NULL; // The header pointer is initialized to null for (i = 1; i
<= n; i++) { scanf("%d", &a); // Apply for a space dynamically , Used to store a node , And use temporary pointer p Point to this node p = (struct
node*)malloc(sizeof(struct node)); p->date = a; p->next = NULL;
// Set the subsequent pointer of the current node to null , That is, the next node is empty if (head == NULL) head = p;
// If this is the first node created , Then point the head pointer to this point else q->next = p;// If it is not the first node created , Then the successor node of the previous node points to the current node q
= p; // Pointer q It also points to the current node } scanf("%d", &a); // Read in the number of to be inserted t = head; // Start traversing from the head of the linked list while (t
!= NULL) { if (t->next->date > a || t->next->next == NULL) {
// Insert if the current node is the last node or the value of the next node is greater than the value to be inserted p = (struct node*)malloc(sizeof(struct
node)); // Apply for a space , To store new nodes p->date = a; p->next =
t->next;// The subsequent pointer of the new node points to the node pointed to by the subsequent pointer of the current node t->next = p; // The subsequent pointer of the current node points to the new node break;
// Exit loop after insertion } t = t->next; // Continue to the next node } // Output all numbers in the linked list t = head; while (t != NULL) {
printf("%d ", t->date); t = t->next; // Continue to the next node } }
 

 

If you have any comments or need , Welcome to Xiaoxuan in the comment area !

Rush !! 

Technology
©2019-2020 Toolsou All rights reserved,
【C++ Must see for entry 】C++ from 0 reach 1 Introductory programming axios Interceptor packaging and use Spring Boot Interview must ask : Automatic configuration principle VMware 16 install centos 7 Detailed tutorial C Language data structure - Sequence table delete duplicates V2.0.0 The 12th Blue Bridge Cup c++b Group personal problem solving On sending data from serial port single chip microcomputer to upper computer centos7 install RabbitMqjava Polymorphic array of opencv-python Fourier transform and inverse transform