1. Basic concepts:
Linked list: a non continuous and non sequential storage structure in the physical storage structure. The logical order of data elements is realized through the pointer link order in the linked list.
The linked list has 8 structures:
1. Headless one-way non circulation 2. Headless one-way circulation 3. Leading single circulation 4. Leading single non circulation
5. Headless two-way non circulation 6. Headless two-way circulation 7. Lead two-way non circulation 8. Lead two-way circulation
In practice, the most commonly used are:
Headless single item acyclic linked list:
Lead two-way circular linked list:
2. Code implementation: one way headless acyclic linked list:
2.1 preparation:
First, reference the header file and create a structure. This structure is the node of the linked list. A node contains data items and pointer items. The pointer item stores the address of the next node. (assuming the stored data is of type int)
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int DataType;
//Headless unidirectional acyclic
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SLNode;
SLNode* phead=NULL;//Create an empty linked list
2.2 basic operation of linked list
2.2. 1 tail interpolation function (insert data at the end of the linked list)
As long as you insert data, you have to malloc a new node. The data item is assigned the value you want, and the pointer item is assigned null. So first encapsulate a function that generates a new node.
SLNode* BuyNewNode(DataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}Tail interpolation function: after the new node is created. To find the tail of the linked list, insert it. There are two cases: the linked list is empty and the linked list is not empty. If it is not empty, find the tail node and then link.
void SListPushBack(SLNode** pphead, DataType x)
{
SLNode* newnode = BuyNewNode(x);
//Tail finding
//1. When the linked list is empty
if (*pphead == NULL)
{
*pphead = newnode;
}
//2. The linked list is not empty
else
{
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}Why pass the secondary pointer (* * pphead): because phead is a pointer type, it stores the address of the first node. If the linked list is empty, the value of phead needs to be changed during tail insertion. Therefore, to pass the address of phead, the address must use the secondary pointer.
2.2. 2 head insertion function (insert data at the front of the linked list)
Create a new node. If the linked list is empty, insert it directly.
The linked list is not empty:
The red arrow is the link process of else.
When the link is complete:
code:
void SListPushFront(SLNode** pphead, DataType x)
{
SLNode* newnode = BuyNewNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLNode* phead = *pphead;
*pphead = newnode;
newnode->next = phead;
}
}2.2. 3 tail deletion function
There are three situations: 1. If the linked list is empty, it will be returned directly.
2. When there is only one node, free this node directly* pphead=NULL. At first I wrote tail=NULL, which is wrong. The code comments are explained.
3. There is at least one node. To find the penultimate node and the last node, you need to find the penultimate node because after free loses the last node, the penultimate node becomes the last node, and its pointer should be set to null.
void SListPopBack(SLNode** pphead)
{
SLNode* tail = *pphead;
SLNode* prev = NULL;
//1. The linked list is empty
if (*pphead == NULL)
{
return;
}
//2. There is only one node
else if (tail->next== NULL)
{
free(tail);
*pphead= NULL;
//tail=NULL;// Both tail and * pphead point to the same block of memory. After passing the function free, this block
//The memory is returned to the operating system, tail=NULL, but * pphead still points to this memory,
//So * pphead becomes a wild pointer, so the program will report an error.
}
//3. There is at least one node
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}This figure shows the process of finding the tail node and the penultimate node in the while loop
2.2. 4 header deletion function
When the linked list is empty, it returns directly.
When the linked list is not empty, define a next node to save the address of the second node, then free the first node, and finally point * pphead to the next node.
void SListPopFront(SLNode** pphead)
{
if (*pphead == NULL)
{
return;
}
else
{
SLNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}2.2. 5 search function (find the address of the node according to the data item and return it)
Traverse the linked list.
SLNode* SListFind(SLNode** pphead, DataType x)
{
SLNode* cur = *pphead;
while (cur != NULL)//Cannot be cur - > next= Null. When cur==NULL, the program null - > next error occurs
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}2.2. 6 pre interpolation function (insert data at pos position)
1. If pos==*pphead, it means header insertion. Just call the header insertion function.
2,else. At this time, you need to find the address of the previous node in the pos location (cur here). (the red arrow in the figure shows the link process)
void SListInsert(SLNode** pphead, SLNode* pos, DataType x)
{
SLNode* newnode = BuyNewNode(x);
if (pos==*pphead)
{
SListPushFront(pphead,x);//When inserting at the first node, the header insertion function is called directly
}
else
{
//Find the previous node of pos
SLNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
//link
cur->next = newnode;
newnode->next = pos;
}
}2.2. 7 delete function (delete the node at pos position)
1. If pos=*pphead is to delete the first node, call the header deletion function
2.else. Find the previous node of pos (cur here), and then link.
When linking, you should pay attention to cur - > next = pos - > next, then free (POS), pos=NULL. If you first free (POS), you can't find the next node of POS.
code:
void SListErase(SLNode** pphead, SLNode* pos)
{
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SLNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}2.2. 8. Modify pos position data
You can traverse it once
void SListModify(SLNode** pphead, SLNode* pos, DataType x)
{
SLNode* cur = *pphead;
while (cur != pos)
{
cur = cur->next;
}
cur->data = x;
}
2.2. 9 destroy function
void SListDestory(SLNode** pphead)
{
SLNode* cur = *pphead;
while (cur != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}2.2. 10 print function
Because it is printing, there is no need to change the value of phead. So there is no need to pass the secondary pointer.
void SListPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3. Total code
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef int DataType;
//Headless unidirectional acyclic
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SLNode;
void SListPrint(SLNode* phead)
{
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLNode* BuyNewNode(DataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}
void SListPushBack(SLNode** pphead, DataType x)
{
SLNode* newnode = BuyNewNode(x);
//Tail finding
//1. When the linked list is empty
if (*pphead == NULL)
{
*pphead = newnode;
}
//2. The linked list is not empty
else
{
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLNode** pphead, DataType x)
{
SLNode* newnode = BuyNewNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLNode* phead = *pphead;
*pphead = newnode;
newnode->next = phead;
}
}
void SListPopBack(SLNode** pphead)
{
SLNode* tail = *pphead;
SLNode* prev = NULL;
//1. The linked list is empty
if (*pphead == NULL)
{
return;
}
//2. There is only one node
else if (tail->next == NULL)
{
free(tail);
*pphead = NULL;
}
//3. There is at least one node
else
{
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
void SListPopFront(SLNode** pphead)
{
if (*pphead == NULL)
{
return;
}
else
{
SLNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
SLNode* SListFind(SLNode** pphead, DataType x)
{
SLNode* cur = *pphead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
void SListInsert(SLNode** pphead, SLNode* pos, DataType x)
{
SLNode* newnode = BuyNewNode(x);
if (pos == *pphead)
{
SListPushFront(pphead, x);//When inserting at the first node, the header insertion function is called directly
}
else
{
//Find the previous node of pos
SLNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
//link
cur->next = newnode;
newnode->next = pos;
}
}
void SListErase(SLNode** pphead, SLNode* pos)
{
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SLNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListModify(SLNode** pphead, SLNode* pos, DataType x)
{
SLNode* cur = *pphead;
while (cur != pos)
{
cur = cur->next;
}
cur->data = x;
}
void SListDestory(SLNode** pphead)
{
SLNode* cur = *pphead;
while (cur != NULL)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
void menu()
{
printf("************ 1,Head insert 2. Tail insertion ************\n");
printf("************ 3,stay pos Insert data from location ************\n");
printf("************ 4,Header deletion 5. Tail deletion ************\n");
printf("************ 6,delete pos Location data ************\n");
printf("************ 7,Modify data 8. Print data ************\n");
printf("********************* -1,sign out *********************\n");
}
int main()
{
SLNode* phead = NULL;
int option = 1;
DataType x = 0;
SLNode* pos = NULL;
while (option != -1)
{
menu();
scanf("%d", &option);
switch (option)
{
case 1:
printf("Please enter the data to insert to-1 end\n");
do
{
scanf("%d", &x);
if (x != -1)
SListPushFront(&phead, x);
} while (x != -1);
break;
case 2:
printf("Please enter the data to insert to-1 end\n");
do
{
scanf("%d", &x);
if (x != -1)
SListPushBack(&phead, x);
} while (x != -1);
break;
case 3:
//Insert data in pos position
printf("Please enter the name before inserting pos Location data\n");
scanf("%d", &x);
pos = SListFind(&phead, x);
if (!pos)
{
printf("No such data\n");
}
else
{
printf("Please enter the data to insert\n");
scanf("%d", &x);
SListInsert(&phead, pos, x);
}
break;
case 4:
SListPopFront(&phead);
break;
case 5:
SListPopBack(&phead);
break;
case 6:
printf("Please enter the name before deleting pos Location data\n");
scanf("%d", &x);
pos = SListFind(&phead, x);
if (!pos)
{
printf("No such data\n");
}
else
{
SListErase(&phead, pos);
}
break;
case 7:
printf("Please enter the value of the modified position\n");
scanf("%d", &x);
pos = SListFind(&phead, x);
if (!pos)
{
printf("No such data\n");
}
else
{
printf("Please enter the value you want\n");
scanf("%d", &x);
SListModify(&phead, pos, x);
}
break;
case 8:
SListPrint(phead);
break;
case -1:
printf("sign out\n");
break;
default:
printf("Input error, please re-enter\n");
}
}
SListDestory(&phead);
return 0;
}If you have any questions, you can leave a message and comment.