算法与数据结构

章节摘录

版权页：   插图：   1.1.2 程序的设计与实现 一般来说，一个问题的解决可以有许多办法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的办法，比较快而且准确地计算出需要的结果。 对于前面抽象出来的着色问题，下面介绍一种简单的求解方法，目的在于使读者从中体会从问题抽象的模型到实现模型的设计过程。 选择算法 穷举珐 求一般着色问题的最优解，可以采用穷举法，具体做法是：从分为1，2，3……组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。 具体来讲，假设求解的图中有n个结点，首先考察如果放在一个组里（这时显然只有一种着色方式）是否可行，即考察组里的结点是否有线相连。如果没有，最优解已经找到；否则考察如果放在两个组里是否可行，这时需要逐个穷举出所有可能的分成两个组的方案，这个数可能很大。例如，两个组按1：n—1分配，就有C1n=n种方案，按2：n—2分配，就有C2n=n（n—1）／2种方案等。当考察了所有放在两个组里可能的方案后，如果都不行的话，接着考虑分为三组、四组的各种组合。以此类推，最多到分成n组，最终总能成功。 但是，对于规模大的问题，由于求解时间会随着实际问题规模的增长而呈指数级上升，这类穷举法可能使计算机无法承受（有耐心的读者，不妨对上述信号灯问题亲自动手模拟一下这个穷举法的求解过程）。 当然，对于一般（任意规模）的着色问题，存在一些比穷举法更快的求最优解的算法，因为超出本课教学范围，不在此展开讨论。实际上，对于一个具体的着色问题（例如本节开头提出的信号灯问题），并没有必要一定找到其最优解。下面给出的是一个比穷举法快得多的，但是通常能够求出次优解的算法。 贪心法 求着色问题的次优解，一种简单的方法称为贪心法：先用一种颜色给尽可能多的结点上色，只要这些结点之间没有边相连；然后再用另一种颜色在未着色结点中给尽可能多的结点上色，如此反复，直到所有结点都着色为止。

内容概要

张乃孝，北京大学教授、博士生导师，曾任北京大学计算机系数据库教研室主任、理论教研室主任和北京大学数学学院信怠系副主任；全国计算机学会“数据组织与结构”学组副组长和“软件理论”学组副组长。长期从事“新语言”和“程序设计方法学”的研究，主持和参加了十多个国家级科研项目，提出“面向语言的方法学”。长期从事基础课教学，发表论文数十篇，出版教材十余本。曾获“第一次全国科学大会奖”、“全国优秀教材奖”、“北京市高等教育精品教材”奖和“普通高等教育精品教材”奖，并多次获得北京大学教学优秀奖和科研成果奖。个人简历收入世界名人录“Who Is Who in theWorld”等。

书籍目录

