数据结构与算法分析——C语言描述（原书第2版）典藏版
本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的程序。
基本信息
内容简介
作译者
[美]马克·艾伦·维斯（Mark Allen Weiss）著：【加照片】
马克·艾伦·维斯（Mark Allen Weiss）佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Robert Sedgewick。 他曾经担任全美AP（Advanced Placement）考试计算机学科委员会的主席（2000-2004）。他的主要研究兴趣是数据结构、算法和教育学。他编写的关于数据结构与算法方面的知名教材还有《Data Structures and Algorithm Analysis : in Java》《Data Structures and Algorithm Analysis : in C++》《Data Structures and Problem Solving : Using Java》《Data Structures and Problem Solving : Using C++》。
马克·艾伦·维斯（Mark Allen Weiss）佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Robert Sedgewick。 他曾经担任全美AP（Advanced Placement）考试计算机学科委员会的主席（2000-2004）。他的主要研究兴趣是数据结构、算法和教育学。他编写的关于数据结构与算法方面的知名教材还有《Data Structures and Algorithm Analysis : in Java》《Data Structures and Algorithm Analysis : in C++》《Data Structures and Problem Solving : Using Java》《Data Structures and Problem Solving : Using C++》。
目录
出版者的话
译者序
前言
第1章 引论┊1
1.1 本书讨论的内容┊2
1.2 数学知识复习┊3
1.2.1 指数┊3
1.2.2 对数┊3
1.2.3 级数┊4
1.2.4 模运算┊5
1.2.5 证明方法┊5
1.3 递归简论┊7
总结┊10
练习┊10
参考文献┊11
第2章 算法分析┊13
2.1 数学基础┊14
2.2 模型┊16
2.3 要分析的问题┊16
2.4 运行时间计算┊18
译者序
前言
第1章 引论┊1
1.1 本书讨论的内容┊2
1.2 数学知识复习┊3
1.2.1 指数┊3
1.2.2 对数┊3
1.2.3 级数┊4
1.2.4 模运算┊5
1.2.5 证明方法┊5
1.3 递归简论┊7
总结┊10
练习┊10
参考文献┊11
第2章 算法分析┊13
2.1 数学基础┊14
2.2 模型┊16
2.3 要分析的问题┊16
2.4 运行时间计算┊18
前言
目的
本书讨论数据结构和算法分析。数据结构主要研究组织大量数据的方法，而算法分析则是对算法运行时间的评估。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益急切。可是，由于在输入量很大的时候程序的低效率现象变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程前对算法进行分析，学生可以决定一个特定的解法是否可行。例如，学生在本书中将读到一些特定的问题并看到精心的实现方法是如何把处理大量数据的时间限制从16年减至不到1秒的。因此，若无运行时间的阐释，就不会有算法和数据结构的提出。在某些情况下，对于影响算法实现的运行时间的一些微小细节都需要认真探究。
一旦确定解法，还必须编写程序。随着计算机的日益强大，它们必须解决的问题也变得更加巨大和复杂，这就要求开发更加复杂的程序。本书的目的是教授学生良好的程序设计技巧和提高学生的算法分析能力，使得他们能够开发出具有最高效率的程序。
本书适合作为高级数据结构（CS7）课程或研究生第一年算法分析课程的教材。学生应该具有中等程度的程序设计知识，包括像指针和递归这样一些内容，还应该具有离散数学的某些知识。
方法
我相信，对于学生来说，重要的是学习如何自己动手编写程序，而不是从书上拷贝程序。但另一方面，讨论现实程序设计问题而不套用样本程序实际上是不可能的。由于这个原因，本书通常提供实现方法的大约一半到四分之三的内容并鼓励学生补足其余的部分。第12章是这一版新加的，讨论主要侧重于实现细节的一些附加的数据结构。
本书中的算法均以ANSI C表示，尽管有些欠缺，但它仍然是最流行的系统程序设计语言。使用C代替Pascal，使得动态分配数组成为可能（见第5章中的“再散列”）。它还在几处地方将代码简化，这通常是与（&&）操作走捷径的缘故。
对C的大多数批评集中在用它写出的程序代码可读性差的事实上。仅仅少击几次键，却牺牲了程序的清晰性，而程序的速度又没有增加。因此，诸如同时赋值以及通过
if(x=y)
测试是否为0等技巧一般不在本书中使用。本书将证明只要细心练习是可以避免那些难以读懂的代码的。
内容提要
第1章包含离散数学和递归的一些复习材料。我相信对递归做到泰然处之的唯一办法是反复不断地看一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。
第2章处理算法分析。该章阐述渐近分析和它的主要弱点。这里提供了许多例子，包括对对数运行时间的深入解释。通过直观地把一些简单递归程序转变成迭代程序而对它们进行分析。介绍了更为复杂的分治程序，不过有些分析（求解递归关系）要推迟到第7章再详细讨论。
第3章包括表、栈和队列。重点聚焦于使用ADT对这些数据结构编程，这些数据结构的快速实现，以及介绍它们的某些用途。文中几乎没有什么程序(只有些例程)，而程序设计作业的许多思想基本上体现在练习之中。
第4章讨论树，重点在于查找树，包括外部查找树（B树）。UNIX文件系统和表达式树是作为例子来介绍的。AVL树和伸展树只进行了介绍而没有分析。程序写出75%，其余部分留给学生完成。查找树的实现细节见第12章。树的另外一些内容，如文件压缩和博弈树，延迟到第10章讨论。外部媒体上的数据结构在这几章的最后讨论。
第5章是相对较短的一章，主要讨论散列表。这里进行了某些分析，该章末尾讨论了可扩散列。
第6章讨论优先队列。二叉堆也在该章讲授，还有些附加的材料论述优先队列某些理论上有趣的实现方法。斐波那契堆在第11章讨论，配对堆在第12章讨论。
第7章讨论排序。它特别关注编程细节和分析，讨论并比较所有通用的排序算法。对以下四种算法进行了详细的分析：插入排序、希尔排序、堆排序以及快速排序。堆排序平均情形运行时间的分析对于这一版来说是新的内容。该章末尾讨论了外部排序。
第8章讨论不相交集算法并证明其运行时间。该章短而专，如果不讨论Kruskal算法则可跳过。
第9章讲授图论算法。图论算法很重要，不仅因为在实践中经常用到它们，而且还因为它们的运行时间强烈地依赖于数据结构的恰当使用。实际上，所有标准算法都是和相应的数据结构、伪代码以及运行时间的分析一起介绍的。为把这些问题放进一本适当的教材中，我们对复杂性理论（包括NP-完全性和不可判定性）进行了简短的讨论。
本书讨论数据结构和算法分析。数据结构主要研究组织大量数据的方法，而算法分析则是对算法运行时间的评估。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益急切。可是，由于在输入量很大的时候程序的低效率现象变得非常明显，因此这又要求对效率问题给予更仔细的关注。通过在实际编程前对算法进行分析，学生可以决定一个特定的解法是否可行。例如，学生在本书中将读到一些特定的问题并看到精心的实现方法是如何把处理大量数据的时间限制从16年减至不到1秒的。因此，若无运行时间的阐释，就不会有算法和数据结构的提出。在某些情况下，对于影响算法实现的运行时间的一些微小细节都需要认真探究。
一旦确定解法，还必须编写程序。随着计算机的日益强大，它们必须解决的问题也变得更加巨大和复杂，这就要求开发更加复杂的程序。本书的目的是教授学生良好的程序设计技巧和提高学生的算法分析能力，使得他们能够开发出具有最高效率的程序。
本书适合作为高级数据结构（CS7）课程或研究生第一年算法分析课程的教材。学生应该具有中等程度的程序设计知识，包括像指针和递归这样一些内容，还应该具有离散数学的某些知识。
方法
我相信，对于学生来说，重要的是学习如何自己动手编写程序，而不是从书上拷贝程序。但另一方面，讨论现实程序设计问题而不套用样本程序实际上是不可能的。由于这个原因，本书通常提供实现方法的大约一半到四分之三的内容并鼓励学生补足其余的部分。第12章是这一版新加的，讨论主要侧重于实现细节的一些附加的数据结构。
本书中的算法均以ANSI C表示，尽管有些欠缺，但它仍然是最流行的系统程序设计语言。使用C代替Pascal，使得动态分配数组成为可能（见第5章中的“再散列”）。它还在几处地方将代码简化，这通常是与（&&）操作走捷径的缘故。
对C的大多数批评集中在用它写出的程序代码可读性差的事实上。仅仅少击几次键，却牺牲了程序的清晰性，而程序的速度又没有增加。因此，诸如同时赋值以及通过
if(x=y)
测试是否为0等技巧一般不在本书中使用。本书将证明只要细心练习是可以避免那些难以读懂的代码的。
内容提要
第1章包含离散数学和递归的一些复习材料。我相信对递归做到泰然处之的唯一办法是反复不断地看一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。
第2章处理算法分析。该章阐述渐近分析和它的主要弱点。这里提供了许多例子，包括对对数运行时间的深入解释。通过直观地把一些简单递归程序转变成迭代程序而对它们进行分析。介绍了更为复杂的分治程序，不过有些分析（求解递归关系）要推迟到第7章再详细讨论。
第3章包括表、栈和队列。重点聚焦于使用ADT对这些数据结构编程，这些数据结构的快速实现，以及介绍它们的某些用途。文中几乎没有什么程序(只有些例程)，而程序设计作业的许多思想基本上体现在练习之中。
第4章讨论树，重点在于查找树，包括外部查找树（B树）。UNIX文件系统和表达式树是作为例子来介绍的。AVL树和伸展树只进行了介绍而没有分析。程序写出75%，其余部分留给学生完成。查找树的实现细节见第12章。树的另外一些内容，如文件压缩和博弈树，延迟到第10章讨论。外部媒体上的数据结构在这几章的最后讨论。
第5章是相对较短的一章，主要讨论散列表。这里进行了某些分析，该章末尾讨论了可扩散列。
第6章讨论优先队列。二叉堆也在该章讲授，还有些附加的材料论述优先队列某些理论上有趣的实现方法。斐波那契堆在第11章讨论，配对堆在第12章讨论。
第7章讨论排序。它特别关注编程细节和分析，讨论并比较所有通用的排序算法。对以下四种算法进行了详细的分析：插入排序、希尔排序、堆排序以及快速排序。堆排序平均情形运行时间的分析对于这一版来说是新的内容。该章末尾讨论了外部排序。
第8章讨论不相交集算法并证明其运行时间。该章短而专，如果不讨论Kruskal算法则可跳过。
第9章讲授图论算法。图论算法很重要，不仅因为在实践中经常用到它们，而且还因为它们的运行时间强烈地依赖于数据结构的恰当使用。实际上，所有标准算法都是和相应的数据结构、伪代码以及运行时间的分析一起介绍的。为把这些问题放进一本适当的教材中，我们对复杂性理论（包括NP-完全性和不可判定性）进行了简短的讨论。
媒体评论
本书是国外数据结构与算法分析方面的经典教材，原书曾被评为20世纪顶尖的30部计算机著作之一。作者Mark Allen Weiss在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学用作教材。
在本书中，作者更加精练并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
本书特点：
专用一章来讨论算法设计的技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。
介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。
安排一章专门讨论摊还分析，考察书中介绍的一些高级数据结构。
新开辟一章讨论高级数据结构以及它们的实现，包括红黑树、自顶向下伸展树、treap树、k维树、配对堆以及其他相关内容。
合并了堆排序平均情形分析的一些新成果。
在本书中，作者更加精练并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
本书特点：
专用一章来讨论算法设计的技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。
介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。
安排一章专门讨论摊还分析，考察书中介绍的一些高级数据结构。
新开辟一章讨论高级数据结构以及它们的实现，包括红黑树、自顶向下伸展树、treap树、k维树、配对堆以及其他相关内容。
合并了堆排序平均情形分析的一些新成果。
