单链表的全称为"不带头单向不循环链表"
注意:
下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点
链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的
链表是由一个一个节点构成的,一个节点分为两部分:存储的数据和指针(结构体指针)
其中的指针存储的是该节点指向的下一个节点的地址
一个节点的结构体可以这样表示:
typedef int SLDataType;
typedef struct SListNode
{
int date;
struct SListNode* next;
}SLTNode;一.链表的打印
SLT = single linked list文章来源：https://www.toymoban.com/news/detail-811056.html
void SLTPrint(SLNode * phead)
{
SLTNode* pcur = phead;
while(pcur != NULL)//遍历链表,pcur为空时跳出循环
{
printf("%d->",pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}二.链表的尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
if(pphead == NULL)//如果为空,则根本不存在链表,自然不能插入
return;
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
//链表存在,但是内容为空,新节点作为phead
if(*pphead == NULL)
{
*pphead = newnode;
return;
}
//链表不为空
SLTNode* ptail = *pphead;
while(ptail->next != NULL)//找到链表的尾节点,pcur->next为空时,则当前pcur为链表的最后一个节点
ptail = ptail->next;
ptail->next = newnode;
}注意:需要改变的是指针的值,因此在传参时需要传入指针的地址,,因此函数需要一个二级指针作为形参文章来源地址https://www.toymoban.com/news/detail-811056.html
三.链表的头插
//申请一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
if(pphead == NULL)//如果为空,则根本不存在链表,自然不能插入
return;
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *pphead;
*pphead = newnode;
}四.链表的尾删
void SLTPopBack(SLTNode** pphead)
{
if(pphead == NULL)
return;
if(*pphead == NULL)
return;
//链表只有一个节点
if((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
//链表有多个节点
SLTNode* ptail = *pphead;//尾节点
SLTNode* prev = NULL;//尾节点的前一个节点
while(ptail->next != NULL)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}五.链表的头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}六.链表数据的查找
void SLTFind(SLTNode* phead,SLTDataType x)
{
assert(pphead);
SLTNode* pcur = phead;
while(pcur != NULL)
{
if(pcur->data == x)
return pcur;
pcur = pcur->next;
}
//没有找到
return NULL;
}七. 指定位置前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x)
{
assert(pphead);
assert(pos);
//链表不能为空,如果为空,则pos数据一定不合法
assert(*pphead);
//pos是头节点时
if(pos == *pphead)
//头插
{
SLTPushFront(pphead,x);
return;
}
//pos不是头节点时
//pos如果时头节点,则while死循环,程序报错
SLTNode* prev = *pphead;
while(prev->next != pos)//prev最终为pos前的节点
{
prev = prev->next;
}
//prev->newnode->pos
prev->next = newnode;
newnode->next = pos;
}八.指定位置后插入数据
//由于该链表为单向链表,所以在找pos前面的节点时就需要遍历链表
//但是在找pos后的节点时,就可以直接用pos定位,不需要头节点了
void SLTInsertAfter(SLTNode* pos,SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
九.删除特定节点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
//删除的节点是头节点时
if(*pphead == pos)
{
SLTPopFront(pphead);
return;
}
//删除的节点不为头节点时
SLTNode* prev = *pphead;
//找到pos前的节点
while(prev->next != pos)
{
prev = prev->next
}
prev->next = pos->next;
free(pos);
pos = NULL;
}十.删除特定节点之后的节点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
//先保存需要删除的节点
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
}十一.销毁链表
void SListDestory(SLTNode* pphead)
{
//由于链表的存储不是线性的,所以无法一次销毁整个链表
//因此选择循环删除链表(一个一个删)
SLTNode* pcur = *pphead;
while(pcur != NULL)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}到了这里，关于数据结构:单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
