数据结构与算法（Java语言描述）
点击看大图
基本信息
编辑推荐
本书图文并茂，循序渐进。作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。书中代码都配有详尽而简洁的注释。书中还结合各部分的具体内容穿插了大量问题，以激发读者的求知欲，培养良好的自学习惯和自学能力。
内容简介回到顶部↑
本书充分展示了面向对象技术在现代数据结构理论中的应用，普遍采用了抽象、封装及继承等技术。本书既介绍了基本的数据结构，包括栈、队列、向量、列表结构；也介绍了若干高级数据结构，包括优先队列结构、映射和词典结构、查找树结构等。并结合具体问题介绍了算法的应用、实现及其分析方法，涉及的算法包括堆结构的生成及调整算法、huffman编码树算法、平衡查找树的生成、插入和删除算法，并着重介绍了串匹配的kmp和bm算法。本书还通过遍历算法框架将各种图算法统一起来，并基于遍历算法模板加以实现，在同类教材中独树一帜。.
本书图文并茂，循序渐进。书中代码都配有详尽而简洁的注释。书中还结合各部分的具体内容穿插了大量问题，以激发读者的求知欲，培养良好的自学习惯和自学能力。本书适合用作计算机专业本科生教材或参考书。
本书作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。..
在体例方面，作者结合多年教学实践，对知识点进行了重新整理编排，许多处理方法在同类教材中独树一帜，旨在将读者引向更高层次，使读者形成对数据结构的宏观认识。
在内容方面，本书并未对各种数据结构面面俱到，而是按照cc2001标准对必要知识点和技能要求精心加以裁剪，通过系统分类和启发式讲解，在基本数据结构与高级数据结构之间架起一座桥梁。
在算法方面，本书不仅强调对复杂度等基本概念的把握，同时结合具体问题介绍算法复杂度的各种分析方法，尤其是分摊分析等高级技巧。而且所有数据结构仍然构成一个完整的体系，帮助读者养成面向实际应用的意识，并掌握构建实际应用的基本能力。...
本书图文并茂，循序渐进。书中代码都配有详尽而简洁的注释。书中还结合各部分的具体内容穿插了大量问题，以激发读者的求知欲，培养良好的自学习惯和自学能力。本书适合用作计算机专业本科生教材或参考书。
本书作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。..
在体例方面，作者结合多年教学实践，对知识点进行了重新整理编排，许多处理方法在同类教材中独树一帜，旨在将读者引向更高层次，使读者形成对数据结构的宏观认识。
在内容方面，本书并未对各种数据结构面面俱到，而是按照cc2001标准对必要知识点和技能要求精心加以裁剪，通过系统分类和启发式讲解，在基本数据结构与高级数据结构之间架起一座桥梁。
在算法方面，本书不仅强调对复杂度等基本概念的把握，同时结合具体问题介绍算法复杂度的各种分析方法，尤其是分摊分析等高级技巧。而且所有数据结构仍然构成一个完整的体系，帮助读者养成面向实际应用的意识，并掌握构建实际应用的基本能力。...
目录回到顶部↑
前言
第1章 算法及其复杂度.
1．1 计算机与算法
1．1．1 过指定垂足的直角边
1．1．2 三等分线段
1．1．3 排序
1．1．4 算法的定义
1．2 算法性能的分析与评价
1．2．1 三个层次
1．2．2 时间复杂度及其度量
1．2．3 空间复杂度
1．3 算法复杂度及其分析
1．3．1 o(1)——取非极端元素
1．3．2 o(logn)——进制转换
1．3．3 o(n)——数组求和
1．3．4 o(n2)——起泡排序
1．3．5 o(2r)——幂函数
1．4 计算模型
1．4．1 可解性
1．4．2 有效町解
第1章 算法及其复杂度.
1．1 计算机与算法
1．1．1 过指定垂足的直角边
1．1．2 三等分线段
1．1．3 排序
1．1．4 算法的定义
1．2 算法性能的分析与评价
1．2．1 三个层次
1．2．2 时间复杂度及其度量
1．2．3 空间复杂度
1．3 算法复杂度及其分析
1．3．1 o(1)——取非极端元素
1．3．2 o(logn)——进制转换
1．3．3 o(n)——数组求和
1．3．4 o(n2)——起泡排序
1．3．5 o(2r)——幂函数
1．4 计算模型
1．4．1 可解性
1．4．2 有效町解
前言回到顶部↑
关于计算机教育规范，最有权威、影响最大的莫过于ACM与IEEE-CS联合制订的Computing Curricula。比如，Computing Curricula 1991(CC1991)就曾对我国高校的计算机教育产生深刻的影响。正在制订中的CC2001(后改称CC2004)认为，随着近年来计算概念的快速发展，计算学科已经发展成为一个内涵繁杂的综合性学科，至少可以划分为计算机工程(CE)、计算机科学(CS)、信息系统(IS)、信息技术(IT)和软件工程(SE)五个领域，而且不同领域的人才所应具备的知识结构与能力侧重也不尽相同。尽管如此，从目前已经完成的部分来看，数据结构与算法在各领域的知识体系中仍占据重要的位置。比如在CE分卷(草案)中，Programming Fundamentals共39个核心学时，其中Algorithms and Problem Solving占8个学时，Data Structures占13个学时；在CS分卷(正式稿)中，Programming Fundamentals共38个核心学时，其中Algorithms and Problem Solving占6个学时，Data Structures占14个学时。.
为什么数据结构与算法长期以来一直受到如此重视呢?数据结构和算法是一对孪生兄弟，数据结构研究的问题包括数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。我们在编写计算机程序解决应用问题时，最终都要归结并落实到这两个问题上。正因为此，N．Wirth早在20世纪?o年代就曾指出“程序＝数据结构+算法”。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成，到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。
为遵循上述原则，本书选择Java作为描述语言，因为相对于其他语言，Java语言比较完整、彻底地体现了面向对象的设计思想，这也是目前国际上同行们的一个主要取向。不过，关于Java语言本身的介绍，本书并未花费多少笔墨，而是直接假定读者已经熟练掌握了该语言。这既能缩减本书篇幅，也符合此领域教学今后的规范。比如，CC2001的CS分卷将Data Structures and Algorithms课程编号为CS103，并明确指出该课程是Programming Fundamentals(CS101)和The Object-Oriented Paradigm(CS102)的后续课程。
在内容选取、剪裁与体例结构上，作者力图突破现成的模式。这里并未对各种数据结构面面俱到，而是通过分类和讲解典型结构，力图使读者形成对数据结构的宏观认识；并结合各部分的具体内容，在书中穿插了大量的问题，把更多的思考空间留给读者。
根据内容侧重，本书具体分为10章。
第1章是全书的基础，重点在于介绍算法与数据结构的关系，以及算法时间、空间复杂度的概念及其度量方法。
第2～4章覆盖了基本的数据结构，既有传统的栈与队列，也有更为抽象和通用的向量和列表。面向对象技术在现代数据结构理论中的重要地位在此得到体现，我们利用接口实现数据结构的封装，抽象出位置的概念，在向量和列表的基础上定义并实现序列结构，引入迭代器概念并针对上述结构具体实现。通过结合数组与链表结构的优点，第4章自然地导出了树结构的概念、实现及算法。..
第5～7章介绍了若干高级数据结构。通过在一般性队列中引入优先级概念，导出了优先队列结构；面向实际问题中的查找需求，导出了映射和词典结构；针对全序集的查找问题，引入了查找树结构，并结合AVL树、伸展树和B—树的实例介绍了平衡查找树结构的原理及其实现。面向对象的思想在这里继续得到贯彻，普遍采用了抽象、封装及继承等技术。
这一部分的侧重点逐渐转向算法，并结合具体问题介绍其应用与实现，包括堆结构的生成及调整算法、Huffman(赫夫曼)编码树算法、散列算法以及二路或多路平衡查找树的生成、插入、删除算法。在这三章中，读者也将对算法复杂度的各种分析方法有所了解。
第8～10章的论述重点完全转向算法。第8章对此前各章中陆续介绍过的排序算法进行了归纳与分类，着重介绍了归并排序算法与快速排序算法，并给出了此类算法的复杂度下界。结合串结构的应用，第9章着重讨论了串匹配问题，从蛮力算法出发，采用不同的启发式加速策略，分别介绍了KMP算法及BM算法。
关于图结构，第10章将重点放在相关算法上，并力图使初学者从各种图算法中梳理出清晰的脉络。为此，这里尝试通过一条主线——遍历——将各种算法串接起来。在这里，面向对象技术的魅力再次得以展现：基于统一的图遍历算法模板，分别实现了深度优先、广度优先和最佳优先三大类遍历算法。实际上，这三类算法本身仍然以模板形式实现，包括边分类、可达分量、连通分量、最短路径以及最小生成树在内的各种具体算法，都进而基于这三个模板分别得到了实现。
书中涉及的所有代码，都符合J2SDK-1．4．1规范，并构成一个名为dsa(Data Structures & Algorithms)的包；所有类之间的扩展、继承关系，可以参见书后的"DSA类关系图”。
要获取本书中的代码及相关教学资料，请访问：http：／／vis．cs．tsinghua．edu．cn／～deng／dsaj．htm。
本书从筹划、撰写、审订到定稿，其间跨越三个年头，在此漫长的过程中，我的父母和妻子给了我巨大的支持，就这个意义而言，他们也是本书的完成者。年幼的女儿总是以她独有的方式，不时将我从写作和调试的苦海中解救出来，她让我体会了禁用PowerOff按钮的妙用(尽管除了拔掉接头外我还没有找到更好的办法，使得在她恶作剧地按下Reset按钮后依然能够继续写作)。我的确需要感谢她，她让我养成了及时备份的良好习惯，更使我意识到在离开电脑后自己依然能够而且更好地思考。
在清华大学执教多年，我日益深刻地体会到教育的伟大和神圣，是我的同事、学生使我懂得了如何忘却劳动的艰辛，并从教育的过程中获得乐趣。
我还要特别感谢机械工业出版社的温莉芳女士，在我一次次地推迟交稿时，她表现出的耐心与理解都令我既钦佩又惭愧，正是这非凡的宽容激励着我不断追求完美。
虽反复斟酌，在本书即将出版之际，内心依然惶恐。“丑媳妇终要见公婆”，恳请读者批评指正。...
邓俊辉
2005年岁未定稿
为什么数据结构与算法长期以来一直受到如此重视呢?数据结构和算法是一对孪生兄弟，数据结构研究的问题包括数据在计算机中存储、组织、传递和转换的过程及方法，这些也是构成与支撑算法的基础。我们在编写计算机程序解决应用问题时，最终都要归结并落实到这两个问题上。正因为此，N．Wirth早在20世纪?o年代就曾指出“程序＝数据结构+算法”。近年来，随着面向对象技术的广泛应用，从数据结构的定义、分类、组成，到设计、实现与分析的模式和方法都有了长足的发展，现代数据结构更加注重和强调数据结构的整体性、通用性、复用性、简洁性和安全性。
为遵循上述原则，本书选择Java作为描述语言，因为相对于其他语言，Java语言比较完整、彻底地体现了面向对象的设计思想，这也是目前国际上同行们的一个主要取向。不过，关于Java语言本身的介绍，本书并未花费多少笔墨，而是直接假定读者已经熟练掌握了该语言。这既能缩减本书篇幅，也符合此领域教学今后的规范。比如，CC2001的CS分卷将Data Structures and Algorithms课程编号为CS103，并明确指出该课程是Programming Fundamentals(CS101)和The Object-Oriented Paradigm(CS102)的后续课程。
在内容选取、剪裁与体例结构上，作者力图突破现成的模式。这里并未对各种数据结构面面俱到，而是通过分类和讲解典型结构，力图使读者形成对数据结构的宏观认识；并结合各部分的具体内容，在书中穿插了大量的问题，把更多的思考空间留给读者。
根据内容侧重，本书具体分为10章。
第1章是全书的基础，重点在于介绍算法与数据结构的关系，以及算法时间、空间复杂度的概念及其度量方法。
第2～4章覆盖了基本的数据结构，既有传统的栈与队列，也有更为抽象和通用的向量和列表。面向对象技术在现代数据结构理论中的重要地位在此得到体现，我们利用接口实现数据结构的封装，抽象出位置的概念，在向量和列表的基础上定义并实现序列结构，引入迭代器概念并针对上述结构具体实现。通过结合数组与链表结构的优点，第4章自然地导出了树结构的概念、实现及算法。..
第5～7章介绍了若干高级数据结构。通过在一般性队列中引入优先级概念，导出了优先队列结构；面向实际问题中的查找需求，导出了映射和词典结构；针对全序集的查找问题，引入了查找树结构，并结合AVL树、伸展树和B—树的实例介绍了平衡查找树结构的原理及其实现。面向对象的思想在这里继续得到贯彻，普遍采用了抽象、封装及继承等技术。
这一部分的侧重点逐渐转向算法，并结合具体问题介绍其应用与实现，包括堆结构的生成及调整算法、Huffman(赫夫曼)编码树算法、散列算法以及二路或多路平衡查找树的生成、插入、删除算法。在这三章中，读者也将对算法复杂度的各种分析方法有所了解。
第8～10章的论述重点完全转向算法。第8章对此前各章中陆续介绍过的排序算法进行了归纳与分类，着重介绍了归并排序算法与快速排序算法，并给出了此类算法的复杂度下界。结合串结构的应用，第9章着重讨论了串匹配问题，从蛮力算法出发，采用不同的启发式加速策略，分别介绍了KMP算法及BM算法。
关于图结构，第10章将重点放在相关算法上，并力图使初学者从各种图算法中梳理出清晰的脉络。为此，这里尝试通过一条主线——遍历——将各种算法串接起来。在这里，面向对象技术的魅力再次得以展现：基于统一的图遍历算法模板，分别实现了深度优先、广度优先和最佳优先三大类遍历算法。实际上，这三类算法本身仍然以模板形式实现，包括边分类、可达分量、连通分量、最短路径以及最小生成树在内的各种具体算法，都进而基于这三个模板分别得到了实现。
书中涉及的所有代码，都符合J2SDK-1．4．1规范，并构成一个名为dsa(Data Structures & Algorithms)的包；所有类之间的扩展、继承关系，可以参见书后的"DSA类关系图”。
要获取本书中的代码及相关教学资料，请访问：http：／／vis．cs．tsinghua．edu．cn／～deng／dsaj．htm。
本书从筹划、撰写、审订到定稿，其间跨越三个年头，在此漫长的过程中，我的父母和妻子给了我巨大的支持，就这个意义而言，他们也是本书的完成者。年幼的女儿总是以她独有的方式，不时将我从写作和调试的苦海中解救出来，她让我体会了禁用PowerOff按钮的妙用(尽管除了拔掉接头外我还没有找到更好的办法，使得在她恶作剧地按下Reset按钮后依然能够继续写作)。我的确需要感谢她，她让我养成了及时备份的良好习惯，更使我意识到在离开电脑后自己依然能够而且更好地思考。
在清华大学执教多年，我日益深刻地体会到教育的伟大和神圣，是我的同事、学生使我懂得了如何忘却劳动的艰辛，并从教育的过程中获得乐趣。
我还要特别感谢机械工业出版社的温莉芳女士，在我一次次地推迟交稿时，她表现出的耐心与理解都令我既钦佩又惭愧，正是这非凡的宽容激励着我不断追求完美。
虽反复斟酌，在本书即将出版之际，内心依然惶恐。“丑媳妇终要见公婆”，恳请读者批评指正。...
邓俊辉
2005年岁未定稿
加载中...
