目录
链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。
?
今天我们主要了解的是链表中的单链表
我们对一个结构体简单定义
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;对于一个单链表，我们一般需要实现的功能如下
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestory(SListNode* plist);下面是每一个功能的具体实现
动态申请一个节点
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
plist->data = x;
plist->next = NULL;
return plist;
}这里我们利用了return把创建的节点返回.
单链表打印
// 单链表打印
void SListPrint(SListNode* plist)
{
while (plist)
{
printf("%d->", plist->data);
plist = plist->next;
}
printf("NULL\n");
}这里我们依次打印，直到最后一个节点.
单链表的尾删
对于尾删我们需要考虑以下几种情况：
1.单链表已空? ? ? 2.只有一个节点? ? ? ?3.具有多个节点?
已空的话，我们就不能对单链表进行删除了
只有一个节点的话，我们直接将单链表空间释放，然后再置空就好了。
具有多个节点的话，我们需要将最后一个节点释放，然后再将前一个结点的尾节点置空。（这里我们需要保存前一个节点）
//尾删
void SLictPopBack(SListNode **pphead)
{
assert(pphead);
SListNode*tail = *pphead;//
//如果只有一个
if (tail->next == NULL)
{
free(tail);
tail = NULL;
}
//如果有多个
else
{
//先找到前一个位置
while(tail->next->next )
{
tail = tail->next;
}
//释放后一个位置
free(tail->next);
tail->next = NULL;
}
}
单链表的头删
?单链表的头删我们需要考虑的情况如下
?1.单链表已空? ? 2.只有一个节点? ?3.具有多个节点
单链表已空的话，我们不能删除，直接判断一下就好了
单链表只有一个节点的情况跟尾删一样，直接释放再置空就好了.
单链表有多个节点的话，我们保存第二个节点，然后释放第一个节点，然后将链表指针指向第二个节点就好了.
//头删
void SListPopFront(SListNode** pphead)
{
assert(pphead&&*pphead );
SListNode* next = (*pphead)->next;//
//如果只有一个
if (next==NULL)
{
free(*pphead);
*pphead = NULL;
}
//如果有多个
else
{
free(*pphead);
*pphead =next ;
}
}
?单链表尾插
单链表的尾插我们需要考虑的情况如下
1.单链表已空? 2.单链表非空
单链表已空的话我们直接创建一个节点
单链表非空的话，我们直接在链表后方接一个节点
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
//如果链表为空，创建链表
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
//链表非空
else
{
SListNode* cur = *pplist;
while (cur->next)//找到最后一个节点
{
cur = cur->next;
}
cur->next = BuySListNode(x);//接上我们新建的节点
}
}单链表的头插
单链表的头插我们需要考虑的情况如下
1.单链表已空? 2.单链表非空
这里我们会发现无论单链表是否为空，我们直接在前面加一个节点就好了，所以不在乎链表是否为空.
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode* cur = BuySListNode(x);//建立新节点
cur->next = *pplist;
*pplist = cur;
}?单链表的查找
单链表的查找我们需要考虑的情况如下
1.单链表为空? ? 2.单链表中不含我们要查找的节点? 3.单链表含有我们要查找的节点
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
while(plist)
{
if (plist->data==x)
{
return plist;//找到了返回
}
plist = plist->next;//找不到继续往后
}
return NULL;
}单链表在pos位置之后插入x
这里我们只需要注意将节点正确连接就好了
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
SListNode* newnode= BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}?单链表删除pos位置之后的值
我们只需要分析下一个节点是否为空
然后将节点间正确连接就好了.
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next)//如果下一个节点非空
{
SListNode* next = pos->next;
pos->next=pos->next->next;
free(next);
}
}?单链表的销毁
// 单链表的销毁
void SListDestory(SListNode** plist)
{
assert(plist);//判空
SListNode* prev, * cur;
cur = *plist;
prev = NULL;
while (cur)
{
prev = cur;
cur = cur->next;
free(prev);
}
*plist = NULL;
}?所有函数代码
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
plist->data = x;
plist->next = NULL;
return plist;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
while (plist)
{
printf("%d->", plist->data);
plist = plist->next;
}
printf("\n");
}
//尾删
void SLictPopBack(SListNode **pphead)
{
assert(pphead);
SListNode*tail = *pphead;//
//如果只有一个
if (tail->next == NULL)
{
free(tail);
tail = NULL;
}
//如果有多个
else
{
//先找到前一个位置
while(tail->next->next )
{
tail = tail->next;
}
//释放后一个位置
free(tail->next);
tail->next = NULL;
}
}
//头删
void SListPopFront(SListNode** pphead)
{
assert(pphead&&*pphead );
SListNode* next = (*pphead)->next;//
//如果只有一个
if (next==NULL)
{
free(*pphead);
*pphead = NULL;
}
//如果有多个
else
{
free(*pphead);
*pphead =next ;
}
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
assert(pplist);
//如果链表为空，创建链表
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
//链表非空
else
{
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;
}
cur->next = BuySListNode(x);
}
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
assert(pplist);
SListNode* cur = BuySListNode(x);
cur->next = *pplist;
*pplist = cur;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
while(plist)
{
if (plist->data==x)
{
return plist;
}
plist = plist->next;
}
return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
SListNode* newnode= BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next)
{
SListNode* next = pos->next;
pos->next=pos->next->next;
free(next);
}
}
// 单链表的销毁
void SListDestory(SListNode** plist)
{
assert(plist);
SListNode* prev, * cur;
cur = *plist;
prev = NULL;
while (cur)
{
prev = cur;
cur = cur->next;
free(prev);
}
*plist = NULL;
}