数据结构
全新正版 极速发货
￥ 43.32 6.3折 ￥ 69 全新
仅1件
广东广州
认证卖家担保交易快速发货售后保障
作者叶飞跃 等 主编
出版社科学出版社
ISBN9787030533777
出版时间2017-06
装帧平装
开本16开
定价69元
货号1201531750
上书时间2024-11-23
商品详情
- 品相描述：全新
- 商品描述
-
目录
丛书序
前言
第1章绪论1
1.1引例1
1.2基本概念3
1.2.1数据、数据元素、数据项和数据对象3
1.2.2数据结构4
1.2.3数据类型和抽象数据类型6
1.3算法和算法分析9
1.3.1算法的定义及算法描述9
1.3.2算法评价10
1.3.3算法的时间复杂度12
1.3.4算法的空间复杂度16
小结17
习题18
上机实验题20
第2章C／C++语言知识21
2.1指针21
2.1.1指针变量21
2.1.2指针运算22
2.1.3数组与指针27
2.2结构体31
2.2.1结构体的定义31
2.2.2结构体数组33
2.2.3结构体指针34
2.3共用体37
2.4C++运算符39
2.4.1动态申请与释放内存运算符39
2.4.2引用41
2.5C程序分析42
小结44
习题44
上机实验题47
第3章线性表48
3.1引例48
3.2线性表的概念及运算49
3.2.1线性表的定义49
3.2.2线性表的抽象数据类型定义49
3.3线性表的顺序表示和实现50
3.3.1线性表的顺序存储表示50
3.3.2顺序表基本运算的实现51
3.4引例中读书兴趣小组活动管理的顺序表解决56
3.5线性表的链式表示和实现61
3.5.1单链表的定义和表示62
3.5.2单链表基本运算的实现62
3.5.3顺序表和链表的比较70
3.6引例中读书兴趣小组活动管理的链表解决71
3.7链表知识的扩展76
3.7.1单循环链表76
3.7.2双向链表77
3.8线性表应用举例78
小结85
习题86
上机实验题89
第4章栈和队列90
4.1引例90
4.2栈92
4.2.1栈的概念及运算92
4.2.2栈的顺序表示和实现93
4.2.3栈的链式表示和实现95
4.3引例中栈相关问题的解决98
4.3.1行编辑的解决98
4.3.2数制转换的解决99
4.3.3表达式求值的解决100
4.3.4递归实现的解决107
4.4队列109
4.4.1队列的概念及运算109
4.4.2队列的顺序表示和实现111
4.4.3队列的链式表示和实现114
4.4.4引例中银行个人业务模拟问题的解决117
小结119
习题120
上机实验题123
第5章串124
5.1引例124
5.2串的概念及运算124
5.2.1串的定义124
5.2.2串的抽象数据类型定义125
5.3串的顺序表示和实现126
5.3.1串的顺序存储表示126
5.3.2顺序串基本运算的实现127
5.4串的链式表示和实现129
5.4.1串的链式存储表示129
5.4.2链串基本运算的实现130
5.5串的模式匹配132
5.5.1Brute—Force算法132
5.5.2KMP算法134
5.6引例的解决138
5.6.1名和姓对换问题的解决138
5.6.2文本文件中单词计数和查找问题的解决139
小结140
习题140
上机实验题142
第6章数组和广义表143
6.1引例143
6.2数组144
6.2.1数组的概念及运算144
6.2.2数组的顺序存储表示145
6.2.3引例中求矩阵马鞍点问题的解决146
6.3特殊矩阵的压缩存储147
6.3.1对称矩阵147
6.3.2引例中求对称矩阵的和与乘积问题的解决148
6.3.3三角矩阵150
6.3.4引例中求三角矩阵的和与乘积问题的解决151
6.3.5对角矩阵152
6.4广义表153
6.4.1广义表的概念及运算153
6.4.2广义表的存储结构155
6.4.3引例中m元多项式表示问题的解决157
小结158
习题158
上机实验题160
第7章树和二叉树161
7.1引例161
7.2树的概念及运算162
7.2.1树的定义162
7.2.2树的抽象数据类型定义164
7.3二叉树165
7.3.1二叉树的概念及运算165
7.3.2二叉树的性质167
7.3.3二叉树的存储结构169
7.4遍历二叉树172
7.4.1遍历二叉树的概念和实现172
7.4.2根据遍历序列确定二叉树178
7.4.3遍历算法应用179
7.5线索二叉树182
7.5.1线索二叉树的概念182
7.5.2线索二叉树的构造和遍历184
7.6树和森林186
7.6.1树的存储结构186
7.6.2树、森林与二叉树的相互转换189
7.6.3树与森林的遍历191
7.7引例的解决193
7.7.1哈夫曼树用于编码的原理和方法193
7.7.2引例中字符编码和译码问题的解决196
7.7.3引例中报文编码和译码问题的解决202？
小结202
习题203
上机实验题206
第8章图207
8.1引例207
8.2图的概念及运算210
8.2.1图的定义210
8.2.2图的术语211
8.2.3图的抽象数据类型定义215
8.3图的存储结构216
8.3.1邻接矩阵法216
8.3.2邻接表法219
8.4图的遍历222
8.4.1图的深度优先遍历222
8.4.2图的广度优先遍历225
8.4.3引例中按中转次数查询最优航线的解决228
8.5最小生成树231
8.5.1最小生成树和通信网络建立231
8.5.2普里姆算法231
8.5.3克鲁斯卡尔算法236
8.5.4引例中通信网络建立问题的解决240
8.6最短路径241
8.6.1两类最短路径问题及应用241
8.6.2迪杰斯特拉算法242
8.6.3引例中按距离、飞行时间、票价查询最优航线的解决246
8.6.4弗洛伊德算法248
8.6.5引例中医院选址问题的解决253
8.7拓扑排序254
8.7.1拓扑排序和课程计划制定254
8.7.2拓扑排序算法255
8.7.3引例中课程计划制定问题的解决258
8.8关键路径260
8.8.1AOE网和关键路径260
8.8.2关键路径算法261
8.8.3引例中工程工期计算问题的解决268
小结270
习题270
上机实验题273
第9章查找274
9.1引例274
9.2查找的基本概念277
9.3线性表的查找278
9.3.1顺序查找278
9.3.2折半查找279
9.4树表的查找282
9.4.1二叉排序树283
9.4.2平衡二叉树292
9.4.3B—树296
9.4.4B+树303
9.5散列表304
9.5.1散列表的基本概念304
9.5.2散列函数的构造方法305
9.5.3处理冲突的方法307
9.5.4散列表的查找及其分析308
9.6引例的解决312
9.6.1手机选择中查找相关问题的解决312
9.6.2火车票信息查询中查找相关问题的解决314
9.6.3学生课程成绩管理中查找相关问题的解决316
9.6.4手机通讯录的解决320
小结321
习题322
上机实验题325
第10章内部排序326
10.1引例326
10.2排序的基本概念327
10.3插入排序328
10.3.1直接插入排序328
10.3.2折半插入排序329
10.3.3希尔排序330
10.4交换排序332
10.4.1冒泡排序332
10.4.2快速排序334
10.5选择排序337
10.5.1简单选择排序337
10.5.2堆排序338
10.6归并排序343
10.7基数排序345
10.7.1多关键字排序345
10.7.2基数排序346
10.8内部排序方法的比较讨论353
10.9引例的解决354
10.9.1手机选择中排序相关问题的解决354
10.9.2火车票信息查询中排序相关问题的解决355
10.9.3学生课程成绩管理中排序相关问题的解决357
小结360
习题360
上机实验题363
参考文献364
索引365
内容摘要
本书介绍数据结构的基本内容，包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、排序、查找等。书中详细介绍了各种数据结构及其在相应结构下数据操作的实现方法和性能分析。本书借鉴理实一体化的编写理念，通过问题导入法，引入要教学的重点内容，以激发读者的学习兴趣，用通俗的语言讲述基础理论，通过举例表述算法的设计思想，用C语言描述算法，并通过算法的设计与实现解决引入的问题，强化读者使用数据结构与算法解决实际问题的能力。
精彩内容
靠前章 绪论
内容提要
数据结构主要研究3个方面的问题：（1）数据的逻辑结构，即数据之间的逻辑关系；（2）数据的存储结构，即数据在计算机内的存储方式；（3）对数据的运算，即基于某种存储方式对数据的操作。本章重点介绍数据结构研究的对象、基本概念，以及算法的描述和算法的性能分析。
学习目标
能力目标：能对算法进行时间复杂度和空间复杂度分析。
知识目标：了解数据结构概貌，了解数据结构研究的问题，理解数据结构的基本概念，掌握描述算法的方法，以及算法的时间复杂度和空间复杂度概念。
1.1 引例
早期的计算机主要用于科学计算，它所处理的数据是数值型数据，对于数值问题抽象出的模型通常是数学方程式，比如计算三角形面积公式、球体体积公式、银行存款利息计算公式等。随着计算机科学与技术的飞速发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值型数据处理领域。计算机可处理的数据除数值型数据外，还有字符、表格、图形、图像、声音等具有一定结构的数据，并且处理的数据量也越来越大。这就给程序设计带来一个问题：应如何组织、存储、处理这些数据呢？在这种情况下人们提出了数据结构，并逐步发展，形成了计算学科中一门很基础、很核心的课程，它以数据表示和数据处理的基本问题为研究的主要内容。下面以引例1.1～1.5说明本课程研究的对象。
引例1.1：公园散步的人
给定一批数据，数据元素之间除了具有相同属性外没有其他任何关系。比如，在公园散步的人，他们除具有同一个特征—“散步的人”外，没有其他任何关系。我们把这些数据元素之间没有任何关系的数据结构称为集合结构。
引例1.2：学生基本情况登记表
如表1.1所示为一张简单的学生基本信息表。该表中的每一列称为一个属性，列属性的每个值表示一个学生的一个特征。表中的每一行称为一个记录，描述某个学生对象的多个特征。
在数据结构中，将记录称为数据元素或结点。表中的数据元素按照一定的顺序排列，其排列的规则既可以按输入时的先后顺序排列，也可以按某个或某些属性值大小的升序或降序排列。这种定义了元素之间的接近顺序关系的数据结构称为线性数据结构，简称线性表。例如，买“狗不理”包子的人一个接着一个排成队，这样就形成了线性关系。
表1.1 学生基本信息表
引例1.3：计算机系统中文件的组织
计算机可处理的信息是多种多样的，在通常情况下，这些信息以文件的形式存放在外存中，当计算机处理这些信息时才从外存装入内存进行加工处理。操作系统中的文件系统的功能就是专门负责文件在外存中的存放、读写、目录管理等。一般情况下，文件系统采用多级目录结构对文件实施管理，图1.1所示是一个文件系统的目录结构示意图。
图1.1 文件系统目录结构
这种多级目录结构形成一棵倒立的树，树中的目录或文件抽象成数据元素，称为结点，结点之间的关系是一对多的关系，通常称此类具有一对多关系的数据结构为树型结构，简称树结构或树。
引例1.4：教学计划编排
一个教学计划包含许多课程，有些课程必须按规定的先后次序进行排课。表1.2列出了计算机软件专业的部分课程以及它们之间的开课先后次序，其中，C1、C2 是独立于其他课程的基础课，其他课程都需要有先修课程，比如，《数据结构》课程就必须安排在《程序设计基础》和《离散数学》两门课程之后。这些先决条件规定了课程安排的优先关系，这种优先关系可以用如图1.2所示的有向图来表示，其中，顶点表示课程，有向边表示前提条件。若课程i 为课程j 的先修课程，则必然存在有向边<i， j>。在制订教学计划时，必须保证学生在学习某门课之前已学过其先修课程。
从图1.2中可以看出，一门课程可以有多门先修课程，也可以有多门后继课程。这种元素之间存在着多对多关系的数据结构称为图结构。
由以上4个例子可见，描述非数值问题的模型不再是数学方程式，而是集合、线性表、树和图等数据结构。数据结构的主要任务是在对问题进行抽象形成模型后对模型进行求解。因此，数据结构是研究非数值问题中计算机的操作对象以及操作对象之间的关系和操作的学科。
图1.2 课程之间关系的有向图
表1.2 软件专业部分课程设置及其开课先后次序表
引例1.5：通讯录程序设计
设计一个通讯录程序时需要考虑哪些问题？当我们着手建立一个通讯录时，需要考虑以下问题。
（1）确定数据元素的结构：记录一个人员的信息时需要哪些信息项，由这些信息项构成通讯录中的数据元素。
（2）数据的逻辑结构：以何种形式把数据元素组织在一起构成一个通迅录，即选择数据的逻辑结构。一般可以选择线性表或树结构。
（3）数据在逻辑结构上的运算：定义在数据的逻辑结构上可进行的运算，比如查找、增加、删除、修改数据元素，或按一定的规则对数据元素进行排序等。
（4）数据存储结构的选择：当需要把通迅录存入计算机时，确定以何种方式存储数据元素，何种存储方式有利于运算的实现以及高效率地运行。
（5）算法的设计：在确定的存储结构上实现数据的运算。
（6）算法的实现：采用程序设计语言实现算法。
1.2 基本概念
1.2.1 数据、数据元素、数据项和数据对象
数据（Data）是一个抽象的概念，它是对客观事物的符号表示且能被计算机存储、处理。数据是信息的载体，信息是数据的内涵。数据包含的内容很好广泛，包括数值、文字、字符、声音、图像、图形、音频、视频等各种媒体。
数据项（Data Item）是具有独立逻辑含义且不能再分解的数据。例如，学生基本信息中的学号、姓名、性别、出生日期、身高、体重等信息都是数据项。若数据项的值能专享标识一个数据元素，则称该数据项为关键字，如学生基本信息表中的数据项“学号”就是一个关键字。
数据元素（Data Element）是数据的基本单位，它由若干个数据项构成。在数据处理的过程中通常将数据元素作为整体进行考虑和处理。例如，每个学生的基本信息就是一个数据元素。在讨论数据结构时所涉及的很小的数据单位就是数据元素。根据应用情境的不同，也称数据元素为元素、记录、结点或顶点。
数据对象（Data Object）是具有相同性质的数据元素的集合，是数据的子集。例如，所有学生的基本信息对应的数据元素构成的集合就是一个数据对象。在计算机数据存储管理中，一个数据对象被组织成一个文件（或表）的形式进行整体存储、维护，并较为保存，因此，数据对象是数据存储管理单位。
1.2.2 数据结构
数据结构（Data Structure）是指数据元素之间的相互关系及数据的组织形式。它一般包括以下3 方面的内容。
1．数据的逻辑结构
数据的逻辑结构是从数据元素之间的逻辑关系（主要是相邻关系）上描述数据的，它独立于计算机且与数据的存储无关。因此，数据的逻辑结构可以看作从具体问题抽象出来的数学模型。
我们常用逻辑结构图来描述数据的逻辑结构，其描述方法是将每一个数据元素看作一个结点，用圆圈表示；元素之间的逻辑关系用结点之间的连线表示，如果强调关系的方向性，则用带箭头的连线表示。
通常，数据元素有下列4种形式的逻辑关系。
（1）集合结构。所有数据元素除了属于同一个集合之外没有任何关系，每个元素都是孤立的。由于集合结构中数据元素之间没有任何关系，一般情况下，不对集合结构进行研究。引例1.1是一个与集合结构相关的例子，其结构示意图如图1.3（a）所示。
（2）线性结构。数据元素之间存在着一对一的关系，即所谓的线性关系。引例1.2是一个线性结构的例子，在该例中数据元素的逻辑结构可用图1.3（b）示意。在讨论线性表时将涉及一些与线性结构有关的问题，例如哪个元素是表中的靠前个元素；哪个元素是表中的很后一个元素；对于表中一个给定的元素而言，哪些元素在它之前，哪些元素在它之后；在一个线性表中总共有多少个元素等。
（3）树结构。数据元素之间存在着一对多的层次关系。引例1.3是一个树结构的例子，其逻辑结构可用图1.3（c）示意。
（4）图结构。数据元素之间存在着多对多的任意关系。引例1.4是一个图结构的例子，再如，公路交通网、电力网等，其逻辑结构示意如图1.3（d）所示。
有时也把除线性结构以外的其他3 种结构称为非线性结构。由于我们不对集合结构进行研究，因此，一般情况下，我们所说的非线性结构常指树结构和图结构。
注意：①逻辑结构与数据元素本身的内容无关。例如，在家谱管理系统中，不管如何描述一个人，比如用姓名、性别、出生年月等描述，或用姓名、性别、出生年月、照片等描述，人和人之间的关系总是树的关系。②逻辑结构与数据元素的个数无关。例如，在家谱中增加或删除某些人，整个家谱还是一个树结构。
2．数据的存储结构
数据的逻辑结构可以看作从具体问题抽象出来的数学模型，它与数据的存储无关。我们把数据的逻辑结构在计算机存储器中的表示称为数据的存储结构，也称为数据的物理结构。它是数据的逻辑结构在计算机存储器中的映射，必须依赖于计算机。
图1.3 4 种基本数据结构的示意图
数据的存储结构包括数据元素本身的存储表示及其逻辑关系的存储表示。常见的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。
（1）顺序存储结构是指把逻辑上相邻的结点存
— 没有更多了 —
以下为对购买帮助不大的评价