DS线性表之单链表的讲解和实现(2)

---

前言

  本篇的单链表完全来说是单向不带头单链表，这种和另外一种链表(双向带头循环链表)使用最广泛，我们只要对它们两个有所了解即可

  正文开始！

---

一、链表的概念

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

二、链表的分类

三、链表的结构

  就如同下图一样，一节一节，前面连着后面就是链表的一种表现


同时我们也发现以下几点：

1. 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 节点一般都是在堆上申请出来的
3. 从堆上申请空间，两次申请得到的内存可能连续，也可能不连续

物理结构：数据实际存储在内存中的结构；
逻辑结构：想象出来的结构

四、前置知识准备

在正式开始实现之前，我希望你有以下认识：

1. 实现部分接口需要通过二级指针接受实参：原因在于我们需要可以修改实参（而形参只是实参的一份拷贝，要想修改实参，必须得传指针，同样若实参本来就是指针，那么就要传指针的指针，即二级指针），而是实参为一级指针时(同样是传递地址)，需要使用二级指针进行接受，否则获得临时拷贝，不会影响到实参。修改实参的情况，比如一开始为空，在插入时需将头指针存储在有效结点的的地址上，需要改变实参的值
2. 单链表的初始化：这里实现链表，没有必要进行初始化，初始化对于一开始就要开辟的空间有初始化的需求，表示多个节点通过地址链接在一起，那么只需要开辟新节点的时候，初始化下就行了(有哨兵位需要初始化)
3. 二级指针断言：二级指针存放的是头节点的地址，头节点的地址为空，那么还有什么意义呢？

五、单链表的模拟实现

定义头节点

//单链表节点
//根据定义需要存储一个数据和一个指向下一个结点的指针
typedef int SLDataType;//定义数据类型，可以根据需要更改，typedef一下就很方便
typedef struct SList
{SLDataType data;    //数据域 存储数据struct SList* next; //指针域 存储指向下一个结点的指针
}SList;

请注意，这里不能在节点内就单独用SList来定义next指针，因为这时候还没有typedef成功呢，还在节点内部

初始化单链表

因为创建一个变量实质是给变量开辟一块内存空间，但是这块内存空间可能有遗留的数据，所以在创建变量之后需要进行初始化，而数据域我们也不清楚到底该传那个，随便传个0就行，但是指针域就必须置空了，否则就是野指针

void SListInit(SList* phead)
{assert(phead);     //防止传入空指针，传入则报错phead->data = 0;   //将数据初始化为0phead->next = NULL;//将结点指针初始化为NULL
}

销毁单链表

有开辟内存，自然而然的就有还回内存，即销毁单链表

void SListDestroy(SList* phead)
{assert(phead);SList* cur = phead; //为了能在后序找到头结点，所以新创建一个变量指向头结点while (cur != NULL){SList* next = cur->next;free(cur);cur = next;}
}

我们不妨来想想为什么是传一级指针即可，首先，我们这里是为了销毁内存，虽然说形参的这个节点指针和实参的节点指针地址不一样，但是所存的节点都是同一个节点！，所以可以直接传指针，有因为我们说链表在物理上是不连续的，所以得通过指针跳着跳着一个个销毁

打印单链表

同样的，我们只要传一级指针就可以了，且通过指针来跳转

void SListPrint(SList* phead)
{assert(phead);SList* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

申请节点

在插入中使用相当频繁，所以我们再对此单独实现一个函数，使得代码更加的结构化

请注意，指针并不单独开空间，它起到的更多是一个中间人的作用，通过指针来控制

SList* BuySeqList(SLDataType x)
{SList* pnewNode = (SList*)malloc(sizeof(SList));//动态开辟一个单链表类型大小if (pnewNode == NULL)//动态开辟的内存不一定成功，所以需要判断{printf("malloc fail\n");exit(-1);}//内存开辟成功则把数据赋值到指定位置pnewNode->data = x;pnewNode->next = NULL;return newnode;
}

头插数据

void SListPushFront(SList** pphead, SLDataType x)
{SList* newnode = BuySeqList(x);newnode->next = *pphead;*pphead = newnode;
}

尾插数据

void SListPushBack(SList** pphead, SLDataType x)
{SList* newnode = BuySeqList(x);if (*pphead == NULL) // 没有节点的时候{*pphead = newnode;}else // 有节点的时候{SList* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

头删数据

void SListPopFront(SList** pphead)
{assert(*pphead);//头结点不为空则有数据SList* head = (*pphead)->next;free(*pphead);*pphead = head;
}

尾删数据

void SListPopBack(SList** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SList* tail = *pphead;SList* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

查询数据

找到则返回当前当前数据结点地址，没找到则返回空地址

SList* SListFind(SList* phead, SLDataType x)
{assert(phead);SList* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos位置之后插入数据

void SListInsertAfter(SList* pos, SLDataType x)
{assert(pos);SList* newnode = BuySeqList(x);SList* next = pos->next;pos->next = newnode;newnode->next = next;
}

删除pos位置之后的数据

void SListEraseAfter(SList* pos)
{assert(pos);assert(pos->next);//判断pos之后是否有数据，没数据则报错SList* next = pos->next->next;free(pos->next);pos->next = next;
}

---

总结

  链表可以说是CS学生遇到的第二个劝退点了（第一个是指针），它是我们所学知识的一个集成展现，需要我们对前面知识的充分掌握，所以对计算机来说，知识比较连贯，这也是学习它比较难受的地方