数据结构--------单链表下

书接上回本章主要讲的是单链表的头删尾删指定位置插入删除链表的查找和链表的销毁一.链表的操作1.头删文字描述如下正所谓头删删除的肯定是链表的头元素但是我们要怎么样进行操作呢首先在删除之前我们肯定要断言一下传过来的链表的地址是不为空的以及链表也是不能为空的代码语言assertIpphead*pphead然后我们要头删删除的是头结点的元素我们在删除之前肯定是要定义一个next指针其数据类型应该是SLTNode*,next指针指向的头结点的下一个结点代码语言SLTNode* next (*pphead)-next;(注意这里的括号是不能省略的因为-操作符的优先级高于*)保存好之后我们就可以free(*pphead)这个头结点了再将next指针指向的结点成为新的头结点代码语言*ppheadnext画个图再熟悉一下这个代码这里存储数据数据1的结点为刚开始的头结点存储数据2的结点为头结点的next结点按照文字描述走一遍存储数据2的结点变为新的头结点存储数据3的结点变为next结点代码上述是分析多个结点接下来我们分析只存在一个结点的时候。同样我们画图分析上述的描述同样适用说到这里我们的头删就讲完了2.尾删文字描述同样的尾删删除的则是链表尾结点的数据同样的分成链表当中存在多个结点或者只有一个结点。同样的在进行操作之前我们还是要断言传过来的链表的地址是不为空的以及链表也是不能为空的代码语言assertIpphead*pphead接下来我们要找尾结点定义一个ptail指针起初它指向头结点以及一个prev指针指向空SLTNode* prevNULLSLTNode* ptail *pphead遍历这个ptail指针让他找尾当ptail找到尾的时候prev也找到ptail之前的结点先将prev的next指针置为空再将ptail指针free掉画图理解一下吧按照上述的文字描述即可实现尾删的操作了代码如下当链表中只有一个结点的时候我们就不能按照多个结点的方式来尾删了画图理解当只有一个结点的时候(*ppheadNULL)我们直接手动free(*pphead)之后再手动将*pphead置为空(*ppheadNULL)3.查找指定位置的结点文字描述首先我们创建一个pcur指针指向头结点SLTNode*pcur*pphead接下来遍历整个链表即whilepcur也就是pcurNULL指针的时候进入循环条件判断pcur-datax等于则说明我们找到了要查找的指定位置返回指定位置即可也就是pcur。若找不到我们返回NULL。画图理解代码4.指定pos位置之前插入数据文字描述指定位置之前插入数据同样的我们在开始操作的时候首先要断言传过去的pphead不能为空以及pos指针不能为空即assertppheadpospphead!NULL pos!NULL。首先我们判断pos所在的位置如果pos在第一个结点的位置那么就是头插我们直接调用头插的函数代码如果pos不在第一个结点的位置找pos前一个结点创建一个prev指针让其找到pos结点我们根据数据x申请一个结点大小的空间称为newnode。当找到prev和pos结点的时候让prev的next指针指向newnode再让newnode的next指针指向pos。先定义一个遍历指针从头结点开始往后走找到指定位置的前驱结点。动态开辟新结点给新结点的数据域赋值。让新结点的 next 指针指向原来指定位置的结点。让前驱结点的 next 指针指向这个新结点。插入完成链表链接关系重构完毕画图理解代码5.指定pos位置之后插入数据文字描述指定pos位置之后插入数据同样的我们在开始操作的时候首先要断言传过去的pphead不能为空以及pos指针不能为空即assertppheadpospphead!NULL pos!NULL。我们创建一个newnoed结点存储x数据然后找到pos以及pos-next结点。这里的插入顺序是有先后之分的我们先将newnode-next指向pos-next指针指向的位置其次将pos-next指向newnode看直观的图像吧代码6.删除指定pos位置的数据文字描述同样的我们在开始操作的时候首先要断言传过去的pphead不能为空以及pos指针不能为空即assertppheadpospphead!NULL pos!NULL。分为三种情况当pos在头结点和尾结点之间的时候与pos在尾结点的时候创建pcur变量遍历链表当pcur-nextpos跳出循环找到pcurpos-next以及pos结点。先让prev-next指针指向pos-next指针然后free(pos)结点再将其置为空。当pos为头结点的时候之间使用上面编译好的头删的函数。先判断链表是否为空若为空直接结束操作。定义遍历指针从头节点开始遍历找到pos 位置的前驱节点。用临时指针保存要删除的 pos 位置节点。让前驱节点的 next 指针指向被删节点的下一个节点。释放被删除节点的内存防止内存泄漏。删除完成链表节点链接重新连通。图像理解代码7.删除pos之后的数据文字描述首先还是断言判空同样的我们在开始操作的时候首先要断言传过去的pphead不能为空以及pos指针不能为空即assertppheadpospphead!NULL pos!NULL。我们可以思考一下当删除pos之后的结点的时候受到影响的结点应该有三个一个是pos结点pos-next结点pos-next-next结点这三个结点。所以我们先创建一个del指针指向pos-next那么del-next指针也就是pos-next-next。我们直接freedel之前先将pos-next指针指向del-next然后再free(del)再将del置为NULL代码8.链表的销毁这个销毁函数的核心逻辑就是用 pcur 遍历每个结点用 next 存好下一个结点的地址释放当前结点后再移动游标最后把外面的头指针置空全程保证不会丢失结点地址也不会访问非法内存。代码二.总结单链表 六大基础操作 文字步骤描述一、头删判断链表是否为空为空则直接结束。用临时指针记录当前头结点。头指针指向原头结点的下一个结点。释放临时指针指向的原头结点内存。二、尾删判断链表是否为空为空直接结束。定义指针从头遍历找到最后一个结点的前驱结点。临时指针记录尾结点。把前驱结点的 next 置为空。释放原尾结点内存。三、指定位置插入判断位置是否合法不合法直接结束。遍历找到指定位置的前驱结点。新建结点并赋值数据。新结点 next 指向原指定位置结点。前驱结点 next 指向新结点完成插入。四、指定位置删除判断链表为空或位置不合法直接结束。遍历找到指定位置的前驱结点。临时指针保存要删除的目标结点。前驱结点 next 指向目标结点的下一个结点。释放目标结点内存。五、链表查找从头结点开始逐个遍历链表结点。依次比对每个结点的数据域与目标值。找到匹配结点则返回该结点地址 / 位置。遍历完无匹配返回查找失败。六、链表销毁定义临时指针从头结点开始循环。每次先用临时指针保存当前头结点。头指针后移到下一个结点。释放临时指针指向的结点。循环直到链表为空所有结点全部释放。以上就是单链表操作的全部内容了希望对大家能有所帮助。