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

This article mainly explains "how to realize the two-way leading circular linked list in the data structure of C language". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn how to realize the two-way leading circular linked list in the data structure of C language.

I. concept

Let's draw a picture and review it in general:

In fact, there are a total of 8 kinds of linked lists, all of which are one-way or two-way, with or without lead and with or without a ring.

What I want to learn today is a two-way-lead-circular linked list. When I hear the name, I feel that the structure is very complex, which is much more complex than the one-way-no-lead-non-circular linked list. Let's draw a picture and feel it as a whole:

Explanation:

Bidirectional: make sure there are two pointers next and prev for each data. Next points to the next node, prev points to the previous node

Lead: the head node with a sentinel bit is at the front of the data.

Loop: the next of the tail node points to the head node of the sentinel bit, while the prev of the previous node of the sentry bit points to the tail node, forming a loop.

The text begins:

2. necessary work 2.1. Create a two-way linked list structure.

Because it is a two-way linked list, there must be two pointers in the structure, one next to the next node and one prev to the previous node.

List.h file:

/ / create a bi-directional linked list structure typedef int LTDataType; / / to facilitate subsequent changes to the data type. In this article, the int integer type is used as the main typedef struct ListNode {LTDataType data; / / storing data struct ListNode* next; / / pointing to the next struct ListNode* prev; / / pointing to the previous} LTNode; / / for subsequent use. There is no need to repeat some struct2.2 and initialize the linked list.

Train of thought:

The address should be passed during initialization, because the change of the parameter will not affect the argument, and the change of pphead will not affect the pList. If you want to pass the address of the pList and receive it with * * pphead, it is time for the assert assertion, because the secondary pointer address cannot be empty. Because it is a two-way circular linked list, point both the next and prev of the created Sentinel node to yourself.

List.h file: (1)

/ / initialize linked list (second-level pointer version) void ListInit (LTNode* pphead)

List.c file: (1)

/ / initialize the linked list (second-level pointer version) void ListInit (LTNode** pphead) {/ / pass the second-level pointer, of course, assert assert (pphead); * pphead = BuyLTNode (0); / / since it is a header node with a sentry position, it is necessary to give a node at the beginning / / in order to loop, let the next and prev of the sentinel point to themselves (* pphead)-> next = * pphead / / pay attention to priority, * pphead should be parenthesized (* pphead)-> prev = * pphead;}

Note:

In the previous method, we passed a second-level pointer, so can we pass a first-level pointer? in fact, it is also possible, just write a function to return the pointer.

List.h file: (2)

/ / initialize linked list (first-level pointer version) LTNode* ListInit ()

List.c file: (2)

/ / initialize the linked list (first-level pointer version) LTNode* ListInit () {LTNode* phead = BuyLTNode (0); phead- > next = phead; phead- > prev = phead; return phead;} 2.3.dynamically apply for node

List.c file:

/ / create a new node LTNode* BuyLTNode (LTDataType x) {LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); if (newnode = = NULL) {printf ("malloc fail\ n"); exit (- 1);} newnode- > data = x; newnode- > next = NULL; newnode- > prev = NULL; return newnode / / return the newly created node} 2.4, print the linked list

Train of thought:

Since it is printing, first of all, we need to understand that the sentinel is not used to store valid data, so there is no need to print, define a cur pointer to iterate, then you should start printing from the next of phead, and stop when cur walks through and returns to phead.

List.h file:

/ / print linked list void ListPrint (LTNode* phead)

List.c file:

/ print linked list void ListPrint (LTNode* phead) {assert (phead); / / assert LTNode* cur = phead- > next; while (cur! = phead) {printf ("% d", cur- > data); cur = cur- > next;} printf ("\ n");} 2.5. destroy the linked list

Train of thought:

Since the linked list is destroyed, it is natural to destroy all the elements of the linked list, including the sentinel bit, but after all, the phead cannot be empty at the beginning, so it is necessary to assert that you can destroy the sentinel bit after destroying all valid data.

Law one: traversing

Define a pointer cur, start with the first valid data in the next of phead, free, save the next, and then free, traverse in turn

Method 2: attach ListErase function

This method is also OK, but every time the Erase is finished, the front and rear nodes will be linked again. Although it will be destroyed in the end, the duck does not need to be superfluous. It is better to adopt method one directly.

List.h file:

/ / destroy linked list void ListDestory (LTNode* phead)

List.c file:

