目录

概念

 链表的单个结点

 链表的打印操作

新结点的申请

尾部插入

头部插入

尾部删除

头部删除

查找

在指定位置之前插入数据

在任意位置之后插入数据

测试运行一下：

 删除pos结点

 删除pos之后结点

 销毁链表

---

概念

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

链表的每个结点有两个部分，分别是数据和指向下个结点的指针，每个链表的最后一个结点的下一个结点为NULL（不能对NULL解引用）。

放一张bit课件里的图,我觉得很形象：

---

 链表的单个结点

<code>typedef int SLDataType;//重定义一下在链表内存放的数据类型，方便后期对类型进行统一修改

//链表的单个结点

typedef struct SListNode {//Single List Node :链表结点

SLDataType data;//存放的数据

struct SListNode* next;//指向下一个结点的指针

}SLNode;//重定义名字方便后期使用

---

 链表的打印操作

//链表的打印操作

void SLPrint(SLNode* phead) {

assert(phead);//不能传入空指针

SLNode* pcur = phead;

//pointer cursor:指针光标，不让头结点丢失(虽然不会改变头结点的指向)

while (pcur) {//等同于pcur!=NULL

printf("%d->", pcur->data);//打印此结点的数据

pcur = pcur->next;//使pcur指向下一个结点

}

printf("NULL\n");

}

---

新结点的申请

后面会涉及到新结点的插入，申请新结点可以封装成一个函数，避免代码冗余

//新结点的申请

SLNode* SLBuyNode(SLDataType x) {

SLNode* node = (SLNode*)malloc(sizeof(SLNode));

if (!node) {//返回值为空,申请失败(一般是空间不足了)，直接退出

perror("malloc fail");

exit(1);

}

node->data = x;//将数据赋给data

node->next = NULL;//将下一个节点置为NULL;

return node;

}

---

尾部插入

//尾部插入

void SLPushBack(SLNode** pphead, SLDataType x) {

//注意在这里我们传参的是二级指针，因为我们需要在函数内部改变头结点的指向

assert(pphead);//不能传NULL

//新结点的申请

SLNode* node=SLBuyNode(x);

if (*pphead == NULL) {

*pphead = node;

}

else {

SLNode* pcur = *pphead;

while (pcur->next) {//找到next元素为NULL的结点，也就是为链表尾部

pcur = pcur->next;

}

pcur->next = node;

}

}

测试运行一下：

---

头部插入

<code>//头部插入

void SLPushFront(SLNode** pphead, SLDataType x) {

assert(pphead);

SLNode* node = SLBuyNode(x);

//这里需要处理头结点为空的情况吗？不需要，因为没有涉及到解引用其元素

node->next = *pphead;

*pphead = node;

}

测试运行一下：

---

尾部删除

<code>//尾部删除

void SLPopBack(SLNode** pphead) {

assert(*pphead && pphead);//

if (!(*pphead)->next) {//处理只有一个元素的情况

free(*pphead);

*pphead = NULL;

}

else {

SLNode* prev = NULL;

SLNode* pcur = *pphead;

while (pcur->next) {//找到尾结点前一个结点

prev = pcur;

pcur = pcur->next;

}

free(pcur);//将尾结点释放

pcur = NULL;

prev->next = NULL;//将尾结点的前一个结点的next元素置为NULL

}

}

测试运行一下：

---

头部删除

<code>//头部删除

void SLPopFront(SLNode** pphead) {

assert(*pphead && pphead);

SLNode* next = (*pphead)->next;//保存头结点的下一个结点地址

free(*pphead);//释放头结点

*pphead = next;//使头结点指向下一个结点

}

测试运行一下：

---

查找

在链表中想要对指定位置进行操作不能使用下标，所以我们必须找到指定位置的地址才能对其进行操作。

<code>//查找

SLNode* SLFind(SLNode* phead, SLDataType x) {

assert(phead);

SLNode* pcur = phead;

while (pcur) {

if (pcur->data == x) {

return pcur;

}

pcur = pcur->next;

}

return NULL;

}

---

在指定位置之前插入数据

//在指定位置之前插入数据

void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) {

assert(pphead && pos && *pphead);//pos和pphead不能为空,以及pphead指向空间不能为空

if (*pphead == pos) {//处理头插的情况

SLPushFront(pphead,x);

}

else {

SLNode* node = SLBuyNode(x);

SLNode* pcur = *pphead;

while (pcur->next != pos) {//找到pos前一个结点

pcur = pcur->next;

}

node->next = pcur->next;

pcur->next = node;

}

}

测试运行一下：

---

在任意位置之后插入数据

<code>//在任意位置之后插入数据

void SLInsertAfter(SLNode* pos, SLDataType x) {

assert(pos);//pos不能为空

SLNode* node = SLBuyNode(x);

node->next = pos->next;

pos->next = node;

}

测试运行一下：

---

 删除pos结点

<code>//删除pos结点

void SLErase(SLNode** pphead, SLNode* pos) {

assert(*pphead && pphead && pos);

if (*pphead == pos) {//处理头删的情况

SLPopFront(pphead);

}

else {

SLNode* pcur = *pphead;

while (pcur->next!= pos) {

pcur = pcur->next;

}

pcur->next = pos->next;

free(pos);

pos = NULL;

}

}

 测试运行一下：

---

 删除pos之后结点

<code>//删除pos之后结点

void SLEraseAfter(SLNode* pos) {

assert(pos && pos->next);//pos后面的结点也不能为空

SLNode* next = pos->next;

pos->next = next->next;

free(next);

next = NULL;

}

 测试运行一下：

 

---

 销毁链表

<code>//销毁链表

void SLDestory(SLNode** pphead) {

assert(pphead && *pphead);

SLNode* pcur = *pphead;

while (pcur) {

SLNode* nextnode = pcur->next;//使用一个变量接受下一个结点地址

free(pcur);

pcur = nextnode;

}

*pphead = NULL;

}