什么是链表
链表： 通过指针将一系列离散的数据关联起来的数据整体叫链表
链表逻辑关系图示：
插入一点题外话： 这个链表就像楼房一样 数据就是每一层的房间，这个指针就像楼梯 这样一比喻 就能明白什么时候需要到楼顶，什么时候不需要到楼顶。
最简单链表的增删查改
- 链表的创建
链表的本质还是结构体，和线性表相比 线性表是连续的 因为 线性表是通过开辟一个连续的空间来存放的 链表的本质是通过指针将离散的结构体链在一起，所以叫链表。
typedef int SLTdataType;
typedef struct SListNode
{
SLTdataType data; // 使用typedef可以方便更改数据类型
struct SListNode* next; // 存放指向下一个结构体的指针变量
}SListNode;
这里的指针一定要注意 指针时结构体类型的 他是指向下一个结构体的。
- 链表的打印
先上代码
void SListprint(SListNode* ps)
{
assert(ps);//如果是空没有打印的必要
SListNode* cue = ps;
while (cue !=NULL)
{
printf("%d ", cue->data);
}
printf("\n");
}
原理解读
每进行一次cue = cue->next; cue指针就会获取下一个结构体的地址。
cue！=NULL与cue->next!=NULL的区别
cue不为空表示cue所指向的结构体不为空
cue->不为空表示cue->所指向的下一个结构体不为空
打印 需要遍历所有。所以使用cue！=NULL
这里需要爬完每一层楼 爬完每一层楼不就到楼顶了嘛。不就是cue->NULL嘛
- 链表的结点申请
```c
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode =
(SListNode*)malloc(sizeof(SListNode));// malloc开辟空间
assert(newnode);//防止空指针出现
newnode->data = x;
newnode->next = NULL;// 不知道他将要插入哪里 所以置空
return newnode;
}
- 链表的尾插
链表的尾插 两步操作
- 找到链表的尾巴
- 将新的结构体链接到尾巴上
void SListPushBack(SListNode* ps,SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* tail = ps;
while (tail->next != NULL)
{
tail = tail->next; //爬楼梯只需要爬到最高层
// 而不是楼顶 否则新来的无处可以上去
}
tail->next = newnode;
}
这个代码有一个问题 如果是链表是空的 ps指向的空 这个代码就处理不了 所以应多加一种情况
void SListPushBack(SListNode* ps, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* tail = ps;
if (ps == NULL)
{
ps = newnode;
}
else
{
while (tail->next != NULL)
{
tail = tail->next; //爬楼梯只需要爬到最高层
// 而不是楼顶 否则新来的无处可以上去
}
tail->next = newnode;
}
}
这个代码还有一个隐藏的问题 ps虽然是指针 但也是变量 出函数失效。
所以应该传二级指针
void SListPushBack(SListNode** ps, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* tail = *ps;
if (*ps == NULL)
{
*ps = newnode;
}
else
{
while (tail->next != NULL)
{
tail = tail->next; //爬楼梯只需要爬到最高层
// 而不是楼顶 否则新来的无处可以上去
}
tail->next = newnode;
}
}
- 头插
头插不就是修地下室嘛
头插也是两步：
- 第一步 给第一层修个去地下室楼梯
2. 第二步 把第一个改到地下室
void SListPsuhFront(SListNode** ps, SLTDataType x)
{
SListNode* newnode=BuySListNode(x);
newnode->next = *ps;
*ps = newnode;
}
- 链表的尾删
尾删两步
- 将楼梯置空
- 将最高层移除
void SListPopBack(SListNode** ps)
{
assert(ps);//空指针 直接报错
SListNode* tail = *ps;
if (tail->next == NULL)
{
*ps = NULL; //一层楼直接平地
}
else
{
SListNode* value = NULL;
while (tail->next != NULL)
{
value = tail; // 先爬到要删的最高层
tail = tail->next;
}
value->next = NULL;// 楼梯炸了
free(tail);
}
}
- 链表的头删
void SListPopFront(SListNode** ps)
{
assert(ps);
SListNode* head = *ps;
if (head->next == NULL)
{
*ps = NULL;
free(*ps);
}
else
{
*ps=head->next;
free(head);
}
}
转载：https://blog.csdn.net/qq_45849625/article/details/115794306
查看评论