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

This article mainly explains "what is the chain storage structure of c language linear table". 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 "what is the chain storage structure of c language linear table"!

Header pointer: the storage location of the first node in the linked list is called the header pointer.

Header node: a node that does not store any data in front of the first node.

The difference between the head node and the head pointer:

1. The head pointer refers to the pointer of the linked list to the first node. If the linked list has a header node, it is the pointer to the header node.

2. The head pointer has the function of identification, so the common head pointer is crowned with the name of a linked list.

3. Whether the linked list is empty or not, the header pointer is not empty. The head pointer is a necessary element of the linked list.

4. The header node is set up for the unity and convenience of operation. If it is placed before the borrowing point of the first element, its data field is generally meaningless (the length of the linked list can also be stored)

5. With the header node, for inserting the node before the first element node and deleting the first node, other operations are unified with those of other nodes.

6. The header node is not necessarily a necessary element of the linked list

The text description is still very abstract, let's look at the picture, this is more intuitive:

After sorting out these concepts, we begin to implement the basic operation of the single linked list in C language (here we will realize and distinguish the similarities and differences between the leading node and the non-leading node):

Preparation: define the node type, some declarations:

# pragma once

# define ElemType int

# define TRUE 1

# define FALSE 0

# define OK 1

# define ERROR 0

Typedef int Status

Typedef int DataType

/ / define node type

Typedef struct Node

{

ElemType data

Struct Node * next

} SeqNode

Typedef struct Node * LinkList; / / define pointer type

Initialize:

/ / initialize the lead node and establish an empty linked list with only the header node. The data field of the header node records the length of the table, and the length of the header node is not included.

/ / return OK for successful initialization and ERROR for failure

Status Init_Head_SeqNode (LinkList * Head)

{

* Head = (LinkList) malloc (sizeof (SeqNode))

If ((* Head) = = NULL)

{

Printf ("out of memory\ n")

Return ERROR

}

(* Head)-> next = NULL

(* Head)-> data = 0

Return OK

}

/ / initialize without leading nodes, and create an empty linked list with only header nodes

Status Init_SeqNode (LinkList * Head)

{

* Head = NULL

Return TRUE

}

Head insertion: the following are the head insertion methods of the lead node and the non-lead node, directly on the code, which may be a little abstract. I have drawn some pictures to help you understand. I hope I can also help you understand:

The head insertion of the leading node:

The head insertion of a node without a lead:

Header code:

/ / lead node header insertion. TRUE is returned for successful insertion, and ERROR is returned for failure.

Status Insert_Head_Fr (LinkList Head,ElemType x)

{

LinkList new_node; / / Save the node of the new application

New_node = (LinkList) malloc (sizeof (Node))

If (NULL = = new_node)

{

Printf ("out of memory\ n")

Return FALSE

}

New_node- > data = x; / / assign the value to be inserted to the data field of the newly applied node

New_node- > next = Head- > next; / / first step: assign the next element of the header node, that is, the address of the first node, to the new node

Head- > next = new_node; / / step 2: assign the newly applied node to the header node

(Head- > data) + +; / / the data field of the header node of the leading node is used to hold the number of linked lists, adding 1 for each element added.

Return TRUE

}

/ / head insertion without leading node. TRUE is returned for successful insertion, and FALSE is returned for failure.

Status Isert_No_Head_Node (LinkList * Head,ElemType x)

{

LinkList new_node; / / Save the node of the new application

New_node = (LinkList) malloc (sizeof (Node))

If (NULL = = new_node)

{

Printf ("out of memory\ n")

Return FALSE

}

New_node- > data = x

New_node- > next = (* Head)

/ / first step: let the newly applied node point to the first meta node, because the link header pointer without the header node saves the address of the primitive node, so you need to assign the value like this.

(* Head) = new_node; / / step 2: point the header pointer to the node of the new application.

Return TRUE

}

Tail insert: I also give some pictures that I have drawn by myself:

Tail insertion of the lead node:

Tail insertion without leading nodes:

Tail-in code:

/ * when inserting tail without lead node and lead node, some people will think that there is no difference between the two.

* * I think you may have overlooked the difference between the two inserts when there are no elements in the linked list.

, /

/ / lead the node to insert at the end. TRUE is returned for successful insertion, and ERROR is returned for failure.

Status Insert_Head_Ba (LinkList Head,ElemType x)

