中图网

>

研究生/本科/专科教材

>

工学

数据结构

作者：陈志贤

出版社：科学出版社出版时间：2022-03-01

开本：其他页数： 268

本类榜单：教材销量榜

中图价:¥37.2(6.3折) 定价 ~~¥59.0~~ 登录后可看到会员价

加入购物车收藏

运费6元，满39元免运费

?新疆、西藏除外

本类五星书更多>

>
中医基础理论

中医基础理论

¥51.7¥59
>
高校军事课教程

高校军事课教程

¥14.2¥38
>
思想道德与法治(2021年版)

思想道德与法治(2021年版)

¥8.8¥18
>
毛泽东思想和中国特色社会主义理论体系概论(2021年版)

毛泽东思想和中国特色社会主义理论体系概论(2021年版)

¥11¥25
>
中医内科学·全国中医药行业高等教育“十四五”规划教材

中医内科学·全国中医药行业高等教育“十四五”规划教材

¥85.1¥99
>
中医诊断学--新世纪第五版

中医诊断学--新世纪第五版

¥50.9¥58
>
中药学·全国中医药行业高等教育“十四五”规划教材

中药学·全国中医药行业高等教育“十四五”规划教材

¥85.1¥99

商品详情
商品评论(0条)

中图价:¥37.2 加入购物车

版权信息
内容简介
目录
节选

数据结构版权信息

ISBN：9787030699770
条形码：9787030699770 ; 978-7-03-069977-0
装帧：一般胶版纸
册数：暂无
重量：暂无
所属分类：
教材
>
研究生/本科/专科教材
>
工学

数据结构内容简介

本书以数据的逻辑结构、存储结构和算法为主线，讨论了线性表、栈、队列、串、数组和广义表、树和二叉树、图等各种数据结构，以及程序设计中经常使用到的各种查找和排序算法。全书共分为八个章节，第1章综述了数据、数据结构和抽象数据类型等基本概念；第2章至第6章介绍上述的几种数据结构及其应用；第7章至第8章讨论查找和排序的各种算法。在此基础上，我们更加强调数据结构的综合应用，对不同的数据结构类型设计了大量经典的应用实例，深入浅出、循序渐进，每一算法或程序的编写都力求高效、简洁、易读，并遵循程序设计的规范和标准，代码完整、自成一体，培养学生良好的编程风格，帮助学生将数据结构与工程应用有机地结合起来，从而培养新工科人才运用C语言和常用算法编写程序解决复杂实际工程问题的能力。全书采用C语言作为数据结构和算法的描述语言。

数据结构目录

