实用数据结构与算法设计
2009-8
水利水电出版社
庄晋林，杨彬 主编
368
自从20世纪60年代末Donald E.Knuth开创了数据结构的最初体系以来，数据结构课程的内容已经变得日益完善。由权威机构IEEE-CS／ACM（TheComputer Society of the Institute for Electrical and Electronic Engineers／TheAssociation for Computing Machinety）推出的一系列课程体系中，都把数据结构作为其核心体系的组成部分。在“中国计算机科学与技术学科教程2002”（China Computing Curricula 2002，简称CCC2002）以及由教育部高等学校计算机科学与技术教学指导委员会2007年推出的“高等学校计算机科学与技术专业公共核心知识体系与课程”中，也都把数据结构作为计算机专业主要的核心课程。可见，数据结构在整个计算机专业课程体系中处于举足轻重的地位。该课程属于专业技术基础课，它与计算机软件、硬件和数学密切相关，是设计与实现操作系统、数据库系统、编译程序及其他系统程序和大型应用程序的重要基础。课程内容包括软件设计中常用的数据结构及其相应的存储结构和算法设计，涉及多种查找和排序技术，并对算法的性能进行分析和评价。 2009年硕士研究生入学考试将计算机科学与技术学科专业基础综合考试纳入全国统一命题的范围，并制订了计算机学科专业基础综合考试大纲。该、大纲涵盖数据结构、计算机组成原理、操作系统和计算机网络4个方面的内容，其中数据结构比例占30％，处于优先地位。本书参照该考试大纲“数据结构”科目的主要核心内容，同时兼顾应用型本科层次学生的实际需要，以培养创新精神和提高实践能力为目标，为改变读者在学习该课程时普遍感到抽象、繁琐、偏难的现状，在内容编排与撰写上，力求深入浅出、表述严谨、突出重点、通俗易懂，以使读者在掌握基本概念、基本知识的基础上，便于自学和巩固。 本书知识点全面，注重理论与实践的结合。除了全面阐述基本概念、基本原理和方法外，还列举了大量的应用实例，帮助读者理解各种数据结构及其算法的设计与实现。在此基础上，针对课程重点内容，给出了实验举例。
本书共分9章，主要内容包括绪论、基本线性结构、拓展线性结构、树结构、图结构、排序与查找、文件、实验与课程设计。 本书从实用的角度，在注重理论基础的前提下强调了实践的重要性。本书介绍了各种常用数据结构的存储以及相应的实现算法，并配有丰富的算法应用实例，这些算法结构化程度高、可读性好，并具有较强的实用性。同时《实用数据结构与算法教程》突出了基本技能的训练，使读者在掌握理论知识的基础上，进一步培养分析，思考和解决问题的能力。 本书适用于计算机科学与技术及相关专业应用型本科层次的学生，亦可作为相关专业教师或工程技术人员的参考书。
前言第1章 绪论 1.1 数据结构的发展史及地位 1.2 数据结构的定义 1.3 数据类型 1.4 算法及算法分析 1.5 程序设计技术简介 1.6 小结 习题1 参考文献第2章 基本线性结构 2.1 线性表 2.2 线性表的顺序存储结构与运算 2.3 线性表的链式存储结构与运算 2.4 栈 2.5 队列 2.6 串 2.7 应用实例 2.8 小结 习题2 参考文献第3章 拓展线性结构 3.1 数组的定义 3.2 数组基本运算的实现 3.3 矩阵的压缩存储与运算 3.4 广义表 3.5 小结 习题3 参考文献第4章 树结构 4.1 树的概念与运算 4.2 二叉树 4.3 二叉树遍历及线索二叉树 4.4 树和森林 4.5 应用实例 4.6 小结 习题4第5章 图结构 5.1 图的概念 5.2 图的存储结构 5.3 图的遍历 5.4 生成树 5.5 应用实例 5.6 小结 习题5 参考文献第6章 排序与查找 6.1 排序概述 6.2 插入排序 6.3 交换排序 6.4 选择排序 6.5 归并排序 6.6 基数排序 6.7 各种内部排序方法的比较与选择 6.8 查找概述 6.9 线性表的查找 6.10 树表上的查找 6.11 哈希表查找 6.12 应用实例 6.13 小结 习题6 参考文献第7章 文件 7.1 文件的概念 7.2 顺序文件 7.3 索引文件 7.4 索引顺序文件 7.5 散列文件 7.6 多关键字文件——多重表文件 7.7 小结 习题7 参考文献第8章 实验第9章 课程设计
第1章 绪论 在计算机广泛普及的今天，其应用几乎涵盖了人类社会的所有领域，而且在航空航天、军事、科学计算、信息检索、生产线控制等一些关键领域已经高度依赖计算机系统。由于受莫尔（Gordon Moore，英特尔公司创始人之一）定律的驱动，计算机硬件系统的性能及其可靠性迅速提高。在硬件系统日趋完善的基础上，如何极大限度地发挥计算机系统的效能，则取决于软件系统的功能及性能。因此，在计算机应用领域中，设计高效而可靠的算法已成为充分发挥计算机效能的基本前提。 虽然电子计算机经历了60余年的发展历史，但是主流计算机的系统结构始终无法摆脱冯?诺依曼体系的束缚，算法设计和数据存储仍然是计算机软件设计者必须面对的两大问题。计算机本质上是一个数据处理系统，而数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。数据结构这门课程研究的主要内容就是解决如何有效地存储数据以及设计正确的算法对其进行加工处理。 1.1 数据结构的发展史及地位 1.1.1 数据结构发展简史 1968年，美国斯坦福大学教授、图灵奖获得者Donald E.Knuth开始出版在计算机领域具有划时代意义的名著《计算机程序设计艺术》（The Art ofComputer Programming）。该丛书曾与牛顿的《自然哲学的数学原理》等书一起，被评为“世界历史上最伟大的十种科学著作”之一。Bill Gates曾经说过：“如果你认为你确实是—个好的程序员，读一读Knuth的《计算机程序设计艺术》吧，要是你真把它读通了，你就可以给我递简历了”。
