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

This article mainly introduces how to realize the function of checking and deleting one-way linked list, which has certain reference value. Interested friends can refer to it. I hope you will gain a lot after reading this article. Let the editor take you to know it.

Slist.h// header file

# ifndef _ SLIST_H_#define _ SLTST_H_#include#include#include#includetypedef int SLTDataType; typedef struct SListNode {SLTDataType data; struct SListNode* next;} SListNode;void SListInit (SListNode** pphead); void SListDestory (SListNode** pphead); SListNode* BuySListNode (SLTDataType x); void SListPushFront (SListNode** pphead, SLTDataType x); void SListPopFront (SListNode** pphead); SListNode* SListFind (SListNode* pphead, SLTDataType x); / / insert void SListInsertAfter (SListNode* pos, SLTDataType x) after pos / insert void SListEraseAfter (SListNode* pos); void SListRemove (SListNode** pphead, SLTDataType x); void SListRemoveAll (SListNode** pphead, SLTDataType x); void SListPrint (SListNode* pphead); void SListReverse (SListNode** pphead); void SListReverse2 (SListNode** pphead) in front of pos; SListNode* getIntersectionNode (SListNode* headA, SListNode*headB); SListNode* detectCycle (SListNode*head); # endif

Slist.c// source file

# include "slist.h" void SListInit (SListNode** pphead) / / initialize {* pphead = NULL;} void SListDestory (SListNode** pphead) {if (* pphead = = NULL) {return;} else {while ((* pphead)-> next) {SListEraseAfter (* pphead);} free (* pphead); * pphead = NULL } SListNode* BuySListNode (SLTDataType x) {SListNode* res = (SListNode*) malloc (sizeof (SListNode)); res- > data = x; res- > next = NULL; return res;} void SListPushFront (SListNode** pphead, SLTDataType x) {SListNode* tmp = BuySListNode (x); tmp- > next = * pphead; * pphead = tmp;} void SListPopFront (SListNode** pphead) {if (* pphead = = NULL) {return } / * (* pphead)-> date = (* pphead)-> next;*/ SListNode* tmp = (* pphead)-> next; free (* pphead); * pphead = tmp;} SListNode* SListFind (SListNode* pphead, SLTDataType x) / / find x data {SListNode* tmp; for (tmp = pphead; tmp; tmp = tmp- > next) {if (tmp- > data = x) {return tmp } return NULL;}} void SListInsertAfter (SListNode* pos, SLTDataType x) / / insert x after pos {SListNode* tmp = BuySListNode (x); tmp- > next = pos- > next; pos- > next = tmp;} void SListEraseAfter (SListNode* pos) / / Delete the data after pos {SListNode* tmp = pos- > next; if (tmp = NULL) {return;} pos- > next = tmp- > next; free (tmp) } void SListRemove (SListNode** pphead, SLTDataType x) / / remove x {SListNode* tmp; if (* pphead = = NULL) {return;} if ((* pphead)-> data==x) {SListPopFront (* pphead);} else {for (tmp = * pphead; tmp- > next; tmp = tmp- > next) {SListEraseAfter (pphead); return } void SListRemoveAll (SListNode** pphead, SLTDataType x) {SListNode* tmp; if (* pphead & & (* pphead)-> data = = x) {SListPopFront (* pphead);} for (; tmp = * pphead; tmp&&tmp- > next) {if (tmp- > next = = x) {SListEraseAfter (tmp) } else {tmp = tmp- > next;} void SListPrint (SListNode* pphead) {SListNode* cur; printf ("pphead- >"); for (cur = pphead; cur; cur = cur- > next) {printf ("% d->", cur- > data);} printf ("NULL\ n") } void SListReverse (SListNode * * pphead) / / reverse linked list {SListNode * head = * pphead; / / this pointer always points to the header of the current linked list in each loop, SListNode * tmp = head- > next; / / this pointer always points to the node to be deleted in each loop SListNode * oldh = * pphead / / this pointer always points to the original header node in each loop, and does not change the point to while (tmp) / / if the tmp is empty, it represents the end of the reverse order, and the next of the old header is empty, becoming the end of the new linked list {oldh- > next = tmp- > next; / / erecting the tmp, which is actually part of the post-delete operation tmp- > next = head. / / make tmp a new header, which is actually part of the headin operation head = tmp; / / change head tmp = oldh- > next; / / make tmp the node to be deleted in the next loop} * pphead = head;} void SListReverse2 (SListNode * * pphead) / / reverse the linked list {SListNode * pre = * pphead; / / the previous node SListNode * cur = pre- > next / / SListNode * next = cur; / / the latter node to which the operation is performed temporarily refers to the cur that jumps to the next node pre- > next = NULL; / / at the beginning of the loop, which will be the tail after the conversion. Here, the chain list trailing node while (next) {next = next- > next is set. / / Let next become the next node first, not at the end, because there will be a restriction that next is empty cur- > next = pre; / / Let the one pointing back point to the front (turn one after another) pre = cur / / pass data for the next loop. Here is to set the previous node of the next loop (the node performing this operation will be the last node of the next loop) cur = next; / / ditto (the next node this time will be the next node to be executed)} * pphead = pre / / after the loop pops out, both cur and next point to null, and pre is the new header} / / enter two linked lists and find their first common node SListNode* getIntersectionNode (SListNode* headA, SListNode*headB) {int lenA = 0; int lenB = 0; int gap, I; SListNode* cur = 0; SListNode* longerlist = headA; SListNode* shorterlist = headB; for (cur = 0; cur; cur = headA- > next) {lenA++ } for (cur = 0; cur; cur = headB- > next) {lenB++;} gap = abs (lenA-lenB); if (lenA > lenB) {longerlist = headA; shorterlist = headB;} else {longerlist = headB; shorterlist = headA;} for (I = 0; I