目录
第1章绪论1
1.1为什么要学习数据结构1
1.2基本概念和术语2
1.2.1逻辑结构3
1.2.2存储结构4
1.2.3数据类型和抽象数据类型5
1.3算法和算法分析6
1.3.1算法的定义及特性6
1.3.2算法的设计要求6
1.3.3算法的时间复杂度7
1.3.4算法的空间复杂度10
1.3.5算法的描述形式11
1.4本章小结11
习题12
第2章线性表14
2.1线性表的定义14
2.2线性表的顺序表示和实现15
2.2.1顺序表的定义和特点15
2.2.2顺序表的存储及其操作16
2.2.3顺序表的性能分析20
2.3线性表的链式表示和实现22
2.3.1单链表的定义和表示22
2.3.2单链表的存储及其操作23
2.3.3单链表的性能分析27
2.3.4单链表的应用实例27
2.4循环链表32
2.5双向链表33
2.6链表的应用：一元多项式的运算34
2.6.1一元多项式的表示及存储34
2.6.2一元多项式的求和35
2.7本章小结39
习题39
第3章栈和队列41
3.1栈的定义41
3.2栈的表示和实现42
3.3栈的应用45
3.3.1数制转换45
3.3.2括号匹配检验46
3.3.3迷宫问题47
3.3.4表达式求值问题51
3.4栈与递归56
3.4.1递归56
3.4.2递归算法到非递归算法的转换60
3.5队列的定义64
3.6队列的表示和实现65
3.7队列的应用693.8
本章小结71
习题71
第4章数组、串和广义表73
4.1数组的定义和抽象数据类型73
4.2数组的存储结构74
4.3特殊矩阵的压缩存储75
4.3.1对称矩阵75
4.3.2三角矩阵76
4.3.3对角矩阵76
4.3.4稀疏矩阵76
4.4串91
4.4.1串的定义91
4.4.2串的存储结构93
4.4.3串的模式匹配算法94
4.5广义表104
4.5.1广义表的定义104
4.5.2广义表的链式存储结构和操作105
4.6本章小结109
习题110
第5章树和二叉树111
5.1树111
5.1.1树的定义和基本术语111
5.1.2树的抽象数据类型113
5.1.3树的存储结构114
5.2二叉树117
5.2.1二叉树的定义117
5.2.2特殊二叉树118
5.2.3二叉树的性质119
5.2.4二叉树的抽象数据类型120
5.2.5二叉树的存储结构121
5.2.6二叉链表的存储表示及操作123
5.3二叉树的遍历126
5.3.1先序遍历127
5.3.2中序遍历127
5.3.3后序遍历128
5.3.4层序遍历129
5.4线索二叉树132
5.5二叉树、树和森林136
5.5.1树和二叉树的转换137
5.5.2森林和二叉树的转换138
5.5.3树和森林的遍历139
5.6哈夫曼树及其应用140
5.6.1哈夫曼树的基本概念140
5.6.2哈夫曼树的构造141
5.6.3哈夫曼树的应用141
5.6.4哈夫曼编码的算法实现142
5.7本章小结147
习题147
第6章图149
6.1图的定义和术语149
6.2图的抽象数据类型152
6.3图的存储结构153
6.3.1邻接矩阵153
6.3.2邻接表159
6.3.3十字链表166
6.3.4邻接多重表167
6.4图的遍历169
6.4.1深度优先遍历169
6.4.2广度优先遍历171
6.5*小生成树173
6.5.1基本概念174
6.5.2普里姆算法175
6.5.3克鲁斯卡尔算法178
6.6*短路径180
6.6.1迪杰斯特拉算法181
6.6.2弗洛伊德算法184
6.7拓扑排序187
6.7.1拓扑排序介绍187
6.7.2拓扑排序算法188
6.8关键路径190
6.8.1关键路径算法原理190
6.8.2关键路径算法实现193
6.9本章小结195
习题196
第7章查找199
7.1查找的基本概念199
7.2线性表的查找200
7.2.1顺序查找200
7.2.2折半查找203
7.2.3分块查找207
7.3树表的查找209
7.3.1二叉排序树209
7.3.2平衡二叉树215
7.4散列表的查找222
7.4.1散列表的基本概念222
7.4.2散列函数的构造方法223
7.4.3处理冲突的方法225
7.4.4散列表的查找及性能分析227
7.5本章小结229
习题230
第8章排序232
8.1排序的基本概念232
8.2插入排序233
8.2.1直接插入排序233
8.2.2希尔排序236
8.3交换排序237
8.3.1冒泡排序238
8.3.2快速排序240
8.4选择排序242
8.4.1简单选择排序242
8.4.2堆排序245
8.5归并排序250
8.6分配排序252
8.6.1桶排序252
8.6.2多关键字排序253
8.6.3基数排序253
8.7本章小结257
习题258
参考文献260

展开全部

数据结构节选

