Single list
- Design ideas
- Preparatory work for adding, deleting, checking and modifying
- Head plug and tail plug
- Delete the head and delete the tail
- find and destroy
- Insert the node with data x after pos and delete the node after pos
- full code
Design ideas
The linked list is a non-sequential and non-sequential storage structure in the physical storage structure. The logical order of the data elements is through the linked list The pointers in link order are implemented in .
Preparatory work for adding, deleting, checking and modifying
There are two source files and one header file:
linked.h linked.c test.c
Node Type Definition
//linked.h
typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list
typedef struct Chain_table//linked list type
{
type data;//data field
struct Chain_table* next;//pointer field
}ct;define a head node
copy//test.c ct* head = NULL;//head node pointer
The default point is empty, if there is no data, it will be empty Open up node space
//linked.c
ct* crunode(type x)//Create a node dynamically
{
ct* cur = (ct*)malloc(sizeof(ct));
if (cur == NULL)
{
perror("malloc fail");
exit(-1);//end of program
}
cur->data = x;
cur->next = NULL;
return cur;//Returns the address of the opened node
}print linked list function It cannot be asserted here whether it is a null pointer, because when there is no data, the point pointed to by the head node is a null pointer, so we also need to print the null pointer (because it is more vivid, and actually does not need to print NULL)
//linked.c
void SListPrint(ct* phead)//print linked list
{
ct* cur = phead;//Let cur also point to the location of the head pointer
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("NULL\n");//print the NULL at the end
}Head plug and tail plug
The following functions are all in the linked.c file tail plug
void SListPushBack(ct** phead, type x)//tail plug
{
assert(phead);//The assertion here is because phead points to the head node, so it cannot be empty
ct* newnode = crunode(x);
if (*phead == NULL)//head node pointer is null
{
*phead = newnode;//Let the head node point to the newly created node
}
else//Head node pointer is not null
{
ct* cur = *phead;
while (cur->next)//find the last node
{
cur = cur->next;
}
cur->next = newnode;//Let the next area of the last node store the address of the newly created node
}
}It should be noted here that the address of the head node is passed by the second-level pointer, otherwise it will cause the formal participation and actual parameters to open up two independent spaces, so that the head node will not move due to the transfer function.
In this way, the head can be controlled by phead. plug
void SListPushFront(ct** phead, type x)//plug
{
assert(phead);
ct* newnode = crunode(x);
newnode->next = *phead;
*phead = newnode;
}The head insertion does not need to be divided into situations, because even if the linked list is empty, the head insertion is to store the position pointed to by the head node in the next of the newly created node.
Delete the head and delete the tail
tail delete
void SListPopBack(ct** phead)//tail delete
{
assert(phead);
assert(*phead);//Check if it is an empty list
ct* cur = *phead;
if (cur->next == NULL)//Determine whether there is only one node left in the linked list
{
free(cur);
cur = NULL;
*phead = NULL;
}
else
{
while (cur->next->next)//Determine whether to come to the end
{
cur = cur->next;
}
free(cur->next);//cur->next->next is empty, it means that cur->next points to the last node, release it
cur->next = NULL;//Set the next of the end node to a null pointer
}
}
head delete
void SListPopFront(ct** phead)//head delete
{
assert(phead);
assert(*phead);//Check if the linked list is empty
ct* cur = *phead;
*phead = cur->next;
free(cur);//Free up head node space
cur = NULL;
}find and destroy
destroy
void SListDestory(ct** phead)//Destroy linked list
{
assert(phead);
ct* cur = *phead;
while (cur)
{
ct* tai = cur->next;//Keep the next node of cur
free(cur);
cur = tai;
}
*phead = NULL;//Finally, let the head node pointer become a null pointer
}look up When designing a search, if the return value is not equal to a null pointer, it exists
ct* SListFind(ct* phead, type x)//search
{
ct* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;//Find the corresponding address
}
cur = cur->next;
}
return NULL;//Returns a null pointer if not found
}Insert the node with data x after pos and delete the node after pos
This works with our lookup The address after the returned pos is where we want to insert and delete insert
void SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos
{
assert(pos);
ct* newnode = crunode(x);
newnode->next= pos->next;
pos->next = newnode;
}
delete
void SListEraseAfter(ct* pos)//Delete the node after pos
{
assert(pos);
if (pos->next == NULL)
{
return;//If the node behind pos is empty, just return it directly
}
else
{
ct* cur = pos->next;
pos->next = cur->next;
free(cur);
cur = NULL;
}
}As for inserting and deleting in front of pos, I don’t need to write it, just add a pointer to find the node in front of pos.
full code
linked.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int type;//Redefine the name of the data type, so that it is convenient to replace the data type in the linked list
typedef struct Chain_table//linked list type
{
type data;//data field
struct Chain_table* next;//pointer field
}ct;
//function declaration
ct* crunode(type x);//The development of the head node
void SListPrint(ct* phead);//print linked list
void SListPushBack(ct** phead, type x);//tail plug
void SListPushFront(ct** phead, type x);//plug
void SListPopBack(ct** phead);//tail delete
void SListPopFront(ct** phead);//head delete
void SListDestory(ct** phead);//Destroy linked list
ct* SListFind(ct* phead, type x);//look up
void SListInsertAfter(ct* pos, type x);//Insert a node with data x after pos
void SListEraseAfter(ct* pos);//Delete the node after poslinked.c
#include "linked.h"
ct* crunode(type x)//Create a node dynamically
{
ct* cur = (ct*)malloc(sizeof(ct));
if (cur == NULL)
{
perror("malloc fail");
exit(-1);//end of program
}
cur->data = x;
cur->next = NULL;
return cur;//Returns the address of the opened node
}
void SListPrint(ct* phead)//print linked list
{
ct* cur = phead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("NULL\n");//print the NULL at the end
}
void SListPushBack(ct** phead, type x)//tail plug
{
assert(phead);
ct* newnode = crunode(x);
if (*phead == NULL)//head node pointer is null
{
*phead = newnode;
}
else//Head node pointer is not null
{
ct* cur = *phead;
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
}
void SListPushFront(ct** phead, type x)//plug
{
assert(phead);
ct* newnode = crunode(x);
newnode->next = *phead;
*phead = newnode;
}
void SListPopBack(ct** phead)//tail delete
{
assert(phead);
assert(*phead);
ct* cur = *phead;
if (cur->next == NULL)
{
free(cur);
cur = NULL;
*phead = NULL;
}
else
{
while (cur->next->next)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
void SListPopFront(ct** phead)//head delete
{
assert(phead);
assert(*phead);//Check if the linked list is empty
ct* cur = *phead;
*phead = cur->next;
free(cur);//Free up head node space
cur = NULL;
}
void SListDestory(ct** phead)//Destroy linked list
{
assert(phead);
ct* cur = *phead;
while (cur)
{
ct* tai = cur->next;
free(cur);
cur = tai;
}
*phead = NULL;
}
ct* SListFind(ct* phead, type x)//search
{
ct* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(ct* pos, type x)//Insert a node with data x after pos
{
assert(pos);
ct* newnode = crunode(x);
newnode->next= pos->next;
pos->next = newnode;
}
void SListEraseAfter(ct* pos)//Delete the node after pos
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
ct* cur = pos->next;
pos->next = cur->next;
free(cur);
cur = NULL;
}
}test.c
#include "linked.h"
void test()
{
ct* head = NULL;//head node pointer
SListPushBack(&head, 1);//tail plug
SListPushBack(&head, 2);
SListPushFront(&head, 3);//plug
SListPushFront(&head, 4);
SListPopFront(&head);//head delete
SListPopBack(&head);//tail delete
ct* pos = SListFind(head, 1);//look up
if (pos)
{
printf("YES\n");
SListInsertAfter(pos, 9);
SListPrint(head);//print linked list
SListEraseAfter(pos);
}
else
{
printf("NO\n");
}
SListPrint(head);
SListDestory(&head);//Destroy linked list
SListPrint(head);
}
int main()
{
test();
return 0;
}Code running results
