数据结构与算法

章节摘录

插图：

前言

“数据结构”是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，也是计算机专业考研的必考课程，而且已成为其他理工科专业的热门课程。学好该课程，不仅对其后续算法设计、数值分析、操作系统、编译原理等课程的学习有很大帮助，而且在实际中有广泛的用途。 数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算的实现。它不仅为计算机语言进行程序设计提供了方法性的理论指导，还在一个更高的层次上总结了程序设计的常用方法和常用技巧。 “数据结构”课程的特点是概念多、算法灵活和抽象性强。针对这种情况，我们在参考各种数据结构教材的基础上，结合作者多年的教学经验，编写了这本适用于普通高等院校计算机及相关专业本科生的数据结构教材。该教材的编写突出了课程学科能力的培养，体现了兼顾“理论和应用”的教学改革理念。 本书分为10章，第1章绪论，介绍数据、数据结构、抽象数据类型等基本概念，特别是算法分析的方法；第2章线性表，介绍线性表的两种存储结构（顺序表和链表）的逻辑结构与基本运算的实现过程；第3章栈与队列，介绍两种特殊的线性结构的概念与应用；第4章串，介绍串的概念与模式匹配算法；第5章数组与广义表，介绍数组和稀疏矩阵的概念及相关运算的实现，以及广义表的存储结构及相关运算的实现；第6章树与二叉树，介绍树与二叉树的概念和各种运算的实现过程，其中特别突出二叉树的各种递归和非递归算法；第7章图，介绍图的基本概念和各种运算的实现过程；第8章查找，介绍各种常用查找算法的实现过程；第9章排序，介绍各种常用排序算法的实现过程；第10章文件，介绍常用的文件结构。 数据结构是一门应用性非常强的课程，必须在掌握了各种数据结构的基础上，尽可能多地上机练习。为此，本书每章后面都配有相应的上机实验题。

书籍目录

前言教学建议第1章 绪论11.1 数据结构的研究对象11.2 数据结构的发展概况41.3 基本概念与术语41.4 数据类型与抽象数据类型61.4.1 数据类型61.4.2 抽象数据类型61.4.3 抽象数据类型的表示与实现71.5 算法与算法分析91.5.1 算法91.5.2 算法设计的原则101.5.3 算法效率的衡量方法和准则101.5.4 算法的存储空间需求121.6 典型例题121.7 上机实验13习题13第2章 线性表162.1 线性表的定义162.1.1 线性表的概念162.1.2 线性表的抽象数据类型定义162.2 线性表的顺序表示与实现172.2.1 线性表的顺序表示172.2.2 线性表的顺序实现182.2.3 顺序表的应用举例212.3 线性表的链式表示与实现222.3.1 单链表222.3.2 双向链表262.3.3 循环链表292.3.4 静态链表312.3.5 链表的应用举例332.4 典型例题352.5 上机实验37习题39第3章 栈与队列413.1 栈413.1.1 栈的抽象数据类型定义413.1.2 栈的表示与实现423.2 栈的应用举例443.2.1 数制转换443.2.2 括号匹配的检验453.2.3 表达式求值463.2.4 求命题公式的真值503.3 栈与递归实现533.3.1 递归的定义533.3.2 递归与栈的关系533.3.3 递归的实现543.3.4 用递归求所有出栈序列563.3.5 递归的消除573.4 队列593.4.1 队列的抽象数据类型定义593.4.2 队列的链式表示与实现603.4.3 队列的顺序表示与实现——循环队列613.4.4 队列的应用举例633.5 典型例题643.6 上机实验66习题68第4章 串704.1 串的定义704.2 串的表示与实现724.2.1 串的顺序存储表示724.2.2 串的链式存储表示754.3 串的模式匹配754.3.1 简单匹配算法754.3.2 首尾匹配算法774.3.3 kmp算法784.4 典型例题804.5 上机实验82习题83第5章 数组与广义表855.1 数组的定义855.2 数组的顺序存储865.3 矩阵的压缩存储885.3.1 特殊矩阵895.3.2 稀疏矩阵905.4 广义表945.4.1 广义表的定义945.4.2 广义表的存储结构965.5 典型例题985.6 上机实验99习题100第6章 树与二叉树1016.1 树的定义1016.1.1 树的概念与术语1016.1.2 树的逻辑表示方法1026.1.3 树的抽象数据类型定义1026.2 二叉树的定义1036.2.1 二叉树的概念1036.2.2 二叉树的重要性质1056.3 二叉树的存储结构1066.3.1 二叉树的顺序存储表示1066.3.2 二叉树的链式存储表示1066.4 二叉树的遍历1086.4.1 二叉树遍历的概念1086.4.2 二叉树遍历的递归算法1086.4.3 二叉树遍历的非递归算法1096.4.4 层次遍历算法1116.4.5 遍历算法的应用举例1126.5 二叉树的构造1156.6 线索二叉树1166.6.1 线索二叉树的定义1166.6.2 线索链表的建立1176.6.3 线索链表的遍历算法1186.7 树和森林的表示方法1196.7.1 双亲表示法1196.7.2 孩子链表表示法1206.7.3 孩子-兄弟链表表示法1216.7.4 树、森林和二叉树的对应关系1216.8 树和森林的遍历1226.8.1 树的遍历1226.8.2 森林的遍历1236.8.3 树遍历算法的应用1246.9 赫夫曼树与赫夫曼编码1246.9.1 赫夫曼树的定义1256.9.2 赫夫曼树的构造1256.9.3 赫夫曼编码1276.1 0典型例题1286.1 1上机实验130习题130第7章 图1337.1 图的定义与术语1337.1.1 图的相关术语1337.1.2 图的抽象数据类型定义1357.2 图的存储表示1367.2.1 图的邻接矩阵存储表示1367.2.2 图的邻接表存储表示1377.2.3 有向图的十字链表存储表示1387.2.4 无向图的邻接多重表存储表示1407.3 图的遍历1417.3.1 深度优先搜索遍历图1417.3.2 广度优先搜索遍历图1427.3.3 图遍历的应用举例1437.4 最小生成树1457.4.1 普里姆算法1457.4.2 克鲁斯卡尔算法1477.5 两点之间的最短路径问题1487.5.1 从某个源点到其余各点的最短路径1487.5.2 每一对顶点之间的最短路径1507.6 拓扑排序1517.7 关键路径1537.8 典型例题1567.9 上机实验158习题160第8章 查找1628.1 基本概念1628.2 静态查找表1638.2.1 顺序查找1638.2.2 有序表查找1648.2.3 索引查找1678.3 动态查找树表1688.3.1 二叉排序树1698.3.2 平衡二叉树1738.3.3 b-树1798.3.4 b+树1838.3.5 键树1848.4 哈希表1858.4.1 哈希表的概念1858.4.2 哈希函数的构造方法1858.4.3 处理冲突的方法1878.4.4 哈希表的查找1898.4.5 哈希表的插入操作1908.4.6 哈希表的删除操作1918.5 典型例题1918.6 上机实验193习题194第9章 排序1969.1 概述1969.1.1 什么是排序1969.1.2 内部排序和外部排序1969.1.3 内部排序的方法1979.2 插入排序1989.2.1 直接插入排序1989.2.2 折半插入排序1999.2.3 二路插入排序2009.2.4 表插入排序2029.2.5 希尔排序2049.3 交换排序2059.3.1 起泡排序2059.3.2 快速排序2069.4 选择排序2099.4.1 简单选择排序2099.4.2 堆排序2099.5 归并排序2129.6 基数排序2139.6.1 多关键字排序2139.6.2 链式基数排序2149.7 各种排序方法的综合比较2169.8 外排序简介2179.8.1 外存信息的存取2189.8.2 外排序的基本方法2189.9 典型例题2199.1 0上机实验221习题222第10章 文件22410.1 文件的基本概念22410.1.1 什么是文件22410.1.2 文件的逻辑结构及操作22410.1.3 文件的存储结构22510.2 顺序文件22510.3 索引文件22610.3.1 isam文件22710.3.2 vsam文件22910.4 哈希文件23110.5 多关键字文件23210.5.1 多重表文件23210.5.2 倒排文件23210.5.3 倒排文件的应用23410.6 典型例题23510.7 上机实验237习题237参考文献239