{

LinkList new_node; / / Save the node of the new application

LinkList temp = Head; / / find the tail node

New_node = (LinkList) malloc (sizeof (Node))

If (NULL = = new_node)

{

Printf ("out of memory\ n")

Return FALSE

}

/ / use temporary variables to traverse all the linked lists to find the tail node. Because temp itself points to the next of the current node, when temp equals NULL, it reaches the last node of the linked list.

While (NULL! = temp- > next)

{

Temp = temp- > next

}

New_node- > data = x

New_node- > next = NULL

Temp- > next = new_node

Head- > data++; / / the data field of the header node of the lead node is used to hold the number of linked lists. Add 1 for each element added.

Return TRUE

}

/ / No lead node is inserted at the end. TRUE is returned if the insertion is successful, and ERROR is returned if failure occurs.

Status Insert_No_Head_Ba (LinkList * Head,ElemType x)

{

LinkList new_node

LinkList temp = (* Head); / / protect the header pointer

New_node = (LinkList) malloc (sizeof (Node)); / / allocate space for the newly applied node

If (NULL = = new_node)

{

Printf ("out of menory\ n")

Return FALSE

}

If (NULL = = (* Head)) / / empty linked list

{

New_node- > next = NULL

New_node- > data = x

(* Head) = new_node

Return TRUE

}

Else

{

/ / use temporary variables to traverse all the linked lists to find the tail node. Because temp itself points to the next of the current node, when temp equals NULL, it reaches the last node of the linked list.

While (NULL! = temp- > next)

{

Temp = temp- > next

}

New_node- > data = x

New_node- > next = NULL

Temp- > next = new_node

Return TRUE

}

}

Insert by location: also look at the picture first:

Insert the lead node by position:

Insert the node according to the position without leading:

/ / the lead node is inserted according to the position, such as the element, the head node is not included in the position, and the insertion time is divided into empty linked list and non-empty linked list, so all operations are the same because of the leading node.

/ / TRUE is returned if the insertion succeeds, and the data element of the header node is added by 1, and the FALSE is returned if the insertion fails.

Status Insert_Head_Pos_SeqNode (LinkList Head, ElemType x, int pos)

{

LinkList temp = Head; / / protect header pointer

LinkList temp_pre = Head; / / Save the pos location address of the location

LinkList new_node

New_node = (LinkList) malloc (sizeof (Node)); / / allocate space for the newly applied node

If (NULL = = new_node)

{

Printf ("out of memory\ n")

Return FALSE

}

If (pos > Head- > data)

{

Printf ("insert position error,% d cannot be inserted\ n", x)

Return FALSE

}

/ / find the node where you want to put the data through traversal, but because the current node of the single linked list can only find the next node.

/ / when inserting data, you need to know the location of the current node, so you need to define a variable to hold the previous node of the current previous node.

For (int I = 0; I

< pos;i++) { temp = temp->

Next

Temp_pre = temp_pre- > next

}

New_node- > data = x; / / assign a value to the data field of the newly applied node

New_node- > next = temp

/ / first step: first point the new node to the location to be inserted, that is, the location where the previous node of the current node is saved

Temp_pre- > next = new_node; / / step 2: let the previous node of the current node point to the new node

Head- > data++; / / inserted successfully, add 1 to the number of linked lists

Return TRUE

}

/ / inserting by position without leading nodes is divided into two cases. If it is an empty linked list, it is necessary to modify the direction of the head pointer, then to modify the pointer, it is necessary to use the secondary pointer to receive.

/ / if it is not an empty linked list, you only need to traverse the linked list to find the location. In both cases, consider whether the insertion position is correct.

/ / TRUE is returned for successful insertion, and FALSE is returned for failed insertion.

Status Inser_No_Head_Pos_SeqNode (LinkList * Head, int pos, ElemType x)