第1章绪论数据结构是计算机学科知识结构的核心和技术体系的基石，也是计算机及相关专业研究生考试和水平等级考试的必考科目。通过该课程的学习，培养数据抽象能力，在实际应用中有效合理地组织、存储和处理具有复杂关系的数据，正确、高效地设计并实现算法，具备分析和评价算法的能力。 1.1 为什么要学习数据结构数据存储的主要目的是方便后期对数据的使用。比如我们使用数组存储某个学生的成绩 96， 82， 61， 54， 73}是为了后期对这些成绩再加工、分析和处理。无缘无故的数据存储行为是对存储空间的不负责任。计算机在用于数值计算时，其解题过程通常是这样的：首先从实际问题或者具体情境中抽象出数学模型，然后设计求解该数学模型的算法，*后编写程序，进行调试、测试，直至解决问题。然而在现实社会中还存在着许多非数值计算问题，其数学模型难以用数学方程描述。我们先来看下面几个例子。例 1-1员工信息管理系统。人事部门使用计算机对公司的所有员工信息统一管理。员工的基本信息包括工号、姓名、性别、籍贯、部门、入职日期等，如表 1-1所示。每个员工的基本信息按照不同的顺序号，依次存放在“员工基本信息表”中，可根据需要对这张表进行查找。每个员工的基本信息记录按顺序号排列，形成了员工基本信息记录的线性序列，呈一种线性关系。表 1-1 员工基本信息表诸如此类的线性表结构还有学生学籍管理系统、图书馆书目管理系统等。在这类问题中，计算机处理的对象是各种表，表中元素之间存在简单的一对一的线性关系，因此这类问题的数学模型就是各种线性表，施加于对象上的操作有插入、删除、修改、查找和排序等。这类数学模型称为“线性”的数据结构。例 1-2家谱管理系统。假如要存储这样一组数据：“岑夫子”“岑守仁”“岑守义”“岑守礼”“岑守信”“岑克勤”“岑克俭”。数据之间具有这样的关系：岑夫子是岑守仁、岑守义、岑守礼和岑守信的父亲，岑守义又是岑克勤和岑克俭的父亲，数据之间的关系如图 1-1所示。对于这类具有复杂关系的数据，用变量或数组来存储数据也是可以的，比如定义数组： char name[7][20] = {“岑夫子” ， “岑守仁” ， “岑守义” ， “岑守礼” ， “岑守信” ， “岑克勤”， “岑克俭” }; 但是这样做无法体现数据之间的逻辑关系，也会给后期的数据使用和维护带来极大的不便，甚至导致数据无法使用，显然这并不是一种有效合理的数据存储方式。此类数据对象的元素之间是一对多的层次关系，施加于对象上的操作有插入、删除、修改、查找和排序等。这类数据模型称为“树”的数据结构。例 1-3自驾游路线规划。 A、B两个城市之间有多条线路，且每条线路耗时不同，那么，如何选择一条线路，使得从城市 A到城市 B的耗时*短呢？这类问题可抽象为图的*短路径问题。如图 1-2所示，图中顶点代表城市，边代表两个城市之间的通路，边上的权值代表从一个城市到另一个城市的耗时。求解 A到达 B的*短耗时，就是要在图中 A点到 B点的多条路径中，寻找一条各边权值之和*小的路径，即*短路径。很显然，图中的这些数据绝不能简单地使用变量或数组进行存储，那样对于数据的使用无疑是一个灾难。图 1-1 数据及数据之间的关系图1-2自驾游路线规划诸如此类的图结构还有通信线路图、网络拓扑图和施工进度计划图等。此类问题的元素之间是多对多的网状关系，施加于对象上的操作同样有插入、删除、修改、查找和排序等。这类数学模型称为“图”的数据结构。从以上例子我们可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图的数据结构。因此，简单地说，“数据结构”是一门研究非数值计算的程序设计问题中计算机的操作对象以及这些对象之间的关系和操作的学科。因此，数据在计算机存储空间中的存放，不应该是随意的、杂乱无序的，需要我们选择一种合适的方式来存储数据，才能对它们进行有效的处理，设计出高效的算法。如何合理地组织数据、高效地处理数据，这正是数据结构的核心研究内容。 1.2 基本概念和术语接下来，我们先介绍数据结构中常用的一些概念和术语。数据(Data)：指所有能输入计算机中的描述客观事物的符号。数据是计算机存储、加工和处理的对象，它不仅仅包括整型、实型等数值类型，还包括文本、声音、图形、图像、视频等非数值类型。数据元素(Data Element)：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在某些情况下，数据元素也称为元素、记录、结点、顶点。例如，表 1-1中，每一行即每个员工的基本信息都是一个数据元素，也称为一条记录。有时，数据元素可以由若干个数据项(Data Item)组成。数据项是数据的有独立含义的*小标识单位，也称为字段、域、属性。例如，表 1-1中，每一列如“工号”“姓名”“性别”“籍贯”“部门”“入职日期”等均为数据项。数据对象(Data Object)：性质相同的数据元素的集合，是数据的一个子集。例如，表 1-1中，所有员工记录的集合就是数据对象。数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。不同数据元素之间不是孤立的，而是存在特定的关系，这些关系称为“结构”。因此，数据结构是带“结构”的数据元素的集合。数据结构包含逻辑结构、存储结构和运算三个要素。其中，运算即对数据施加的操作。 1.2.1 逻辑结构逻辑结构是指数据对象中数据元素之间的相互关系。它与数据的存储无关，独立于计算机，是从具体问题中抽象出来的数学模型。逻辑结构分为以下四种。 1．集合结构集合结构：数据元素间除了同属于一个集合外，没有其他关系。集合中的元素是离散的、无序的，它们之间没有什么关系。而数据结构重点研究的是数据之间的关系，因此，集合虽然是一种数据结构，但在该课程中却不予讲述。 2．线性结构线性结构：数据元素之间是一对一的关系，如线性表(典型的线性结构)、栈和队列(操作受限的线性表)、数组(线性表的推广，它的数据元素是一个线性表)、串、广义表(线性表的推广，它的数据元素是一个线性表，但不同构，或是单元素，或是线性表)。非空的线性结构有唯一的开始结点和唯一的终端结点，除了**个元素外，每个元素都有唯一的直接前驱；除了*后一个元素外，每个元素都有唯一的直接后继。 3．树形结构树形结构：数据元素之间存在一对多的层次关系，好像一棵倒立的树。 4．图状结构图状结构：数据元素之间存在多对多的关系。其中，集合结构、树形结构(树和二叉树)和图状结构(有向图和无向图)都属于非线性结构。从以上例子可以看出，逻辑结构是针对具体问题的，为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构(线性表、树或图)来表示数据元素之间的逻辑关系。可以说，算法的设计取决于数据的逻辑结构。 1.2.2 存储结构存储结构又称为物理结构，是指数据元素及其关系在计算机中的存储表示。除了存储各数据元素的数据，数据的存储结构还应该正确反映数据元素之间的逻辑关系。如何存储数据之间的逻辑关系，是实现物理结构的重点和难点。数据元素在计算机中有四种存储结构：顺序存储、链式存储、散列存储和索引存储。 1．顺序存储顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。数据元素存放在地址连续的存储空间中，元素间的逻辑关系是由元素在存储空间中的相对位置来表示的。通常借助于程序设计语言的数组类型来描述。 2．链式存储链式存储是把数据元素存放在任意的存储单元里，这些存储单元可以是连续的，也可以是不连续的。数据元素在存储空间内的相对位置并不能反映其逻辑关系，因此需要给每个元素附加指针域，用于存放相关联数据元素的地址。通常借助于程序设计语言中的指针类型来描述。 3．散列存储散列存储又称为哈希( Hash)存储，是把数据元素存放在一块连续的存储空间中，由元素的关键字( Key)值来决定该元素的存储地址。用散列函数确定数据元素的存储地址与关键字值之间的对应关系。 4．索引存储索引存储是指除存储元素信息外，还建立附加的索引表来标识元素的存储地址。索引表由若干索引项组成。若每个元素在索引表中都有一个索引项用于指示该元素所在的存储位置，则该索引表称为稠密索引。若一组元素在索引表中只对应一个索引项，该索引项指示这一组元素的起始存储位置，则该索引表称为稀疏索引。索引项的一般形式是关键字、地址，如图 1-3所示。其中，关键字是数据元素中某个数据项(字段)的值，又称为键值，用它可以标识一个数据元素或该数据项，该数据项称为关键码。若此关键字可以唯一地标识一个数据元素，则称此关键字为主关键字( Primary Key)。这也就意味着，对于不同的数据元素，其主关键字必然不同。主关键字所在的数据项称为主关键码。而对于可以识别多个数据元素的关键字，我们称为次关键字( Secondary Key)，它不能唯一标识一个数据元素，它对应的数据项就是次关键码。例如，表 1-1中，“工号”就是主关键码，“ 20080801”是主关键字，它可以唯一标识一条记录。“性别”就是次关键码，“性别”为“女”(次关键字)的记录在表中有两条。换句话说，“字”是数据项的值，而“码”是数据项(或称为字段)，是值的“统一名称”。在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空复杂度要求。也就是说，算法的实现依赖于采用的存储结构。 1.2.3 数据类型和抽象数据类型 1．数据类型数据类型(Data Type)是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。例如，C语言中的整型和实型。数据类型可分为两类：原子类型和结构类型。原子类型是不可再分解的基本类型，如整型、实型、字符型等；结构类型是由若干个类型组合而成的，是可以再分解的，如整型数组是由若干个整型数据组成的。 2．抽象数据类型抽象是指抽取出事物所具有的普遍性的本质，是计算机求解问题的基本方式和重要手段，它使得一种设计可以应用于多种场景。通过抽象可以屏蔽底层的实现细节，使设计更加简单、理解更加方便。抽象数据类型( Abstract Data Type，ADT)一般指用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作的总称。可以理解为将数据对象、数据对象之间的关系和对数据对象的基本操作封装在一起的一种表达方式。抽象数据类型的定义格式如下： ADT抽象数据类型名 { 数据对象 D(Data Object)：数据对象的说明数据关系 S(Structure)：数据元素之间逻辑关系的描述基本操作 P(Perform)：基本操作的定义基本操作 1：初始条件描述操作结果描述基本操作 2：基本操作 n： } “抽象”描述数据类型的方法是不依赖于具体实现的，即数据对象、基本操作的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型独立于具体实现，它只是描述数据对象和基本操作“做什么”，并不涉及

商品评论(0条)

写书评赚书币

暂无评论……

书友推荐