1、开辟内存
/************开辟内存**************/
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if(newnode == NULL)
{
printf("malloc failed\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
2、初始化链表
/************初始化链表**************/
void SListInit(SLTNode** pphead)
{
*pphead = NULL;//传头指针的地址,通过解引用改变头指针。
}
3、打印链表
/************打印链表**************/
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;//不能直接用phead(头指针)访问数据,改变phead的值会导致数据丢失。
while(cur != NULL)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL\n");
}
4、尾插
/**************尾插 ***************/
void SListPushBack(SLTNode** pphead,SLTDataType x)
{
assert(pphead);
//申请新节点
SLTNode* newnode = BuyListNode(x);
//头指针为空不找尾
if(*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
//找到尾,尾节点标志,next为空
while(tail->next != NULL)
{
tail = tail->next;
}
//串联节点
tail->next = newnode;
}
}
5、尾删
/***************尾删****************/
void SListPopBack(SLTNode** pphead)
{
//空链表
if(*pphead == NULL)
{
return;
} //assert(*pphead != NULL);
//1个节点
if((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//2个及以上节点
else
{
SLTNode* tail = *pphead;
/*
两个方法均适用于大于一个的链表
方法一:借助一个变量
SLTNode* prev = NULL;
//while(tail->next),0(NULL)假,1真
while(tail->next != NULL)
{
prev = tail;//保存前一个指针
tail = tail->next;
}
free(tail);
prev->next = NULL;
*/
//方法二:判断tail->next->next为空
while(tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
6、头插
/**************头插 ***************/
void SListPushFront(SLTNode** pphead,SLTDataType x)
{
SLTNode* newnode = BuyListNode(x);
/*
if(*pphead == NULL)
{
newnode->next = NULL;
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead =newnode;
}
*/
newnode->next = *pphead;//对于空链表同样适用,因为空链表的头指针就是NULL。
*pphead =newnode;
}
7、头删
/**************头删****************/
void SListPopFront(SLTNode** pphead)
{
//空链表
if(*pphead == NULL)
{
return;
}
//assert(*pphead != NULL);
//1个及以上节点
else
{
SLTNode* next = (*pphead)->next;//先储存下一个节点的地址,否则free之后会丢失
free(*pphead);
*pphead = next;
}
}
8、查找
/**************查找数据***************/
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
SLTNode* cur = phead;
while(cur)
{
if(cur->data == x)
{
return cur;//找到
}
else
{
cur = cur->next;
}
}
return NULL;//未找到
}
9、特定位置插入
/**************在pos位置之前(单链表不太适合)插入数据***************/
void SListInsertBefore(SLTNode** pphead,SLTNode* pos,SLTDataType x)
{
SLTNode* newnode = BuyListNode(x);
if(*pphead != pos)
{
SLTNode* pre = *pphead;//保存pos的前一个位置
/*
找pos的前一个位置
SLTNode* cur = *pphead;
while(cur->data != (*pos)->data)
{
pre = cur;
cur =cur->next;
}
*/
while(pre->next != pos)
{
pre = pre->next;
}
pre->next = newnode;
newnode->next = pos;
}
else//头插
{
newnode->next = pos;
*pphead = newnode;
}
}
/**************在pos位置之后插入数据 ***************/
void SListInsertAfter(SLTNode* pos,SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;//注意先后顺序
pos->next = newnode;
}
10、特定位置删除
/**************在pos位置删除数据***************/
void SListErase(SLTNode** pphead,SLTNode* pos)
{
assert(pphead);//地址不可能为空,错误的一种表示,方便调试
assert(pos);
if(*pphead == pos)
{
*pphead = pos->next;
free(pos);
}
else
{
SLTNode* pre = *pphead;//保存pos的前一个位置
while(pre->next != pos)
{
pre = pre->next;
}
pre->next = pos->next;
free(pos);
}
}
/**************删除pos位置之后数据***************/
void SListEraseAfter(SLTNode* pos)
{
assert(pos->next != NULL);//断言
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
11、销毁链表
/**************毁灭链表***************/
void SListDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while(cur != NULL)
{
SLTNode* next = cur->next;//保存后一个地址
free(cur);
cur = next;
}
*pphead = NULL;
}
标签:pphead,单链,SLTNode,实现,pos,next,newnode,NULL
From: https://blog.csdn.net/qq_63057731/article/details/140822568