{

Int Num = 0; / / calculate the total number of nodes in the linked list

LinkList temp = (* Head); / / protect the header pointer

LinkList temp_pre = (* Head); / / Save the address of the pos location

LinkList new_node

New_node = (LinkList) malloc (sizeof (Node)); / / allocate space for the newly applied node

If (NULL = = new_node) / / prevent memory opening failure

{

Printf ("out of memory\ n")

Return FALSE

}

/ / handle the case of empty linked list

If (NULL = (* Head))

{

If (pos > 0)

{

Printf ("insert position error,% d cannot be inserted\ n", x)

Return FALSE

}

Else

{

New_node- > data = x; / / assign values to the opened new nodes

New_node- > next = NULL; / / first step: let the newly applied node point to the next node of the node to be inserted

(* Head) = new_node; / / Let the header pointer point to the new node

Return TRUE

}

}

/ / handle the case of non-empty linked list

Else

{

/ / find the node where you want to put the data through traversal, but because the current node of the single linked list can only find the next node.

/ / when inserting data, you need to know the location of the current node, so you need to define a variable to hold the previous node of the current previous node.

While (NULL! = temp)

{

Num++

Temp = temp- > next

}

If (pos+1 > Num) / / if the insertion position is wrong, jump out directly

{

Printf ("insert position error,% d cannot be inserted\ n", x)

Return FALSE

}

Else if (0 = = pos)

{

New_node- > data = x; / / assign values to the opened new nodes

New_node- > next = (* Head)

(* Head) = new_node

}

Else

{

/ / when the traversal determines that the location of the pos is correct, the pointing of several pointers has changed. You need to re-point to the head pointer and traverse to find the node to be inserted.

Temp = * Head

For (int I = 0; I

< pos - 1; i++) //定位到要删除的结点的前一个结点 { temp = temp->

Next

}

New_node- > data = x; / / assign values to the data fields of the new node

New_node- > next = temp- > next

/ / first step: first point the new node to the location to be inserted, that is, the location where the previous node of the current node is saved

Temp- > next = new_node; / / step 2: let the previous node of the current node point to the new node

}

}

Return TRUE

}

Head deletion: the analogy between the delete operation and the insert operation, not in drawing, the two are similar.

/ / if you delete a header without a leading node, you need to consider whether the linked list is an empty linked list, or if there is only one element, you need to delete the header, modify the direction of the header pointer, delete in other places in the same order, and put back the deleted data with x.

/ / return TRUE for successful deletion and FALSE for failure

Status Delite_No_Head_SeqNode (LinkList * Head,ElemType * x)

{

LinkList temp_node = (* Head); / / prevent the header pointer from being modified

If (NULL = = temp_node)

{

Printf ("the linked list is empty and there are no more elements to delete\ n")

Return FALSE

}

If (NULL = = temp_node- > next)

{

* x = temp_node- > data; / / put the value of the node to be deleted in x

(* Head) = NULL

Free (temp_node); / / release deleted nodes to prevent memory leaks

Temp_node = NULL

Return TRUE

}

Else / / handles the deletion of more than one node in the linked list

{

* x = temp_node- > data; / / put the value of the node to be deleted in x

* Head = temp_node- > next; / / fix the pointing of the header pointer

Free (temp_node); / / release deleted nodes to prevent memory leaks

Temp_node = NULL

Return TRUE

}

}

/ / the header deletion of the leading node, regardless of whether there is one element or more and elements, the deletion operation does not need to modify the header pointer to point to, so it is not necessary to modify the header pointer to point to, and use x to put back the deleted data

/ / return TRUE for successful deletion and FALSE for failure

Status Delite_Head_Fr_SeqList (LinkList Head,ElemType * x)

{

LinkList temp = Head- > next; / / defines a temporary variable to prevent the header pointer from being modified

If (NULL = = temp- > next)

{

Printf ("the linked list is empty and there are no elements deleted\ n")

Return FALSE

}

* x = temp- > next- > data; / / put the value of the node to be deleted in x

Temp = temp- > next; / / first step: point the temporary node to the next node of the node to be deleted

Free (Head- > next); / / step 2: free the memory of the first meta node to prevent memory leakage

Head- > next = temp; / / step 3: modify the direction of the header pointer

Return TRUE

}

Tail deletion: also not to show the intention: compare the picture inserted at the end.

/ / tail deletion of the lead node, because all operations of the header node are the same

Status Delite_Head_Br_SeqNode (LinkList Head,ElemType * x)

{

/ / define a temporary variable to prevent the header pointer from being modified, first point to the first meta node, and then use it to locate the last node.

/ / since the single linked list only knows the location of the next node of the current node, you need to define a variable to hold the address of the current node.

LinkList temp = Head- > next; / / locate the last pointer

LinkList temp_node_pre = Head; / / saves the address of the last node

If (NULL = = temp)

{

Printf ("the linked list is empty and there are no elements deleted\ n")

Return FALSE

}

While (NULL! = temp- > next)

{

Temp = temp- > next

Temp_node_pre = temp_node_pre- > next

}

* x = temp- > data; / / saves the value of the data field of the last node

Temp_node_pre- > next = NULL; / / modify the direction of the penultimate node of the original node

Free (temp); / / at this time, temp_node points to the last node to prevent memory leakage and free the memory of the last node.

Temp = NULL

Return TRUE

}

/ / tail deletion of no leading node, because when there is only one element in the linked list, it is necessary to modify the pointer to delete the last node, so it is necessary to use the secondary pointer to receive the header pointer and x to put back the deleted data.

