数据结构简明教程(第2版)-微课版 - (EPUB全文下载)

文件大小：0.4 mb。
文件格式：epub 格式。
书籍内容：

数据结构简明教程(第2版)-微课版
第1章　概论
第2章　线性表
第3章　栈和队列
第4章　串
第5章　数组和稀疏矩阵
第6章　树和二叉树
第7章　图
第8章　查找
第9章　排序
附录
参考文献
附录CD
第1章　概论
计算机的主要功能是数据运算，这些数据绝不是杂乱无章的，而是有着某种内在联系。只有分清楚数据的联系，合理地组织数据，才能对它们进行有效的运算。合理地组织数据、高效率地实施数据运算，正是数据结构课程的目的。本章简要介绍有关数据结构的基本概念和算法分析方法。
1.1　数据结构概述
1.1.1　什么是数据结构
计算机数据运算的一般过程如图1.1所示。数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。例如，某个班的全部学生记录、a~z的字母集合、1~1000的所有素数等都是数据。信息是数据的内涵，即数据所表达的意义，例如，通过统计后产生某课程的平均分85，这里85是数据，表示某课程平均分的信息。
图1.1　数据运算的过程
数据的基本单位是数据元素（有时称为元素、结点或记录等），通常把数据元素作为一个整体进行处理。例如，一个班的学生数据包括张三、李四等数据元素。
数据对象是具有相同类型的数据元素的集合，因为所有数据元素类型相同时处理起来更加方便，所以在数据结构中除特别指定外数据通常都是数据对象。
有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立意义的不可分割的最小标识单位。例如，在1~100的整数数据中，10就是一个数据元素；又比如在一个学生表中，一个学生记录可称为一个数据元素，而这个元素中的某一字段（如姓名）就是一个数据项。
【例1.1】组成数据的基本单位是________。
A．数据项
B．数据类型
C．数据元素
D．数据变量
解：数据是由数据元素组成的，数据元素是数据的基本单位。本题答案为C。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，如图1.2所示。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。在现实中，数据元素之间的关系多种多样，在“数据结构”课程中主要讨论数据元素之间的相邻关系。
图1.2　数据结构由数据和结构组成
归纳起来，数据结构一般包括以下三个方面的内容。
（1）数据元素之间的逻辑关系。所有元素的逻辑关系构成了数据逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（2）数据元素（有时简称为元素）及其逻辑关系在计算机存储器内的表示，构成了数据存储结构。数据存储结构是逻辑结构用计算机语言实现的（也称为映像），它是依赖于计算机语言的。一般只在高级语言的层次上讨论存储结构。
（3）数据运算，即对数据施加的操作。数据运算的定义（指定运算的功能描述）是基于逻辑结构的，每种逻辑结构都有一组相应的运算。例如，最常用的运算有检索、插入、删除、更新、排序等；而数据运算的实现是基于存储结构的，通常是采用某种计算机语言实现的。
例如，一个学生成绩表Score如表1.1所示，它由多个学生成绩记录（即数据元素）组成，每个元素又包括多个数据项，其中，学号数据项是关键字，即学号唯一标识一个学生记录，现要求计算所有学生的平均分。
表1.1　一个学生成绩表Score
在这个求解问题中，表1.1给出了数据的逻辑结构，其数据运算是求所有学生的平均分。为了实现这个功能，先要设计对应的存储结构，即把Score表存放到计算机内存中，然后设计出实现求平均分的算法。
这里包含的学生成绩表逻辑结构，对应的存储结构设计和求平均分运算的实现都是数据结构所涉及的内容。
1.1.2　逻辑结构
数据元素之间的逻辑关系的整体称为数据的逻辑结构。现实中，数据元素的逻辑关系千变万化，而数据结构课程中讨论的逻辑关系主要是指数据元素之间的相邻关系，如果两个数据元素是相邻的，说明它们之间是有关系的，否则它们之间没有关系。实际上，这种相邻关系处理方法很容易推广到其他复杂关系的处理。
根据数据元素之间逻辑关系的不同特性，分为下列4类基本结构。
（1）集合：包含的所有数据元素同属于一个集合（数据元素之间没有关系，集合是一种最松散的逻辑结构）。
（2）线性结构：包含的数据元素之间存在一对一的关系。（3）树状结构：包含的数据元素之间存在一对多的关系。
（4）图形结构：包含的数据元素之间存在多对多的关系。也称为网状结构。
数据的逻辑结构可以采用多种方式描述，二元组是一种既常用也十分通用的数据逻辑结构表示方式。二元组表示如下。
S=(D,R)
D={di|1≤i≤n}
R={rj|1≤j≤m}
其中，D是数据元素的有限集合，即D是由有限个数据元素所构成的集合，R是D上的关系的有限集合，即R是由有限个关系rj（1≤j≤m）所构成的集合，而每个关系都是指D→D的关系。
每个关系rj用序偶集合来表示，一个序偶表示两个元素之间的相邻关系，用尖括号表示有向关系，如表示存在元素a到b之间的关系；用圆括号表示无向关系，如（a，b）表示既存在元素a到b之间的关系，又存在元素b到a之间的关系。
设rj是一个D到D的关系，rj∈R，若元素d∈D，d′∈D，且∈rj，则称d′是d的直接后继元素（简称后继元素），d是d′的直接前驱元素（简称前驱元素），这时d和d′是相邻的元素（都是相对rj而言的）；如果不存在一个d′使∈rj，则称d为rj的终端元素；如果不存在一个d′使∈rj，则称d为rj的开始元素；如果d既不是终端元素也不是开始元素，则称d是内部元素。
例如，表1.1数据的逻辑结构是怎么样的呢？从该表中可以看出，学号为201201的元素为开始元素（没有前驱元素），学号为201204的元素为终端元素（没有后继元素）。除此之外，所有元素都只有一个前驱元素和一个后继元素，如学号为201205的学生记录的唯一前驱元素为学号 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。