数据结构

出版时间：2005-8  出版社：包振宇、孙干、 陈勇 中国铁道出版社 (2005-08出版)  

前言

“数据结构”是计算机程序设计的重要基础，也是计算机科学与技术等电子信息类相关专业的一门重要基础课程。它对程序设计思想的建立和提升有着重要的作用，既为后续的计算机课程奠定了一个较为扎实的基础，又可提高学生分析问题和解决问题的能力。本书作为2005年版《数据结构》的第二版，保持了前一版的基本框架，概念清楚、论述充分、面向应用，进一步完善了算法与数据结构体系的内容，每章都增加了“典型例题”一节，并对实验部分进行调整和补充。教材主要面向高职高专院校计算机科学与技术等电子信息类专业的学生。教材内容以“实践应用”为主体，理论以“够用”为尺度。全书共分理论知识和实验指导两个部分，理论知识部分又分为八章：第1章，绪论；第2章，线性表；第3章，栈和队列；第4章，字符串、数组和广义表；第5章，树；第6章，图；第7章，查找；第8章，排序。实验部分精选18个典型实例以帮助学生巩固所学知识。本教材有如下特点：（1）所有例题都包括示意图、分析、流程图和程序代码四个部分，思路清晰，层次鲜明，能逐步培养和提高学生分析问题和解决问题的能力。本书每章均配有适量习题和实验，具有很强的针对性和可操作性。（2）以全国计算机程序员考试大纲为基准，涉及考试的章节选用部分历年试题作为示例，加强学生对所学内容的进一步理解、巩固和应用。（3）各章都配有“典型例题”一节，列举分析了很多实用的例子，有助于学生加深对基础理论知识的理解和实际应用能力的培养。（4）本书的算法和实验程序用标准C语言函数实现，可直接在turbo C或Visual C++6.0环境下运行。（5）为配合本教材的教学，还编制了多媒体课件，以加深对基本概念的理解。课件和习题答案，可通过E-mail（[e-mail]）向包振宇索取。建议本教材的理论教学时数为40学时，实验教学时数为30学时。本教材由包振宇、孙干、陈勇编著。其中，理论部分的第1～5章和实验部分由包振宇编写，理论部分的第6、7章和习题部分由孙干编写，理论部分的第8章由陈勇编写，最后由包振宇完成全书统稿。周永华、朱其俊参与了编写大纲的讨论并编写了初稿的部分内容，陈刚、张琴、刘呈真、杨健等参与了全书的校订工作，刘爱华、吴亮等在使用本书的过程中提出了一些修改建议，使得本书更加完善。本书在编写和修订过程中，得到了许多专家和众多院校数据结构任课教师的大力支持和帮助，他们提出了许多中肯的意见和很好的建议，对本书的编写及修订起到了很大的指导作用。编者对此表示衷心的感谢。

内容概要

《数据结构(第2版)》内容以“实践应用”为主体，理论以“够用”为尺度，理论与实验相结合。其内容分为两部分，包括理论知识部分与实验部分。本教材有如下特点：（1）所有例题都包括示意图、分析、流程图和程序代码四个部分，思路清晰，层次鲜明，能逐步培养和提高学生分析问题和解决问题的能力。每章均配有适量习题和实验，具有很强的针对性和可操作性。（2）以全国计算机程序员考试大纲为基准，涉及考试的章节选用部分历年试题作为示例，以加强学生对所学内容的进一步理解、巩固和应用。（3）书中的算法和实验程序用标准C语言函数实现，可直接在Turbo C或Visual C抖6.0环境下运行。《数据结构(第2版)》适合于高职高专院校计算机类专业的学生。

书籍目录