/ / return TRUE for successful deletion and FALSE for failure

Status Delite_No_Head_Br_SeqNode (LinkList * Head,ElemType * x)

{

/ / define a temporary variable to prevent the header pointer from being modified, first point to the first meta node, and then use it to locate the last node.

/ / since the single linked list only knows the location of the next node of the current node, you need to define a variable to hold the address of the current node.

LinkList temp_node = (* Head)-> next

LinkList temp_node_pre = (* Head)

If (NULL = (* Head))

{

Printf ("the linked list is empty and there are no elements to delete\ n")

Return FALSE

}

While (NULL! = temp_node- > next)

{

Temp_node = temp_node- > next

Temp_node_pre = temp_node_pre- > next

}

* x = temp_node- > data; / / saves the value of the data field of the last node

Temp_node_pre- > next = NULL; / / modify the direction of the penultimate node of the original node

Free (temp_node); / / at this time, temp_node points to the last node to prevent memory leakage and free the memory of the last node.

Return TRUE

}

/ / if the lead node is deleted according to the location, we should first consider whether the deleted location exists, and then because of the lead node, whether it is an element or multiple elements, the deletion operation is the same

Status Delite_Head_Pos_SeqNode (LinkList Head,int pos, ElemType * x)

{

/ / define a temporary variable to prevent the header pointer from being modified, first point to the first meta node, and then use it to locate the last node.

/ / since the single linked list only knows the location of the next node of the current node, you need to define a variable to hold the address of the current node.

LinkList temp = Head- > next; / / locate the previous node of the node whose last pointer needs to be deleted

LinkList temp_node_pre = Head; / / Save the address of the node to be deleted

If (NULL = = temp)

{

Printf ("the linked list is empty and there are no elements deleted\ n")

Return FALSE

}

If (pos > temp_node_pre- > data) / / determine whether the deleted location exists

{

Printf ("deletion location error\ n")

Return FALSE

}

For (int I = 0; I

< pos-1;i++) //遍历链表找到链表要删除的结点的前一个结点 { temp = temp->

Next; / / locate the location to be deleted

}

* x = temp- > next- > data; / / return the value of the node to be deleted with x

Temp_node_pre = temp- > next

Temp- > next = temp- > next- > next; / / Let the previous node deleted point to the next node to be deleted

Free (temp_node_pre); / / at this time, temp_node points to the deleted node to prevent space leakage and free memory

Temp_node_pre = NULL

The Head- > data--; / / header node holds the length of the linked list. Subtract one after deletion.

Return TRUE

}

Delete by location: nor is it intended to show: compare the pictures deleted by location.

/ / No leading node is deleted according to location, because when only one node is deleted, the header pointer needs to be modified to point to it requires special processing.

Status Delite_No_Head_Pos_SeqNode (LinkList * Head, int pos, ElemType * x)

{

Int NUM = 0; / / count the total number of nodes in the linked list

/ / define a temporary variable to prevent the header pointer from being modified, first point to the first meta node, and then use it to locate the last node.

/ / since the single linked list only knows the location of the next node of the current node, you need to define a variable to hold the address of the current node.

LinkList temp = (* Head)

If (NULL = = temp)

{

Printf ("the linked list is empty and there are no elements to delete\ n")

Return FALSE

}

Else if (NULL = = temp- > next) / / handles situations where there is only one node

{

* x = temp- > data; / / return the value of the node to be deleted with x

(* Head) = NULL; / / header node is empty

Free (temp); / / Free the space of the first node to prevent memory leak

Temp = NULL; / / prevent pointing to illegal space

Return TRUE

}

Else

{

While (NULL! = temp)

{

NUM++

Temp = temp- > next

}

If (pos > NUM)

{

Printf ("delete location error")

Return FALSE

}

If (0 = = pos)

{

Temp = * Head

* x = temp- > data

* Head = temp- > next

Free (temp)

Temp = NULL

}

Else

{

/ / when the traversal determines that the location of the pos is correct, the pointing of several pointers has changed. You need to re-point to the head pointer and traverse to find the node to be inserted.

Temp = * Head

For (int I = 0; I

< pos-1; i++) { temp = temp->

Next

}

* x = temp- > next- > data; / / return the value of the node to be deleted with x

LinkList free_node = temp- > next; / / free_node to save the node to be deleted

Temp- > next = temp- > next- > next

Free (free_node); / / Free the space of the first node to prevent memory leak

Free_node = NULL

}

}

Return TRUE

}

Print out all data:

/ / lead the node to print out all the data

Status Show_Node (LinkList Head)

