Data structure is to define a certain structure, such as array structure, linked list structure, tree structure, etc. the implementation of data structure is the implementation function that we actively manage additions, deletions, checks and changes
Concept understanding of linked list
Concept: a linked list is a node by node. You can apply for memory on the heap as needed. You need to apply for one by one. It will be easy to understand the "headless one-way acyclic linked list" first, and then understand other linked list structures. The value of a single linked list is also convenient for us to learn hash buckets
Before programming, we need to know the real stored procedure of the linked list in memory. In essence, it can point to the next node because the previous one has the next address
Next, we still program and implement the dynamic sequence table in the vs environment. Here we write it in files, in the header file slist H, in slist C for specific function definitions, in test C to do specific test implementation
First, let's take a look at the header file seqlist H middle interface
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //Typedef when using typedef to change the type, you can change int to double, char, etc typedef int SLTDateType; typedef struct SListNode { SLTDateType data;//Define date to save data //One pointer in each data points to the next, otherwise it cannot be found struct SListNode* next; } SListNode; //The linked list has a pointer to the first node, and the first one is saved until the last pointer points to null SListNode* BuyListNode(SListNode* phead);//Add new node function void SListPrint(SListNode* phead);//Print function, first pass a pointer to the first void SListPushBack(SListNode** pphead,SLTDateType x);//Tail insertion void SListPopBack(SListNode** pphead);//Tail deletion void SListPushFront(SListNode** pphead, SLTDateType x);//Head insertion void SListPopFront(SListNode** pphead);//Header deletion void SListDestroy(SListNode** pphead);//Empty function to free up space SListNode* SListFind(SListNode* phead, SLTDateType x);//Find a node location void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x); //Insert before specifying location void SListInsertAfter(SListNode* pos, SLTDateType x);//Insert after specifying location void SListErase(SListNode** pphead, SListNode* pos);//Delete specified location void SListEraseAfter(SListNode* pos);//Delete the data behind the specified location
We know that the definition method of function is very important and we need to understand it in depth. Let's study it in slist The specific function implementation in C
Add new node function definition
SListNode* BuyListNode(SLTDateType x)//Add new node function { //Consider that when the linked list is empty, so open a new node first SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode;//Return to new node }
Print function definition
Each node will have a next to store the address of the next node
void SListPrint(SListNode* phead)//Print linked list function { SListNode* cur = phead; //At this time, cur is equal to the pointer passed to the header node //There is a data stored in the address of the first node while (cur != NULL) { printf("%d->", cur->data);//Get header node data using pointer cur = cur->next; //Each node will have a next to store the address of the next node //The next node can be found through the address } printf("NULL\n"); }
Tail insert function definition
The tail node flag next points to null
void SListPushBack(SListNode** pphead, SLTDateType x)//Tail insert node { assert(pphead); //Consider that when the linked list is empty, so open a new node first SListNode* newnode = BuyListNode(x); //Call the above function to open a new node if (*pphead == NULL)//If it is empty, it will not find the tail { //Let the first pointer point to the new node and save the address of the new node *pphead = newnode; } else// //Not empty go down { SListNode* tail = *pphead;//Define the tail pointer, point to the head first, and look back from the beginning while (tail->next != NULL)//Not empty keep looking { tail = tail->next; } //Find the tail here. Next, give the address of the new node to the tail node just now tail->next = newnode;//As long as the next of the tail node points to the new node } }
Tail delete function definition
//The tail deletion also needs to pass the secondary pointer, and finally the header pointer needs to be modified void SListPopBack(SListNode** pphead)//Tail deletion { assert(*pphead != NULL);//Judgment is not empty if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode* prev = NULL;//Save the tail pointer by defining more than one pointer //At this time * pphead first pointer address SListNode* tail = *pphead; while (tail->next != NULL)//Let's find the tail { prev = tail;//Give me a prev before you leave tail = tail->next; } //Find the tail here // Note that before deleting, we need to point the previous one of the tail to null, otherwise it will become a wild pointer free(tail); tail = NULL; prev->next = NULL; } }
Header insert function definition
First define a new node and give the address of the first node to the new node
void SListPushFront(SListNode** pphead, SLTDateType x) { assert(pphead); SListNode* newnode = BuyListNode(x);//Call the above function to open a new node newnode->next = *pphead;//Give the address of the first node to the new node *pphead = newnode;//And then become the new head }
Header delete function definition
void SListPopFront(SListNode** pphead)//Header deletion { assert(*pphead != NULL); SListNode* next = (*pphead)->next;//Take the next one of phead first free(*pphead); *pphead = next; }
Null function definition
Empty functions are generally placed at the end of the functions we insert or delete, freeing up the space we apply for on the heap and returning it to the operating system. In addition, they will also check for cross-border problems accordingly
void SListDestroy(SListNode** pphead)//Empty function to free up space { assert(pphead); //If the space is discontinuous, it should be released, otherwise the memory leaks SListNode* cur = *pphead;//Empty from the beginning while (cur)//It's not empty. Keep going { //First find the next node location and delete it SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
We first use the above interface to implement a test The first test case in C TestSList 1
void TestSList1() { //Empty the start list SListNode* plist = NULL; SListPushBack(&plist, 1);//Tail insertion 123456 SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushBack(&plist, 5); SListPushBack(&plist, 6); SListPrint(plist);//Print 1->2->3->4->5->6->null SListPopBack(&plist);//Tail deletion twice SListPopBack(&plist); SListPrint(plist);//Print 1->2->3->4->null SListPushFront(&plist, 1);//Head insert data 1234 SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPrint(plist);//Print 4->3->2->1->1->2->3->4->null SListPopFront(&plist);//Delete the header twice SListPopFront(&plist); SListPrint(plist);//Print 2->1->1->2->3->4->null SListDestroy(&plist);//Empty the function and put it at the end to free up space } int main() { TestSList1(); return 0; }
Note: here plist (argument) and phead (formal parameter) both point to the address of the first node
Next, we will learn the remaining function interfaces in slist The specific function implementation in C
Find a node location
SListNode* SListFind(SListNode* pphead, SLTDateType x)//Find a node { //Traverse the linked list, and find the value of x node SListNode* cur = pphead; while (cur) { if (cur->data == x) { return cur;//Return when you find it } else { cur = cur->next;//I haven't found it. Keep looking } } return NULL;//Last not found, return null }
Here we use find using the pointer of the return node (SListNode* pphead). First, use the above search interface to implement a search in test The second test case in C TestSList 2
void TestSList2() { //Empty the start list SListNode* plist = NULL; SListPushFront(&plist, 1);//Head insert data 12342 SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPushFront(&plist, 2); SListPrint(plist);//Print 2->4->3->2->1->null //When finding multiple data SListNode* pos = SListFind(plist, 2); int i = 1; while (pos) { printf("Section%d individual pos node:%p->%d\n",i++,pos,pos->data); //Print the first pos node: 0000020c088ef120->2 //Print the second pos node: 0000020c088ef580->2 pos = SListFind(pos->next, 2); //Here, continue to look behind the first 2 } //be careful: //Using find that returns the pointer of the node, in addition to finding, you can also modify the pos position data pos = SListFind(plist, 3);//Revision 3 - >30 if (pos) { pos->data = 30; } SListPrint(plist);//Print 2->4->30->2->1->null SListDestroy(&plist);//Empty the function and put it at the end to free up space } int main() { TestSList2(); return 0; }
Insert before specifying location
//Insert before specifying location void SListInsert(SListNode** pphead, SListNode* pos, SLTDateType x) { assert(pphead); assert(pos); //pos position alone is not enough //We also need to have a previous location of pos, so that the previous location points to the new data node, and the new node location points to pos //The first step is to prepare a new node SListNode* newnode = BuyListNode(x);//Call the above function to open a new node if (*pphead == pos)//Judge the condition of head insertion { newnode->next = *pphead; *pphead = newnode; } else { //Find the previous position of pos SListNode* posprev = *pphead;//Define posorev find from scratch while (posprev->next != pos) { posprev = posprev->next; } posprev->next = newnode;//Let the previous location point to the new data node newnode->next = pos;//The new node location is pointing to pos } }
Insert after specifying location
void SListInsertAfter(SListNode* pos, SLTDateType x)//Insert after specifying location { assert(pos); //At this time, note that the newnode must first point to the next pos //Step 1 / / prepare a new node first SListNode* newnode = BuyListNode(x);//Call the above function to open a new node newnode->next = pos->next; pos->next = newnode; }
Delete specified location
void SListErase(SListNode** pphead, SListNode* pos)//Delete specified location { assert(pphead); assert(pos); //pos is anywhere //Before deleting, let the previous point to the next pos position if (pos == *pphead)//Consider deleting headers first { SListPopFront(pphead);//Call the top header deletion function } else { //Find the previous position of pos SListNode* posprev = *pphead;//Define posorev find from scratch while (posprev->next != pos) { posprev = posprev->next; } // posprev->next = pos->next;//Let the previous position point to the next position of pos first free(pos);//Then delete pos } }
Delete the data behind the specified location
void SListEraseAfter(SListNode* pos)//Delete the data behind the pos at the specified location { //Let pos point to the next position of pos first assert(pos->next); SListNode* next = pos->next;//Define next as the data to be deleted pos->next = next->next; //Let the next position of pos point to the next position of data to be deleted (next) free(next);//Then delete next }
At this time, we use the above interface to implement a test The third test case in C TestSList 3
void TestSList3() { //Start to empty the linked list SListNode* plist = NULL; SListPushBack(&plist, 1);//Tail insertion 1234 SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListNode* pos = SListFind(plist, 4);//Insert before specifying digit 4 position if (pos) { SListInsert(&plist, pos, 60);//Insert 60 in front of position 4 } SListPrint(plist);//Print 1->2->3->60->4->null pos = SListFind(plist, 4);//Insert after specifying the position of number 4 if (pos) { SListInsertAfter(pos, 5);//Insert 5 after position 4 } SListPrint(plist);//Print 1->2->3->60->4->5->null pos = SListFind(plist, 4);//Find 4 if (pos) { SListErase(&plist, pos);//Delete current position 4 } SListPrint(plist);//Print 1->2->3->60->5->null pos = SListFind(plist, 60);//Find 60 if (pos) { SListEraseAfter(pos);//Delete the last one of 60 } SListPrint(plist);//Print 1->2->3->60->null SListDestroy(&plist);//Empty the function and put it at the end to free up space } int main() { TestSList3(); return 0; }
In the learning of Java and C++, the sequence table, linked list and binary tree in the early learning data structure are convenient for us to learn better later. We will continue to share the implementation of binary tree and algorithm later
I hope you can gain something from this article. See you next