目录
前言
?
🌏一、链表
🍯1链表的概念及结构
🍤链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
🍯2链表的分类
🍤链表在逻辑上是连续的，但是在物理上不是连续的。
🍤现实中节点是从堆上申请的
?🍯3链表自定义
SListNode* slist = NULL;
SListNode* n1 = malloc(sizeof(SListNode));
SListNode* n2 = malloc(sizeof(SListNode));
SListNode* n3 = malloc(sizeof(SListNode));
n1->data = 1;
n2->data = 2;
n3->data = 3;
n1->next = n2;
n2->next = n3;
n3->next = NULL;
slist = n1;🍯4链表的实现?
????????🍍单个节点的定义
🍤实现单个链表结构体
typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;//存储的数据
struct SListNode* next;//下一个数据的地址
}SListNode;
🍤故使用typedef，后续若是需要修改，改动typedef就足够了?
????????🍍链表的接口
//打印链表
void SListPrint(SListNode* phead);
//销毁链表
void SListDestory(SListNode** pphead);
//尾插
void SListPushBack(SListNode** pphead, SLDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SLDataType x);
//头删
void SListPopFront(SListNode** pphead);
//查找
SListNode* SListFind(SListNode* phead, SLDataType x);
//任意位置后插入
void SListInsertAfter(SListNode* pos, SLDataType x);
//任意位置后删除
void SListEraseAfter(SListNode* pos);
????????🍍单链表的打印?
🍤不用断言phead，如果是空，就打印空
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
?????????🍍单链表的尾插
🍤原来链表指向的是NULL，我们要让这个指向发生改变，指向这个新开辟的节点，节点应该是在堆上开辟的，因为形参是实参的一份临时拷贝，所以传参来改变指针的指向只能通过二级指针来改变，一级指针是不行的。传一级指针不会head的指向,关键是我们是是否需要改变Slist的值。
void SListPushBack(SListNode** pphead, SLDataType x)
{
SListNode* newNode = BuySListNode(x);
assert(pphead);
//1.链表为空
if (*pphead == NULL)
{
*pphead = newNode;
}
//2.链表不为空
else
{
SListNode* cur = *pphead;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newNode;
}
}
?🍤错误：cur存放的是newNode的的值，函数结束的时候销毁函数，没有指向最后一个元素的next指向新插入的节点，不因该是用一个空指针指向next
SListNode* cur = *pphead;
while (cur != NULL)
{
cur = cur->next;
}
cur->next = newNode;🍤这里我把申请节点封装成了一个函数?
SListNode* BuySListNode(SLDataType x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
newNode->data = x;
newNode->next = NULL;
return newNode;
}
????????🍍单链表的头插
🍤头插比较简单，无论是链表为空还是不为空都不用单独考虑，只要考虑到传
二级指针就可以很好的实现了。?
void SListPushFront(SListNode** pphead, SLDataType x)
{
//第一步,创建新节点
SListNode* newNode = BuySListNode(x);
//第二步,新结点链接原来的头结点
newNode->next = *pphead;
//第三步,phead指针指向新节点
*pphead = newNode;
}
?????????🍍单链表的尾删
🍤分三种情况判断，没有节点，一个节点，多个节点
void SListPopBack(SListNode** pphead)
{
//分三种情况
//1.没有节点
//2.只有一个节点
//3.两个及两个以上的节点
//assert(*pphead);//暴力解决
if (*pphead == NULL)
{
return;//温柔解决
}
else if ((*pphead)->next == NULL)
{
free(*pphead);//释放指针指向空间
*pphead = NULL;
}
else
{
SListNode* prev = NULL;//前一个节点
SListNode* cur = *pphead;//当前节点
while (cur->next != NULL)
{
prev = cur;
cur = cur->next;
}
free(cur);
cur = NULL;
prev->next = NULL;
}
}
????????🍍单链表的头删
🍤链表为空，链表不为空，两种情况讨论
void SListPopFront(SListNode** pphead)
{
if (*pphead == NULL)
{
//让程序能继续
return;
}
else
{
SListNode* firstNode = *pphead;
//多结点，第一步,保留第二个结点地址
*pphead = (*pphead)->next;
//第二步,释放第一个结点
free(firstNode);
//第三步,连接第二个
firstNode = NULL;
}
}
????????🍍单链表的查找
🍤过给出的节点地址来查找，并返回该节点的地址，找不到就返回
NULL
SListNode* SListFind(SListNode* phead, SLDataType x)
{
SListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
????????🍍单链表的在pos位置之后插入
🍤找到目标结点之前结点
🍤创建新结点
🍤新结点链接目标结点
🍤原目标结点之前的结点链接新结点
?🍤一下是两种写法，更推荐第一种，不用考虑顺序问题
void InsertAfter_Linked_list(Linked_list* pos, Linked_list_data x) {
assert(pos);
//指向pos的下一个位置
Linked_list* next = pos->next;
Linked_list* newnode = Application_Linked_list(x);
//将pos指向newnode
pos->next = newnode;
//将newndoe指向next
newnode->next = next;
}void InsertAfter_Linked_list(Linked_list* pos, Linked_list_data x) {
assert(pos);
//申请一个新空间
Linked_list* newnode = Application_Linked_list(x);
//将pos的下一个节点地址存在newnode中(注意顺序不能调换)
newnode->next = pos->next;
//将pos指向newndoe
pos->next = newnode;
}???????🍍单链表的在pos位置之前插入
void Insert_Linked_list(Linked_list** pphead, Linked_list* pos, Linked_list_data x) {
assert(pphead);
assert(pos);
//pos是第一个节点
//pos不是第一个节点
if (*pphead == pos) {
PushFront_Linked_list(pphead, x);
}
else {
Linked_list* pre = *pphead;
while (pre->next != pos) {
pre = pre->next;
}
//创建一个新结构体
Linked_list* newnode = Application_Linked_list(x);
//将pre指向newnode
pre->next = newnode;
//将newnode指向pos
newnode->next = pos;
}
}??🍤更加推崇在pos位置之后插入，因为在pos位置之前插入要考虑是否为空
?????????🍍单链表的在pos位置删除
void Erase_Linked_list(Linked_list** pphead, Linked_list* pos) {
assert(pos);
assert(pphead);
//判断是不是头删
if (*pphead == pos) {
PopFront_Linked_list(pphead);
}
else {
Linked_list* cur = *pphead;
while (cur->next != pos) {
cur = cur->next;
}
//将pos指向要删除的结构体的下一个
cur->next = pos->next;
free(pos);
pos = NULL;
}
}????????🍍单链表的在pos位置之后删除
void EraseAfter_Linked_list(Linked_list* pos) {
assert(pos);
Linked_list* next = pos->next;
if (next != NULL) {
pos->next = next->next;
free(next);
next = NULL;
}
}
?🍤更推荐在pos位置之后删除，这样时间复杂度是O(n)，在pos位置删除时间复杂度是O(n)
????????🍍单链表的销毁
void Destroy_Linked_list(Linked_list** pphead) {
assert(pphead);
Linked_list* cur = *pphead;
while (cur != NULL) {
//保存cur的下一个
Linked_list* next = cur->next;
free(cur);
cur = next;
}
//哨兵滞空
*pphead = NULL;
}
总结
🍤适合头插头删.尾部或者中间某个位置插入删除不适合。
🍤双向链表比单链表更适合存储数据
🍤单链表学习的意义:????????1、单链表会作为复杂数据结构的子结构(图的邻接表、哈希桶)
????????2、单链表会出很多经典的练习题
?
