算法精解:C语言描述(Kyle Loudon著)

编辑推荐

《算法精解:C语言描述》编辑推荐：数据结构和算法领域最具特色著作之一，公认权威经典，畅销不衰！

作者简介

作者：（美国）Kyle Loudon 译者：肖翔陈舸

Kyle Loudon是美国加州洛斯加托斯Jeppesen Dataplan公司的一名软件工程师，主管图形接口开发小组，主攻航迹规划软件的研发，这些软件主要用于商业航空公司、私营航空部门和其他一些航空制造业。在来到Jeppesen之前，Kyle在IBM公司是一名系统程序员。在技术上，Kyle主要对操作系统、网络、人机交互等领域感兴趣。1992年，Kyle在普渡大学拿到了计算机科学学士学位，并取得了法语的第二学位，同时他还被选入斐陶斐荣誉学会（美国大学优等生之荣誉学会）。他在普渡大学计算机系教了三年的计算机课程。在这期间，他完成了他个人的第一本书《Understanding Computers》，这本书用理论结合实践的方式介绍计算机的方方面面。如今，尽管他继续工作在硅谷的软件业，但他仍然坚韧不拔地在追求一个更高的学位。
除了计算机，Kyle多年来喜欢打网球、教网球。他还喜欢山地骑行、滑冰，偶尔也和朋友们一起参加高尔夫课程。另外，Kyle还喜欢各种形式的戏剧、美食，以及某些风格的音乐和艺术；他期望成为钢琴家和艺术家，但希望渺茫。他现在在Jeppesen的工作是从他1992年开始驾驶飞机之后找到的。现在，他是一个拥有美国联邦航空局颁发的商业飞行员执照的飞行员。

第1部分预备知识
第1章概述
数据结构简介
算法简介
小酌软件工程
如何使用本书
第2章指针操作
指针基础
存储空间分配
数据集合与指针的算术运算
作为函数参数的指针
泛型指针与类型转换
函数指针
问与答
相关主题
第3章递归
基本递归
尾递归
问与答
相关主题
第4章算法分析
最坏情况分析
O表示法
计算的复杂度
实例分析：插入排序
问与答
相关主题
第2部分数据结构
第5章链表
单链表介绍
单链表接口的定义
单链表的实现与分析
使用链表的例子：页帧管理
双向链表介绍
双向链表接口的定义
双向链表的实现与分析
循环链表介绍
循环链表接口的定义
循环链表的实现与分析
使用循环链表的例子：第二次机会页面置换法
问与答
相关主题
第6章栈和队列
栈的描述
栈的接口定义
栈的实现与分析
队列的描述
队列的接口定义
队列的实现与分析
队列示例：事件处理
问与答
相关主题
第7章集合
集合介绍
集合的性质
集合接口的定义
集合抽象数据类型的实现和分析
Set示例：集合覆盖
问与答
相关主题
第8章哈希表
链式哈希表的描述
链式哈希表的接口定义
链式哈希表的实现与分析
链式哈希表的例子：符号表
开地址哈希表的描述
开地址哈希函数的接口定义
开地址哈希表的实现与分析
问与答
相关主题
第9章树
二叉树介绍
二叉树的接口定义
二叉树的实现与分析
二叉树示例：表达式处理
二叉搜索树介绍
二叉搜索树的接口定义
二叉搜索树的实现与分析
问与答
相关主题
第10章堆和优先队列
堆的描述
堆的接口定义
堆的实现与分析
优先队列的描述
优先队列的接口定义
优先队列的实现与分析
优先队列的示例：包裹分拣
问与答
相关主题
第11章图
图的描述
图的接口定义
图的实现与分析
关于图的应用举例：计算网络跳数
关于图的应用举例：拓扑排序
问与答
相关主题
第3部分算法
第12章排序和搜索
插入排序的描述
插入排序的接口定义
插入排序的实现与分析
快速排序的描述
快速排序的接口定义
快速排序的实现与分析
快速排序的例子：目录列表
归并排序的描述
归并排序的接口定义
归并排序的实现与分析
计数排序的描述
计数排序的接口定义
计数排序的实现与分析
基数排序的描述
基数排序的接口定义
基数排序的实现与分析
二分查找的描述
二分查找的接口定义
二分查找的实现与分析
二分查找的例子：拼写检查器
问与答
相关主题
第13章数值计算
多项式插值法
多项式插值的接口定义
多项式插值的实现与分析
最小二乘估计法
最小二乘估计的接口定义
最小二乘估计的实现和分析
方程求解介绍
方程求解的接口定义
方程求解的实现与分析
问与答
相关主题
第14章数据压缩
位操作的描述
位操作的接口定义
位操作的实现与分析
霍夫曼编码的描述
霍夫曼编码的接口定义
霍夫曼编码的分析与实现
霍夫曼编码的例子：网络优化
LZ77的描述
LZ77的接口定义
LZ77的实现与分析
问与答
相关主题
第15章数据加密
DES算法介绍
DES的接口定义
DES算法的实现和分析
DES应用举例：分组加密模式
RSA算法介绍
RSA的接口定义
RSA算法的实现与分析
问与答
相关主题
第16章图算法
最小生成树的描述
最小生成树的接口定义
最小生成树的实现与分析
最短路径的描述
最短路径的接口定义
最短路径的实现与分析
最短路径的例子：路由表
旅行商问题的描述
旅行商问题的接口定义
旅行商问题的实现与分析
问与答
相关主题
第17章几何算法
测试线段是否相交
测试线段是否相交的标准方法
检测线段是否相交的接口定义
检测线段是否相交的实现与分析
凸包简介
Jarvis'sMarch
凸包的接口定义
凸包的实现与分析
球面弧长
求解球面弧长的接口定义
求解球面弧长的实现和分析
球面弧长的应用举例：地球上两点之间的近似距离
问与答
相关主题

文摘

版权页：

插图：

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