数据结构简明教程

出版时间：2009-9  出版社：北京航空航天大学出版社  作者：徐翠霞 编  页数：280  

前言

　　在计算机及其应用的各个领域中，都会用到各种各样的数据结构，学会分析、研究计算机加工对象的特性，选择合适的数据结构和存储表示，以及编制相应的实现算法，是计算机工作者不可缺少的技能。因此，“数据结构”是高等院校计算机专业教学中的一门重要的专业基础课。在我国当前的计算机专业教学计划中，它是核心课程之一。　　目前，市面上大多数有关“数据结构”的教材都采用传统编排模式，先是总体介绍，然后是基础知识，再是算法体系等。这种方法以知识点为主线，拘泥于语法细节，而忽略了程序本身的重要性。　　基于案例教学过程的实践和思考，更是为了培养读者的编程能力，编者提出了这样一个问题：能不能打破传统教材和讲授模式，先以案例入手，提出解决问题的方法和思路，分析问题需要的知识点，然后根据需要讲解知识点，再解决提出的问题，最后举一反三，并以应用实例加以提升和巩固知识点，实现综合应用的目的。适合这样讲授的教材或参考书目前市面上很少，编者经过不断探讨并通过多年的案例教学经验积累，最终形成了本书。　　案例教学是计算机语言教学最有效的方法之一。好的案例对学生理解知识、掌握如何应用知识十分重要。本书以指导案例教学为目的，围绕教学内容组织案例，对学生的知识和能力训练具有很强的针对性，主要特色如下：　　（1）以知识线索设计案例，分解知识点，有明确的目的和要求，针对性强。　　（2）选择有代表性的案例，突出重点知识的掌握和应用。　　（3）将技术指导、代码与分析、应用提高、相关知识有机结合。　　（4）注意新方法、新技术的应用。　　（5）处理好具体实例与思想方法、局部知识应用与综合应用的关系。　　（6）强调实用性，培养应用能力。　　本书中每一个案例的结构模式为“案例说明一案例目的一技术要点一代码及分析一相关知识及注意事项”。每一章均包含多个案例，并配有相应的习题。通过强化案例和实训教学，加深学生对理论知识的理解。　　本书在内容的组织上，本着由浅入深、循序渐进的原则，注重基本知识和基本概念的介绍，结合案例重点介绍实用性较强的内容，对难度过大的内容只作少量介绍，使学生有的放矢，掌握所学内容。　　本书注重培养学生的实际应用技能和综合解决问题的能力，使学生能熟练掌握和运用理论知识解决实际问题，达到学以致用的目的，能真正地为培养新世纪的适用型人才出一份力。

内容概要

本书系统地介绍了各种常用的数据结构，内容丰富，概念讲解清楚，叙述严谨流畅，逻辑性强。书中配备了大量的案例，每个案例都经过精心的考虑，既能帮助读者理解知识，又具有启发性。本书对给出的每一种算法，均先描述了它的基本思路和要点，使得算法清晰易读，便于学生理解和掌握。    本书共分9章，内容包括绪论，线性表，栈和队列，串、多维数组和广义表，树和二叉树，图，查找，排序和综合实训。    本书可作为全国高等学校计算机类专业或信息类专业的教材，也可供广大从事计算机工程与应用的科技工作者参考。

书籍目录

第1章 绪论　1.1 基本概念和术语　　案例1.1数据模型的确定　1.2 算法和算法评价　　案例1.2矩阵乘法算法的时间复杂度分析　本章小结　习题1第2章 线性表　2.1 线性表的顺序存储　　案例2.1 模拟集合的基本运算　2.2 线性表的链式存储　　案例2.2 一元多项式的加法运算　　案例2.3 采用循环链表模拟约瑟夫（Josephus）问题　本章小结　习题2第3章 栈和队列　3.1 栈　　案例3.1 数制转换（十进制数转换为二、八、十六进制数）　　案例3.2 后缀表达式的求值　3.2 栈与递归　　案例3.3 迷宫问题　3.3 队列　　案例3.4 农夫过河问题　本章小结　习题3第4章 串、多维数组和广义表　4.1 串　　案例4.1 模拟“天书密码”的生成和破解　　案例4.2 无回溯的模式匹配 　4.2 多维数组和广义表　　案例4.3 稀疏矩阵的转置　本章小结　习题4第5章 树和二叉树　5.1 树和二叉树的存储表示　　案例5.1 完全二叉树的基本运算　5.2 树和二叉树的遍历　　案例5.2 表达式树的构造及输出　5.3 线索二叉树　　案例5.3 中序线索二叉树及其遍历　5.4 哈夫曼树及其应用　　案例5.4 哈夫曼编码器　本章小结　习题5第6章 图　6.1 图的存储和遍历　　案例6.1 图的连通性判定　6.2 最小生成树和最短路径　　案例6.2 局域网络布线问题　6.3 有向无环图及其应用　　案例6.3 教学计划的编制　本章小结　习题6第7章 查找　7.1 线性表的查找　　案例7.1 学生信息表的分块查找　7.2 树表的查找　　案例7.2 借助二叉排序树实现单词统计　7.3 散列表的查找　　案例7.3 散列表的双散列探测查找　本章小结　习题7第8章 排序附录 常用数据结构的类型定义参考文献

章节摘录

　　【技术要点】　　（1）图书馆的书目检索系统自动化问题　　在图书馆内有各种名目的卡片：有按书名编排的，有按作者编排的，还有按分类编排的，等等。若实现自动检索，则计算机处理的对象便是这些卡片上的书目信息。　　列在一张卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等若干项组成，每一本书都有唯一的一个登录号，但不同的书目之间可能有相同的书名、相同的作者名或者相同的分类号。　　在书目自动检索系统中，可以建立一张按登录号顺序排列的书目文件和3张分别按书名、作者名和分类号顺序排列的索引表。　　由这4张表构成的文件便是书目自动检索的数据结构，可谓线性结构。　　（2）计算机和人对弈问题　　棋盘为3×3的方格，当一方的3个棋子占同一行、同一列或同一对角线时便为胜方。　　在对弈问题中，计算机操作的对象是对奕过程中可能出现的棋盘状态——格局。从一个棋盘格局可以派生出几个格局，因此，若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“树”。“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树枝到某个叶子的过程。　　树是该问题的数据模型，它也是一种数据结构。　　（3）多又路口交通灯的管理问题　　在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。假设多岔路口既有单行道也有双行道。在路口有若干条可行的通路，其中有的可以同时通行，而有的不能同时通行。那么，在路口应如何设置交通灯进行车辆的管理呢？　　通常，这类道路交通问题的数据模型是一种称为“图”的数据结构。例如，在此例的问题中，可用图中一个顶点表示一条通路，而通路之间互相矛盾的关系以两个顶点之间的连线表示。　　【相关知识及注意事项】　　1.数据　数据（Data）是客观事物的数字、字符以及所有能输入计算机中并被计算机程序处理的符号的集合，它是计算机程序加工的“原料”。常见的数据可分为数值数据和非数值数据。数值数据包括整数、实数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像和语音等。

编辑推荐

　　本书以指导案例教学为目的，围绕教学内容组织案例，对学生的知识和能力训练具有很强的针对性。