-
>
决战行测5000题(言语理解与表达)
-
>
软件性能测试.分析与调优实践之路
-
>
第一行代码Android
-
>
深度学习
-
>
Unreal Engine 4蓝图完全学习教程
-
>
深入理解计算机系统-原书第3版
-
>
Word/Excel PPT 2013办公应用从入门到精通-(附赠1DVD.含语音视频教学+办公模板+PDF电子书)
数据结构 版权信息
- ISBN:9787030752406
- 条形码:9787030752406 ; 978-7-03-075240-6
- 装帧:一般胶版纸
- 册数:暂无
- 重量:暂无
- 所属分类:>
数据结构 本书特色
本书是为数据结构课程编写的教材,其内容选择符合教学大纲要求,并兼顾计算机理论及应用专业、计算机相关专业(如信息管理与信息系统、电子商务、大数据管理与应用等专业)的宽泛理论与深层次的知识点,适用面广。
数据结构 内容简介
本书分为三个方面:①线性结构(线性表,栈和队列,串、数组和广义表)的概念、抽象数据类型的定义、算法描述及其应用;②非线性结构(树与图)的概念、抽象数据类型的定义、算法描述及其应用;③查找与排序的概念、算法描述及其应用。学习数据结构课程的意义在于:让学生了解客观世界问题在计算机外部的表示方法(逻辑结构),及其在计算机内部对应的存储方式(存储结构),以及如何对它们进行运算的计算机解题全过程。
数据结构 目录
前言
第1章 绪论 1
1.1 数据结构的研究现状与发展 1
1.1.1 国外的研究现状与发展 1
1.1.2 国内的研究现状与发展 1
1.1.3 数据结构在计算机专业中的地位 2
1.2 什么是数据结构 3
1.3 相关概念 6
1.4 数据类型与抽象数据类型 10
1.5 算法和算法分析 13
1.5.1 算法简述 13
1.5.2 算法的特征 13
1.5.3 算法对应的程序设计模式 14
1.5.4 时间复杂度 19
1.5.5 空间复杂度 22
1.6 数据结构的选择与评价 24
习题 24
第2章 线性表 26
2.1 线性表的概念、存储结构与应用 26
2.1.1 线性表的定义 26
2.1.2 线性表的抽象数据类型定义 26
2.1.3 线性表的存储结构 28
2.1.4 线性表的应用 29
2.2 线性表的顺序存储结构 31
2.2.1 线性表的顺序存储结构定义 31
2.2.2 线性表的顺序存储结构的基本操作 32
2.3 线性表的链式存储结构 37
2.3.1 线性表的链式存储结构定义 37
2.3.2 线性表的链式存储结构的基本操作 38
2.3.3 循环链表、双向链表的存储结构与操作 44
2.4 顺序表与链表的比较 49
2.5 线性表的应用举例 50
2.5.1 一元多项式的线性表的顺序存储结构及特点 50
2.5.2 一元多项式的线性表的链式存储结构 50
习题 56
第3章 栈和队列 60
3.1 栈 60
3.1.1 栈的定义 60
3.1.2 栈的抽象数据类型定义 60
3.1.3 栈的表示和实现 61
3.2 栈的应用 66
3.2.1 数制转换 66
3.2.2 括号匹配 67
3.2.3 运用栈实现行编辑程序 69
3.2.4 迷宫求解 71
3.2.5 表达式求值 77
3.3 栈与递归 83
3.3.1 递归的定义 83
3.3.2 递归过程的内部实现 85
3.3.3 递归消除 86
3.3.4 运用栈阅读递归程序 89
3.4 队列 100
3.4.1 队列的定义 100
3.4.2 队列的抽象数据类型定义 100
3.4.3 队列的表示和实现 101
3.5 队列的应用——离散事件模拟的例子 107
习题 113
第4章 串、数组和广义表 116
4.1 串的基本概念、存储结构与基本操作 116
4.1.1 串的基本概念 116
4.1.2 串的存储结构及算法 120
4.1.3 串的模式匹配算法 128
4.1.4 文本编辑的应用 140
4.2 数组及其应用 144
4.2.1 数组 144
4.2.2 数组的应用——矩阵的压缩存储 149
4.3 广义表的基本概念、抽象数据类型定义与基本操作 165
4.3.1 广义表的基本概念 165
4.3.2 广义表的抽象数据类型定义 166
4.3.3 广义表的表示和实现 167
习题 171
第5章 树和二叉树 175
5.1 树 175
5.1.1 树的定义 175
5.1.2 树的抽象数据类型定义 176
5.2 二叉树 178
5.2.1 二叉树的定义 178
5.2.2 二叉树的抽象数据类型定义 178
5.2.3 二叉树的性质 180
5.2.4 二叉树的存储结构 183
5.3 遍历二叉树 186
5.3.1 问题的提出 186
5.3.2 二叉树遍历算法 187
5.3.3 二叉树遍历递归算法的应用 193
5.4 线索二叉树 198
5.4.1 问题的提出 198
5.4.2 线索二叉树的存储结构 199
5.4.3 二叉树的中序线索化 201
5.5 树和森林 212
5.5.1 树、森林与二叉树的相互转换 212
5.5.2 树和森林的存储 214
5.5.3 树和森林的遍历 217
5.6 哈夫曼树及其应用 219
5.6.1 哈夫曼树 219
5.6.2 哈夫曼编码 222
5.6.3 哈夫曼树的应用 228
习题 229
第6章 图 235
6.1 图的定义、抽象数据类型定义和存储结构 235
6.1.1 图的定义和基本术语 235
6.1.2 图的抽象数据类型定义 240
6.1.3 图的存储结构 241
6.2 图的遍历 246
6.2.1 深度优先搜索递归算法及其阅读 247
6.2.2 广度优先搜索算法及其阅读 259
6.3 生成树与*小生成树 265
6.3.1 Prim算法 266
6.3.2 Kruskal算法 268
6.3.3 破圈法 270
6.3.4 生成树与图的遍历 272
6.4 两点之间的*短路径 273
6.4.1 从某个源点到其余各顶点的*短路径 273
6.4.2 每一对顶点之间的*短路径 278
6.5 有向无环图及其应用 279
6.5.1 拓扑排序 280
6.5.2 关键路径 288
习题 295
第7章 查找 301
7.1 查找的基本概念 301
7.2 静态查找表 302
7.2.1 无序顺序表查找——顺序查找 302
7.2.2 有序顺序表查找——折半查找 304
7.2.3 索引顺序表查找——分块查找 307
7.3 动态查找表 308
7.3.1 二叉排序树 309
7.3.2 平衡二叉树 314
7.4 哈希表 320
7.4.1 什么是哈希表 320
7.4.2 哈希函数的构造方法 321
7.4.3 处理冲突的方法 323
7.4.4 哈希表的查找 330
7.4.5 哈希表实现的比较 331
习题 332
第8章 内部排序 336
8.1 排序的基本概念 336
8.2 插入排序 337
8.2.1 直接插入排序 337
8.2.2 折半插入排序 339
8.2.3 表插入排序 340
8.2.4 希尔排序 342
8.3 交换排序 344
8.3.1 起泡排序 344
8.3.2 快速排序 345
8.4 选择排序 348
8.4.1 简单选择排序 348
8.4.2 堆排序 349
8.5 归并排序 352
8.6 分配排序 355
8.6.1 多关键字排序 355
8.6.2 基数排序 356
8.7 各种内部排序方法的比较 359
习题 360
参考文献 364
数据结构 节选
第1章 绪论 【内容提要】数据结构是计算机应用、信息管理与信息系统、电子商务、信息科学与大数据技术等专业重要的专业基础课程,它为后续的专业课程提供了必要的知识和技能准备。本章介绍数据结构的概念和相关术语,以及数据类型的相关知识和算法分析。 【学习要求】了解数据结构的发展历史;掌握和理解数据结构的相关术语与基本概念;运用形式化方法定义和描述一个实际问题对应的数据结构;了解算法的时间复杂度与空间复杂度以及判断算法好坏的方法。 1.1 数据结构的研究现状与发展 1.1.1 国外的研究现状与发展 早在1968年,美国一些学校的计算机系就开始将数据结构作为一门计算机专业的基础课程。数据结构的课程体系*早是由美国计算机专家D. E. Knuth提出的,在他所著的《计算机程序设计技巧》(**卷《基本算法》于1968年出版)一书中,较为系统地描述了客观世界中各类数据的计算机外部结构(逻辑结构)、计算机内部对应的存储方式(存储结构)及其形式化定义和对应的操作之间的关系。其描述方式已经与实际问题的解决方案非常贴近,数据结构作为一门计算机专业的基础课程逐渐成为现实。随后,第二卷《半数字化算法》于1969年出版,第三卷《排序与搜索》于1973年出版,这些著作中的算法及其应用,奠定了数据结构的理论基础。当时,数据结构这门课程已经被美国其他高校所接纳。后来,数据结构课程以算法为主要的讲授内容,成为当时计算机专业的一门重要的基础课程。 20世纪90年代出现的C++语言和Java语言,从根本上解决了计算机网络环境下复杂数据结构应用的问题:如C++语言是面向对象的程序设计语言,它在C语言的基础上发展起来,但它比C语言更容易为人们所学习和掌握。C++以其独*的语言机制在计算机科学的各个领域中得到了广泛应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一次质的飞跃,C++很好地体现了面向对象的各种特性。同样Java语言也是如此,其优点在于:①Java的风格类似于C++;②Java摒弃了C++中容易引发程序错误的地方,如指针和内存管理;③Java提供了丰富的类库。C++和Java语言跨平台、跨系统且操作方便的特点,为复杂数据结构算法的实现带来了非常灵活的操作模式。 1.1.2 国内的研究现状与发展 20世纪70年代后期,数据结构课程在我国已经作为计算机专业一门重要的基础与核心课程,清华大学严蔚敏等学者所编制的教材《数据结构》,逻辑结构清晰、算法丰富,多年来一直作为国内多所高校数据结构课程的首选教材。清华大学的《数据结构》教材*大的特点是:将所有形式的数据结构运用形式化定义方法进行描述,其描述与定义方法严谨,为学生提供了一套逻辑性强的定义方法。与此同时,书中的形式化定义方法还可以将形式化定义用于其他复杂系统的数据结构的定义中。在20世纪80年代,基本上采用Fortran和Basic语言来描述算法。到了20世纪90年代初期,国内大多数教材的算法采用Pascal描述(或类Pascal或伪码来描述),如早期清华大学的《数据结构》教材就是采用这种描述方法。20世纪90年代后期,C语言成为数据结构算法的主要描述语言。2000年以后,随着C++、VC++版本的出现,国内的数据结构教材又以C++、VC++版本为主流。之后,随着强大的网络技术的普及与应用,又出现了跨平台的数据结构版本,如Java、.Net版本。这些语言的诞生与应用,给多系统的复杂数据的整合、定义域知识的描述提供了新的解决方案,尤其是当前大数据的形成和云计算架构的形成,给数据结构课程增添了更多的新模式。 因此,数据结构是一门专业性非常强的计算机基础课程,同时,也是计算机和信息管理等专业必不可缺的核心课程。换句话说,数据结构课程覆盖的专业知识广阔,涉及解决问题的数学模型众多。随着计算机、网络技术的发展和数据处理能力的增强,国内外相关专业开设数据结构课程的学校越来越多,且包括的内容也越来越多。由早先的线性表运算、非线性表运算、堆栈、排队、递归、树、图等传统的数据操作模式,扩充到多系统环境下的多维数据结构、复杂类型的数据结构以及跨平台模式的数据结构模式。 1.1.3 数据结构在计算机专业中的地位 数据结构不仅是计算机和信息管理等专业主要的基础课程,更重要的是作为编译原理、操作系统、数据库原理、汇编语言程序设计、管理与决策等课程的前驱课程,对该课程内容的掌握程度直接反映了计算机软件水平、管理与决策水平的高低。数据结构在计算机专业中的地位如图1.1所示。 图1.1 数据结构在计算机专业中的地位 数据结构并不是要告诉我们怎样编程,而是教会我们如何用*精练的语言和*少的资源编写出*优秀、*合理的算法与程序。换句话说,数据结构存在的意义就是使程序*优化。所以学习数据结构需要一定的基础知识。如果缺乏数据结构的知识,仅仅学会计算机语言的使用,想要编制出好的程序是不可能的,也不可能将客观世界复杂问题对应的实际模型进行建模和求解。同时,在大型软件开发的六个阶段(计划、需求分析、设计、编码、测试和维护)中,数据结构的内容体现在以客观管理问题求解过程中的数据建模及设计为核心,同时也涉及编码和需求分析阶段的一小部分内容。 总之,数据结构随着计算机应用与网络的普及一直在发展,并且面向特殊领域的数据结构也在不断发展,如新兴的图像处理与动画技术需要新的数据结构予以支持。面向对象技术与其他新兴技术的出现,掀起了从更加抽象的层次上讨论数据结构的概念和内容的新趋势。 1.2 什么是数据结构 数据结构课程主要是介绍一些常用的数据结构,阐明数据结构内在的逻辑关系,讨论它们在计算机中的存储表示和它们进行各种运算的实现算法。 按照字面含义,数据结构一定包括与数据及其结构相关的含义。广义上,数据结构包括数据的逻辑结构、数据的存储结构和数据运算三个方面,即涉及数据之间的逻辑关系、数据在计算机中的存储方式和相关的一组操作。 1. 数据结构主要任务 数据结构主要任务是:首先,将某实际问题的逻辑结构找出来;然后,在针对该逻辑结构进行科学分析后,映射为其对应的物理结构(即数据结构)形式;*后,对该数据进行操作。 美国计算机科学家Niklaus Wirth(尼 沃思)认为: Algorithms+Data Structure=Programs Algorithms(算法):实现程序的逻辑步骤。 Data Structure(数据结构):描述了解决问题的数学模型;解决问题的相关数据集合;数据之间的结构关系集合。 Programs(程序):为解决实际问题而编制的一组指令集合。 2. 算法、数据结构与程序之间的关系 (1)算法是实现程序的核心。 (2)如果一个问题的解决方法确定,则该问题的数据结构及数据之间的运算关系也是确定的,即该数据结构的选取决定了其算法的时间复杂性——程序运行的时间和速度。 (3)程序运行速度与算法本身、计算机本身、操作系统、网络环境等紧密相关。 如图1.2所示为计算机解决问题的步骤,数据结构的工作主要体现在第1步“分析问题”与第2步“确定处理方案”,这既是*基本的工作,也是*重要的工作。下面将举几个例子来帮助理解。 图1.2 计算机解决问题的步骤 例1.1 求解 。 具体步骤如下。 (1)首先判断该问题是否属于计算问题,即所涉及的运算对象是否属于整型、实型或布尔型的简单变量。 (2)运用某语言将中的a与b分别输入后,再进行计算。 (3)打印或显示运行结果。 例1.2 电话号码的查询。 具体步骤如下。 (1)构造一张电话号码登记表,表中的每个结点存放两个数据项:姓名与电话号码。 (2)按照链表结构构造该问题的数据存储方式,即问题对应的内部存储方式,确定链表的模式,如单链表模式。如图1.3所示。 图1.3 链式电话号码登记表 例1.3 计算矩阵的乘积 。 具体步骤如下。 (1)分析问题中的各个运算参数的外部表示。如图1.4所示。 图1.4 矩阵运算参数的外部表示 (2)确定、与矩阵的内部存储方式。 A. 以行为主序存储。 在内存的顺序是:。 在内存的顺序是:。 在内存的顺序是:。 B. 以列为主序存储。 在内存的顺序是: 在内存的顺序是: 在内存的顺序是: (3)寻址方式决定其计算模式。 A. 如果以行为主序存储,该矩阵乘积的寻址公式为 B. 如果以列为主序存储,该矩阵乘积的寻址公式为 (4)计算矩阵乘积,显示计算结果。 例1.4 单车道车辆进库与出库满足先进后出或者后进先出的规律,也将满足这种规律的运算叫作栈,栈的运算与操作在栈的一端进行(详细内容请参考第3章栈和队列的相关内容)。 例1.5 银行窗口业务处理,满足先来先服务、后来后服务的排队的操作规律,也叫作队列(详细内容请参考第3章栈和队列的相关内容)。 例1.6 图论问题。图的算法将在本书的后面章节介绍,该算法主要包括:图的表示方法、图的遍历、*短路径算法、影响工程进度的关键路径等算法(详细内容请参考第6章图的相关内容)。 以多岔路口交通灯设置问题为例。通常在十字路口只需要设置红、绿两种颜色的交通灯以便维持交通秩序,但在多岔路口则需设置多种颜色的交通灯才能使车辆流通量*大又保证交通秩序。如图1.5(a)所示五岔路口,C和E表示单行道。图1.5(b)表示五岔路口的车流方向,在路的中间有L1~L13共13个交通信号灯,图中箭头方向表示每条路上的车流方向,车流有交叉或者箭头指向相同出口表示两条道路不能同时通车,否则会发生交通事故。当且仅当某个方向上的交通灯变为绿色时,此方向上的车辆才能通行。问怎样变换交通灯的颜色才能使此路口的车都能安全通过又能达到路口的*大流通量? 图1.5 五岔路口交通灯设置问题 在图1.5中,用一个顶点表示一条通路,两条通路之间相互矛盾的关系用两个顶点之间的连线表示,即若两条通路之间不能同时通车,则两个顶点之间连一条线。因此设置交通灯的问题转换为对图中顶点的着色问题,要求对图中的每个顶点着一种颜色,并且要求有线相连的两个顶点不能同时具有相同的颜色,而总的颜色种类尽可能少。图1.6为其中的一种着色方案。 图1.6 五岔路口交通灯设置问题的一种着色方案 解决方案: 1号灯亮时,只有AB、BA、AC、AD、DC、ED方向上的车能同时通过; 2号灯亮时,只有BC、BD、EA方向上的车能同时通过; 3号灯亮时,只有DA、DB方向上的车能同时通过; 4号灯亮时,只有EB、EC方向上的车能同时通过。 例1.7 报文编码问题。此问题属于*优二叉树问题,即该问题对应的数据结构属于二叉树的优化问题,运用该优化解决方法可解决报文编码问题(详细内容请参考第6章关于哈夫曼树及其应用的相关内容)。 另外,利用数据结构还可以对如下问题提出解决方法:①将文本编辑与操作归结为字符串操作问题;②为提高查找速度提出各类查找算法;③为方便各类快速查找而对数据的科学排序方法。 归纳起来讲,数据结构课程是一门“描述现实世界实体的数学模型(非数值计算)及其操作在计算机中如何表示和实现”的理论和应用性强的计算机专业基础课。 1.3 相关概念 在本节中,我们将对一些概念和术语赋以确定的含义,以便与读者取得“共同的语言”。这些概念和术语将在以后的章节中多次出现。 1. 数据
- >
有舍有得是人生
有舍有得是人生
¥20.1¥45.0 - >
名家带你读鲁迅:朝花夕拾
名家带你读鲁迅:朝花夕拾
¥10.5¥21.0 - >
二体千字文
二体千字文
¥21.6¥40.0 - >
我与地坛
我与地坛
¥15.4¥28.0 - >
李白与唐代文化
李白与唐代文化
¥12.5¥29.8 - >
罗曼·罗兰读书随笔-精装
罗曼·罗兰读书随笔-精装
¥17.4¥58.0 - >
月亮与六便士
月亮与六便士
¥18.1¥42.0 - >
苦雨斋序跋文-周作人自编集
苦雨斋序跋文-周作人自编集
¥6.9¥16.0
-
Photoshop 2022中文版案例教程
¥44.1¥59.8 -
局域网组建、管理与维护(第4版)(微课版)
¥47¥59 -
园林AUTOCAD教程
¥24¥45 -
Python实战编程:从零学Python
¥81¥108 -
Java程序设计基础
¥37¥50 -
数据备份与恢复
¥51.4¥69