Next;} for (; longerlist&&shorterlist; longerlist = longerlist- > next, shorterlist = shorterlist- > next) {if (longerlist = = shorterlist) {return longerlist;}} return NULL;} / / given a linked list, returns the first node where the linked list begins to enter the ring. If the linked list is free, return NULLSListNode * detectCycle (SListNode * head) {SListNode * fast = head; SListNode * slow = head; while (fast & & slow & & fast- > next) {fast = fast- > next- > next;// traversal speed is 2 slow = slow- > next;// traversal speed is 1 if (fast = = slow) / / determine the intersection of two different traversal speeds {break }} for (; fast & & fast- > next; fast = fast- > next, head = head- > next) / / the distance from the intersection to the first node in the ring is equal to the distance between the head node and the first node in the ring {if (fast = = head) {return fast;}} return NULL;}

Main.c// test

# include "slist.h" # if 0 / 1, select program segment int main () / / Test {SListNode * phead1; / / SListNode * phead2; SListNode * tmp; SListNode * tmp2; SListInit (& phead1); / / SListInit (& phead2); SListPushFront (& phead1, 8); tmp = phead1; SListPushFront (& phead1, 7); SListPushFront (& phead1, 6); SListPushFront (& phead1, 5); SListPushFront (& phead1, 4) SListPushFront (& phead1, 3); tmp2 = phead1; SListPushFront (& phead1, 2); SListPushFront (& phead1, 1); tmp- > next = tmp2; / / phead2- > next = phead1- > next- > next; SListNode * ret = detectCycle (phead1); if (ret) {printf ("% d\ n", ret- > data);} else {printf ("NULL\ n");} / / SListDestory (phead1) / / SListDestory (& phead2); return 0;} # elseint main () / / Test {SListNode * phead; SListInit (& phead); SListPushFront (& phead, 1); SListPushFront (& phead, 2); SListPushFront (& phead, 3); SListPushFront (& phead, 4); SListPushFront (& phead, 5); SListPushFront (& phead, 6); SListPushFront (& phead, 7); SListPushFront (& phead, 8); SListPushFront (& phead, 9) / / SListPopFront (& phead); / / SListPopFront (& phead); / * SListInsertAfter (SListFind (phead, 6), 9); SListEraseAfter (SListFind (phead, 4)); SListRemove (& phead, 7); SListPrint (phead); * / / SListRemoveAll (& phead, 8); SListReverse2 (& phead); SListPrint (phead); SListDestory (& phead); / / SListPrint (phead); return 0 } # endif//int main () / / Joseph ring problem, linked list to solve / / {/ / SListNode * phead;// SListNode * plast;// SListNode * cur;// int m = 11, n = 3 SListInit (& phead); / / SListPushFront (& phead, m); / / plast = phead;// for (I = m-1; I > = 1; I plast -) / {/ / SListPushFront (& phead, I) / /} / / plast- > next = phead;// cur = plast;// for (; m > 1; Mmuri -) / / {/ / for (I = 1; I

Next;// printf ("% d report the number% d\ n", cur- > data, I); / /} / / printf ("% d is removed\ n", cur- > next- > data); / / SListEraseAfter (cur); / /} / / printf ("% d wins\ n", cur- > data); / / free (cur); / / return 0 / /} Thank you for reading this article carefully. I hope the article "how to check and delete one-way linked list" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.