第一部分 理论知识第1章 绪论1.1 数据结构与算法1.1.1 数据结构的基本概念1.1.2 算法的概念和特性1.2 算法的描述和分析1.2.1 算法的描述1.2.2 算法的分析1.3 典型例题习题1第2章 线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构2.2.1 顺序分配2.2.2 线性表的操作2.3 线性表的链式存储结构2.3.1 线性链表的实现2.3.2 线性链表的运算2.3.3 循环链表2.4 典型例题习题2第3章 栈和队列3.1 堆栈3.1.1 堆栈的定义和基本操作3.1.2 顺序存储栈3.1.3 链式存储栈3.2 队列3.2.1 顺序存储队列3.2.2 链式存储队列3.3 典型例题习题3第4章 字符串、数组和广义表4.1 字符串基本概念4.2 字符串的存储结构4.2.1 串的顺序存储结构4.2.2 串的链式存储结构4.3 字符串的模式匹配4.3.1 模式匹配的BF算法4.3.2 模式匹配的KMP算法4.4 数组的基本概念4.5 矩阵的压缩存储4.5.1 特殊矩阵的压缩4.5.2 稀疏矩阵4.6 广义表4.6.1 广义表的存储结构4.6.2 综合举例4.7 典型例题习题4第5章 树5.1 树的定义和术语5.1.1 树的定义5.1.2 树的基本术语5.2 二叉树5.2.1 二叉树的定义和性质5.2.2 二叉树的存储结构5.3 遍历二叉树5.3.1 遍历二叉树的方法5.3.2 遍历二叉树的函数5.4 线索二叉树5.5 树和森林5.5.1 树的存储结构5.5.2 树与二叉树的转换（通过二叉链表存储联系）5.6 树的应用5.6.1 二叉排序树5.6.2 哈夫曼树5.7 典型例题习题5第6章 图6.1 图的基本概念6.1.1 图的定义6.1.2 图的相关术语6.2 图的存储结构6.2.1 邻接矩阵6.2.2 邻接表6.3 图的遍历6.3.1 深度优先搜索(DFS)6.3.2 广度优先搜索(BFS)6.4 最小代价生成树6.4.1 最小代价生成树的概念6.4.2 构造最小生成树的PRIM算法6.5 最短路径6.5.1 从某个顶点到其他顶点的最短路径6.5.2 每一对顶点间的最短路径6.6 拓扑排序6.7 典型例题习题6第7章 查找7.1 线性表的查找7.1.1 顺序存储线性表的查找7.1.2 分块查找7.1.3 链式存储线性表查找7.2 树的查找7.2.1 二叉树查找7.2.2 平衡二叉树7.2.3 B树7.3 哈希表及其查找7.3.1 哈希表7.3.2 常见的散列函数7.3.3 解决冲突的方法7.4 典型例题习题7第8章 排序8.1 选择排序8.2 直接插入排序8.2.1 顺序存储线性表的直接插入排序8.2.2 链式存储线性表的直接插入排序8.3 冒泡排序8.3.1 顺序存储线性表的冒泡排序8.3.2 链式存储线性表的冒泡排序8.4 希尔排序8.5 堆排序8.6 快速排序8.7 合并排序8.8 典型例题习题8第二部分 实验部分实验一 时间复杂度的计算实验二 顺序存储线性表的操作(1)实验三 顺序存储线性表的操作(2)实验四 链式存储线性表的操作(1)实验五 链式存储线性表的操作(2)实验六 链式存储线性表的操作(3)实验七 顺序栈的操作实验八 顺序存储队列的进队列和出队列操作实验九 字符串的操作实验十 数组的操作实验十一 广义表的操作实验十二 树的操作实验十三 图的操作实验十四 二分法查找的操作实验十五 插入排序的操作实验十六 选择排序的操作实验十七 快速排序的操作实验十八 冒泡排序和希尔排序的操作参考文献

章节摘录

插图：第1章 绪论“数据结构”形成和发展的背景：自1946年第一台计算机问世以来，计算机已深入到人类社会的各个领域，计算机的应用已不再局限于科学计算，而更多地用于控制、管理及信息处理等非数值计算的工作。计算机加工处理的对象由纯粹的数值发展到字符、表格、图像、声音等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为编写出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是“数据结构”这门学科形成和发展的背景。1.1 数据结构与算法1.1.1 数据结构的基本概念1.数据对现实世界的事物采用计算机能识别、存储和处理的形式所进行的描述。简言之，数据是计算机程序能加工和处理的对象，也就是计算机化的信息。2.数据元素数据的基本单位，又称为结点。在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素可由若干个数据项组成。如一的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。数据项是数据不可分割的最小单元。3.数据对象数据对象是性质相同的数据元素的集合，是数据的一个子集。4.数据结构（1）相互之间存在一种或多种特定关系的数据元素的集合。数据结构是指数据对象及其相互关系和构造方法。一个数据结构Ds可以被形象地用一个二元组表示为：DS=（D，R）。其中，D是数据结构中的数据（称为结点）的非空集，R是定义在D上的关系的非空有限集合。结构是指结点之间的关系，数据结构就是结点的有限集合和关系的有限集合。（2）数据结构中，结点及结点间的相互关系是数据的逻辑结构。数据结构在计算机中的存储内容，一般包括结点的值和结点间的关系，数据结构的存储形式是数据的存储结构（或物理结构）。（3）数据结构按逻辑关系的不同分为线性结构和非线性结构两大类，其中非线性结构又分为树形结构和图状结构，而树形结构又可分为树结构和二叉树结构。

编辑推荐

《数据结构(第2版)》为中国铁道出版社出版。