Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "what are the operation methods of C language headless one-way non-cyclic linked list". The editor shows you the operation process through actual cases, the operation method is simple, fast and practical. I hope this article "what are the operation methods of C language headless one-way non-circular linked list" can help you solve the problem.

Linked list introduction

Q: last time we looked at the sequence table, what are the advantages and disadvantages of the sequence table?

Advantages:

The sequence table is a continuous physical space that facilitates random access to the subscript.

Disadvantages:

1. Capacity increase requires applying for new space, copying data, and freeing up old space. There will be a certain amount of consumption.

two。 When inserting or deleting data in the head or middle position, it is inefficient to move the data.

3. There may be a certain amount of space occupied, wasted space, and can not be applied for and released on demand.

In order to solve the problem of appeal, we introduce a linked list. First of all, let's look at the single linked list.

Introduction to linked list

Linked list is a kind of non-continuous and non-sequential storage structure in physical storage structure, and the logical order of data elements is realized through the pointer link order in the linked list. The linked list consists of a series of nodes (each element in the linked list is called a node), and the node can be generated dynamically at run time. Each node consists of two parts: one is the data field in which the data elements are stored, and the other is the pointer domain in which the address of the next node is stored.

In fact, linked lists have a variety of structures, as follows:

1. Unidirectional or bidirectional

two。 Take the lead or not

3. Cyclic or non-cyclic

Create a linked list

Linked lists are made up of node links, so creating a linked list requires the creation of a node type.

