数据结构与算法

章节摘录

插图：1.1.4 算法及其特性算法是一个十分古老的研究课题。简单来说，它是为求解问题而给出的指令序列。一个算法可能有若干个输入，这些输入数据在算法开始时提供一组量。对算法的描述应该精确地说明这些输入的个数、类型以及它们应满足的初始条件，算法的每个步骤必须被明确描述，并且可行，不能有二义性。算法的一般性质包括以下几点：（1）通用性对于那些符合输入类型的任意输入数据，都能根据算法进行问题求解，并保证计算结果的正确性。（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的。（3）确定性算法每执行一步之后，对于它的下一步，应该有明确的指示。即，保证每一步之后都有关于下一步动作的指令，不能缺乏下一步指令或仅仅含有模糊不清的指令。（4）有穷性算法的执行必须在有限步内结束。在实际应用中，算法的表现形式千变万化，但许多算法的设计思想具有相似之处。归纳起来，常用的算法大致可分为以下几类：（1）穷举法基本思想是在一个可能存在可行状态（可行解）的状态全集中依次遍历所有的元素，并判断是否为可行状态。（2）贪心法基本思想是试图通过局部最优解得到全局最优解。（3）分治法基本思想是把一个规模较大的问题划分成相似的小问题，各个求解，再得到整个问题的解。（4）回溯法基本思想是一步一步向前试探，有多种选择时任意选择一种，只要可行就继续向前，一旦失败时就后退回来选择其他可能性。（5）动态规划法基本思想是把大问题分解为若干小问题，通过求解子问题来得到原问题的解。由于这些子问题相互包含，为了复用已计算的结果，常把计算的中间结果全部保存起来，自底向上多路径地求解计算原问题的解。（6）分支界限法基本思想是在表示问题空间的树上进行系统搜索时采用广度优先策略，同时利用最优解属性的上下界来控制搜索的分支。1.1.5 算法的执行效率及其度量解决同一个问题一般存在多种算法。要想从这些算法中选择一个适合的算法作为解决方案，则需对算法进行度量和评价的方法。评价一个算法优劣的重要依据是渐近分析实现.该算法的程序在计算机中执行时所需占用的机器资源的多少。两个重要指标为算法的空间代价（或称空间复杂度）和算法的时间代价（或称时间复杂度）。

前言

计算机科学已经深入应用到各个领域，不仅有效地解决了各种工程和科学计算中的数值计算问题，而且也有效地解决了许多文本处理、信息检索、数据库管理、图像识别、人工智能等非数值的数据处理问题。数据结构是计算机学科的一个重要分支研究领域，它是算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课的先行课。其他计算机科学领域及有关的应用软件都要使用到各种数据结构，例如：语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图，等等。美国IEEE和ACM的教学计划CC2001把“算法与数据结构”列入计算机以及信息技术相关学科专业的本科必修基础课程。在我国，“数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构更是必须透彻地掌握的重要基础，有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序，以满足错综复杂的实际需要。从字面上来看，数据结构就是指数据间的相互关系。具体到计算机环境，谈到任何一种结构时，都自然地联系着作用在这种类型的数据上的运算（即函数），为了在计算机上执行这些运算，有必要把这些数据以某种方式存储在计算机中。因此，可以认为，所谓数据结构，就是由某种逻辑关系组织起来的一批数据，按一定的存储方法被存储于计算机中，并在这些数据上定义了一个运算的集合。也就是说，数据结构具有3个方面：数据的逻辑结构、数据的存储结构和数据的运算。事实上，数据结构的三个侧面，以数据的逻辑结构和数据的运算定义更为重要。因为很多时候人们并不关心数据的存储结构和运算的具体实现。1983年Aho等人把数据结构的存储与实现细节剥离，定义了抽象数据类型（简称“ADT”）的概念。抽象数据类型是定义了一组运算的数学模型。这种抽象的数据类型可以在较高级的算法中直接引用，而不用考虑其实现细节。这就使得设计者可以在不同的设计阶段采用不同的抽象数据类型作为设计的基础，在适当的抽象层次上考虑程序的结构和算法，从而很好地支持了逻辑设计和物理实现的分离，支持封装和信息隐蔽。

书籍目录