第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.1Josephus问题 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章栈与队列 4.1栈及其抽象数据类型 4.1.1基本概念 4.1.2抽象数据类型 4.2栈的实现 4.2.1顺序表示 4.2.2链接表示 4.3栈的应用 4.3.1栈与递归 4.3.2迷宫问题 4.3.3表达式计算 4.4队列及其抽象数据类型 4.4.1基本概念 4.4.2抽象数据类型 4.5队列的实现 4.5.1顺序表示 4.5.2链接表示 4.6队列的应用 小结 习题 第5章二叉树与树 5.1二叉树及其抽象数据类型 5.1.1基本概念 5.1.2主要性质 5.1.3抽象数据类型 5.2二叉树的周游 5.2.1什么是周游 5.2.2周游的分类 5.2.3一个例子 5.2.4周游的抽象算法 5.3二叉树的实现 5.3.1顺序表示 5.3.2链接表示 5.3.3线索二叉树 5.4二叉树的应用 5.4.1堆与优先队列 5.4.2哈夫曼树及其应用 5.5树及其抽象数据类型 5.5.1基本概念 5.5.2抽象数据类型 5.5.3树的周游 5.6树的实现 5.6.1父指针表示法 5.6.2子表表示法 5.6.3长子一兄弟表示法 5.6.4树的其他表示法 5.7树林 5.7.1树林的周游 5.7.2树林的存储表示 5.7.3树林与二叉树的转换 小结 习题 第6章集合与字典 6.1集合及其抽象数据类型 6.1.1基本概念 6.1.2主要运算 6.1.3抽象数据类型 6.2集合的实现 6.2.1集合的位向量表示 6.2.2集合的单链表表示 6.3字典及其抽象数据类型 6.3.1基本概念 6.3.2抽象数据类型 6.4字典的顺序表示 6.4.1存储结构 6.4.2算法的实现 6.4.3 有序顺序表与二分法检索 6.5字典的散列表示 6.5.1基本概念 6.5.2散列函数 6.5.3碰撞的处理 6.5.4散列文件 小结 习题 第7章高级字典结构 7.1字典与索引 7.1.1字典的索引 7.1.2索引的抽象 7.2字符树 7.2.1双链树表示 7.2.2多链表示 7.3二叉排序树 7.3.1二叉排序树 7.3.2二叉排序树的检索 7.3.3二叉排序树的插入和构造 7.3.4二叉排序树的删除 7.4最佳二叉排序树 7.4.1基本概念 7.4.2等概率的检索 7.4.3不等概的情况 7.5平衡二叉排序树 7.5.1基本概念 7.5.2调整平衡的模式 7.5.3实现 7.6索引文件 7.6.1多分树 7.6.2B树 7.6.3B+树 小结 习题 第8章排序 8.1基本概念 8.2插入排序 8.2.1直接插入排序 8.2.2二分法插入排序 8.2.3表插入排序 8.2.4Shell排序 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.6.1内排序 8.6.2外排序 小结 习题 第9章图 9.1基本概念及其抽象数据类型 9.1.1基本概念 9.1.2抽象数据类型 9.2图的周游 9.2.1深度优先周游 9.2.2广度优先周游 9.3存储表示 9.3.1邻接矩阵表示法 9.3.2邻接表表示法 9.3.3两种表示的比较 9.4最小生成树 9.4.I最小生成树及其性质 9.4.2最小生成树的构造 9.5最短路径 9.5.1Dijkstra算法 9.5.2Floyd算法 9.6拓扑排序 9.6.1AOV网 9.6.2拓扑排序 9.7关键路径 9.7.1AOE网 9.7.2关键路径 小结 习题 第10章算法分析与设计 10.1算法分析技术 10.1.1空间代价分析 10.1.2时间代价分析 10.2算法设计技术 10.2.1分治法 10.2.2贪心法 10.2.3动态规划法 10.2.4回溯法 10.2.5分枝界限法与0／1背包问题 小结 习题 索引 算法清单 参考文献

编辑推荐

《面向21世纪课程教材:算法与数据结构:C语言描述(第3版)》编辑推荐：许多知识模块具有一定的独立性和相关性，因此不同专业和不同水平的读者可以根据需要组合使用。《面向21世纪课程教材:算法与数据结构:C语言描述(第3版)》既可以作为计算机专业本科“数据结构”课程教材，也可以作为理工科有关专业本科和计算机专业专科相关课程的教材或考研参考书。

作者简介

《面向21世纪课程教材:算法与数据结构:C语言描述(第3版)》以数据结构为主线、算法为辅线组织教学内容。《面向21世纪课程教材:算法与数据结构:C语言描述(第3版)》体系完整、概念清楚、内容充实、取材适当，采用“数据结构作为抽象数据类型的物理实现”观点，既提高了抽象数据类型在本课程教学中的地位和作用，又突出了自身的教学重点。《面向21世纪课程教材:算法与数据结构:C语言描述(第3版)》在讲解知识的同时，重视能力的培养，以提高学生运用知识解决实际问题的能力。新版对第2版教材中许多算法进行了改进，力求为读者提供一套具有良好C语言风格、更便于教学的程序代码，以期帮助学生从中体会到算法的魅力和C语言编程的艺术，提高学生的学习兴趣。同时，新版内容也适当地提高了知识的深度和广度，完全覆盖了最新考研大纲的内容要求。

---

 算法与数据结构下载

---