Typedef int SLTDataType;typedef struct SListNode {SLTDataType data;// is used to store the data of the node struct SListNode* next;// is used to store the address of the next node} SListNode; print linked list

Start at the position where the head pointer points, print backwards in turn, and end the loop until cur accesses the NULL.

Void SListPrint (SListNode* phead); void SListPrint (SListNode* phead) {SListNode* cur = phead;// We don't usually change the header pointer, so we assign the header pointer to the cur while (cur) / / linked list end condition {printf ("% d->", cur- > data); cur = cur- > next;} printf ("NULL\ n") / / indicates that the data has been printed} create a node

Whenever we need to insert a data, we need to apply for a node, and it will be troublesome to reapply each time, so we will create a new node and encapsulate it as a function.

SListNode* BuySListNode (SLTDataType x) {SListNode* newnode = (SListNode*) malloc (sizeof (SListNode)); if (newnode = = NULL) {printf ("BuySListNode::%s\ n", strerror (errno)); / / if the application fails, print the error message exit (- 1);} else {newnode- > data = x / / assign data to the data field of the new point newnode- > next = NULL;// the pointer field of the new node is set to null pointer} return newnode;// returns the address of the new node} single chain footer insertion

We need to divide the tail insertion into two situations:

Case 1: the linked list is empty, so we just let the header pointer point to the new node.

Case 2: the linked list already has multiple nodes, we need to find the last node of the linked list, and then let the last node point to the new node.

Void SListPushBack (SListNode** pphead, SLTDataType x); void SListPushBack (SListNode** pphead, SLTDataType x) {assert (pphead); SListNode* newnode = BuySListNode (x); / / empty if (* pphead = = NULL) {* pphead = newnode / / header pointer to the new node} / / the linked list is not empty else {SListNode* tail = * pphead; while (tail- > next! = NULL) {tail = tail- > next;} tail- > next = newnode;}}

Note: for the parameters of the chain header insert function, we should pass the address of the header pointer, not the header pointer itself. If the call is to pass a value, then the parameter is a temporary copy of the argument, and changes to the parameter will not affect the argument.

Single chain watch head insert

When the single-chain table is inserted, we apply for a new node, then let the pointer field of the new node point to the previous first node, and then let the head pointer point to the new node.

Note: the order of these two steps cannot be reversed. If you let the header pointer point to the new node first, it will be impossible to find the location of the first node. It's impossible to find the rest of the data.

Void SListPushFront (SListNode** pphead, SLTDataType x); void SListPushFront (SListNode** pphead, SLTDataType x) {assert (pphead); SListNode* newnode = BuySListNode (x); newnode- > next = * pphead; * pphead = newnode;} single linked trailer deletion

Demonstrate a wrong way of writing:

For the tail deletion of a single linked list, we need to consider three situations:

1. When the linked list is empty, no processing is done.

two。 When the linked list has only one node, release the node and set the header pointer to null.

3. When a linked list has multiple nodes, there are two processing methods, as detailed in the code.

Code 1: find the previous node of the last node and release the last node. Sets the pointer field of the previous node to a null pointer.

Void SListPopBack (SListNode** pphead); void SListPopBack (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) return; else if ((* pphead)-> next = = NULL) {free (* pphead); * pphead = NULL;} else {SListNode* prev = NULL SListNode* tail = * pphead; while (tail- > next! = NULL) {prev = tail; tail = tail- > next;} free (tail); tail = NULL; prev- > next = NULL;}}

Code 2: find the previous node of the last node, release the latter node, and then leave it empty.

Void SListPopBack (SListNode** pphead); void SListPopBack (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) return; else if ((* pphead)-> next = = NULL) {free (* pphead); * pphead = NULL;} else {SListNode* tail = * pphead While (tail- > next- > next! = NULL) {tail = tail- > next;} free (tail- > next); tail- > next = NULL;}} single chain header deletion

If the linked list is empty, it is not processed. If the linked list is not empty, let the header pointer point to the second node and release the first node.

Void SListPopFront (SListNode** pphead); void SListPopFront (SListNode** pphead) {assert (pphead); if (* pphead = = NULL) / / the linked list is empty return; else {SListNode* head = * pphead; * pphead = head- > next;// lets the address in the header pointer domain point to the header pointer free (head) / / release the first node head = NULL;}} insert data before the pos location

If pos is the first node, we directly call the header that was written before. If pos is not the first node, we find the previous node in the pos location, let the new node point to the node with the address pos, and then let the previous node point to the new node.

Void SListInsertBefore (SListNode** pphead, SListNode* pos, SLTDataType x); void SListInsertBefore (SListNode** pphead, SListNode* pos, SLTDataType x) {assert (pphead); assert (pos); if (* pphead = = pos) {SListPushFront (pphead,x); / / header function} else {SListNode* prev = * pphead While (prev- > next! = pos) / / find the previous node of pos {prev = prev- > next;} SListNode* newnode = BuySListNode (x); newnode- > next = prev- > next;// let the new node point to pos node prev- > next = newnode / / Let the previous node point to the new node}} insert data after the pos location

Let the new node point to the next location of the location, and then let the node of that location point to the new node.

Void SListInsertAfter (SListNode** pphead, SListNode* pos, SLTDataType x); void SListInsertAfter (SListNode** pphead, SListNode* pos, SLTDataType x) {assert (pphead); SListNode* newnode = BuySListNode (x); newnode- > next = pos- > next; pos- > next = newnode;} delete pos location node

Void SListErase (SListNode** pphead, SListNode* pos); void SListErase (SListNode** pphead, SListNode* pos) {assert (pphead); assert (pos); if (* pphead = = pos) {SListPopFront (pphead);} else {SListNode* prev = * pphead While (prev- > next! = pos) {prev = prev- > next;} prev- > next = pos- > next; free (pos); pos = NULL;}} delete the node after pos location

Void SListEraseAfter (SListNode* pos); void SListEraseAfter (SListNode* pos) {assert (pos); SListNode* next = pos- > next; if (next) / / if next is not empty, the condition is true {pos- > next = next- > next;// to point pos to the next node free (next) at the location to be deleted / / release the next node of pos next = NULL;}} destroy the linked list

When destroying the linked list. First, we assign the header pointer to a new pointer, use the pointer to traverse the linked list in turn, first save the address of the next node of the node, then release the node, and finally set the header pointer to null.

Note: be sure to save the address of the next node of the pointer before releasing it, otherwise the next node will not be found.

Void SListDestroy (SListNode** pphead); void SListDestroy (SListNode** pphead) {assert (pphead); SListNode* cur = * pphead; while (cur) {SListNode* next = cur- > next;// to store the next node address free (cur); / / release the current node cur = NULL;} * pphead = NULL SListNode* SListFind (SListNode* phead, SLTDataType x) {SListNode* cur = phead; while (cur! = NULL) {if (cur- > data = = x) {return cur;} cur = cur- > next;} return NULL } on the "C language headless one-way non-circular linked list what are the operation methods" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

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.