长沙网站设计公司哪家好,php音乐网站设计,百度链接提交入口,seo就是搜索引擎广告目录
一.相关指针知识点
二.链表
1.为什么学了顺序表还要学链表
2.优点
三.实现
1.链表的打印 —— 理解链表结构
(2) 物理结构图
2.链表的尾插 —— 入门
错误写法#xff1a;tail ! NULL
总结#xff1a;
正确代码物理图解#xff1a;
(2) 尾插整体代码 (思考…目录
一.相关指针知识点
二.链表
1.为什么学了顺序表还要学链表
2.优点
三.实现
1.链表的打印 —— 理解链表结构
(2) 物理结构图
2.链表的尾插 —— 入门
错误写法tail ! NULL
总结
正确代码物理图解
(2) 尾插整体代码 (思考对吗?)
Bug
3.头插
4.尾删
Bug
5.头删
6.查找
7. Find 查找的功能
1pos 之前插入
2pos 位置删除
3pos 之后插入
4pos位置后面删除 8.销毁 四.思维提升
五.总结
1.传什么
2.要不要断言
1打印、查找
2pphead
3*pphead
六.整体代码
SList.h
SList.c 一.相关指针知识点
调用一个函数就会建立一个空间这个空间叫栈帧。局部变量是存放在栈帧里的除了static修饰的局部变量。函数结束栈帧空间就销毁局部变量也销毁
函数传参不管是传值还是传地址其实都是拷贝。就看拷贝值还是地址。
代码1y 的改变不会改变 x 的值
void Func(int y)
{y 1;
}
int main()
{int x 0;Func(x);return 0;
}
这是两个栈帧Func 里面是 ymain 里面是 x。x 传给 y 是拷贝给 yy 的改变不会影响 x并且 Func 会销毁
代码2解决上面问题传地址。改变的是 int 使用的是 int 的指针
void Func(int* p)
{*p 1;
}
int main()
{int x 0;Func(x);return 0;
}
这里的 p 是 x 地址的拷贝。在传参里面我们要改变什么就要用它的指针。然后 * 解引用可以改变
代码3
void Func(int* ptr)
{ptr (int*)malloc(sizeof(int));
}
int main()
{int* px NULL;Func(px);free(px); // 加上也没用return 0;
}
这也是拷贝值把 px 的值拷贝给 ptrptr 是空。但是我 malloc 了一块空间让 ptr 指向这块空间。 px 拷贝给 ptrptr 的改变不会影响 px 。并且出了作用域 Func 销毁malloc 的内存块还找不到了内存泄漏就算 free 也 free 不到 这里我们要改变的是 int* 不是 int 。传 int* 不起作用。应该传 int**二级指针
代码4改变 int* 使用 int* 的地址int**二级指针
void Func(int** pptr)
{*pptr (int*)malloc(sizeof(int));
}
int main()
{int* px NULL;Func(px);free(px);return 0;
}
这里把 px 的地址传过去pptr 指向 px 。malloc了一块空间是让 *pptr 即 px 指向这块空间 Func 结束栈帧销毁。但 px 还指向这块空间free 可以 free 到。这里内存释放值也拿回来了 二.链表
1.为什么学了顺序表还要学链表
顺序表是有很多缺陷的 1中间,头部 插入,删除数据需要挪动数据效率低下。你也不可能说在中间插入一块空间没有这种概念这本来就是一块连续的空间。 2空间不够需要扩容拷贝数据释放旧空间。会有不小的消耗 扩容有一定的效率消耗。原地扩还好异地扩呢 还可能会有一定的空间浪费。一次扩太少会频繁扩一次扩太多浪费
能不能说我用一点给一点呢存一块数据开一块空间 可以但怎么管理呢 顺序表里开了整片空间由于存放的数据是连续的只需要记录这块空间最开始的地址。 现在要一块空间去 malloc 。多次 malloc 他们之间的地址不能保证相邻。
这时候链表会用一个指针指向第一个内存块节点 Node。 为了通过第一个能找到第二个怎么办上一个会存下一个的地址上一个指向下一个。 什么时候结束顺序表是 size 。链表里最后一个节点的指针存 NULL 即可
2.优点
不需要扩容。存一块开一块。 可以从中间插入不需要挪动数据。
顺序表链表是互补相辅相成的。很多情况是配合起来使用的
三.实现
上面的理解链表是一个个的内存块再由指针链接起来 先来定义它的结构从语言的角度来说凡是有多个数据都要存到结构体里面 为方便替换成其他类型的数据我们将类型统一重命名为 SLTDataType
1.链表的打印 —— 理解链表结构
SList.h
上一个节点要存下一个节点的地址每个节点都是结构体类型所以存结构体指针 next 链表要有个头指针 phead 指向第一个节点判断结束只需要走到空 NULL 即可。 不能断言 phead 为空空链表也可以打印
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);
SList.c
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;//while (cur-next ! NULL) 错误写法//while(cur ! NULL)while (cur){printf(%d-, cur-data);cur cur-next; // 指向下一个位置// 不能写成 cur;}printf(NULL\n);
} 问为什么不能写成 cur 答链表地址不连续cur 不能保证它指向下一个位置。如果强行把地址弄成连续不就成顺序表了吗 怎么理解 cur cur-next cur 是结构体指针cur- 就是访问结构体成员。next 是结构体成员是下一个节点的地址 赋值操作是把下一个节点的地址给 cur 为什么循环判断条件 cur-next ! NULL 为错 cur-next 是下一节点地址。走到尾就结束了没有打印最后的数据 (2) 物理结构图
上面画的是逻辑结构图是为方便理解形象画出来的 物理结构图实实在在数据在内存中的变化 2.链表的尾插 —— 入门
依然不能断言 phead 为空。为空没有数据依然可以尾插
顺序表尾插先要判断空间够不够不够扩容。 链表不用永远有空间
第一步搞个节点并初始化。后面多次用到分装成函数 第二步找尾。 尾的特征tail-next NULL
// 搞节点并初始化
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}// 初始化newnode-data x;newnode-next NULL;return newnode;
}void SLTPushBack(SLTNode* phead, SLTDataType x) // 思考这里对吗
{SLTNode* newnode BuySLTNode(x);// 找尾SLTNode* tail phead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;
} 错误写法tail ! NULL
// 找尾
SLTNode* tail phead;
while (tail ! NULL)
{tail tail-next;
}
tail newnode;
从逻辑结构图角度看似正确 从物理结构图理解 tail newnode 都是局部变量出了作用域销毁 上一个节点没有存下一个节点的地址链接失败 总结
tail 是个局部变量。不应该赋值给 tail 。应该赋值给 tail 指向的结构体(存放下一个节点地址的)成员
不为空链表尾插的本质原尾节点中要存新的尾节点的地址 正确代码物理图解
// 找尾
SLTNode* tail phead;
while (tail-next ! NULL)
{tail tail-next;
}
tail-next newnode; tail newnode 都是局部变量出了作用域销毁 上一个节点存储下一个节点的地址链接成功
(2) 空链表尾插
phead NULL tail phead 让 phead 指向新节点即可 (2) 尾插整体代码 (思考对吗?)
SList.h
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x); // 思考这里对不对
SList.c
void SLTPushBack(SLTNode* phead, SLTDataType x) // 对吗
{SLTNode* newnode BuySLTNode(x);if (phead NULL){phead newnode;}else{// 找尾SLTNode* tail phead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
Test.c
void TestSList1()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);
}
Bug
我们运行上面的代码
看下图phead 和 newnode 都是结构体指针类型的指针变量 phead newnode 是赋值行为其真正含义是让 phead 也指向 newnode 指向的新节点
函数结束栈帧空间销毁。我们的目标是让 plist 指向新节点但最后没有造成了内存泄漏 改Bug
我们要改变 SLNode* plist 传参里要传 SLNode* plist 的地址 用 SLNode** 接收
SList.h
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印链表
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
SList.c
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);if (*pphead NULL){*pphead newnode;}else{// 找尾SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
pphead 存的是 plist 的指针。*pphead 就是 plist 。 函数结束栈帧空间销毁。plist 指向了新节点 链表运行结果
3.头插
盲猜头插要用二级指针因为一定有一个情况是为空为空肯定要用 void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}
如果传的是 phead 改变的就是 phead 无法改变外边的 plist
这段代码同样可以解决空的情况
4.尾删
SList.c
void SLTPopBack(SLTNode** pphead) // 这么写对吗
{assert(pphead);assert(*pphead);// 找尾SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}free(tail);tail NULL;
}
Test.c
void TestSList1()
{SLTNode* plist NULL;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);
} Bug 碰上这种情况多半是野指针调试看看 尾就是1这个节点2这个节点存着他的地址 直接把 tail 指向的尾节点 free 了前一个节点的 next 就是野指针了。指向已经被释放的空间的指针是野指针 这里把 tail 置空不会把前一个节点的 next 置空 前一个节点是结构体想改变结构体的内容要用结构体指针 修改1
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* prev NULL;// 找尾SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;
} 修改2找的是倒数第2个
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);// 找尾SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;
} 如果链表删到只剩1个元素还删。 如果链表本身为空
void TestSList1()
{SLTNode* plist NULL;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);
} 下面用红圈圈起来的是两组代码在只剩1个的情况下分别有误的地方 修改只有1个节点直接 freeplist 置空。不用找尾节点 所以尾删如果用一级指针接收phead 是 plist 的拷贝对 phead 置空的改变不影响 plist达不到置空 plist 的目的plist 会变成野指针
void SLTPopBack(SLTNode** pphead)
{//暴力检查assert(pphead);assert(*pphead);//温柔检查/*if (*pphead NULL)return;*/if ((*pphead)-next NULL) // 只有1个节点{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;*/// 找尾SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}
5.头删
不需要单独处理只有1个节点的情况
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first *pphead;*pphead first-next;free(first);first NULL;
}
6.查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
返回的是对应节点的指针可以用 Find 实现修改
void TestSList2()
{SLTNode* plist NULL;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);// 值为2的节点 *2SLTNode* ret SLTFind(plist, 2);ret-data * 2;SLTPrint(plist);
} Find 主要是与下面的功能相配合
7. Find 查找的功能
我们这里不传下标传结构体指针与 C 贴合
1pos 之前插入
为啥不是在 pos 位置插入 是把 pos 及以后的数据往后移所以逻辑上说是之前插入
单链表不适合 pos 之前插入只适合在后面插入因为要找到 pos 前一个节点的地址只能从头找 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{if (pos *pphead){SLTPushFront(pphead, x);}else{// 找到 pos 的前一个位置SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySLTNode(x);newnode-next pos;prev-next newnode;}
}
如果 pos 不是链表里的指针while 循环停不下来最终出现空指针 这种情况怎么办 (甚至 pos 就是 NULL) 说明传错了断言起码可以排除 NULL
2pos 位置删除
这里 *pphead 可以不断言pos 间接断言了 pos 不为空有节点一定不为空链表
pos 位删除要找到前一个位置。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;}
}
pos NULL 没用形参的修改不改变实参。要不要传二级指针呢不。 为保持和其他的一致性通常由用的人考虑置空
void TestSList4()
{SLTNode* plist NULL;SLTPushFront(plist, 1);SLTPushFront(plist, 2);SLTPushFront(plist, 3);SLTPushFront(plist, 4);SLTPrint(plist);SLTNode* ret SLTFind(plist, 2);SLTErase(plist, ret);ret NULL;SLTPrint(plist);
} 3pos 之后插入
错误写法会造成死循环
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);pos-next newnode;newnode-next pos-next;
} 正确写法先改后面
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);newnode-next pos-next;pos-next newnode;
}
4pos位置后面删除
法1pos-next pos-next-next; 这里从右往左赋值 橙圈的内容丢了所以要引入del void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
法2好理解
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
} 8.销毁
写法1一级指针
void SLTDestroy(SLTNode* phead); // SList.hvoid SLTDestroy(SLTNode* phead)
{SLTNode* cur phead;while (cur){SLTNode* tmp cur-next;free(cur);cur tmp;}// phead NULL;
}
phead NULL 没用形参的修改不改变实参。让用的人置空
void TestSList4()
{SLTNode* plist NULL;......SLTDestroy(plist);plist NULL;
}
写法2二级指针 自己置空
void SLTDestroy(SLTNode** pphead); // SList.hvoid SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* tmp cur-next;free(cur);cur tmp;}*pphead NULL;
}SLTDestroy(plist); // Test.c 四.思维提升
单链表给了 pos 没给头指针
1插入 2删除
没有前一个位置就删后一个。先换值后删。但是不能删尾 五.总结
1.传什么
我们刚开始拿到链表plist 是 NULL 。要插入新节点要让 plist 指向新节点会改变 plist 所以要传指针的地址。 删除时总会删到空这时要将 plist 置为 NULL 也改变 plist 所以也传指针的地址
如果不需要修改头指针的链接就传一级指针
2.要不要断言
断言可以排出明显的错误避免调试耗时。一定不能为空就断言
1打印、查找
问是否要 assert 指针 phead 为空 一级指针 答不要。空的 (没有数据) 的链表顺序表都可以打印、查找。链表为空时phead NULL断言直接终止程序不合适。
顺序表链表结构不一样不能一概而论。 phead 是指向第一个存有数据的节点链表为空时phead NULL 顺序表的打印 void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-a[i]);}printf(\n);
}
指针 ps 指向结构体 SL 顺序表的数据不是存储在结构体上。而是存储在结构体里的一个指针 a 指向的空间。即使顺序表里没有数据ps 指向的结构体也是必须要有的。ps-a 是否为空也不重要到底有没有数据取决于 ps-size 是否为 0 所以对顺序表而言指针就不能为空 总结不要看到指针上来就断言
2pphead
要pphead 不能为空。为什么 pphead 是 plist 的地址。plist 是指针变量值有可能是空地址一定不为空
3*pphead
*pphead 就是 plist 是看是否为空 二级指针
要不要断言 *pphead 取决于函数是否包容空链表的情况
先 assert ( pphead ) 后 assert ( *pphead ) 如果反了先 * 再检查有啥用
空链表能插入不断言不能删要断言。
六.整体代码
SList.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead); // 打印链表
void SLTPushBack(SLTNode** pphead, SLTDataType x); // 尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x); // 头插void SLTPopBack(SLTNode** pphead); // 尾删
void SLTPopFront(SLTNode** pphead); // 头删SLTNode* SLTFind(SLTNode* phead, SLTDataType x); // 查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); // pos之前插入
void SLTErase(SLTNode** pphead, SLTNode* pos); // pos位置删除void SLTInsertAfter(SLTNode* pos, SLTDataType x); // pos之后插入
void SLTEraseAfter(SLTNode* pos); // pos位置后面删除//void SLTDestroy(SLTNode* phead); // 链表销毁
void SLTDestroy(SLTNode** pphead); // 链表销毁
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include SList.hvoid SLTPrint(SLTNode* phead)
{SLTNode* cur phead;//while (cur-next ! NULL) 错误写法//while(cur ! NULL)while (cur){printf(%d-, cur-data);cur cur-next;//cur; 错误写法}printf(NULL\n);
}// 搞新节点并初始化
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);return NULL;}// 初始化newnode-data x;newnode-next NULL;return newnode;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);if (*pphead NULL){*pphead newnode;}else{// 找尾SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}void SLTPopBack(SLTNode** pphead)
{//暴力检查assert(pphead);assert(*pphead);//温柔检查/*if (*pphead NULL)return;*/if ((*pphead)-next NULL) // 只有1个节点{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;*/// 找尾SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* first *pphead;*pphead first-next;free(first);first NULL;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SLTPushFront(pphead, x);}else{// 找到 pos 的前一个位置SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySLTNode(x);newnode-next pos;prev-next newnode;}
}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;}
}void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);newnode-next pos-next;pos-next newnode;
}void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//SLTNode* del pos-next;//pos-next pos-next-next;//free(del);//del NULL;SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}/*
void SLTDestroy(SLTNode* phead)
{SLTNode* cur phead;while (cur){SLTNode* tmp cur-next;free(cur);cur tmp;}
}
*/void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* tmp cur-next;free(cur);cur tmp;}*pphead NULL;
} 本篇的分享就到这里了感谢观看如果对你有帮助别忘了点赞收藏关注。 小编会以自己学习过程中遇到的问题为素材持续为您推送文章
