数据结构与算法
2006-1
高等教育出版社
幸运帏
315
无
自20世纪70年代以来，数据结构开始成为计算机科学与技术专业的核心课程。最近十几年来，数据结构与算法在计算学科的4个主要分支：计算机科学（CS）、计算机工程（CE）、软件工程（SE）和信息系统（IS）中的地位越来越重要了，这一点可以从ACM和IEEE／CS的“Computing Curricula 1991”和“Computing Curricula 2001”中体现出来。 目前，计算机应用已经几乎渗透到人们活动的所有领域。由于高级程序设计语言和编程工具的推出和普遍使用，为各行各业的人员学习程序设计提供了可行的条件。现在为计算机编写程序已经不仅仅是计算机专业人员的工作，各行各业的专家都在开发本行业的应用软件。因此，数据结构与算法课程早已不仅仅是计算机专业独有的课程，本书是为所有需要学习计算机程序设计技术的计算机专业和与计算机相关专业的读者编写的。 数据结构与算法的设计是程序设计的核心，二者密不可分。事实上，过去所有的数据结构教材都包含一定的算法方面的内容，最常见的是查找与排序算法以及一些图论问题（如图的连通性、最小生成树、最短路径等）。最近十年，情况有所变化，有关算法设计与分析的知识和技术受到更多的重视。国内外出现了许多新的教材，例如“Data Structures andAlgorithmAnalysis”等，与一般的数据结构教材相比，新教材增加了更多的算法方面的内容，这种趋势是很明显的。本书的编写正是适应了这种形势，我们参阅了国内外经典著作和最新教材，结合编者多年讲授算法、数据结构和程序设计课程的经验，力求在内容方面深入浅出，既先进、严谨，又通俗易懂，希望能受到我国相关专业的老师和同学的欢迎。 “数据结构与算法”是为学习了一种程序设计语言的读者编写的。掌握了初步的程序设计方法之后，面对实际的应用问题，最重要的就是学习如何选择和设计有效的数据结构和算法。编写程序的目的是解决问题，而问题的求解过程就是对于数据的组织和处理的过程，数据的组织方法是数据结构部分的基本内容，数据的处理方法是算法部分的基本内容，二者是相辅相成的。本书全面地介绍了解决从简单到复杂的各种应用问题的数据结构及其编程实现方法，包括较为简单的线性表、栈、队列、数组和较为复杂的树结构与图。对于算法的分析与设计技术，本书把重点放在介绍各种算法的设计方法，一方面介绍了与数据结构相关的算法，例如查找算法、排序算法和图论算法；另一方面则介绍了诸如分治、贪心、动态规划等常用的算法设计策略，这部分内容，过去属于研究生学习的范围，特别是第9章，篇幅不大，但内容较多、较深，本科生学习可能会有一定难度，教师在讲授中可以适当取舍。
《数据结构与算法》是数据结构与算法设计的教材，其宗旨是将数据结构与算法设计有机地结合起来，向读者系统介绍了数据结构的基本概念及主要的算法设计方法。全书共分9章，第1章介绍了数据结构的基本概念，第3～8章分别介绍了线性表、串、栈、队列和数组、树结构和图结构以及查找和排序等数据结构的相关知识，在第2章简单介绍算法概念的基础上，第9章详细介绍了几种算法的设计方法，并给出实例具体说明设计过程。书中主要算法都用C++语言写出，并给出了详细的注解。《数据结构与算法》概念清楚，选材精练，叙述深入浅出，用了大量的例子和图表来说明基本概念和方法，直观易懂。每章后面都附有习题，读者可以通过习题复习和检验所学知识。《数据结构与算法》可以作为高等院校理工科学生的教材，也可以作为广大计算机科学与工程领域从业人员的参考书。
辛运帏，1965年生。1986年毕业于南开大学计算机与系统科学系，并留校任教。曾先后从师于陈有祺教授、卢桂章教授，并获得工学硕士、博士学位，现为南开大学信息技术科学学院计算机科学技术系教授。多年来主讲“数据结构”、“形式语言与自动机”、“计算方法”等课程。主要研究领域为人工智能、电子商务、加密技术等，曾承担科技部、天津市重点基金等多项科研项目，出版教材《数据结构导论》、《Java程序设计》等，发表论文十余篇。 刘璟，1942年生。1981年于南开大学数学系研究生毕业。南开大学计算机科学技术系教授，博士生导师，教育部计算机科学与技术教学指导委员会委员，基础分会副主任，天津市高等学校计算机基础教学指导委员会副主任，中国计算机学会理论计算机科学分会理事，天津市学位委员会学科评议组成员。长期讲授“高级语言程序设计”、“算法设计与分析”等课程。主要研究领域为并行与分布式系统、算法设计与分析、网络存储系统、面向对象程序设计等。曾主持国家863、自然科学基金、博士点基金项目等十余项，在国内外发表论文60篇，出版教材“计算机算法引论”、“高级语言C++程序设计”等。 陈有祺，1936年生。1960年毕业于北京大学数学力学系，同年在南开大学任教。1980-1982年在美国西密西根大学作访问学者，研修人工智能和形式语言，现为南开大学教授。曾任南开大学计算机与系统科学系主任，现兼任中国计算机学会理论计算机科学分会理事，全国高等学校计算机教育研究会理事，《理论计算机科学》常务编委等职。多年来从事编译理论、形式语言与自动机、人工智能和自然语言理解等领域的教学与研究工作，共发表论著二十余篇（部）。1991年被评为天津市优秀教师。
第l章 绪论1.1 数据结构简介1.1.1 数据结构的发展历史1.1.2 数据结构的基本概念和术语1.2 有关的预备知识1.2.1 集合1.2.2 递归1.2.3 数学证明方法习题第2章 算法的基本概念与算法分析2.1 算法的基本概念2.1.1 一个简单的算法2.1.2 什么是算法2.1.3 算法与问题2.1.4 算法与程序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.3.5 平均情形和算法的期望复杂度2.3.6 复杂度函数的表示2.4 算法设计与分析的重要性2.4.1 一个实例2.4.2 计算机应用领域的变化2.4.3 计算机技术的发展需要设计有效算法2.5 MAXMIN问题2.5.1 MAxMIN问题的平凡算法2.5.2 第一次改进算法2.5.3 第二次改进算法2.5.4 采用分治策略的改进算法2.5.5 算法MAxMIN的讨论习题第3章 线性表3.1 线性表的定义和基本运算3.2 线性表的实现3.2.1 顺序存储结构3.2.2 链式存储结构3.2.3 两种基本实现方法的比较3.2.4 循环链表3.2.5 双向链表3.3 线性表的应用习题第4章 栈、队列和数组4.1 栈4.1.1 顺序栈4.1.2 链式栈4.1.3 顺序栈与链式栈的比较4.1.4 栈的应用4.2 队列4.2.1 队列的定义及基本运算4.2.2 顺序队列4.2.3 链式队列4.2.4 队列的应用4.3 数组4.3.1 数组的抽象数据类型4.3.2 数组的存储方式4.3.3 特殊数组4.3.4 数组的应用习题第5章 树形结构5.1 树5.1.1 树的基本概念5.1.2 树的抽象数据类型5.2 二叉树5.2.1 二叉树的定义及其主要特性5.2.2 二叉树的实现5.2.3 二叉树的遍历5.3 树、森林与二叉树的关系5.3.1 树的存储结构5.3.2 森林与二叉树的转换5.3.3 树和森林的遍历5.4 树形结构的应用5.4.1 等价类问题5.4.2 哈夫曼树和哈夫曼编码习题第6章 图6.1 图的基本概念6.1.1 图的基本概念6.1.2 图的抽象数据类型6.2 图的存储结构6.2.1 邻接矩阵6.2.2 邻接表6.2.3 逆邻接表6.2.4 邻接多重表6.2.5 图的实现6.3 图的遍历及求图的连通分量6.3.1 深度优先搜索6.3.2 广度优先搜索6.3.3 无向图的连通分量6.4 生成树和最小代价生成树6.4.1 生成树6.4.2 最小代价生成树6.5 最短路径6.5.1 从某个源点到其他各顶点的最短路径6.5.2 每一对顶点间的最短路径6.6 有向无环图及其应用6.6.1 有向无环图6.6.2 拓扑排序6.6.3 关键路径习题第7章 查找7.1 查找的基本概念7.2 顺序表的查找7.2.1 顺序查找7.2.2 折半查找7.2.3 索引顺贡序表的查找7.3 树表的查找7.3.1 二叉排序树7.3.2 平衡二叉树7.3.3 B-树7.4 P台希表及其查找7.4.1 什么是哈希7.4.2 哈希函数的构造方法7.4.3 处理冲突的几种方法7.4.4 哈希表的查找及其效率分析习题第8章 内部排序8.1 排序的一般概念8.2 插入排序8.2.1 直接插入排序8.2.2 折半插入排序8.2.3 希尔排序8.3 交换排序8.3.1 起泡排序8.3.2 快速排序8.4 选择排序8.4.1 简单选择排序8.4.2 堆排序8.5 归并排序8.5.1 两个有序序列的归并操作8.5.2 归并排序8.6 分配排序和基数排序8.7 有关内部排序算法的比较习题第9章 算法设计技术9.1 求解问题的基本思路9.2 分治技术9.2.1 分治策略的思想9.2.2 大整数乘法9.2.3 矩阵相乘的Strassen算法9.2.4 选择问题的分治算法9.3 贪心技术9.3.1 贪心算法的思想9.3.2 活动安排问题9.3.3 背包问题9.3.4 多机调度问题的近似算法9.3.5 单源最短路径问题的Dijkstra算法9.4 回溯与分枝限界技术9.4.1 两个适合回溯技术的问题9.4.2 八后问题9.4.3 0-1背包问题的回溯算法9.4.4 分枝限界算法9.5 动态规划技术9.5.1 Fibonacci数的计算9.5.2 矩阵连乘的顺序问题9.5.3 适合动态规划算法的两个条件综合练习题一综合练习题二综合练习题三综合练习题四综合练习题五综合模拟题一综合模拟题二参考文献
1.1.2 数据结构的基本概念和术语 为了对数据结构有一个全面正确的了解，在本节给出有关的基本概念和术语。 数据：能输入到计算机中并能被计算机处理的一切对象。这里必须强调指出，所谓数据绝不能仅仅理解为整数或实数这种狭义的“数”，必须做广义的理解。例如，一个用某种程序语言编写的源程序、一篇文稿、一张地图、一幅照片、一首歌曲等，都可以视为“数据”。今后随着计算机的发展，数据的范围还将不断扩大。 数据元素：数据的基本单位。由于数据的范围非常广泛，因此其基本单位也是可大可小的。大到可以是一个国家的地图、一 、一部电影；小到可以是一个字符，甚至是计算机中的一位。对于较大的单位，还可以由称为“数据项”的较小单位组成。如图书馆中一本书的目录卡片就可以包含书名、作者名、出版社名、书号和出版日期等数据项。 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。因为在实际应用中不会同时处理一切类型的数据，总是针对特定的问题处理一种或几种对象。例如，用计算机求素数这个问题只涉及“整数”这种数据对象。 数据结构：彼此具有一定关系的数据元素的集合。事实上，这些关系反映了客观世界事物之间的联系。由于客观事物存在着各种不同的联系形式，所以反映在数据关系上也就各不相同。一般来说，数据有四类基本结构：（1）集合。这个结构中数据元素之间除了。“同属于一个集合”这一关系外，没有其他关系。（2）线性结构。这个结构中数据元素之间存在着依次排列的先后次序关系。（3）树形结构。这个结构中数据元素之间存在着层次关系或分支关系。（4）图状结构或网状结构。这个结构中数据元素之间相互连接成网状。
无