包邮程序设计抽象思想：C语言描述

内容简介

本书全面介绍了数据结构的基础内容，帮助学生深入了解软件工程的思想和技术。学生还可以通过对一些高级编程概念（如接口、抽象和封装）的了解，为进一步深入学习高级编程知识打下坚实的基础。本书观点清晰明了、语言风格鲜明独特，深入浅出地介绍了一些高级主题。
本书特色：
◆介绍了多个库包，可用于简化编程流程，使学生可以专注于高层次理论问题的研究，避免了C语言编程的繁琐细节；
◆详细讨论了递归编程的用法，包括大量难度各异的编程示例和练习，如简单的递归函数，分析双人游戏的*小*大(minimax)策略，等等；
◆帮助读者培养编写健壮、可重用代码的良好编程习惯。

前言

　　写给教师本教程适用于大学编程课程，它覆盖了AMCCurriculum78报告中所定义的计算机科学2标准课程的材料，并且包括ComputingCurriculum1991算法与数据结构课程中的大部分知识。本书将教会学生现代软件工程方法论。本书的内容建立在我于1995年写的TheArtandScienceofC教科书的基础上，并将抽象和接口设计作为核心主题。虽然我写作这两本书是有先后顺序的，但是读者完全可以单独使用本书。本书的第Ⅰ部分包括了TheArtandScienceofC中学生应该掌握的所有背景知识。这些背景知识对于理解本课程其他部分中的例子和方法已经绰绰有余了。由于第Ⅰ部分的介绍是比较简单，因此学生必须熟悉计算机基础课程中涉及的基本编程概念。但是，读者不需要对C语言有所了解，因为在本书的前几章中将介绍C语言的基础。学习过TheArtandScienaofC课程的学生完全可以跳过第Ⅰ部分的内容。在学习完了第Ⅰ部分的预备知识之后，学生可以继续该课程的学习。第Ⅱ部分将讨论递归算法。在第Ⅱ部分的4章内容中，穿插了大量的实例。根据我个人的经验，介绍递归算法的*合理时刻是在第Ⅱ门编程课程开始学习的时候。很多学生都会觉得递归是一个难以理解的概念，必须花很多时间才能较好地掌握它。如果在新学期的一开始就面临递归这个难点，那么学生将有更多的时间来掌握它。在本书中，尽可能早地介绍递归概念，其目的是让读者在作业和考试中运用这种知识。期中考试可以检查学生对递归概念的掌握情况，对于那些确确实实理解递归概念比较差的学生，可以给他们以警示，以便他们及时采取相应的补救措施。如果想压缩学习递归的时间，那么可以跳过第Ⅱ部分的6.1节，这对整个课程的讲述没有什么影响。也许鞍点算法对于部分学生来说有点儿太复杂了，但是它却很好地说明递归算法可以使用很少的代码来解决非常困难的问题。类似地，第7章中大O的理论基础也不是该课程的重点内容。第Ⅲ部分有双重目的：一方面，它介绍了数据结构课程中涉及的非递归算法的概念，包括堆栈、队列以及符号表；另一方面，这部分为学生提供了一些工具，从而帮助学生理解其他部分中涉及的基于接口编程的数据抽象概念。与这个概念相一致的是抽象数据类型(ADT)，它是由行为而不是由表现形式定义。本书的一个重要特点是，它不完全使用ANSIC的工具来定义ADT，其中ADT的内部表示对于客户端来说是不可访问的。由于这样的编程风格强调了抽象的难度，因此可以培养学生具有编写良好结构的程序和模块的习惯。我认为在本书中学习的接口是个实用的工具。在许多情况下，学生可以在他们自己的代码中包含和实现这些接口。在第Ⅲ部分的*后一章，即第11章，将介绍几个重要的概念，例如，函数指针、映射函数以及迭代器。相对来说，迭代器在斯坦福大学的课程中是新近加入的，但是教学效果相当好。根据我们的经验，减少客户代码的复杂性所带来的收益远远超过建立迭代器抽象所做工作的代价。第Ⅲ和第Ⅳ部分的重点是抽象数据类型。在某种程度上，这是人为划分的结果。这两部分的不同之处在于，第Ⅳ部分中的抽象数据类型是用递归实现的，而第Ⅲ部分则不是。这样安排的好处是第Ⅳ部分在本书中起到综合的作用，将前两部分的递归和ADT进行综合。尽管第14章中关于表达式树的内容可以跳过，但是我发现尽早地在课程中包括这些内容是很有价值的，因为这样可以减少对C语言编译器操作的神秘感，可以帮助学生更好地理解和控制程序。第17章确实不是本课程的主要内容，而是为学生继续接下来的学习作的预备。本章主要使用Java语言介绍面向对象编程，讲述主要的概念。尽管有些机构已经开始采用由浅入深的顺序方式介绍Java，但是我们认为，由于下列一些原因，先介绍结构化编程方法再介绍面向对象编程方法是很有意义的：1.Java环境的变化太快了，无法为教学提供稳固的基础；2.学生有必要理解结构化编程方法；3.如果在基础课程中强调数据抽象和接口，那么学生学习面向对象编程将更加容易。在斯坦福大学的经验给我们的启示是，这种策略很有效，它能够使学生相对容易地接受面向对象的概念。

节选

作者简介

　　EricS.Roberts于1980年在哈佛大学获取了应用数学的博士学位，毕业后在Wellesley大学创建了计算机科学系并担任主任，随后在加利福尼亚的DigitalEquipemntCorporation的系统研发中心担任了5年的调研员，现就职于斯坦福大学计算机科学系，并担任斯坦福大学教务部主任。作为一位知名教授，Roberts还编写过TheArtandScienceofC等经典教材。闪四清，大学教师，长期从事数据库、数据挖掘、数据结构等方面的数学、学术研究。已经发表学术论文30多篇，翻译、编写了《数据库系统原理和应用》等多部著作。