Embedded team structure & linked list training
structural morphology
From basic data type to abstract data type
From the previous knowledge we learned, C language specifies some basic data types, such as int, long, float, char, etc., but these basic data types are insufficient when describing some complex transactions, which leads to the structure we learn today, which allows users to customize data, Take some different types of data as a whole. This also contains the idea of object-oriented.
Definition of structure
How do we describe a student's information in C language? This student contains the attributes of name, age, gender and student number.
We can abstract such a structure
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
It can be seen that structure is to combine some basic types of data, treat them as a whole and give them new meaning.
Three definition methods of structure
1. Declare the structure before defining it
struct Structure name
{
Data type variable name 1;
Data type variable name 2;
...
Data type variable n；
};//Notice that there is a semicolon outside the braces
eg:
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};//First statement
int main(){
struct student st1;//Redefinition
st1.id = 1001;//Access to variables in structures
printf("%d",st1.id);
return 0;
}
1. Structure variables are defined when a structure is declared
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
}st1;//Declaration and definition
int main(){
// struct student st1;
st1.id = 1001;
printf("%d",st1.id);
return 0;
}
3. Using typedef to define data types
The keyword typedef is used to define an alias for a data type inherent in the system or customized by the programmer. Aliases for data types usually use uppercase letters.
eg:
typedef int INTEGER;
This defines a new name for int, INTEGER. Int and INTEGER have the same meaning and are completely equivalent.
Therefore, of course, we can also use typedef to define an alias for the structure, which makes it more convenient for us to use.
eg:
#include <stdio.h>
typedef struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
}STUDENT;//An alias is used when declaring the structure. STUDENT is equivalent to struct student
int main(){
STUDENT st1;
int i;
st1.id = 1001;
printf("%d",st1.id);
return 0;
}
/******Or*******/
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};//First statement
typedef struct student STUDENT;//Rebirth alias
int main(){
STUDENT st1;
int i;
st1.id = 1001;
printf("%d",st1.id);
return 0;
}
Access and initialization of structure
Access to structure
Look directly at the example:
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT st1;
st1.id = 1001;//Access to id in st1
printf("%d",st1.id);
return 0;
}
Access format: structure variable name +. + data variable name
After knowing how to access, we can assign values to structural variables in the same way as the previous basic data types.
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT st1;
st1.id = 1001;
scanf("%s",st1.name);
scanf("%d",&st1.age);
st1.gender = 'w';
printf("%s%d Years old",st1.name,st1.age);
return 0;
}
But! When we point to a structure with a pointer
eg:
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT *st1;
// st1.id = 1001;
// scanf("%s",st1.name);
// scanf("%d",&st1.age);
// st1.gender = 'w';
// printf("%s%d is old", st1.name,st1.age);
return 0;
}
For example, the st1 pointer here, how can we access the data of the structure through the pointer?
In the front, we use. Here, we use the arrow symbol like - > here.
eg:
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT *st1;//Defines a pointer of type STUDENT
STUDENT stu;//Define a STUDNET structure
st1 = &stu;//Point the st1 pointer to the stu
// st1.id = 1001;
// scanf("%s",st1.name);
// scanf("%d",&st1.age);
// st1.gender = 'w';
// printf("%s%d is old", st1.name,st1.age);
st1->id = 1001;//Note that - >
scanf("%s",st1->name);
scanf("%d",&st1->age);
st1->gender = 'w';
printf("%s%d Years old\n",st1->name,st1->age);
printf("%s%d Years old",(*st1).name,(*st1).age);//After dereferencing the st1 pointer, it is used as an ordinary structure variable
return 0;
}
Structure pointers are lighter than structures and are often used to pass a structure through a function.
Initialization of structure
In addition to the conventional initialization, the structure can be initialized by assigning all values directly
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT stu= {"Zhang San",18,'w',1001};
return 0;
}
Structure array
How to represent some student records with the same structure? Like the previous basic data types, structures also have arrays.
#include <stdio.h>
struct student{
char name[32];//full name
int age;//Age
char gender;//Gender
long long id;//Student number
};
typedef struct student STUDENT;
int main(){
STUDENT stu[3] = {{"Zhang San",18,'w',1001},
{"Li Si",19,'m',1002},
{"Wang Wu",20,'w',1003}};
return 0;
}
Bytes occupied by structure
Let's practice by ourselves and run the following code. What will you find?
(memory alignment)
#include <stdio.h>
struct test{
char ch;
int a;
short b;
};
int main(){
printf("%d",sizeof(test));
return 0;
}
Linked list
When we need to store a series of data with the same meaning, we will use the array according to the previous knowledge, but the array must first define the number of array elements. Is there a structure that can be used to achieve dynamic data growth when we don't know how many data elements there are? This is the linked list we are going to learn today.
Structure of linked list
As the name suggests, a linked list connects data like a chain.
As can be seen from the figure, the linked list is composed of nodes one by one. Each node is divided into two parts
- Data field: used to store node data
- Pointer field: used to point to the next node
Therefore, you need to use a structure. A simple linked list structure is defined as follows:
struct link {
int data;//Data domain
struct link *next;//Pointer field. Next means the pointer to the next link structure
};
The special storage structure of the linked list determines the special access mode to the linked list data, that is, the single linked list can only be accessed sequentially, not randomly. If you want to access a single linked list, you must first find the head of the linked list.
The head of the linked list is represented by the head pointer, so the structure diagram of a complete linked list is as follows:
About header nodes:
Header pointer:
- Head pointer refers to the pointer to the first node. If the linked list has a head node, it refers to the pointer to the head node
- The head pointer has the function of identification, so the commonly used head pointer is preceded by the name of the linked list (the name of the pointer variable)
- Whether the linked list is empty or not, the header pointer is not empty
- The header pointer is a necessary element of the linked list
Header node:
- The header node is set up for the unification and convenience of operation (for example, when using header interpolation). If it is placed before the node of the first element, its data field is generally meaningless (but it can also store the length of the linked list)
- You can have no header node
Single linked list of the leading node:
Single linked list without leading node:
Establishment of single linked list by head interpolation (no leading node)
The linked list structure is as follows:
struct Node {
int data;//Data domain
struct Node *next;//Pointer field. Next means the pointer to the next link structure
};
typedef struct Node node;
-
Define a pointer to the Node structure, which is the header pointer.
node *head; head = NULL;//Pointing to NULL means pointing to NULL
-
Define and initialize a node pnew, and point the head to the node
node *pnew;//New node pnew = (node *)malloc(sizeof(node));//Allocate memory for nodes pnew->next = NULL;//First set the next of the new node to NULL; if(pnew == NULL){ printf("insufficient memory"); exit(0); }Because the single linked list we created does not take the lead node, there are two situations for header insertion: one is when inserting the first node, and the other is when inserting other nodes.
if(head == NULL){ head = pnew;//Point the head pointer to the new node }The second node is inserted into the linked list, as shown in the figure below:
Let's think about whether operation a or operation b comes first in the process of inserting the second node into the linked list?
pnew->next = head;//pnew points to the node that head points to head = pnew;//The head pointer points to pnew
After that, the node insertion process is the same as the second insertion process.
The insertion of nodes is the same as this process.
Summarize the process of establishing a single linked list:
- The header pointer needs to be defined, and memory needs to be allocated for the node when initializing the node.
- Note that each node also points to the header pointer. It is recommended to draw a picture to understand.
- Point the last node to NULL.
Node deletion
Suppose there is a linked list as shown in the figure
cur node is the node we want to delete. How can we delete it?
Only one line of code is needed. However, when creating the linked list, we allocate memory for each node, so we should also free the memory when deleting the node and use the free() function to free the memory.
pre->next = cur->next;//Let the pointer field of the previous node point to the next node of the node to be deleted free(cur);//Free memory for deleting nodes
Expansion: circular linked list and bidirectional linked list
Circular linked list
Changing the pointer end of the last node in the single linked list from pointing to NULL to pointing to the head node (or the first node) will make the whole single linked list form a ring. This head to tail connected single linked list is called circular linked list, which is called circular linked list for short. Like the one-way linked list, the circular linked list does not necessarily have a head node, but the circular linked list with a head node makes the processing of empty linked list and non empty linked list consistent.
Bidirectional linked list
Double linked list is to set a pointer field to its predecessor node in each node of the single linked list. A two-way linked list has two pointer fields, one to the predecessor and the other to the successor. Its structure can be designed as:
typedef struct DulNode
{
int data;
struct DulNode * prev;
struct DulNode * next;
}DulNode,
typedef DulNode * pDuLinkList;
Bidirectional linked list can be traversed in reverse.