第1章 概论1.1 知识点总结1.2 教材习题解答1.3 增补习题1.4 增补上机题第2章 线性表、栈和队列2.1 知识点总结2.2 教材习题解答2.3 增补习题2.4 增补上机题第3章 字符串3.1 知识点总结 3.2 教材习题解答3.3 教材上机题解答3.4 增补习题3.5 增补上机题第4章 二叉树4.1 知识点总结 4.2 教材习题解答4.3 教材上机题解答4.4 增补习题4.5 增补上机题第5章 树5.1 树的概念和表示法5.2 树的周游5.3 树的存储5.4 K叉树5.5 教材习题解答5.6 教材上机题解答5.7 增补习题5.8 增补上机题第6章 图6.1 知识点总结6.2 教材习题解答6.3 教材上机题解答6.4 增补习题6.5 增补上机题第7章 内排序7.1 内排序知识点总结7.1.1 内排序概念7.1.2 内排序的性质(重点)7.1.3 评价一个排序算法的好坏(重点)7.1.4 基于比较的排序问题的下限7.1.5 几种重要的排序算法(重点，难点)7.2 内排序性能总结7.2.1 简单排序算法的时间代价比较7.2.2 排序算法的时间代价和空间代价7.2.3 排序算法的实验性能比较7.3 内排序知识扩充7.3.1 索引排序和地址排序7.3.2 海豚算法7.4 教材习题解答7.5 教材上机题解答7.6 增补习题7.7 增补上机题第8章 文件管理和外排序8.1 知识点总结8.1.1 文件管理和外排序的基本概念8.1.2 磁盘访问时间估算8.1.3 置换选择排序8.1.4 二路外排序8.2 教材习题解答8.3 教材上机题解答8.4 增补习题8.5 增补上机题第9章 检索9.1 知识点总结9.1.1 检索概念9.1.2 检索算法的基本分类9.1.3 衡量检索算法的效率(重点)9.1.4 基于线性表的检索(重点)9.1.5 基于散列表的检索(重点、难点)9.2 教材习题解答9.3 教材上机题解答9.4 增补习题9.5 增补上机题第10章 索引技术10.1 知识点总结10.1.1 索引概念10.1.2 索引技术的简单分类10.1.3 线性索引(重点)10.1.4 动态索引(重点、难点)10.2 教材习题解答10.3 教材上机题解答10.4 增补习题10.5 增补上机题第11章 高级线性结构11.1 知识点总结11.1.1 基本概念11.1.2 多维数组11.1.3 广义表11.1.4 存储管理技术11.2 教材习题解答11.3 教材上机题解答11.4 增补习题11.5 增补上机题第12章 高级树结构12.1 知识点总结12.1.1 适用于存储、检索字符串组的树形结构12.1.2 二叉搜索树BsT的几个变体(重点)12.1.3 空间数据结构12.1.4 树形结构的两个应用12.2 扩充知识——红黑树12.2.1 红黑树的定义12.2.2 红黑树相关性质12.2.3 插入结点算法12.2.4 删除结点算法12.3 教材习题解答12.4 教材上机题解答12.5 增补习题12.6 增补上机题第13章 数据结构与算法实习指导13.1 基本数据结构的应用13.2 穷举法13.3 搜索和剪枝13.4 动态规划13.5 贪心法13.6 图算法13.7 实习范例13.8 增补习题第14章 北京大学计算机系“数据结构与算法”试题选14.1 北京大学信息学院2004年“数据结构与算法”试题14.1.1 2004年期中考试试题14.1.2 2004年期末考试试题14.2 北京大学信息学院2004年“数据结构与算法”试题参考答案14.2.1 2004年期中考试试题参考答案14.2.2 2004年期末考试试题参考答案14.3 北京大学硕士研究生入学考试“数据结构”试题14.3.1 1999年试题14.3.2 2000年试题14.3.3 2001年试题14.3.4 2002年试题14.3.5 2003年试题14.3.6 2004年试题14.3.7 2005年试题14.4 北京大学硕士研究生入学考试“数据结构”试题参考答案14.4.1 1999年试题参考答案14.4.2 2000年试题参考答案14.4.3 2001年试题参考答案14.4.4 2002年试题参考答案14.4.5 2003年试题参考答案14.4.6 2004年试题参考答案14.4.7 2005年试题参考答案参考文献

编辑推荐

《数据结构与算法:学习指导与习题解析》为普通高等教育“十五”国家级规划教材配套参考书。全书共14章，前13章从题意分析、典型错误、数据结构、算法代码、算法分析等多个角度给出了主教材中212道习题和53道上机题的综合分析和参考解答，并新收入了覆盖各章知识点的170多道习题和40多道上机题供读者练习；第14章以1999～2005年北京大学计算机系研究生入学考试数据结构试题及解答为主，辅助读者自学与自测。 《数据结构与算法:学习指导与习题解析》可作为普通高等院校计算机及相关专业数据结构与算法课程的教学参考书，也可供参加计算机硕士、计算机博士、软件工程硕士入学考试的考生参考使用，还可供计算机应用技术人员参考使用。

作者简介

《数据结构与算法:学习指导与习题解析》配合我社出版的面向21世纪课程教材《数据结构与算法》的使用，为读者学习数据结构与算法课程给予指导。全书共14章，其中，第1～12章总结了本课程重要的内容知识点、学习重点和难点，某些章节还对相关知识点进行了扩展；前13章从题意分析、典型错误、数据结构、算法代码、算法分析等多个角度给出了主教材中212道习题和53道上机题的综合分析和参考解答，并新收入了覆盖各章知识点的170多道习题和40多道上机题供读者练习；第13章内容基本上选自ACM国际大学生程序设计竞赛题，强化算法实现和上机实习能力；第14章以1999～2005年北京大学计算机系研究生入学考试数据结构试题及解答为主，辅助读者自学与自测。教据结构与算法课程的学习目的是，根据应用问题的性质选择合理的数据结构，在合理的时间、空间复杂度限制下编程加以解决。认真地完成习题和上机题，是学好本课程，提高程序设计质量的重要环节。

《数据结构与算法:学习指导与习题解析》可作为普通高等院校计算机及相关专业数据结构与算法课程的教学参考书，也可供参加计算机硕士、计算机博士、软件工程硕士入学考试的考生参考使用，还可供计算机应用技术人员参考使用。

---

 数据结构与算法下载

---