快速通关单链表秘籍

1.单链表概念与结构

1.1 概念

链表是一种逻辑结构连续，物理结构不连续的存储结构，数据结构的逻辑顺序是通过链表中的指针链接次序实现。

光看定义有点不好理解，我们举个简单例子！

我们都看过火车吧，我们看到的火车是有一节一节的车厢相连接，这个链接的纽带我们可以抽象的看作指针链接，我们通过车厢链接去找到下一节车厢，在单链表中我们可以通过指针链接去找到下一个节点。当我们需要增加（或减少）节车厢时，可以额外增加（或减少）几节。链表也是如此，这也是链表相对于顺序表的一大优点：可以随意增（减）容。

由此我们可以抽象出单链表的基本结构：

 1.2 结点结构

火车的每一节车厢叫车厢，链表的每一节“车厢”叫结点。

链表里面的每一节“车厢”都是独立像内存申请的空间，我们称作“结点”。

根据这幅图，我们plist就是头结点，通过plist里的存放的地址我们可以找到下一结点的位置，要找到下一节点，我们就必须的有它对应的地址，因此节点不仅存放了相应的数据还有下一结点的地址！

所以结点的结构：数据+下一结点的地址。

同理我们也可以去修改对应的地址，去访问不同的结点空间。例如：修改plist的值，plist=0x0012FFA0，再去访问结点访问的就是数据2对应的结点了。

注意：结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量保存下一结点的地址才能找到下一个结点。

1.3 链表的性质

1. 链表在逻辑结构上是连续的，物理结构是不连续的！

2. 结点是独立的，是从堆上申请的。

3. 从堆上申请下来的结点，是按一定策略分配的，可能申请的空间连续，也可能不连续。

这里有人可能不知道什么是堆区，这里留了一张大概的图片有助于理解：

 1.4 链表结点的结构

typedef int SLTDataType;//这里重命名，可以更改数据的类型
typedef struct SListNode
{SLTDataType data;//节点里面的数据struct SListNode* Next;//节点里存放的下一个结点的地址
}SLTNode;

2. 链表的实现 

2.1 手动构造一个链表

void test()
{SLTNode SL;SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTNode* plist = node1;//头结点
}

2.2 尾插

//头插
void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;*pphead = newnode;}
}

2.3 头插

//头插
void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;*pphead = newnode;}
}

 2.4 尾删

//尾删
void SLPopBack(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;SLTNode* prev = NULL;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;free(pcur);pcur = NULL;}
}

 2.5 头删

//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

2.6 指定位置之前插入数据 

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);SLTNode* prev = *pphead;if (*pphead == pos)SLPushFront(pphead, x);else{while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

2.7 在指定位置之后插入数据

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.8 删除指定位置之前的数据

//删除指定位置之前的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);SLTNode* prev = *pphead;//当只有一个节点的时候if (*pphead == pos)SLPopFront(pphead);else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

2.9 删除pos之后的结点

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* next = pos->next;pos->next = pos->next->next;free(next);next = NULL;
}

2.10 销毁链表

//销毁链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;SLTNode* next = *pphead;while (pcur){next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

3. 单链表实现代码

SList.h文件

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//头结点的位置会发生改变，即形参会影响实参，传二级指针
//尾插
void SLPushBack(SLTNode** pphead,SLTDataType x);
//打印链表
void SLPrint(SLTNode* phead);
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLPopBack(SLTNode** pphead);
//头删
void SLPopFront(SLTNode** pphead);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除指定位置之前的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

 SList.c文件

#include "SList.h"SLTNode* BuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;
}
//打印链表
void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuyNode(x);//这里需要讨论两种情况：空链表和非空链表SLTNode* pcur = *pphead;//空链表if(*pphead==NULL){*pphead = newnode;}else//非空链表{while (pcur->next){pcur = pcur->next;}pcur->next=newnode;}
}
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;*pphead = newnode;}
}
//尾删
void SLPopBack(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;SLTNode* prev = NULL;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;free(pcur);pcur = NULL;}
}
//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);SLTNode* prev = *pphead;//当只有一个结点的时候if (*pphead == pos)SLPushFront(pphead, x);else{while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);SLTNode* newnode = BuyNode(x);newnode->next = pos->next;pos->next = newnode;
}
//删除指定位置之前的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);SLTNode* prev = *pphead;//当只有一个节点的时候if (*pphead == pos)SLPopFront(pphead);else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* next = pos->next;pos->next = pos->next->next;free(next);next = NULL;
}
//销毁链表
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;SLTNode* next = *pphead;while (pcur){next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

test.c 文件

#include "SList.h"//void test()
//{
//	SLTNode sl;
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	node2->data = 2;
//	node3->data = 3;
//	node4->data = 4;
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//}
void test()
{SLTNode SL;SLTNode* plist = NULL;SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//SLPushFront(&plist, 1);//SLPushFront(&plist, 2);//SLPushFront(&plist, 3);//SLPushFront(&plist, 4);//SLPopBack(&plist);//SLPopBack(&plist);//SLPopBack(&plist);//SLPopBack(&plist);//SLPopFront(&plist);//SLPrint(plist);//SLPopFront(&plist);//SLPrint(plist);//SLPopFront(&plist);//SLPrint(plist);//SLPopFront(&plist);//SLPrint(plist);SLTNode* find = SLTFind(plist, 3);//if (find)//	printf("找到了\n");//else//	printf("未找到\n");//SLTInsert(&plist, find, 6);//SLPrint(plist);//SLTInsertAfter(&plist, find, 5);//SLPrint(plist);//SLTErase(&plist, find);//SLPrint(plist);SLTEraseAfter(find);SLPrint(plist);
}
int main()
{test();return 0;
}