/ destroy linked list void ListDestory (LTNode* phead) {assert (phead); LTNode* cur = phead- > next; / / destroy data from the first node to the tail while (cur! = phead) {LTNode* next = cur- > next; / / ListErase (cur); free (cur); cur = next } / / empty sentinel node phead free (phead); phead = NULL;}

Test.c file:

Void TestList7 () {LTNode* pList = ListInit (); for (int I = 1; I prev- > next = newnode; newnode- > prev = pos- > prev; / / Link right newnode- > next = pos; pos- > prev = newnode;}

Test.c file:

Void TestList3 () {LTNode* pList = ListInit (); for (int I = 1; I prev; / / find the tail node to facilitate subsequent insertion of data LTNode* newnode = BuyLTNode (x); / / create a new node / / link this newly inserted tail node with the previous node tail- > next = newnode; newnode- > prev = tail / / Link the tail node to the sentinel phead to form a loop newnode- > next = phead; phead- > prev = newnode;}

Test.c file:

Void TestList1 () {/ / initialize (method 1) / * LTNode* pList = NULL; ListInit (& pList); * / / initialize (method 2) LTNode* pList = ListInit (); for (int I = 1; I next), when the data is inserted before it, is the header inserted soon, as shown below:

List.h file:

/ / insert void ListPushFront (LTNode* phead, LTDataType x)

List.c file:

/ / void ListPushFront (LTNode* phead, LTDataType x) {assert (phead); ListInsert (phead- > next, x);}

Test.c file:

Void TestList4 () {LTNode* pList = ListInit (); for (int I = 1; I next; / / Link prev and next together prev- > next = next; next- > prev = prev; / / free release free (pos); pos = NULL;}

Test.c file:

Void TestList5 () {LTNode* pList = ListInit (); for (int I = 1; I next! = phead); / / prevent the linked list from being empty, resulting in deletion of the sentinel node LTNode* tail = phead- > prev; LTNode* tailPrev = tail- > prev; / / release tail node free (tail); tail = NULL; / / cycle the linked list tailPrev- > next = phead Phead- > prev = tailPrev;}

Test.c file:

When void TestList2 () {LTNode* pList = ListInit (); for (int I = 1; I prev), whether the tail node is deleted is the tail node. Therefore, the tail deletion should be written as follows:

List.c files: 2.0

/ / tail delete void ListPopBack (LTNode* phead) {assert (phead); / / it has sentinel bit and cannot be empty, so assert assert (phead- > next! = phead); / / prevent the linked list from being empty, resulting in deletion of Sentinel node ListErase (phead- > prev);} header deletion

Train of thought:

With the above warning, we can directly use the previously written function to delete data at pos. When pos is phead- > prev, the position of pos is the tail, and what is deleted is the tail. Of course, it is important to note that additional assert assertions are required to prevent deleted data from being sentinel nodes.

List.h file:

/ / head deletion void ListPopFront (LTNode* phead)

List.c file:

/ / header deletion void ListPopFront (LTNode* phead) {assert (phead); assert (phead- > next! = phead); / / prevent deletion of Sentinel node ListErase (phead- > next);}

Test.c file:

Void TestList6 () {LTNode* pList = ListInit (); for (int I = 1; whether I data is the searched data x, if so, cur is returned, otherwise continue (cur=cur- > next), and NULL is returned if it cannot be found.

List.h file:

/ / linked list lookup LTNode* ListFind (LTNode* phead, LTDataType x)

List.c file:

/ / find LTNode* ListFind (LTNode* phead, LTDataType x) {assert (phead); LTNode* cur = phead- > next; while (cur! = phead) {if (cur- > data = = x) {return cur; / / return cur} cur = cur- > next when found } return NULL; / / return empty} IV. General code List.h file # pragma once#include#include#include// to create a two-way linked list structure typedef int LTDataType; / / to facilitate subsequent changes to the data type. This article uses the int integer as the main typedef struct ListNode {LTDataType data; / / store data struct ListNode* next; / / points to the next struct ListNode* prev / / pointing to the previous} LTNode; / / for subsequent use, there is no need to repeat some struct / / initialize the linked list (second-level pointer version) / * void ListInit (LTNode** pphead); * / / initialize the linked list (first-level pointer version) LTNode* ListInit (); / / print the linked list void ListPrint (LTNode* phead); / / find the linked list LTNode* ListFind (LTNode* phead, LTDataType x); / / destroy the linked list void ListDestory (LTNode* phead) / / insert void ListPushBack (LTNode* phead, LTDataType x); / delete void ListPopBack (LTNode* phead); / / insert void ListPushFront (LTNode* phead, LTDataType x); / / insert void ListPopFront (LTNode* phead); / / insert data void ListInsert (LTNode* pos, LTDataType x) before pos; / / delete data void ListErase (LTNode* pos) at pos List.c file # define _ CRT_SECURE_NO_WARNINGS 1#include "List.h" / / create a new node LTNode* BuyLTNode (LTDataType x) {LTNode* newnode = (LTNode*) malloc (sizeof (LTNode)); if (newnode = = NULL) {printf ("malloc fail\ n"); exit (- 1);} newnode- > data = x; newnode- > next = NULL Newnode- > prev = NULL; return newnode; / / returns the newly created node} / / initialize the linked list (second-level pointer version) / * void ListInit (LTNode** pphead) {/ / pass the second-level pointer, of course, assert assert (pphead); * pphead = BuyLTNode (0) / / because it is the head node with the sentry position, it is necessary to give a node at the beginning / / in order to loop, let the next and prev of the sentry point to themselves (* pphead)-> next = * pphead; / / pay attention to the priority, and * pphead to add parentheses (* pphead)-> prev = * pphead;} * / / initialize the linked list (first-level pointer version) LTNode* ListInit () {LTNode* phead = BuyLTNode (0) Phead- > next = phead; phead- > prev = phead; return phead;} / / print linked list void ListPrint (LTNode* phead) {assert (phead); / / assert LTNode* cur = phead- > next; while (cur! = phead) {printf ("% d", cur- > data); cur = cur- > next } printf ("\ n");} / / linked list lookup LTNode* ListFind (LTNode* phead, LTDataType x) {assert (phead); LTNode* cur = phead- > next; while (cur! = phead) {if (cur- > data = = x) {return cur / / return cur} cur = cur- > next;} return NULL; / / if not found, return empty} / / destroy the linked list void ListDestory (LTNode* phead) {assert (phead); LTNode* cur = phead- > next / / destroy data from the first node to the tail while (cur! = phead) {LTNode* next = cur- > next; / / ListErase (cur); free (cur); cur = next;} / / empty sentinel node phead free (phead); phead = NULL } / / insert void ListPushBack (LTNode* phead, LTDataType x) {assert (phead); / / assert to prevent the header node from being empty / * method 1: LTNode* tail = phead- > prev; / / find the tail node to facilitate subsequent insertion of data LTNode* newnode = BuyLTNode (x) / / create a new node / / Link the newly inserted tail node to the previous node tail- > next = newnode; newnode- > prev = tail; / / Link the tail node to the sentinel phead to form a loop newnode- > next = phead; phead- > prev = newnode; * / / method II: ListInsert (phead, x) } / / tail deletion void ListPopBack (LTNode* phead) {assert (phead); / / has sentinel bit and cannot be empty, assert assert (phead- > next! = phead); / / prevent the linked list from being empty, resulting in deletion of sentinel node / * method 1: LTNode* tail = phead- > prev; LTNode* tailPrev = tail- > prev; / / release tail node free (tail) Tail = NULL; / / Loop the linked list tailPrev- > next = phead; phead- > prev = tailPrev; * / / method II: ListErase (phead- > prev);} / / insert void ListPushFront (LTNode* phead, LTDataType x) {assert (phead); ListInsert (phead- > next, x);} / / head delete void ListPopFront (LTNode* phead) {assert (phead) Assert (phead- > next! = phead); / / prevent deletion of sentinel node ListErase (phead- > next);} / / insert data void ListInsert (LTNode* pos, LTDataType x) {assert (pos) before pos; / / create new node LTNode* newnode = BuyLTNode (x); / / link left pos- > prev- > next = newnode; newnode- > prev = pos- > prev / / newnode- > next = pos; pos- > prev = newnode;} / delete data void ListErase (LTNode* pos) {assert (pos) at pos; / / define two pointers to save nodes on both sides of pos LTNode* prev = pos- > prev; LTNode* next = pos- > next; / / Link prev and next prev- > next = next Next- > prev = prev; / / free release free (pos); pos = NULL;} Test.c file # define _ CRT_SECURE_NO_WARNINGS 1#include "List.h" void TestList1 () {/ / initialize (method I) / * LTNode* pList = NULL; ListInit (& pList); * / initialize (method II) LTNode* pList = ListInit () For (int I = 1; I

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.