图书目录第Ⅰ部分 预备知识　　第1章 ANSI C概述1　　1.1 什么是C　　1.2 C程序的结构　　1.3 变量、值和类型　　1.4 表达式　　1.5 语句　　1.6 函数　　1.7 小结　　1.8 复习题　　1.9 编程练习　　第2章 C的数据类型　　2.1 枚举类型　　2.2 数据和内存　　2.3 指针　　2.4 数组　　2.5 指针和数组　　2.6 记录　　2.7 动态分配　　2.8 小结　　2.9 复习题　　2.10 编程练习　　第3章 库和接口　　3.1 接口的概念　　3.2 随机数字　　3.3 字符串　　3.4 标准的I/国外经典教材计算机科学与技术程序设计抽象思想c语言描述(美) Eric S. roberts著闪四清译清华大学出版社北京Simplified Chinese edition copyright e 2005 by PEARSON EDUCATION ASIA LIMITED and TSINGHUAUNIVERSITY PRESSOniginal English language title from Proprietor,'s edition of the WorkOriginal English language title: Programming Abstractions in C by Eric S Roberts, Copyright 2003EsBN:0-20154541-1Al Rights ReservedPublished by arrangement with the original publisher, Pearson Education, Inc, publishing as Addison-Wesley.This edition is authorized for sale only in the peaples Republic of china(excluding the Special AdministrativeRegion of Hong Kong and Macao)本书中文简体翻译版由培生教育出版集团授权给淸华大学出版社在中国境内(不包括中国否港、澳门特别行政区〕出版发行。北京市版权局著作权合同登记号图字:01-2003-1779版权所有,翻印必究。举报电话:010-627829891350125667813801310933本书封面贴有 Pearson education(培生教育出版集团)激光防伪标签,无标签者不得销售。图书在版编目(CIP)数据程序设计抽象思想—C话言描述(美罗伯茨( Roberts,ES)著:闪四清译一北京:清华大学出版社,20056书名原文: Programming Abstractions in C(国外经典教材→计算机科学与技术)ISBN7302-10165-5I.程…Ⅱ①罗…②闪…ⅢC语言一程序设计Ⅳ.TP312中国版本图书馆CIP数据核字(2004)第135866号出版者:清华大学出版社地址:北京清华大学学研大厦htp://www.tup.con.cn邮编:100084社总机:0106277075客户服务:01062776969组稿编辑:曹康文稿编辑:王黎封面设计:康博版式设计:康博印刷者:北京市世界知识印刷厂装订者:北京鑫海金澳胶印有限公司发行者:新华书店总店北京发行所开本:185×260印张:43.25字数:117千字服次:2005年6月第1版2005年6月第1次印刷书号:ISBN7-302101655/TP·6950印数:I-4000定价:78.00元出版说明近年来,我国的髙等教育特別是计算机学科教育,进行了一系列大的调整和改革,急需批门类齐全、具有国际先进水平的计算机经典教材,以适应当前我国计算机科学的教学需要。通过使用国外先进的经典教材,可以了解并吸收国际先进的教学思想和教学方法,使我国的计算机科学教育能够跟上国际计算机教育发展的步伐,从而培育出更多具有国际水准的计算机专业人才,增强我国计算机产业的核心竞争力。为此,我们从国外知名的出版集团 Pearson引进这套“国外经典教材计算机科学与技术”教材。作为全球最大的图书出版机构, Pearson在高等教育领域有着不凡的表现,其下属的 PrenticeHal和 Addison Wesley出版社是全球计算机高等教育的龙头出版机构。清华大学出版社与Pearson出版集团长期保持着紧密友好的合作关系,这次引进的“国外经典教材·计算机科学与技术”教材大部分出自 Prentice hal和 Addison Wesley两家出版社。为了组织该套教材的出版,我们在国内聘请了一批知名的专家和教授,成立了一个专门的教材编审委员会。教材编审委员会的运作从教材的选题阶段即开始启动,各位委员根据国内外高等院校计算机科学及相关专业的现有课程体系,并结合各个专业的培养方向,从 Pearson出版的计算机系列教材中精心挑选针对性强的题材,以保证该套教材的优秀性和领先性,避免出现“低质重复引进”或“高质消化不良”的现象。为了保证出版质量,我们为该套教材配备了—批经验丰富的编辑、排版、校对人员,制定了更加严格的出版流程。本套教材的译者,全部来自于对应专业的高校教师或拥有相关经验的IT专家。每本教材的责编在翻译伊始,就定期不间断地与该书的译者进行交流与反馈。为了尽可能地保留与发扬教材原著的精华,在经过翻译、排版和传统的三审三校之后,我们还请编审委员或相关的专家教授对文稿进行审读,以最大程度地弥补和修正在前面一系列加工过程中对教材造成的误差和瑕疵。由于时间紧迫和受全体制作人员自身能力所限,该套教材在出版过程中很可能还存在一些遗憾,欢迎广大师生来电来信批评指正。同时,也欢迎读者朋友积极向我们推荐各类优秀的外计算机教材,共同为我国高等院校计算机教育事业贡献力量。清华大学出版社国外经典教材·计算机科学与技术编审委员会主任委员:孙家广清华大学教授副主任委员:周立柱清华大学教授委员(按姓氏笔画排序)王成山天津大学教授王珊中国人民大学教授冯少荣厦门大学教授冯全源西南交通大学教授刘乐善华中科技大学教授刘腾红中南财经政法大学教授吉根林南京师范大学教授孙古贵吉林大学教授阮秋琦北京交通大学教授何晨上海交通大学教授吴百锋复旦大学教授李彤云南大学教授杨宗源华东师范大学教授沈钧毅西安交通大学教授邵志清华东理工大学教授陈纯浙江大学教没陈钟北京大学教授陈道蓄南京大学教授周伯生北京航空航天大学教授孟祥旭山东大学教授姚淑珍北京航空航天大学教授徐佩霞中国科学技术大学教授徐晓飞哈尔滨工业大学教授秦小麟南京航空航天大学教授钱培德苏州大学教授曹元大北京理工大学教授龚声蓉苏州大学教授谢希仁中国人民解放军理工大学教授致谢编写一本教材绝不是一个人所能完成的工作。在完成这本书的过程中,我很幸运地得到了许多有才华和有奉献精神的人的帮助。我特别要感谢斯坦福大学的以下各位同事,他们以各自不同的方式给予了我帮助过去几年一直以该书的草稿进行教学的讲师,包括 Jerry cain、 Maggie Johnson、BobPlummer、 Mehran sahami以及 Julie Zelenski我的助教, Stacey Doerr和 Brain o' Connor,,他们为该书精选了作业题,很多作业作为练习题出现在该书中。所有我所在科部的教师,他们帮助我向学生解释了在我较早版本的手稿屮没有包含的概念。● Steve freund和 Thetis开发团队的成员,他们提供了一个优秀的计算杋环境供学生使用。●教育部的工作人员,特别是 Claire Stager和 die wallace,保证了一切都进展顺利。●我的关于计算机科学入门教学研讨会的各位参与者。斯坦福大学学习该课程的学生,他们完成了很多实验非常感谢 Addison-Welsey的各位书评员提出的关于改进该书结构和质量的建议:· Phillip Barry,明尼苏达大学Martin Cohn,布兰代斯大学Dan ellard,哈佛大学Gopal gupta,新墨西哥大学Phillip w.Huto,埃默里大学Randall pruim,波士顿大学· Zhong Shao,耶鲁大学我也收到了里德学院的 Joe Buhler、普雷斯瓦勒公司的 Pavel curtis、巴尔的摩马里兰大学Jim Mayfield的很好的建议。该书的大部分工作是我在里德休假时完成的,非常感谢数学系Joe和他的同事,他们为我提供了十分适合工作的地方我还要感谢我的编辑, Susan hartman和 Addison- Welsey的所有工作人员 Cynthia Benn、ynne doran Cote、 Jackie davies、 Julie dunn、 Peter gordon、 Amy Willcutt、 Bob Woodbury和Tom Ziolkowski,感谢他们对本书和以前我出版的图书的支持。最后,我要感谢我的搭档 Lauren rusk,她又一次展现了其开发编辑的魅力。 Lauren的专业知识让该书条理更为清晰,使本书增色不少。没有她,就不可能有这样本好书诞生。写给教斯本教程适用于大学编程课程,它覆盖了 AMC Curriculun"78报告中所定义的计算机科学2标准课程的材料,并且包括 Computing Curriculum199算法与数据结构课程中的大部分知识。本书将教会学生现代软件工程方法论。本书的内容建立在我于1995年写的 The art andScience ofo教科书的基础上,并将抽象和接口设计作为核心主题。虽然我写作这两本书是有先后顺序的,但是读者完全可以单独使用本书。本书的第I部分包括了 The Art and Science of c中学生应该掌握的所有背景知识。这些背景知识对于理解本课程其他部分中的例子和方法已经绰绰有余了。由于第I部分的介绍是比较简单,因此学生必须熟悉计算机基础课程中涉及的基本编程概念。但是,读者不需要对C语言有所了解,因为在本书的前几章中将介绍C语言的基础。学习过 The Ar and Sciena ofc课程的学生完全可以跳过第I部分的内容。在学习完了第I部分的预备知识之后,学生可以继续该课程的学习。第Ⅱ部分将讨论递归算法。在第Ⅱ部分的4章内容中,穿插了大量的实例。根据我个人的经验,介绍递归算法的最合理时刻是在第门编程课程开始学习的时候。很多学生都会觉得递归是一个难以理解的概念,必须花很多时间才能较好地掌握它。如果在新学期的一开始就面临递归这个难点,那么学生将有更多的时间来掌握它。在本书中,尽可能早地介绍递归概念,其目的是让读者在作业和考试中运用这种知识。期中考试可以检査学生对递归概念的掌握情况,对于那些确确实实理解递归概念比较差的学生,可以给他们以警示,以便他们及时采取相应的补救措施。如果想压缩学习递归的时间,那么可以跳过第Ⅱ部分的6.1节,这对整个课程的讲述没有什么影响。也许鞍点算法对于部分学生来说有点儿太复杂了,但是它却很好地说明递归算法可以使用很少的代码来解决非常困难的问题。类似地,第7章中大O的理论基础也不是该课程的重点内容。第I部分有双重目的:一方面,它介绍了数据结构课程中涉及的非递归算法的概念,包括堆栈、队列以及符号表;另一方面,这部分为学生提供了一些工具,从而帮助学生理解其他部分中涉及的基于接口编程的数据抽象概念。与这个概念相一致的是抽象数据类型(ADI),它是行为而不是由表现形式定义。本书的一个重要特点是,它不完全使用 ANSI C的于具来定义ADT,其中ADT的内部表示对于客户端来说是不可访问的。由于这样的编程风格强调了抽象的难度,因此可以培养学生具有编写良好结构的程序和模块的习惯。我认为在本书中学习的接口是个实用的工具。在许多情况下,学生可以在他们自已的代码中包含和实现这些接口。在第Ⅲ部分的最后章,即第11章,将介绍儿个重要的概念,例如,函数指针、映射函数以及迭代器。相对来说,迭代器在斯坦福大学的课程中是新近加入的,但是教学效果相当好根据我们的经验,减少客户代码的复杂性所带来的收益远远超过建立迭代器抽象所做工作的代价。第Ⅲ和第Ⅳ部分的重点是抽象数据类型。在某种程度上,这是人为划分的结果。这两部分的不同之处在于,第Ⅳ部分中的抽象数据类型是用递归实现的,而第Ⅲ部分则不是。这样安排的好处是第Ⅳ部分在本书中起到综合的作用,将前两部分的递归和ADT进行综合尽管第14章中关于表达式树的内容可以跳过,但是我发现尽早地在课程中包括这些内容是根有价值的,因为这样可以减少对C语言编译器操作的神秘感,可以帮助学生更好地理解和控制程序。第17章确实不是木课程的主要内容,而是为学生继续接下来的学习作的预备。本章主要使用Java语言介绍面向对象编程,讲述主要的概念。尽管有些机构已经开始采用由浅入深的顺序方式介绍Java,但是我们认为,由于下列一些原因,先介绍结构化编程方法再介绍面向对象编程方法是很有意义的:.Java环境的变化太快了,无法为教学提供稳固的基础2.学生有必要理解结构化编程方法;3.如果在基础课程中强调数据抽象和接口,那么学生学习面向对象编程将更加容易。在斯坦福大学的经验给我们的启示是,这种策略很有效,它能够使学生相对容易地接受面向对象的概念。写给学生每一年,计算机领域都会取得许多令人振奋的发展。计算机硬件变得比以前更小、更快、更便宜。在计算机商店里的货架上,摆满了各种各样的、十年前根本无法想象的应用软件。像Internet和万维网这样的技术创新正在改变着人们获取信息、商业交易、与人沟通的方式。掌握计算机技术的人将拥有无穷的机遇。计算机科学的学习有相似之处。您所学到的每一个新概念,都会使得编程变得越来越让人兴奋。您将具有更多的创造性,可以解决更难的问题,能够开发更加精密复杂的软件。这本书适合于那些学习了计算机科学导论,并对编程有一定了解的初学者大部分的入门课程都以编程技术为中心:学习某种语言的语法,并使用这种语言编写简单的程序。本书的目的是想通过介绍编程过程中遇到的难点和问题,来拓宽视野。编程不是简单的记忆语法规则和写—些简单的过程代码,而是解决难题,这需要经过大量的思考和做大量的工作。然而,通过本书介绍的策路和方法,读者可以简化这个学习过程。在学习书中介绍的概念时,将从策略的角度(例通归算法)和技术细节的角度(例如散列技术)进行介绍,这样将使得读者能够解决现在看来似乎不能解决的问题。当然,学习这些概念是一项挑战性的工作。有时对于某些概念,读者可能迷惑不解。但是,一旦真正地理解了这些概念,那么读者将会更加深刻地理解计算机的强大能力。祝学习癫利愉快!Eric Roberts斯坦福大学计算机科学系997年6月