单链表的基本概念及特点
定义：
单链表是由一系列节点组成的线性序列，每个节点包含两个部分，一个是存储数据元素的数据域，另一个是指向下一个节点的指针域。最后一个节点的指针域为空（通常用NULL表示），表示链表的结束。
特点：
1、动态性：
单链表的存储空间是在程序运行过程中动态分配和释放的，可以根据实际需要灵活地增加或删除节点，不像数组那样需要预先分配固定大小的存储空间。
2、非连续性：
节点在内存中的存储位置可以是不连续的，通过指针将各个节点连接起来形成线性序列，这使得单链表在插入和删除操作时不需要像数组那样移动大量元素，提高了操作效率。
3、顺序性：
尽管节点存储位置不连续，但逻辑上仍然是线性顺序，可以通过从头节点开始逐个遍历指针来访问每个节点。
4、访问效率低：
由于节点存储位置不连续，不能像数组那样通过下标快速随机访问元素，需要从头节点开始逐个遍历指针来查找，时间复杂度为O(n)。
5、存储空间开销大：
每个节点除了存储数据外，还需要额外存储一个指针域，增加了存储空间的开销。
代码示例
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
数据的打印
void SLTPrint(SLTNode* phead)//打印
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
注意:
1这里不能使用assert断言，因为空指针也可以打印，在顺序表中能使用assert断言 ,是因为顺序表开辟的是一整块空间。
2cur=cur->next不能写出cur++，因为链表不是一整块连续的空间，它是由指针将它们连在一起。
新节点的创建
SLTNode* BuySLTNode(SLTDataType x)//创建新的节点，值为x
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
在尾部插入数据
1、首先找到原数据的尾部
2、将尾部的next指向newnode。
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找到尾部
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void testSLT()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
}
int main()
{
testSLT();
return 0;
}
注解：
1在函数的调用过程中，形参只是实参的一份临时拷贝，对形参的改变不影响实参
例：
int func(int y)
{
y = 2;
return y;
}
int main()
{
int x = 1;
func(x);
printf("%d ", x);
return 0;
}
如果想改变实参，就只能传递指针
int func(int* y)
{
*y = 2;
return *y;
}
int main()
{
int x = 1;
func(&x);
printf("%d ", x);
return 0;
}
2请分析这段代码为什么在尾部插入数据失败
void SLTPushBack(SLTNode* pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
if (pphead == NULL)
{
pphead = newnode;
}
else
{
//找到尾部
SLTNode* tail = pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void testSLT()
{
SLTNode* plist = NULL;
SLTPushBack(plist, 1);
SLTPushBack(plist, 2);
SLTPushBack(plist, 3);
SLTPushBack(plist, 4);
SLTPrint(plist);
}
int main()
{
testSLT();
return 0;
}
在函数调用传值时，要想改变实参，只需要使用一级指针，改变地址；同样，在传一级指针时，形参也是实参的临时拷贝，改变形参不影响实参，这时就需要使用二级指针，通过修改一级指针的地址来进行改变。
在头部插入数据
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void testSLT()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPushFront(&plist, 1);
SLTPrint(plist);
}
int main()
{
testSLT();
return 0;
}
在尾部删除数据
void SLTPopBack(SLTNode** pphead)//尾删
{
assert(*pphead);
//1、只有一个节点 2、有多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//找尾
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
void testSLT()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPushFront(&plist, 1);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
}
int main()
{
testSLT();
return 0;
}
在头部删除数据
void SLTPopFront(SLTNode** pphead)
{
assert(*pphead);
SLTNode* first = *pphead;
*pphead = first->next;
free(first);
first = NULL;
}
void testSLT()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
SLTPushFront(&plist, 1);
SLTPrint(plist);
SLTPopBack(&plist);
SLTPrint(plist);
SLTPopFront(&plist);
SLTPrint(plist);
}
int main()
{
testSLT();
return 0;
}
查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
插入数据
1在pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pos);
assert(pphead);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
// 找到pos的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
2在pos之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
删除数据
1在pos之前删除数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//assert(*pphead);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
// 找到pos的前一个位置
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
//pos = NULL;
}
}
2在pos之后删除数据
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
链表的销毁
void SLTDestory(SLTNode* phead)//销毁
{
SLTNode* cur = phead;
while (cur)
{
SLTNode* tmp = cur->next;
free(cur);
cur = tmp;
}
}
总结：
单链表是由一个个节点组成，每个节点包含数据元素和指向下一节点的指针。优点是动态存储，但是其查找效率低。
标签：pphead,单链,SLTNode,NULL,pos,next,详解,数据结构,plist From： https://blog.csdn.net/ccf3699f/article/details/145192066