数据结构与算法

出版时间：2010-1  出版社：机械工业出版社  作者：吴跃 编  页数：244  

前言

　　近20年里，计算机学科有了很大的发展，人们普遍认为，“计算机科学”这个名字已经难以涵盖该学科的内容，因此，改称其为计算学科（Computing Discipline）。在我国本科教育中，1996年以前曾经有计算机软件专业和计算机及应用专业，之后被合并为计算机科学与技术专业。2004年以来，教育部计算机科学与技术专业教学指导分委员会根据我国计算机专业教育和计算学科的现状，为更好地满足社会对计算机专业人才的需求，发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称《规范》），提出在计算机科学与技术专业名称之下，构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类，在于鼓励办学单位根据自己的情况设定不同的培养方案，以培养更具针对性和特色的计算机专业人才。　　为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：　　（1）体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。　　（2）围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。　　（3）教材内容的组织科学、合理。体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。　　（4）教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。　　（5）开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。　　我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。

内容概要

《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。《数据结构与算法》注重理论与实践相结合，内容深入浅出，可以作为高等院校计算机学科工程硕士及相关层次的教材或参考书，同时对计算机科技工作者也有参考价值。

作者简介

　　吴跃，四川省学术和技术带头人、国务院政府特殊津贴专家、教育部计算机科学与技术专业教学指导委员会委员、四川省教学名师、四川省高等学校省级教学团队计算机专业核心课程教学团队带头人，从事数据结构与算法课程的教学工作20余年，主持了国家863教育部博士点基金、国防重点和省科技攻关等十余项科研项目，发表学术论文（70余篇，获省部级科研奖5项、国家级教学成果奖2项、已编著出版《计算机操作系统》教材一部。

书籍目录

出版者的话序言前言教学建议第1章 绪论1.1 计算机问题求解过程1.2 迷宫问题1.3 数据结构1.3.1 数据结构研究的内容1.3.2 数据结构概念1.4 算法1.4.1 算法概念及特性1.4.2 算法描述1.4.3 算法分析1.5 本章小结1.6 习题第2章 线性表2.1 线性表2.1.1 线性表的定义2.1.2 线性表的顺序存储2.1.3 线性表的链式存储2.1.4 链表的各种变形2.1.5 线性表的应用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.4 数组2.4.1 数组的定义2.4.2 数组的表示和实现2.4.3 数组的应用2.5 本章小结2.6 习题第3章 树3.1 二叉树3.1.1 二叉树的基本概念和性质3.1.2 二叉树的存储结构3.1.3 二叉树的遍历3.2 二叉树的变形3.2.1 线索二叉树3.2.2 二叉排序树3.2.3 平衡二叉树3.2.4 赫夫曼树及赫夫曼编码3.3 树和森林3.3.1 树和森林的定义3.3.2 树和森林的存储结构3.3.3 树和森林的基本操作3.4 树的变形3.4.1 四叉树3.4.2 B树3.4.3 2-3树3.5 树的应用3.5.1 算术表达式3.5.2 堆排序3.5.3 决策分析3.6 本章小结3.7 习题第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.4 图的应用4.4.1 最小生成树4.4.2 拓扑排序4.4.3 关键路径4.4.4 最短路径4.5.1 一义表4.5.1 一义表的定义4.5.2 一义表的存储结构4.5.3 义表的遍历4.5.4 广义表的运算4.6 本章小结4.7 习题第5章 算法设计策略5.1 算法分析技术5.2 直接法5.2.1 穷举法5.2.2 递推法5.2.3 迭代法5.3 分治法5.3.1 分治法的基本思想5.3.2 斯特拉森矩阵乘法5.4 贪心法5.4.1 贪心法的基本思想5.4.2 背包问题5.5 动态规划法5.5.1 动态规划法的基本思想5.5.2 矩阵连乘问题5.6 回溯法5.6.1 回溯法的基本思想5.6.2 回溯法的形式化描述5.6.3 k皇后问题5.7 分支限界法5.7.1 分支限界法的基本思想5.7.2 货郎担问题5.8 本章小结5.9 习题第6章 查找6.1 顺序表的查找6.1.1 倾序查找6.1.2 分查找6.2 索引表的查找6.2.1 索引表的基本概念6.2.2 索引表的顺序查找6.2.3 索引表的二分查找6.2.4 索引表的树组织查找6.3 散列表的查找6.3.1 基本概念6.3.2 散列函数6.3.3 突处理6.3.4 散列查找与性能分析6.4 本章小结6.5 习题第7章 排序7.1 排序的基本概念7.2 插入排序7.2.1 直接插入排序7.2.2 分插入排序7.2.3 希尔排序7.3 交换排序7.3.1 冒泡排序7.3.2 快速排序7.4 选择排序7.4.1 简单选择排序7.4.2 树形选择排序7.52 路归并排序7.6 基数排序7.6.1 多关键字排序7.6.2 链式基数排序7.7 各排序方法的比较7.8 本章小结7.9 题参考文献

章节摘录

　　性表的存储方式除了常用的顺序存储外，链式存储也是一种常见的方式。本小节将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点的单链表、循环链表等。　　线性表的链式存储是指用一组任意的存储单元（可以连续也可以不连续）存储线性表中　的数据元素。数据元素在存储空间表示时通常称为结点。　　前面讨论的顺序表用物理位置上的相邻关系来表示结点之间的逻辑关系，这使得可以随机存取表中任一指定位置的数据元素，但同时导致插入和删除运算进行大量的数据元素移动。采用线性表的链式存储结构能解决这个问题，基于它的插入和删除运算不需要移动数据元素，从而使得时间复杂度从顺序表的0（2）变为0（1）。　　在链式存储结构中，为了反映数据元素之间的逻辑关系，每个结点不仅要存放数据元素本身，还需要一些额外的存储空间来存放和它有关系的数据元素的地址，即需要存放指向其他元素的指针（或链）。称指向第一个结点的指针为头指针，一个链表由头指针唯一确定。一旦知道头指针，就可以沿着指针访问其他数据元素。　　可以根据不同的标准对链表进行分类。例如，根据结点中指针数量的多少，可以将链表分为单链表、双向链表和多重链表；根据是否在链表的第一个元素前附加额外的结点，可以将链表分为带头结点的链表和不带头结点的链表；根据头指针是指向第一个结点还是最后一个结点，可以将链表分为带头指针的链表和带尾指针的链表等等。　　在链式存储结构中，由于线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致，因此在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式称为顺序存取方式。因此，链式存储结构失去了随机存取数据元素的功能，但换来了操作的方便性：进行插入和删除时无需移动数据元素。　　……

编辑推荐

在计算机科学技术的各个领域，选择合适的数据结构都是一个重要问题。通过数据结构与算法的学习，读者能进一步提高软件设计与程序编写的能力.提高应用计算机技术解决宴际问题的能力。《数据结构与算法》是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的.涵盖了“”数据结构“”公共核心课程的知识单元。《数据结构与算法》以基本数据结构和算法设计策略为知识单元.系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法书中分为数据结构和算法两大部分其中，数据结构部分（第1～4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表表示一对多关系的树以及表示多对多关系的图和广义表：算法部分（第5～7章）以查找和排序算法作为常用算法.所以该部分由算法设计策略、查找和排序组成。