数据结构——单链表（C语言）

链表的概念和结构：

概念：链表是一种物理存储结构上非连续，非顺序的结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

---

下面是我们想象出来的图：

而实际上的图：

链表的结构多样，第一个就是不带头节点的链表，第二个是带哨兵位的头节点，而哨兵位是没有任何有效数据的。

目录

链表的概念和结构：

链表的尾插：

链表的头插：

链表的尾删：

链表的头删：

链表的查找：

链表指定位置之后的插入：

链表指定位置之前的插入：

链表指定位置之后的删除：

链表指定位置的删除：

链表最后的处理：

下面我将讲解链表的各个实现，源码如下：

SListNode* BuySListNode(SListDateType x){SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->date = x;newnode->next = NULL;return newnode;}void SListPrint(SListNode* plist){SListNode* cur = plist;while(cur){printf("%d->", cur->date);cur = cur->next;}printf("NULL\n");}void SListPushBack(SListNode** pplist, SListDateType x){SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* tail = *pplist;//βwhile (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}void SListPushFront(SListNode** pplist, SListDateType x){SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}void SListPopFront(SListNode** pplist){assert(*pplist);SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;}void SListPopBack(SListNode** pplist){assert(*pplist);SListNode* tail = *pplist;SListNode* newnode = NULL;if ((*pplist)->next == NULL){free(*pplist);*pplist = newnode;}else{while (tail->next){newnode = tail;tail = tail->next;}free(tail);newnode->next = NULL;}}SListNode* SListFind(SListNode* plist, SListDateType x){SListNode* tail = plist;while (tail->next){if (tail->date == x){return tail;}tail = tail->next;}return NULL;}SListNode* SListInsertAfter(SListNode* pos, SListDateType x){assert(pos);SListNode* newnode = BuySListNode(x);SListNode* posnext = pos->next;pos->next = newnode;newnode->next = posnext;}void SListDestroy(SListNode* plist){assert(plist);free(plist);}void SListEraseAfter(SListNode* pos){assert(pos);SListNode* posnext = pos->next->next;free(pos->next);pos->next = posnext;}

ps：1.这里我设计的链表函数时没有返回值的，所以我用到了二级指针，因为如果我们传一级指针的话，形参只是实参的一份临时拷贝，当出了作用域后，创建的newnode等等这些在栈上开辟的变量就会不存在了，不会影响到要改变的plist。

2.当然你也可以设计一个返回结构体，这样就可以直接传值，最后也可以改变链表的结构。

链表的尾插：

• 这里我是调用了一个BuySListNode的函数来创建一个节点，BuySListNode的实现就是用malloc开辟了结构体类型的空间，然后把SListDateType的类型数据给了结构体中的date，然后把指针域赋为了NULL
• 尾插的思想：分为2种，第一种是一开始传的plist为NULL时，第二种就是plist不为NULL
• 第一种情况：当传的plist为NULL时，说明我们链表还没数据，直接把创还能得newnode给给plist就行了。
• 第二种情况：当plist不为NULL时，我们就用while循环找尾，然后把尾的next给给newnode，就实现了链表的尾插。

SListNode* BuySListNode(SListDateType x){SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->date = x;newnode->next = NULL;return newnode;}

void SListPushBack(SListNode** pplist, SListDateType x){SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}

链表的头插：

• 头插的思想：
• 我们直接让创建出来的newnode指向*pplist，然后更新头结点就可以了。

void SListPushFront(SListNode** pplist, SListDateType x){SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}

链表的尾删：

• 一开始用断言检查一下，*pplist不能为NULL，这里的意思是如果是NULL,就代表了没有数据了，不能删除
• 第一种情况：当只有一个节点的时候，我就创建了newnode的节点，只需要free第一个节点，然后把newnode给给它就行了。
• 第二种情况：当有二个或多个节点的时候，我就定义了一个tail指针来记录尾节点的位置，然后用newnode来记录尾结点前一个的位置，最后free掉tail节点，然后把前一个置为NULL。

void SListPopBack(SListNode** pplist){assert(*pplist);SListNode* tail = *pplist;SListNode* newnode = NULL;if ((*pplist)->next == NULL){free(*pplist);*pplist = newnode;}else{while (tail->next){newnode = tail;tail = tail->next;}free(tail);newnode->next = NULL;}}

链表的头删：

• 一开始也是和尾删一样的思路，用assert断言一下，防止没节点了还删除。
• 头删的思路：记录头结点下一个节点的位置，然后free掉头结点，然后让下一个节点当头节点。

void SListPopFront(SListNode** pplist){assert(*pplist);SListNode* next = (*pplist)->next;free(*pplist);*pplist = next;}

链表的查找：

• 如果我们要查找链表中某个节点，直接遍历链表，当我们查找的数据和X相同时，就是我们要找的节点了，如果没有，就返回NULL。

SListNode* SListFind(SListNode* plist, SListDateType x){SListNode* tail = plist;while (tail->next){if (tail->date == x){return tail;}tail = tail->next;}return NULL;}

链表指定位置之后的插入：

• 首先先断言一下，pos是有效的节点
• 我先创建了一个节点，然后用posnext来记录pos之后的节点，最后我让pos指向newnode，然后用newnode的next指向posnext。这样我就实现了链表指定位置之后的插入了。

SListNode* SListInsertAfter(SListNode* pos, SListDateType x){assert(pos);SListNode* newnode = BuySListNode(x);SListNode* posnext = pos->next;pos->next = newnode;newnode->next = posnext;}

链表指定位置之前的插入：

• 首先也是老套路，先断言一下，让pos和pplist为有效。
• 这里分为二种情况：

1. 第一种：当pos是第一个节点的时候，就复用头插的函数。
2. 第二种：当pos指向第二个或后面的节点的时候，用prev来记录pos之前节点的位置，然后让prev指向创建的newnode，newnode指向pos。

void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x){assert(pplist);assert(pos);if (pos == *pplist){SLTPushFront(pplist, x);}else{SLTNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}

链表指定位置之后的删除：

• 老套路，先断言一下（保持好习惯）。
• 用posnext来记录pos的下下的节点，free掉pos之后的节点，然后让pos指向posnext。

void SListEraseAfter(SListNode* pos){assert(pos);SListNode* posnext = pos->next->next;free(pos->next);pos->next = posnext;}

链表指定位置的删除：

• 先断言，这里就不再叙述了。
• 第一种情况：当pos为第一个节点的时候，就是头删，复用头删的函数就可以了。
• 第二种情况：用prev来记录pos之前的节点，然后让prev指向pos之后的节点，最后free掉pos节点。

void SLTErase(SLTNode** pplist, SLTNode* pos){assert(pplist);assert(pos);if (pos == *pplist){SLTPopFront(pplist);}else{SLTNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}

链表最后的处理：

• 还是先断言。
• 然后用把第一个节点赋给cur，迭代往后走，用next来记录cur的下一个节点，free掉cur节点，最后让把cur下一个节点给给cur。

void SListDestroy(SListNode** pplist){assert(pplist);SListNode* cur = *pplist;while (cur){SListNode* next = cur->next;free(cur);cur = next;}}

#pragma once#include #include #include typedef int SListDateType;typedef struct SListNode{SListDateType date;struct SListNode* next;}SListNode;SListNode* BuySListNode(SListDateType x);void SListPrint(SListNode* plist);void SListPushBack(SListNode** pplist, SListDateType x);void SListPushFront(SListNode** pplist, SListDateType x);void SListPopFront(SListNode** pplist);void SListPopBack(SListNode** pplist);SListNode* SListFind(SListNode* plist, SListDateType x);void SListInsertAfter(SListNode* pos, SListDateType x);void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x);void SListEraseAfter(SListNode* plist);void SLTErase(SLTNode** pplist, SLTNode* pos);void SListDestroy(SListNode** pplist);