算法与数据结构

前言

　　关于算法的研究已经有数千年的历史。计算机的出现，使得用机器自动解题的梦想成为现实，人们可以将算法编写成程序交给计算机执行，使许多原来认为不可能完成的算法变得实际可行。数据结构的概念最早由C.A.R.Hoare和N.Wirth在1966年提出。大量关于程序设计理论的研究表明：对大型复杂程序的构造进行系统而科学的研究，必须对这些程序中所包含的数据结构进行深入的研究。事实上，程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。不清楚解决问题的算法就无法决定如何组织数据，反之算法的实现又在很大程度上依赖于数据的具体组织。简言之，算法与数据结构是程序设计中相辅相成、不可分割的两个方面。因此，1976年N.Wirth用“算法+数据结构=程序”这个公式表达了算法与数据结构的联系和它们在程序中的地位。　　抽象数据类型起源于20世纪70年代，可以定义成：有一定行为（操作）的抽象（数学）类型。它抽象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。它支持数据类型的实现与使用分离的原则，是一种十分有效的对问题进行抽象与分解的思维工具，后来发展成为面向对象技术与方法的主要理论基础。?　　从抽象数据类型的观点出发，数据结构可以理解成为“抽象数据类型的物理实现”。对于数据结构的学习和研究，主要围绕两个问题：一个是如何具体表示抽象数据类型中的数学模型；另一个是如何给出抽象数据类型中需要的操作的具体实现。用上述观点，可以从更加抽象的角度理解数据结构与算法的关系，也容易解释数据的逻辑结构、存储结构与运算的三者关系。?　　目的与动机?　　“数据结构”（或称“数据结构与算法”或“算法与数据结构”）是计算机科学的基础课程，它被独立列入大学本科的教学计划有30多年的历史。其主要目的是使读者全面地理解数据结构和算法的概念、掌握设计数据结构与算法的主要原理和方法、比较不同数据结构和算法的特点。通过学习和实践，提高学生使用计算机解决问题的能力。?　　1998年，北京大学把“算法与数据结构”作为第一批理科各系主干基础课列入学校的教学计划。经北大信息学院和数学学院共同推荐，著者连续六年被校长聘任为该课程的全校主持人，负责组织理科各院系的主讲老师制定教学大纲、编写教材和教学辅导用书、交流教学经验等工作。　　本书的第一版就是在这个背景下，邀请了北大物理学院、化学学院和计算中心的几位主讲老师与著者共同编写的。从2000年开始，本书作为北京大学主干课“算法与数据结构”的教材在校内试用，2002年得以在高等教育出版社正式出版，并得到广大校内外老师和学生的支持和鼓励，被评为“2004年北京市高等教育精品教材”。为了回报广大读者，使得这本书能够更上一个台阶，成为过得硬的“精品”教材，在高等教育出版社的大力支持下，著者决定认真修改后出此新版。?

书籍目录

1　绪论　1.1　从问题到程序  　1.1.1　问题分析与抽象　  1.1.2　程序的设计与实现　1.2　抽象数据类型  　1.2.1　什么是抽象数据类型　  1.2.2　意义与作用  　1.2.3　举例  1.3  数据结构　  1.3.1　什么是数据结构  　1.3.2　数据结构的分类　  1.3.3　结点与结构  　1.3.4　外存数据的组织  1.4　算法　　1.4.1　什么是算法　　1.4.2　算法的设计　　1.4.3　算法的精化　　1.4.4　算法的分析　小结　习题2　线性表　2.1　基本概念与抽象数据类型    2.1.1　基本概念    2.1.2　抽象数据类型  2.2　顺序表示    2.2.1　存储结构    2.2.2　运算的实现    2.2.3　分析与评价    2.2.4　顺序表空间的扩展　2.3　链接表示　　2.3.1　单链表表示　　2.3.2　单链表上运算的实现　　2.3.3　分析与比较　　2.3.4　单链表的改进和扩充　2.4　应用举例　  2.4.1　Josephus问题　  2.4.2　采用顺序表模拟  　2.4.3　采用循环链表模拟　2.5　矩阵　  2.5.1　矩阵的顺序表示　  2.5.2　稀疏矩阵的表示方法　2.6　广义表与动态存储管理  　2.6.1　广义表　  2.6.2　结点的动态分配与回收　  2.6.3　废料收集与存储压缩　小结　习题3　字符串  3.1　字符串及其抽象数据类型    3.1.1　基本概念    3.1.2　抽象数据类型  3.2　字符串的实现    3.2.1  顺序表示    3.2.2　链接表示  3.3　模式匹配    3.3.1　朴素的模式匹配    3.3.2　无回溯的模式匹配  小结  习题4  线与队列5  二叉树与树6  集合与字典7  高级字典结构8  排序9  图10  算法分析与设计参考文献索引算法清单后记

编辑推荐

　　《算法与数据结构：C语言描述（第2版）》以数据结构为主线，算法为辅线组织教学内容。全书共分10章：绪论、线性表、字符串、栈与队列、二叉树与树、集合与字典、高级字典结构、排序、图和算法分析与设计。《算法与数据结构：C语言描述（第2版）》体系完整，概念清楚，内容充实，取材适当。第一版在2004年被评为“北京市高等教育精品教材”。

作者简介

《算法与数据结构:C语言描述(第2版)》以数据结构为主线，算法为辅线组织教学内容。全书共分10章：绪论、线性表、字符串、栈与队列、二叉树与树、集合与字典、高级字典结构、排序、图和算法分析与设计。《算法与数据结构:C语言描述(第2版)》体系完整，概念清楚，内容充实，取材适当。第一版被列入“面向21世纪课程教材”，2004年被评为“北京市高等教育精品教材”，第二版被列入普通高等教育“十一五”国家级规划教材。

新版采用“数据结构作为抽象数据类型的物理实现”观点，在内容和形式上都进行了许多改进和扩充，提高了抽象数据类型在教学中的地位和作用，更加突出了重点，还补充了习题，增加了索引。新版的第4次印刷本对书稿中的各种问题进行了认真的修改与完善，提高了全书的可读性。

由于在编写中注意到知识模块的独立性和相关性，不同专业和不同水平的学生可以根据需要组合使用。《算法与数据结构:C语言描述(第2版)》既可以作为计算机专业本科“数据结构”教材，也可以作为理工科有关专业本科和计算机专业专科学生学习相关课程的教材或教学参考书。

图书封面

---

 算法与数据结构下载

---