Shulou(Shulou.com)06/03 Report--

This article mainly introduces "how to understand C++ programming language to realize single linked list". In daily operation, I believe many people have doubts about how to understand C++ programming language to realize single linked list. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "how to understand C++ programming language to realize single linked list". Next, please follow the editor to study!

Catalogue

A brief introduction to the single linked list

Second, let's initialize the single linked list first.

Third, to insert and delete data from a single linked list.

A brief introduction to the single linked list

First of all, let's review the two storage methods of linear tables-sequential storage and linked storage.

The image above shows sequential storage on the left and chained storage on the right.

Before we used the array to achieve the sequence table, for the advantages and disadvantages of the sequence table, to sum up, it is convenient to find, complex to add and delete.

Advantages and disadvantages of sequential storage of linear tables

The characteristics of the linked list can be said to be on the contrary, the addition and deletion is convenient, and the search is complex.

What is implemented today is the simplest kind of linked list-single linked list (there is only one pointer field in each node).

For the linked list, we only know that the physical address of each node is discontiguous, but logically it still conforms to the "one-to-one" characteristic of the linear table. Therefore, we need to connect these discontiguous nodes sequentially with "lines" (pointers).

Nodes of linked lists are stored discontiguously in memory

Connect each node sequentially by a pointer

Here we can find that in order to represent the nodes in the linked list, just storing the data of the nodes is not enough, there must be pointers. Therefore, the node structure of the single linked list is as follows:

Data field stores data, pointer field stores pointers

/ / = single linked list storage structure of linear table = typedef struct LNode {ElemType data;// data field struct LNode * next;// pointer domain} LNode

Note: because the pointer points to each node, that is, to the custom structure type struct LNode, the pointer type is struct LNode*.

Second, let's initialize the single linked list first.

The initialization of a single linked list is actually to create several nodes and then connect them with pointers.

First create a header pointer, which is actually creating a header node, and then the header pointer points to the header node OK.

LNode* CreateList_L (int n) {/ / enter the values of n elements in order to establish a single-linked linear table with header node L LNode* p = (LNode*) malloc (sizeof (LNode)); / / create a header node (p, that is, head pointer) LNode* temp = pash / declare a pointer to the header node for traversing the linked list (not the header pointer, because it only points to the header node temporarily) / generate the linked list for (int I = n) I > 0;-- I) {LNode * node = (LNode *) malloc (sizeof (LNode)); / / create node if (node) {/ / address assignment successful scanf_s ("% c", & (node- > data); node- > next = NULL; / / establish the logical relationship between the new node and the direct precursor node temp- > next = node; temp = temp- > next } else {/ / if address allocation fails, an error message printf is returned ("Node creation failed! \ n ");}} return p;} 3. Insert and delete data from a single linked list

Data insertion in single chain table

From the observation, we can see that to implement the insert operation, we need the same operation.

S1: assign the pointer of the successor node to the pointer field of the new node

S2: change the pointer field of the precursor node to the pointer to the new node.

Note: S1 and S2 cannot be changed.

/ / = algorithm 2.9==Status ListInsert_L (LNode * L, int I, ElemType e) {/ / insert the element e int j = 0 before the I position in the single linked list L of the lead node; LNode * p = L; while

Next; + + j;} / / find the I-1st node if (! p | | j > iMur1) if the return ERROR;//i is less than 1 or greater than the table length, LNode* s = (LNode*) malloc (sizeof (LNode)); / / generate a new node s-> data = e; s-> next = p-> next;//S1 p-> next = s next S2 return OK;}

Schematic diagram of single linked list delete data

Observation shows that it is only necessary to change the value of the pointer field of the precursor node of the node to be deleted with the pointer of the subsequent node of the node to be deleted.

/ / = algorithm 2.10==Status ListDelete_L (LNode * L, int I, ElemType * e) {/ / in the single linked list L of the lead node, delete the I element and return its value LNode * p = L; int j = 0 by e; while (p-> next&&j)

Next; + + j;} if (! (p-> next) | | j > I-1) unreasonable return ERROR;// deletion position LNode * Q = p-> next; p-> next = Q-> next;// delete and release node * e = Q-> data; free (Q); return OK;} III. Reference code implementation and screenshot # single linked list storage structure of include#include#define OK 1#define ERROR 0#define OVERFLOW-2#define ElemType chartypedef int Status;//= linear table = typedef struct LNode {ElemType data / / data field struct LNode* next;// pointer field} LNode;LNode* CreateList_L (int n) {/ / enter the values of n elements in order to establish a single-linked linear table with header node L LNode* p = (LNode*) malloc (sizeof (LNode)); / / create a header node LNode* temp = ptactic / declare a pointer to the header node for traversing the linked list (not the header pointer) / / generate the linked list for (int I = n; I > 0) -- I) {LNode * node = (LNode *) malloc (sizeof (LNode)); / / create node if (node) {/ / address assignment successful scanf_s ("% c", & (node- > data); node- > next = NULL; / / establish the logical relationship between the new node and the direct precursor node temp- > next = node; temp = temp- > next } else {/ / if address allocation fails, an error message printf is returned ("Node creation failed! \ n ");}} return p;} / / = algorithm 2.9==Status ListInsert_L (LNode * L, int I, ElemType e) {/ / insert the element e int j = 0 before the I position in the single linked list L of the leading node; LNode * p = L; while

Next; + + j;} / / find the I-1st node if (! p | | j > iMur1) when return ERROR;//i is less than 1 or greater than the table length, LNode* s = (LNode*) malloc (sizeof (LNode)); / / generate a new node s-> data = e; s-> next = p-> next; p-> next = s; return OK } / / = algorithm 2.10==Status ListDelete_L (LNode * L, int I, ElemType * e) {/ / in the single linked list L of the lead node, delete the I element and return its value LNode * p = L; int j = 0 by e; while (p-> next&&j)

Next; + + j;} if (! (p-> next) | | j > I-1) unreasonable return ERROR;// deletion position LNode * Q = p-> next; p-> next = Q-> next;// delete and release node * e = Q-> data; free (Q); return OK;} void display (LNode * L) {LNode * temp = Lscape / redirects the temp pointer to the header node / / executes the output statement as long as the next of the node pointed to by the temp pointer is not Null. While (temp- > next) {temp = temp- > next; printf ("% c", temp- > data);} printf ("\ n");} int main () {LNode * L = NULL; L=CreateList_L (5); display (L); ListInsert_L (L, 2,'Y'); display (L); ElemType e; ListDelete_L (L, 2, & e); display (L); printf ("return value:% c", e); system ("pause"); return 0;}

Initialize the linked list to abcdef, insert Y in the second position, and then delete Y

At this point, the study on "how to understand the C++ programming language to achieve a single linked list" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.