- 头结点不为空或插入结点就是头结点指向的结点，找到pos前一个结点进行插入
单链表删除函数
头删
从头部删除数据，将头结点位置删除，将头结点的下一个位置指向头结点
void LLPopFront(LinkedList** PPhead) { assert(PPhead); assert(*PPhead); LinkedList* temp = (*PPhead)->next; free(*PPhead); //释放掉删除的结点 *PPhead = temp; }
尾删
void LLPopBack(LinkedList** PPhead) { assert(PPhead); assert(*PPhead); if ((*PPhead)->next == NULL) { *PPhead = NULL; } else { LinkedList* tail = *PPhead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
- 如果头结点为空，不能进行删除。
- 如果头结点下一个为空，直接进行删除
- 如果头结点和头结点的下一个都不为空，删除下一个结点为空的结点，那就需要找到头结点下一个结点的下一个结点为空的结点
指定结点后删除
后面的数据依次向前移动
void SListEraseAfter(LinkedList* pos) { if (pos == NULL) { printf("没发现此数据"); return; } if (pos->next == NULL) { printf("链表后面已经为空了\n"); return; } LinkedList* temp = pos->next; pos->next = pos->next->next; free(temp); }
- 如果pos为空或pos->next为空则提示并返回
指定结点删除
删除指定结点，将指定结点的next连接到指定结点前面的next结点，然后释放指定的结点
void SListErase(LinkedList**PPhead,LinkedList* pos) { assert(pos); assert(PPhead); assert(*PPhead); if (pos == *PPhead) { LLPopFront(PPhead); return; } LinkedList* cur = *PPhead; while (cur->next != pos) { cur = cur->next; } cur->next = cur->next->next; free(pos); }
- 头结点指针指向的结点等于pos，复用尾插函数
销毁单链表
将每个结点依次释放。最后将头结点制空。
void SListDestroy(LinkedList** PPhead) { assert(*PPhead); if (*PPhead == NULL) { printf("已经是空链表了\n"); return; } while ((*PPhead)->next != NULL) { LinkedList* tep = (*PPhead)->next; (*PPhead)->next = (*PPhead)->next->next; free(tep); } free(*PPhead); *PPhead = NULL; }
文件分类
🌞🌞为了使代码更有阅读性，我们不建议把所有函数写在一个文件里，所以这里分成三个文件，模块化管理
test.c
测试文件
#include "LinkedList.h" int main() { LinkedList *Phead = NULL; LLPushFront(&Phead, 8); LLPushBack(&Phead,2); LLPushBack(&Phead,3); LLPushBack(&Phead,4); LLPushBack(&Phead,5); //LLPopBack(&Phead); //LLPopFront(&Phead); //LLPopBack(&Phead); //LLPopFront(&Phead); //LLPopFront(&Phead); LinkedList* temp = LListFind(Phead, 3); SListInsertAfter(temp,88); temp = LListFind(Phead, 4); SListEraseAfter(temp); temp = LListFind(Phead, 4); SListInsertFront(&Phead,temp, 99); printLL(Phead); temp = LListFind(Phead, 99); SListErase(&Phead, temp); SListDestroy(&Phead); }
LinkedList.c
将所有单链表需要的函数封装在此文件下⭐
#include "LinkedList.h" LinkedList* BuyNewNode(LLDataType x) { LinkedList* ret = (LinkedList*)malloc(sizeof(LinkedList)); if (ret == NULL) { perror("Malloc:"); return NULL; } ret->data = x; ret->next = NULL; return ret; } void LLPushBack(LinkedList** PPhead, LLDataType x) { assert(PPhead); LinkedList* NewNode = BuyNewNode(x); if (*PPhead == NULL) { *PPhead = NewNode; } else { LinkedList* tail = *PPhead; while (tail->next != NULL) { tail = tail->next; } tail->next = NewNode; } } void LLPushFront(LinkedList** PPhead, LLDataType x) { assert(PPhead); LinkedList* NewNode = BuyNewNode(x); if (*PPhead == NULL) { *PPhead = NewNode; } else { NewNode->next = *PPhead; *PPhead = NewNode; } } void LLPopBack(LinkedList** PPhead) { assert(PPhead); assert(*PPhead); if ((*PPhead)->next == NULL) { *PPhead = NULL; } else { LinkedList* tail = *PPhead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void LLPopFront(LinkedList** PPhead) { assert(PPhead); assert(*PPhead); LinkedList* temp = (*PPhead)->next; free(*PPhead); *PPhead = temp; } void printLL(LinkedList* Phead) { while (Phead!=NULL) { printf("%d->", Phead->data); Phead = Phead->next; } printf("NULL"); } LinkedList* LListFind(LinkedList* phead, LLDataType x) { assert(phead); LinkedList *ret = phead; while (ret->data != x) { if (ret == NULL) { return NULL; } ret = ret->next; } return ret; } void SListInsertAfter(LinkedList* pos, LLDataType x) { assert(pos); LinkedList *newnode = BuyNewNode(x); newnode->next = pos->next; pos->next = newnode; } void SListInsertFront(LinkedList** PPhead, LinkedList* pos, LLDataType x) { assert(pos); assert(PPhead); if (*PPhead == NULL||*PPhead==pos) { LLPushFront(PPhead, x); } else { LinkedList* cur = *PPhead; while (cur->next != pos) { cur = cur->next; } LinkedList* newnode = BuyNewNode(x); newnode->next = cur->next; cur->next = newnode; } } void SListEraseAfter(LinkedList* pos) { if (pos == NULL) { printf("没发现此数据"); return; } if (pos->next == NULL) { printf("链表后面已经为空了\n"); return; } LinkedList* temp = pos->next; pos->next = pos->next->next; free(temp); } void SListErase(LinkedList**PPhead,LinkedList* pos) { assert(pos); assert(PPhead); assert(*PPhead); if (pos == *PPhead) { LLPopFront(PPhead); return; } LinkedList* cur = *PPhead; while (cur->next != pos) { cur = cur->next; } cur->next = cur->next->next; free(pos); } //void SListDestroy(LinkedList** Phead) //{ // assert(Phead); // if (*Phead == NULL) // { // printf("已经是空链表了"); // return; // } // while ((*Phead) != NULL) // { // LinkedList* temp = *Phead; // *Phead = (*Phead)->next; // free(temp); // } //} void SListDestroy(LinkedList** PPhead) { assert(*PPhead); if (*PPhead == NULL) { printf("已经是空链表了\n"); return; } while ((*PPhead)->next != NULL) { LinkedList* tep = (*PPhead)->next; (*PPhead)->next = (*PPhead)->next->next; free(tep); } free(*PPhead); *PPhead = NULL; }
LinkedList.h
将主程序所需要的函数全部在头文件中声明，增加代码阅读性⭐
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int LLDataType; typedef struct LinkedList { LLDataType data; struct LinkedList* next; }LinkedList; void printLL(LinkedList* Phead); void LLPushBack(LinkedList** PPhead, LLDataType x); void LLPushFront(LinkedList** PPhead, LLDataType x); void LLPopBack(LinkedList** PPhead); void LLPopFront(LinkedList** PPhead); LinkedList* LListFind(LinkedList* phead, LLDataType x); void SListInsertAfter(LinkedList* pos, LLDataType x); void SListEraseAfter(LinkedList* pos); void SListDestroy(LinkedList** Phead); void SListInsertFront(LinkedList** Phead, LinkedList* pos, LLDataType x); void SListErase(LinkedList** PPhead, LinkedList* pos);
撒花
这就是实现单链表的全部内容了，创作不易，还请各位小伙伴多多点赞👍关注收藏⭐，以后也会更新各种关于c语言，数据结构的博客，撒花！
