拓冰网站定制 
一.链表基础单链表1. 物理结构与逻辑结构逻辑结构线性结构元素一个接一个排列。物理结构非连续、非顺序存储。各节点独立分布在内存堆中。比喻火车车厢。每节车厢独立通过挂钩指针连接可灵活增删车厢。2. 节点Node结构单链表每个节点包含两个域数据域存储实际数据如int data指针域存储下一个节点的地址称为“后继指针”或next// 数据类型重定义便于后续修改存储的数据类型typedef int SLTDataType;// 单链表节点结构体typedef struct SListNode {SLTDataType data; // 存储的数据struct SListNode* next; // 指向下一个节点的指针} SLTNode;next指针的类型必须是struct SListNode*。因为它指向的是下一个同类型的节点。这是链表定义的核心不可以使用SLTNode* next; -------编译报错C语言编译器是向上编译的不能在结构体内部使用结构体别名。此时 SLTNode 还未被定义定义加打印函数测试3. 头指针与空链表头指针一个指向第一个节点的指针如struct SListNode* plist。空链表头指针plist NULL表示链表不存在任何节点。按需申请释放节点无空间浪费。插入删除节点只需修改指针指向头部操作时间复杂度为O(1)。不支持随机访问查找元素需从头遍历。特性顺序表单链表初始化需要初始化容量(size)和大小(capacity)无需初始化空状态数组指针为NULL或size0头指针phead NULL即可原因底层是连续数组需要管理内存空间节点离散分布只需管理头指针4.二级指针传参深度解析核心原理形参的改变不影响实参若要修改实参的值必须传递实参的地址。1. 误区纠正错误认知看到形参是一级指针就认为是“传地址”。正确认知无论是指针变量还是普通变量都是内存中的变量都有属于自己的地址。传地址的标志必须使用取地址符数组名除外因为数组名本身代表首元素地址。若传plist一级指针传的是该指针变量存储的值即某个节点的地址若要修改plist本身使其指向新节点必须传plist一级指针的地址。2. 类比理解变量类型存储的值自身地址aint10x100paint*0x1000x800修改a的值需传a(0x100) 给int*接收。修改pa的值需传pa(0x800) 给int**接收。二.单链表的操作1尾插算法思路申请新节点。若链表为空phead NULL直接将新节点作为头节点。若链表非空遍历找到尾节点尾节点特征next NULL将尾节点的next指向新节点。易错点重点参数必须传二级指针因为可能需要修改头指针本身如空链表插入时。如果传一级指针SLTNode* phead函数内修改的是形参实参不会改变。若链表为空插入第一个节点时需要改变头指针plist的指向。结论凡是可能改变头指针指向的函数如头插、尾插、头删、尾删形参必须设计为**二级指针SLTNode**。找尾循环条件必须是ptail-next ! NULL而非ptail ! NULL。如果使用后者循环结束时ptail为NULL无法连接新节点。2头插算法思路创建新节点newNode。将newNode的next指向原头节点*pphead。将头指针*pphead指向newNode。3尾删算法思路断言检查链表不能为空*pphead ! NULL。特殊情况若只有一个节点(*pphead)-next NULL直接释放头节点并置空。一般情况定义两个指针ptail指向当前节点prev指向ptail的前一个节点。遍历链表找到尾节点ptail。将prev的next置为NULL。释放ptail。4头删算法思路断言检查链表不能为空。保存原头节点的下一个节点地址next。释放原头节点。将头指针*pphead指向保存的next节点5查找算法思路遍历链表比较当前节点数据与目标值x。找到则返回该节点指针否则返回NULL。6在指定位置前插入算法思路断言pphead和pos均不能为空。特殊情况若pos恰好是头节点即*pphead pos直接调用头插函数。一般情况定义prev指针遍历找到pos的前一个节点。创建新节点newnode。建立链接prev-next newnode; newnode-next pos;7在指定位置之后插入节点算法思路已知pos节点要插入数据为x的新节点newNode通过SLTBuyNode(x)创建新节点先让newNode-next指向pos-next即原后继节点后让pos-next指向newNode易错点:// 错误先改 pos-next会导致原后继节点丢失pos-next newNode;newNode-next pos-next; // 此时 pos-next 已经是 newNode相当于自指重点如果先执行pos-next newNode那么pos-next的指向已经发生改变了此时再通过pos-next去找原来的后继节点如节点4就找不到了导致链表断裂。newNode-next会指向newNode自身原后继节点无法访问。正确先连后面再连前面newNode-next pos-next; // 第一步newNode 指向原 pos 的后继pos-next newNode; // 第二步pos 指向 newNode(8)删除指定位置的节点算法思路已知pos节点要删除它如果pos是头节点 → 执行头删否则 → 从头遍历找pos的前驱prev先让prev-next指向pos-next跨过pos后free(pos)并将pos置为NULL易错点1删除头节点需要特殊处理如果pos恰好是头节点从头开始找前驱的代码会失效——prev永远找不到prev-next pos会导致死循环或对空指针解引用崩溃。必须单独判断pos *pphead走头删逻辑。易错点2必须先改指针再释放如果先free(pos)则pos变成野指针无法再通过pos-next获取后继节点地址链表断裂。所以必须先让前驱跨接再释放pos。9删除指定位置之后的节点算法思路已知pos节点要删除pos-next用del指针保存pos-next即待删节点让pos-next指向del-next跨过待删节点free(del)并将del置为NULL相较删除指定位置节点删除其后继无需找前驱效率更优——这是链表相比顺序表的重要优势。易错点pos-next必须非空删除pos之后的节点不仅要求pos不能为空pos-next也不能为空。如果pos是尾节点pos-next NULL没有后继可删必须断言assert(pos-next)拦截否则del为空free(NULL)虽不崩溃但逻辑错误。10销毁链表算法思路逐个释放所有节点最后将头指针置NULL定义pcur指向头节点next保存下一节点循环保存pcur-next→free(pcur)→pcur移到下一节点循环结束将*pphead置为NULL易错点1必须用二级指针销毁链表需要将头指针本身置为NULL所以要传头指针的地址二级指针SLTNode** pphead否则修改不会影响实参。易错点2释放前必须先保存后继如果先free(pcur)再访问pcur-nextpcur已是野指针无法找到下一个节点。所以必须在释放前用next保存pcur-next。关于free后是否置NULL的讨论函数内的局部变量如pcur、next跳出作用域自动销毁不置NULL不影响程序正确性但养成良好习惯free后将指针置NULL可避免后续误用时对野指针解引用对于传递给函数的外部指针如posfree后置NULL是必要习惯 数据结构精讲：单链表的操作
一.链表基础单链表1. 物理结构与逻辑结构逻辑结构线性结构元素一个接一个排列。物理结构非连续、非顺序存储。各节点独立分布在内存堆中。比喻火车车厢。每节车厢独立通过挂钩指针连接可灵活增删车厢。2. 节点Node结构单链表每个节点包含两个域数据域存储实际数据如int data指针域存储下一个节点的地址称为“后继指针”或next// 数据类型重定义便于后续修改存储的数据类型typedef int SLTDataType;// 单链表节点结构体typedef struct SListNode {SLTDataType data; // 存储的数据struct SListNode* next; // 指向下一个节点的指针} SLTNode;next指针的类型必须是struct SListNode*。因为它指向的是下一个同类型的节点。这是链表定义的核心不可以使用SLTNode* next; -------编译报错C语言编译器是向上编译的不能在结构体内部使用结构体别名。此时 SLTNode 还未被定义定义加打印函数测试3. 头指针与空链表头指针一个指向第一个节点的指针如struct SListNode* plist。空链表头指针plist NULL表示链表不存在任何节点。按需申请释放节点无空间浪费。插入删除节点只需修改指针指向头部操作时间复杂度为O(1)。不支持随机访问查找元素需从头遍历。特性顺序表单链表初始化需要初始化容量(size)和大小(capacity)无需初始化空状态数组指针为NULL或size0头指针phead NULL即可原因底层是连续数组需要管理内存空间节点离散分布只需管理头指针4.二级指针传参深度解析核心原理形参的改变不影响实参若要修改实参的值必须传递实参的地址。1. 误区纠正错误认知看到形参是一级指针就认为是“传地址”。正确认知无论是指针变量还是普通变量都是内存中的变量都有属于自己的地址。传地址的标志必须使用取地址符数组名除外因为数组名本身代表首元素地址。若传plist一级指针传的是该指针变量存储的值即某个节点的地址若要修改plist本身使其指向新节点必须传plist一级指针的地址。2. 类比理解变量类型存储的值自身地址aint10x100paint*0x1000x800修改a的值需传a(0x100) 给int*接收。修改pa的值需传pa(0x800) 给int**接收。二.单链表的操作1尾插算法思路申请新节点。若链表为空phead NULL直接将新节点作为头节点。若链表非空遍历找到尾节点尾节点特征next NULL将尾节点的next指向新节点。易错点重点参数必须传二级指针因为可能需要修改头指针本身如空链表插入时。如果传一级指针SLTNode* phead函数内修改的是形参实参不会改变。若链表为空插入第一个节点时需要改变头指针plist的指向。结论凡是可能改变头指针指向的函数如头插、尾插、头删、尾删形参必须设计为**二级指针SLTNode**。找尾循环条件必须是ptail-next ! NULL而非ptail ! NULL。如果使用后者循环结束时ptail为NULL无法连接新节点。2头插算法思路创建新节点newNode。将newNode的next指向原头节点*pphead。将头指针*pphead指向newNode。3尾删算法思路断言检查链表不能为空*pphead ! NULL。特殊情况若只有一个节点(*pphead)-next NULL直接释放头节点并置空。一般情况定义两个指针ptail指向当前节点prev指向ptail的前一个节点。遍历链表找到尾节点ptail。将prev的next置为NULL。释放ptail。4头删算法思路断言检查链表不能为空。保存原头节点的下一个节点地址next。释放原头节点。将头指针*pphead指向保存的next节点5查找算法思路遍历链表比较当前节点数据与目标值x。找到则返回该节点指针否则返回NULL。6在指定位置前插入算法思路断言pphead和pos均不能为空。特殊情况若pos恰好是头节点即*pphead pos直接调用头插函数。一般情况定义prev指针遍历找到pos的前一个节点。创建新节点newnode。建立链接prev-next newnode; newnode-next pos;7在指定位置之后插入节点算法思路已知pos节点要插入数据为x的新节点newNode通过SLTBuyNode(x)创建新节点先让newNode-next指向pos-next即原后继节点后让pos-next指向newNode易错点:// 错误先改 pos-next会导致原后继节点丢失pos-next newNode;newNode-next pos-next; // 此时 pos-next 已经是 newNode相当于自指重点如果先执行pos-next newNode那么pos-next的指向已经发生改变了此时再通过pos-next去找原来的后继节点如节点4就找不到了导致链表断裂。newNode-next会指向newNode自身原后继节点无法访问。正确先连后面再连前面newNode-next pos-next; // 第一步newNode 指向原 pos 的后继pos-next newNode; // 第二步pos 指向 newNode(8)删除指定位置的节点算法思路已知pos节点要删除它如果pos是头节点 → 执行头删否则 → 从头遍历找pos的前驱prev先让prev-next指向pos-next跨过pos后free(pos)并将pos置为NULL易错点1删除头节点需要特殊处理如果pos恰好是头节点从头开始找前驱的代码会失效——prev永远找不到prev-next pos会导致死循环或对空指针解引用崩溃。必须单独判断pos *pphead走头删逻辑。易错点2必须先改指针再释放如果先free(pos)则pos变成野指针无法再通过pos-next获取后继节点地址链表断裂。所以必须先让前驱跨接再释放pos。9删除指定位置之后的节点算法思路已知pos节点要删除pos-next用del指针保存pos-next即待删节点让pos-next指向del-next跨过待删节点free(del)并将del置为NULL相较删除指定位置节点删除其后继无需找前驱效率更优——这是链表相比顺序表的重要优势。易错点pos-next必须非空删除pos之后的节点不仅要求pos不能为空pos-next也不能为空。如果pos是尾节点pos-next NULL没有后继可删必须断言assert(pos-next)拦截否则del为空free(NULL)虽不崩溃但逻辑错误。10销毁链表算法思路逐个释放所有节点最后将头指针置NULL定义pcur指向头节点next保存下一节点循环保存pcur-next→free(pcur)→pcur移到下一节点循环结束将*pphead置为NULL易错点1必须用二级指针销毁链表需要将头指针本身置为NULL所以要传头指针的地址二级指针SLTNode** pphead否则修改不会影响实参。易错点2释放前必须先保存后继如果先free(pcur)再访问pcur-nextpcur已是野指针无法找到下一个节点。所以必须在释放前用next保存pcur-next。关于free后是否置NULL的讨论函数内的局部变量如pcur、next跳出作用域自动销毁不置NULL不影响程序正确性但养成良好习惯free后将指针置NULL可避免后续误用时对野指针解引用对于传递给函数的外部指针如posfree后置NULL是必要习惯