一文弄懂C语言如何实现单链表

 #pragma once #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef int SListDataType; //节点 typedef struct SListNode { SListDataType data; struct SListNode* next; }SListNode; //struct SList //{ //	SListNode* head; //	SListNode* tail; //}; //尾插尾删 void SListPushBack(SListNode** pphead, SListDataType x); void SListPopBack(SListNode** pphead); //头插头删 void SListPushFront(SListNode**  pphead, SListDataType x); void SListPopFront(SListNode** pphaed); void SListPrint(SListNode* phead); //查找并修改 SListNode* SListFind(SListNode* phead, SListDataType x); //中插中删 void SListInserAfter(SListNode**pphead,SListNode* pos, SListDataType x); void SListEraseAfter(SListNode* pos); //从头到尾打印链表 void PrintTailToHead(SListNode* pList);

 //开辟的下一个空间 SListNode* BuySListNode(SListDataType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (newNode == NULL) { printf("申请结点失败\n"); exit(-1); } newNode->data = x; newNode->next = NULL; return newNode; }

 //尾插 void SListPushBack(SListNode** pphead, SListDataType x) { SListNode* newNode = BuySListNode(x);//我们指向头指针的那个结点是**pphead，*pphead就是头指针的地址 //如果头指针的地址为空，我们就把新开辟的这个空间指针（已经传入值）再赋给头指针，也就是下面的这个if循环 if (*pphead == NULL) { *pphead = newNode; } else { //找尾巴，判断尾巴是不是空地址,这个函数实现的是尾插，我们找到尾巴后，如果尾巴是空地址，我们将插入的newNode赋给尾巴，此时 //实现了尾插，在下面的代码中，我们首先把头指针当成尾巴，从头指针开始依次往后找，如果下一个不是空指针，我们就令 //tail=tail->next,此时指向下一个结点，进入循环继续判断，当找到后，我们再令尾巴=newNode,在上面我们也判断了头指针为空的情况 SListNode* tail = *pphead; while (tail->next!= NULL) { tail = tail -> next; } tail->next = newNode; } } void SListPopBack(SListNode** pphead) { //1、空 //2、一个结点 //3、一个以上 if (*pphead == NULL) { return; } else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SListNode* prev = NULL; SListNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); //tail = NULL;//这个无所谓，因为我们释放后，出了这个作用域，tail和prev都被销毁，没人能拿到，所以不会被再找到 prev->next = NULL; } }

 //头插头删 void SListPushFront(SListNode** pphead, SListDataType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } void SListPopFront(SListNode** pphead) { //1、空 //2、一个结点+3、一个以上 if (*pphead == NULL) { return; } //(*phead)->next:*和>都是解引用，同一优先级，我们需要给*pphead带括号，(*pphead)->next才是下一个结点 else{ //我们头删也会遇到情况，我们删除第一个的话，第一个里面还存有第二个结点的地址，我们必须在删除前，保存第二个结点的地址 SListNode* next = (*pphead)->next; free(*pphead);//通过调试我们发现：free前后，*pphead的地址不变，但是*pphead里的值被置为随机值，free不仅仅把这块空间还给操作系统 //而且还把这块空间存的值和地址都置为随机值 *pphead = next; } }

 //单链表查找 SListNode* SListFind(SListNode* phead, SListDataType x) { SListNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }

 void SListInserAfter(SListNode** pphead,SListNode* pos, SListDataType x) { assert(pos && pphead); if (*pphead == pos) { SListPushFront(pphead, x); } else { SListNode* newnode = BuySListNode(x); SListNode* tmp = *pphead; while (tmp->next != pos) { tmp = tmp->next; } tmp->next = pos; pos->next = newnode; } }

 void SListEraseAfter(SListNode* pos) { //删除pos后面的 assert(pos); if (pos->next) { //pos->next=pos->next->next//不推荐 SListNode* next = pos->next; SListNode* nextnext = next->next; pos->next = nextnext; free(next); } }

 void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } void PrintTailToHead(SListNode* pList) { if (pList == NULL) { return; } PrintTailToHead(pList->next); printf("%d->",pList->data); }

 #include"SList.h" TestSList1() { SListNode* pList = NULL;//这个结构体指针指向开辟的空间,头指针指向链表的开头 SListPushBack(&pList, 1); SListPushBack(&pList, 2); SListPushBack(&pList, 3); SListPushBack(&pList, 4); SListPrint(pList); SListPopBack(&pList); SListPopBack(&pList); SListPopBack(&pList); SListPopBack(&pList); SListPopBack(&pList); SListPrint(pList); SListPushFront(&pList, 1); SListPushFront(&pList, 2); SListPushFront(&pList, 6); SListPushFront(&pList, 4); SListPushFront(&pList, 5); SListPrint(pList); SListPopFront(&pList); SListPopFront(&pList); SListPopFront(&pList); SListPopFront(&pList); SListPopFront(&pList); SListPopFront(&pList); SListPrint(pList); } TestSList2() { SListNode* pos1; SListNode* pList = NULL;//这个结构体指针指向开辟的空间,头指针指向链表的开头 SListPushBack(&pList, 1); SListPushBack(&pList, 2); SListPushBa<mark style="color:transparent">来源gaodaimacom搞#^代%!码网</mark>ck(&pList, 3); SListPushBack(&pList, 4); SListPrint(pList); SListNode* pos = SListFind(pList, 3); if (pos) { pos->data = 30;//这里将cur-data改为pos->data,然后再将pos-data原来的值改为30 } SListPrint(pList); pos1 = SListFind(pList, 30);//我们先去找到这个pos1的位置，然后再去插入 SListInserAfter(&pList,pos1,50);//函数传参要对应起来，我们用指针传用指针接收，不能在pos1位置直接写个数字 SListPrint(pList); SListEraseAfter(pos1);//pList指向第一个结点，pList->next指向第二个结点，那么我们删除的是目标节点后面 SListPrint(pList); //PrintTailToHead(&pList); } int main() { TestSList1(); TestSList2(); return 0; }