《算法基础》——3.10　练习

本节书摘来自华章计算机《算法基础》一书中的第3章，第3.10节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.10　练习

3.2.5节“在尾部添加单元格”中给出了在单向链表尾部添加单元格的一个时间复杂度为O(N)的算法。如果使用另一个变量bottom来指向链表最后一个单元格，则可以用O(1)时间向链表尾添加项。写出这样的算法。添加变量后会使在首尾添加项、寻找项、删除项变得怎样复杂？写一个从这样链表中移除项的算法。2.写出一个在整数组成的、未排序的单向链表中找出最大项的算法。

3.写出一个在双向链表首部添加一个项的算法。4写出一个在双向链表尾部添加一个项的算法。5.如果把练习3、4的算法与“双向链表”一节中提供的InsertCell算法相比，应该发现它们非常相似。重写练习3、4的算法，让它们调用InsertCell算法而不是直接更新链表的链接。6.写一个移除双向链表中特定单元格的算法。画一张图来表示这一过程。7.假设有一个排好序的存储名字双向链表，利用尾部而不是首部的哨兵，可以想出一个提高检索表现的方法吗？这个方法改变了时间复杂度吗？8.写出一个向已排序双向链表中添加项的算法。假设首尾哨兵分别掌握着数值的下限和上限。9.写出一个算法判断一个给定链表是否已排序。10.插入排序和选择排序都拥有O(N2)的时间复杂性。解释为什么选择排序实际花费时间更长。11.参照3.7节的描述，写一个程序建立一个行星的多线索链表。用户可以单击单选框或组合框来显示按照不同依据排列的行星。（提示：建立一个Planet类包含以下字段。Name、DistanceToSun、Mass、Diameter、NextDistance、NextMass以及NextDiameter。然后创建一个AddPlanet-ToList方法用来按线索添加排好序的项。）12.写出一个程序实现龟兔算法。