| 商家名称 | 信用等级 | 购买信息 | 订购本书 |
 |
 |
算法精解:C语言描述(Kyle Loudon著) |  |
 |
|
算法精解:C语言描述(Kyle Loudon著) | |
版权页： 
插图： 
问与答
问：链表比数组优越的地方前面已经介绍过了。但是，数组同样也有比链表优越的地方，那么什么情况下适合使用数组呢？
答：当我们期望进行频繁的插入和删除操作时，链表比数组更有优势。然而，当我们期望进行随机访问的次数高于插入和删除操作的次数时，数组就显得更有优势了。随机访问是数组的强项，因为它们的元素在内存中是连续排列的。这种连续的排列方式使得数组中的任何元素能够在O(1)的时间内通过其索引访问。回顾一下访问链表中元素的方法，我们必须得有一个指向元素的指针。如果我们对访问元素的方式不甚了解，那么要获取某个指向特定元素的指针的代价将非常高。在实践中，对于许多应用来说，我们至少需要遍历链表的一部分。如果存储数据的总量是恒定的，则数组也有更大的优势，因为它们不需要增加额外的指针来使得它们所有的元素“链接”起来。
问：关于链表的插入、删除以及访问元素的操作和数组相比有何差异？
答：回顾一下本章中各种形式的链表，除了销毁链表操作外，其他的操作都具有O(1)的运行时复杂度。确实，这种表现似乎很难控制。然而，在分析过程中有一点并没有说明，那就是对于许多链表的操作来说，想得到指向链表中某个特定元素的指针其代价是很高的。例如，在最坏的情况下，可能需要遍历整个链表，此时的开销就是O(n)，这里n代表链表中的元素个数。另一方面，在一个设计得当的应用中，比如本章的页帧管理，则对此就不会有任何性能上的额外开销。因此，观察应用的特点是非常重要的。对于数组，插入和删除都是O(n)级别的操作，因为在最坏的情况下，插入或删除索引为0的元素需要将其他所有的元素都移动一个位置来调整整个数组的布局。如果我们知道索引值，则访问数组中的元素就是o(1)的操作。
问：假设我们想在本章给出的单链表基础上写一个名为list_ins_pos的函数，它的作用是在给定的位置之后插入一个新元素。假设我们希望在第9个元素之后插入新元素，但并不直接提供指向第9个元素的指针。那么这个函数的运行时复杂度是什么？
相关阅读：
更多图书资讯可访问读书人图书频道：http://www.reAder8.cn/book/
