怎样才算是掌握单链表呢?

单链表的一些基本操作与思路
服务器君一共花费了354.718 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

很多人学习单链表的时候,觉得学得不够深刻,不知道该深入到哪个程度。这里就罗列一下,学了单链表之后至少需要会写的一些对单链表的一些操作。只是简单罗列下,如果你有建议可以补充。

  • 初始化
  • 销毁
  • 在尾部增加数据
  • 在指定位置前插入数据
  • 删除指定位置的数据
  • 遍历链表
  • 取链表长度
  • 链表是否为空
  • 清空链表
  • 搜索链表是否包含某个数据
  • 取链表只定位置的数据

具体实现方法可以参看本栏目的其它文章,这里只大概介绍下思路。

首先要声明一个结构体,包含两部分:一是数据域,就是存放数据的。另一个是指针域,指向下一个节点的指针。

初始化:就是申请空间初始化一个头节点,如果申请空间失败则报错返回。头指针的数据域不存储任何数据(有的在这里存放链表长度),指针域指向NULL,因为就是个初始化,链表没有任何数据,所以指向NULL。

销毁:释放所有的内存,这里可能跟链表清空有些重复,不过这个销毁是彻底的销毁,包括头指针的,就是说不用这个链表了。

在尾部增加数据:函数声明一个指针指向头节点的指针域,依次判断,知道指针域为NULL的时候,申请一个空间,将NULL修改为申请的位置,数据域存入数据,并将新申请的空间的指针域设为NULL表示结束。

在指定位置前插入数据:这个跟上面有些重复,不过上面的是简化版的操作,不用弄太多。这依然是一个指针指向头节点的数据域,也就是首节点的位置,依次判断知道要插入的位置之前,比如说要在第三个节点前插数据,就遍历到第二个节点,因为第二个节点的指针域指向第三个节点,申请空间后,数据域插入位置,然后将这个节点的指针域修改为第二个节点所指向的指针,然后将第二个节点的指针指向新申请的空间,这样就完成插入了。(在插入的时候设置一个判断,判断插入的位置是否超出链表长度,如果超过了,直接返回失败,就不用遍历了,长度判断可以用下面的取链表长度)。

删除指定位置的数据:跟上面的差不多,遍历至要删除的数据的前一个位置,讲这个位置的指针修改为下一个节点的指针域的内容,将指针所指向的内存释放(在删除的时候设置一个判断,判断插入的位置是否超出链表长度,如果超过了,直接返回失败,就不用遍历了,长度判断可以用下面的取链表长度)。

遍历链表:这个就简单了,直接指向头指针的指针域,依次遍历打印输出,直到NULL的时候结束循环。

取链表长度:跟遍历的方法一样,无非就是不用打印,设置一个计数器即可。

链表是否为空:直接看头指针的指针域是否非NULL即可,如果不是NULL,就非空。

清空链表:同遍历方法一下,依次遍历找到一个free释放一个节点,直到最后,然后将头指针的指针域置为NULL。

搜索链表是否包含某个数据:遍历链表,将符合数据的第一个位置返回。

取链表只定位置的数据:遍历链表到相应位置,将数值返回即可。

上面的是对单链表的基本操作,如果你都懂了,可以自己手写一遍程序,那么对单链表应该可以说初步掌握了。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1816,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1816

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《算法导论(原书第2版)》 科曼(Cormen T.H.) (作者), 等 (作者, 译者), 潘金贵 (译者)

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

更多计算机宝库...