编辑推荐

《数据结构与算法:C语言版》：语言通俗易懂，阐述简洁明了。重点突出算法设计思路，注重培养学生的编程思想和解决实际问题的能力。为激发学生学习该课程的兴趣，增强学生的创新意识，书中融入了一些利用所学知识解决实际问题的例子，如真值表的求解算法、出栈序列的求解算法等。算法丰富，讲解透彻，便于学生自学。通过典型算法设计的分析，使学生对所学知识的掌握更加系统化和条理化，更易于对所学知识融会贯通和举一反三。数据结构课程的特点是概念多、算法灵活和抽象性强。针对这种情况，作者在参考各种数据结构教材的基础上，结合多年的教学经验，编写了这本适用于普通高等院校计算机及相关专业本科生数据结构课程的教材。《数据结构与算法:C语言版》的编写突出了课程学科能力的培养，体现了兼顾"理论和应用"的教学改革理念。

作者简介

《数据结构与算法:C语言版》共10章，一方面，涵盖数据结构的基本概念，定义了线性表、栈、队列、串、数组、广义表、树和二叉树、图、查找、排序等各种结构的抽象数据类型，并给出了相应操作的实现算法；另一方面，采用C语言描述算法，并给出了各种算法的效率分析，以及这些结构在计算机科学及其他领域的应用。此外，每章后均配有典型例题、上机实验和习题。《数据结构与算法:C语言版》中的所有算法均在VC++环境下调试通过。

《数据结构与算法:C语言版》在内容安排上，突出由浅入深、循序渐进、通俗易懂的特点，算法分析透彻，讲解清晰，便于学生自学。为了激发学生的学习兴趣，培养学生解决实际问题的能力，书中融入了一些典型的应用实例，如命题公式真值表的求解算法、出栈序列的求解算法等。《数据结构与算法:C语言版》可作为高等院校计算机及相关专业本科生的“数据结构”课程教材，也可供相关科技人员学习参考。

图书封面

---

 数据结构与算法下载

---