{

LinkList temp = Head- > next

While (NULL! = temp)

{

Printf ("d", temp- > data)

Temp = temp- > next

}

Printf ("\ n")

Return TRUE

}

/ / print out all data without leading nodes

Status Show_Node_No_Head (LinkList Head)

{

LinkList temp = Head

While (NULL! = temp)

{

Printf ("d", temp- > data)

Temp = temp- > next

}

Printf ("\ n")

Return TRUE

}

Clear the linked list: release all valid nodes. For the lead node linked list, set the data field of the head node to 0.

/ / empty the linked list without leading nodes and release all nodes

Status Clean_No_Head_SeqNode (LinkList * Head)

{

LinkList temp_node = * Head

LinkList temp_node_pre = * Head

* Head = NULL

While (NULL! = temp_node)

{

Temp_node = temp_node- > next; / / because the header node is not empty, let the temporary pointer point to the next node

Free (temp_node_pre); / / release the space of the first node

Temp_node_pre = temp_node; / / points to the next space

}

Return TRUE

}

/ / clear the chain table of the lead node to release the space except the head node

Status Clean_Head_SeqNode (LinkList Head)

{

LinkList temp_node = Head- > next

LinkList temp_node_pre = Head- > next

Head- > next = NULL

Head- > data = 0

While (NULL! = temp_node- > next)

{

Temp_node = temp_node- > next

Free (temp_node_pre)

Temp_node_pre = temp_node

}

Return TRUE

}

Sorting: for sorting, you can first use a variety of sorting methods, and then in the sorting process, I mention that you only need to swap values and not nodes. Bubbling sort is used here.

/ / sort, since you only need to exchange the values in the two linked lists, there is no need to modify the pointer, so the operation with or without leading nodes is similar, but with slight differences.

Status Sort_No_Head_SeqNode (LinkList Head)

{

LinkList temp_node_i = Head

LinkList temp_node_j = Head

LinkList temp_node_pre = Head

ElemType temp; / / use and exchange values

If (NULL = = temp_node_i)

{

Printf ("the linked list is empty and cannot be sorted\ n")

Return FALSE

}

For (temp_node_i = temp_node_i- > next; NULL! = temp_node_i; temp_node_i = temp_node_i- > next)

{

For (temp_node_j = temp_node_j; NULL! = temp_node_j; temp_node_j = temp_node_j- > next)

{

If (temp_node_j- > data > temp_node_pre- > data)

{

Temp = temp_node_j- > data

Temp_node_j- > data = temp_node_pre- > data

Temp_node_pre- > data = temp

Temp_node_pre = temp_node_pre- > next

}

Temp_node_pre = temp_node_pre- > next

}

}

Return TRUE

}

/ / sorting lead node

Status Sort_Head_SeqNode (LinkList Head)

{

LinkList temp_node_i = Head- > next

LinkList temp_node_j = Head- > next

LinkList temp_node_pre = Head- > next

ElemType temp; / / use and exchange values

If (NULL = = temp_node_i)

{

Printf ("the linked list is empty and cannot be sorted\ n")

Return FALSE

}

For (temp_node_i = temp_node_i; NULL! = temp_node_i- > next; temp_node_i = temp_node_i- > next)

{

For (temp_node_j = Head; NULL! = temp_node_j- > next; temp_node_j = temp_node_j- > next)

{

If (temp_node_j- > data > temp_node_j- > next- > data)

{

Temp = temp_node_j- > next- > data

Temp_node_j- > next- > data = temp_node_j- > data

Temp_node_j- > data = temp

}

}

}

Return TRUE

}

The above single linked list leading node and non-leading node head insertion, tail insertion, according to position insertion, head deletion, tail deletion, location deletion, empty list, sort, printout to do as detailed notes as possible, all tested, but did not give the main function, the data structure, here is not the key point, and is limited to space, so no main function is given. Of course, the above code is only my understanding, if you can find that piece of error, hope to correct it.

Finally, careful people will find that there are a lot of resent code: for example, generate a new node, locate the location to be inserted and deleted, and have a lot of duplicate code, then you can write it as a function, simplify the code, and even more, the structure of this structure is somewhat inconvenient to operate, and if you adopt the following structure, it will be more simplified and easy to understand.

Typedef struct node / / Node Type

{

Type value

Struct node * next

} Node

Typedef struct list

{

Node * phead

Node * ptail

} List

Thank you for your reading. the above is the content of "what is the linked storage structure of c language linear table". After the study of this article, I believe you have a deeper understanding of what the linked storage structure of c language linear table is. Specific use also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.