当前位置：首页 > news >正文

认识单链表

news 2025/7/14 23:55:50

-之前我们学过储存数据的一种表——顺序表，那么为什么还有链表呢
首先我们回顾一下顺序表
顺序表是物理地址连续的一段内存空间（数组），我们通过动态内存开辟的，
那么：在这里插入图片描述
顺序表也有自己的一些优点，比如我们之前做过的一些题，可以通过下标来快速完成，因为他的地址是连续的所以只要利用下标的加减就可以实现

既然顺序表有缺点，那么我们就有了链表。（按需求申请空间）

在这里插入图片描述

通过插入数据，来理解链表

打印函数
在这里插入图片描述

在链表的尾部插入数据

在这里插入图片描述

代码：


SLTPushBack(SLTNode* plist, SLTDataType x)
{//首先要开辟一个结构体来把要插入的数据的内容写进去，在之前的BuySListNode函数就是干这个事情的SLTNode* newnode = BuySListNode(x);SLTNode* tail = plist;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}

上述的尾插是建立在之前已经头插了几个节点的情况下的

那么当链表还是空的时候，这样的尾插还适用吗
在这里插入图片描述
知道了这个问题我们来修改代码：

那么想要修改plist就要传址，

尾插总结图

头插：头插不管什么情况都要挪动plist的，所以也是传址操作，上面已经写到过头插的指针变换了，这里我们直接写代码就行

void TestSList3(){SLTNode* plist = NULL;SLTPushFront(&plist,5);SLTPushFront(&plist, 4);SLTPushFront(&plist, 3);SLTPushFront(&plist, 2);SLTPrin(plist);}void SLTPushFront(SLTNode** head, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *head;*head = newnode;}

在这里插入图片描述

尾删
在这里插入图片描述
代码：

//尾删SLTPopBack(&plist);SLTPrin(plist);SLTPopBack(&plist);SLTPrin(plist);SLTPopBack(&plist);SLTPrin(plist);SLTPopBack(&plist);SLTPrin(plist);SLTPopBack(&plist);SLTPrin(plist);

void SLTPopBack(SLTNode** head)
{assert(*head);if ((*head)->next == NULL){free(*head);*head = NULL;}else{SLTNode* stail = NULL;SLTNode* tail = *head;while (tail->next!=NULL){stail = tail;tail = tail->next;}free(tail);stail->next = NULL;}
}

在这里插入图片描述

头删
在这里插入图片描述

代码：

SLTPopFront(&plist);SLTPrin(plist);SLTPopFront(&plist);SLTPrin(plist);SLTPopFront(&plist);SLTPrin(plist);SLTPopFront(&plist);SLTPrin(plist);void SLTPopFront(SLTNode** head)
{assert(*head);SLTNode* newnode = (*head)->next;free(*head);*head = newnode;
}

在这里插入图片描述

查找链表中的数的指针，并改变这个指针所指节点的数据

在这里插入图片描述
代码：

//查找链表中的一个值的指针，并且改变他SLTNode* newnode = SLTFind(plist, 3);newnode->data = 20;SLTPrin(plist);
SLTNode* SLTFind(SLTNode* head, SLTDataType x)
{SLTNode* cur = head;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在Pos位置插入节点
在这里插入图片描述
代码：

//在指定数据的指针pos位置前插入一个节点SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针posSLTnsert(&plist, pos, 30);SLTPrin(plist);
void SLTnsert(SLTNode** head, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *head){SLTPushFront(head, x);//头插}else{SLTNode* prev = *head;while (prev->next != pos){prev = prev->next;//找到pos位置之前的那个节点的指针}SLTNode* newnode= BuySListNode(x);//为要插入的数据创建一个节点prev->next = newnode;newnode->next = pos;}
}

在这里插入图片描述
在pos位置之后插入节点

代码:

SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针pos/*	SLTnsert(&plist, pos, 30);SLTPrin(plist);*/SLTnsertAfter(plist, pos, 30);SLTPrin(plist);
void SLTnsertAfter(SLTNode* head, SLTNode* pos, SLTDataType x)
{assert(head);SLTNode* newnode = BuySListNode(x);//为要插入的数据创建一个节点newnode->next = pos->next;pos->next = newnode;
}

删除Pos位置的节点
在这里插入图片描述

SLTErase(&plist, pos);pos = NULL;SLTPrin(plist);void SLTErase(SLTNode** head, SLTNode* pos)
{assert(pos);if (pos == *head){SLTPopFront(head);//头删}else{SLTNode* per = *head;while (per->next!=pos){per = per->next;}per->next = pos->next;free(pos);}
}

删除pos位置之后的节点
在这里插入图片描述
代码：

SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针posSLTEraseAfter(pos);SLTPrin(plist);
void SLTEraseAfter(SLTNode* pos)
{assert(pos->next);assert(pos);SLTNode* per = pos->next;pos->next = per->next;free(per);}