数据结构基础教程
2005-1
清华大学出版社/北京交通大学出版社
文益民等郭杰李健
215
1997年5月，一台名为“深蓝”的超级计算机将棋盘上的一个兵走到C4位置时，人类有史以来最伟大的国际象棋名家卡斯帕罗夫不得不沮丧地服输，上世纪末的一场人机大战终于以计算机的微弱优势取胜。2003年4月14日人类基因组计划宣告完成，后基因组时代已经到来，各种生物学成果在计算中不断出现。这些成果使得人们再一次认识到计算的重要性。如今，计算技术已广泛地应用到各个领域，后因特网时代已经到来，以信息化带动工业化已成为时代的主题。计算机程序设计是计算技术的重要内容，而数据结构是计算机程序设计的重要理论基础，它不仅是计算机学科的核心课程，而且已成为其他专业的热门选修课。数据结构课程的教学目标是学会分析需要计算机处理的数据对象的特性，以选择适当的数据结构和存储结构，从而选择相应的算法；初步掌握算法性能分析的方法。通过本课程的学习，使学生获得更进一步的程序设计技能训练，提高编程能力。 长久以来，由于数据结构课程自身的抽象性和严密性，以及数据结构开设的时间通常在刚入大学的第二学期，教师大都感觉数据结构课程难教，学生普遍反映数据结构课程难学，学生很难独立完成算法的实现。基于上述问题，我们在编写本教材时充分考虑了学生的知识结构和教师的教学方法。本教材的编写宗旨是，既注重原理又注重实践，既注重抽象思维又注重形象思维，既方便自学又方便教学。本书的编写具有以下特色。 1.首次尝试在计算机专业的核心基础课程中增加计算机科学知识，使学生在学习本教材的过程中，不但能学到专业知识，还能了解计算机科学发展历史的相关知识和数据结构课程与其他课程的联系。对提高学生学习本课程的兴趣，拓宽学生的知识面大有益处。 2.在教材中使用“A思考”标志，提出问题拓展学生思维。思考不同于习题，习题的作用代替不了思考。因为习题在每个章节之后，一般要等讲完一个章节才会遇到，因此习题对于课堂教学是滞后的。采用提示思考的方式，可以在教学中恰到好处地启发学生的思维。教材使用“A思考”标志通常有三种情况：一种是提醒学生需要注意的内容，一种是启发学生基于当前知识基础进一步思考的内容，第三种是提示本教材没有讲授的内容，以引导学有余力的学生拓展自身的知识面。 3.以学生为主体设计数据结构课程的实践内容。数据结构课程是计算机专业的一门重要的基础课程，其性质是实践性的。如何引导学生利用所学概念和算法进行实践是这门课程成败的关键，为此我们采取了两个措施：一是注重概念和算法的应用背景，对每种数据结构都有应用实例，有代码实现：二是在基本运算的实现代码中留有要求学生自己实现代码的部分。这就要求学生不但要读懂已经实现的部分代码，还要自己设计代码，最后才能得到一个完整实现的系统。这有利于提高学生对数据结构概念和算法的理解，真正提高学生的编程能力。每章后的上机实习就由这两部分内容组成，本书中提供的实现代码均在VC6.0中编译通过。 本书介绍了各种最常用的数据结构，阐述了各种数据结构内涵的逻辑关系，讨论了它们在计算机中的存储表示，.以及基于这些数据结构的运算和实际的执行算法，并对算法的效率进行了简要的分析和讨论。
《数据结构基础教程》系统地介绍了各种常用的数据结构及排序、查找的各种算法，阐述了各种数据结构的逻辑结构、存储结构及其基本运算。各数据结构类型和基本运算，首先用类C代码描述，然后用可编译运行的C语言代码实现，并给出了详细的注释。全书既注重原理又强调实践，配有大量的图表和习题，概念讲解清楚、逻辑性强、可读性好。《数据结构基础教程》的特点在于，首次尝试在基础课程中介绍计算机科学发展史知识，采用脚注的形式使学生了解计算机科学史知识和数据结构课程与其他课程之间的关系；附有大量以“思考”形式出现的问题，以便在恰当的时机引导学生思考，启发思维；以学生为主体精心设计了数据结构课程的实践教学内容。
第1章 绪论1.1 数据结构基本概念1.1.1 数据结构实例1.1.2 数据结构概念1.2 算法分析基本概念1.2.1 算法1.2.2 算法效率分析1.2.3 算法效率评价习题1第2章 线性表2.1 概念和运算2.1.1 线性表概念2.1.2 线性表基本运算2.2 顺序存储结构2.2.1 顺序表2.2.2 顺序表基本运算2.3 链式存储结构2.3.1 线性链表2.3.2 线性链表基本运算2.4 线性表应用2.5 基本运算实现2.5.1 顺序表基本运算实现2.5.2 链表基本运算实现上机实习线性表习题2第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 表达式求值3.3.3 栈和递归3.4 栈基本运算实现3.4.1 顺序栈基本运算实现3.4.2 链栈基本运算实现上机实习栈习题3第4章 队列4.1 概念和基本运算4.1.1 队列概念4.1.2 队列基本运算4.2 顺序存储结构和运算4.3 循环队列4.4 链队列4.5 队列应用4.6 队列基本运算实现4.6.1 循环队列运算实现4.6.2 链队列运算实现上机实习队列习题4第5章 线性结构推广5.1 串5.1.1 定义5.1.2 基本运算5.1.3 定长顺序存储5.1.4 模式匹配5.1.5 链式存储结构5.2 数组5.2.1 定义和存储5.2.2 矩阵压缩存储5.3 广义表5.3.1 定义5.3.2 存储5.4 串的基本运算实现上机实习串习题5第6章 树6.1 树的概念和基本运算6.1.1 定义6.1.2 基本术语6.1.3 基本运算6.2 树的存储6.3 二叉树的概念和性质6.3.1 概念和基本运算6.3.2 性质6.3.3 存储6.4 二叉树遍历6.5 线索二叉树6.6 树和二叉树6.6.1 树与二叉树的转换6.6.2 二叉树与森林的转换6.7 哈夫曼树及其应用6.8 二叉树基本运算6.9 二叉树基本运算实现上机实习二叉树习题6第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.4 最小生成树7.4.1 Prim算法7.4.2 Kruskal算法7.5 单源点最短路径7.6 图的基本运算实现上机实习图习题7第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.4.3 堆排序8.5 归并排序8.6 各种排序方法的综合比较8.7 外部排序8.8 各类排序算法的综合实现上机实习排序习题8第9章 查找9.1 基本概念9.2 静态查找表9.2.1 顺序查找法9.2.2 折半查找法9.2.3 分块查找法9.3 动态查找表9.4 哈希表9.4.1 基本概念9.4.2 哈希函数构造方法9.4.3 冲突处理方法9.4.4 哈希表查找9.5 查找表实现上机实习查找表习题9参考文献
综上所述，非数值计算问题的数学模型不再是数学方程，而是要研究诸如例1.1 、例1.2 和例1.3 所描述的数据之间的这些关系，以及通过数据之间的这些关系可以方便地进行何种运算。因此，简单地说数据结构是一门研究数据之间的关系及其运算的学科。 数据结构作为一门独立的学科始于1968年，但在此之前有关内容已散见于编译原理和操作系统的教材之中。1968年，美国的图灵奖”获得者克努特（D.E.Knuth）教授开创了数据结构的最初体系，他的著作《计算机程序设计艺术》第1卷《基本算法》是第一本比较系统地阐述数据的逻辑结构和存储结构及其操作的著作。20世纪60年代末到70年代，出现了大型程序，软件也相对独立，结构程序设计即成为程序设计的主要内容。人们越来越重视数据结构，著名的瑞士计算机科学家沃斯（N.Wirth）教授指出，算法斗数据结构：程序。70年代中期到80年代初，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，例如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越为人们所重视。 从我国计算机教学现状来看，数据结构不仅是计算机专业教学计划中的核心课程之一，而且已逐步成为非计算机专业的主要选修课程之一。数据结构又是一门介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中，数据结构不仅是一般非数值计算程序设计的基础，而且是设计和实现汇编语言、编译程序、操作系统、数据库系统，以及其他系统程序和大型应用程序的重要基础。打好数据结构课程的扎实基础，对于学习计算机专业的其他课程，例如操作系统、编译原理、数据库管理系统、软件工程和人工智能等都是十分有益的。 1.1 2数据结构概念 1.数据 数据是信息的载体，是对客观事物的符号表示。通俗地说，凡是能被计算机识别、存取和加工处理的符号、.字符、图形、图像、声音、视频信号、程序等一切信息都可以称为数据。数据可以是数值数据，也可以是非数值数据。数值数据包括整数、实数、浮点数、复数等，主要用于科学计算和商务处理等；非数值数据包括文字、符号、图形、图像、动画、语音、视频信号等。随着多媒体技术的飞速发展，计算机中处理的非数值数据越来越多。 2.数据元素 数据元素是对现实世界中某独立个体的数据描述，是数据的基本单位。在计算机中，数据元素通常作为一个整体来处理。一个数据元素可以由若干个数据项组成，在C程序设计中一个数据元素可以由一个stmct表示。数据项是具有独立意义的最小数据单位，是对数据元素属性的描述。 ……
《数据结构基础教程》可作为高等学院校非计算机专业教材或高孙、高专院校计算机专业教材，也可作为成人教育(面授或函授)的教材，还可为参加全国计算机软件水平程序员等级考试提供参考，亦可供广大从事计算机应用的科技人员参考。
