本文介绍了数据结构和算法的基础概念，数据包括数值和非数值类型，数据元素是数据处理的基本单位，数据对象是性质相同数据元素的集合。数据结构关注数据元素之间的逻辑关系和存储结构，分为线性结构和非线性结构。逻辑结构有集合、线性、树形和图形结构，而存储结构包括顺序、链式、索引和散列。数据类型和抽象数据类型定义了值的集合及操作，抽象数据类型是数学模型加上相关操作。
数据结构和算法绪论
Base—青岛大学 数据科学和软件工程学院
程序=数据结构+算法----------------Nicklaus Wirth图灵奖获得者Pascal的语言之父
绪论
1、数据(Data)
- 能够输入计算机且能被计算机处理的各种符号的集合
- 信息的载体
- 是对客观事物符号化的表示
- 能够被计算机识别，存储和加工
- 包括
- 数值类型的数据：整数，实数
- 非数值型的数据：文字、图像、图形、声音等
2、数据元素(Data Element)和3、数据项
2.1数据元素
- 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理
- 也简称为元素，或者记录，结点或顶点
- 一个数据元素可由若干个数据项组成（Data item）
2.2数据项
- 构成数据元素的不可分割最小单位
2.3数据、数据元素、数据项三者之间的关系
数据>数据元素>数据项
例：学生表>个人纪录>学号、姓名
4、数据对象（Data Object）
数据对象
- 是性质相同的数据元素的集合，是数据的一个子集
例如：
- 整数的数据对象是集合 N = {0,±1，±2，…}
- 字母字符的数据对象是集合 C = {“A”, “B”, “C”…"Z}
- 学籍表也可以看作一个数据对象（由若干条学生记录组成的集合）
数据元素和数据对象
- 数据元素—组成数据的基本单位
- 与数据的关系：是集合的个体
- 数据对象----性质相同的数据元素的集合
- 与数据的关系是：集合的子集
数据对象有点像学渣，学霸，不同的类，成堆成堆的，但属于这个班级（数据），数据元素呢，就是班级的个体数据对象有点像学渣，学霸，不同的类，成堆成堆的，但属于这个班级（数据），数据元素呢，就是班级的个体
1.2.2数据结构(Data Structure)
数据结构
- 数据元素不是孤立存在的，他们之间存在着某种关系，**数据元素相互之间的关系称为结构(**Structure)
- 是指相互之间存在一种或多种特定关系的数据元素的集合
- 或者说，数据结构是带结构的数据元素的集合
数据结构包括以下三个方面的内容：
-
数据元素之间的逻辑关系，也称为逻辑结构
-
数据元素及其关系在计算机内存中的表示(又称为映像)，称为数据的物理结构或者数据的存储结构
数据元素及其关系对应在内存中，既要把数据存进去也要把关系存进去即为映像
-
数据的运算和实现，及对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
数据结构的两个层次
-
逻辑结构
- 描述数据元素之间的逻辑关系
- 与数据存储无关，独立于计算机
- 是从具体问题抽象出来的数学模型
-
物理结构（存储结构）
- 数据元素及其关系在计算机存储器中的结构方式（存储方式）
- 是数据结构在计算机中的表示
-
逻辑结构和存储结构的关系
- 存储结构是逻辑关系的映像与元素本身的映像
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
- 两者综合起来建立的数据元素之间的结构关系
逻辑结构强调的是关系，只有存储结构才会扯到计算机
逻辑结构的种类
划分方法一
1、线性结构（一对一）
有且仅有一个开始和一个终端结点，并且所有的结点都最多只有一个直接前趋和一个直接后继
例如：线性表、栈、队列、串
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vqMI09VD-1639009050106)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211206211747097.png)]
- 比如这张线性表，只有一个开始结点(60214201)和终端节点(60214216),并且所有的结点(这四个学生)，最多只有一个直接前趋和一个直接后继（60214202的直接前趋是201后继是215，201和216则没有前趋或者后继）
- 准确来说是除开始和终端节点，其他节点都有一个前趋和后继。
- 直接前驱是 上一个结点
- 直接后继 下一个结点
2、非线性结构（一对多，多对多）
一个节点可能有多个直接前趋和直接后继
例如：树、图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VX6u2bbG-1639009050109)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211206212644168.png)]
--------------------树形结构 一对多
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mHvM0tcS-1639009050110)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211206212849932.png)]
--------------------图形结构 多对多 两个地方找最短路径
划分方法二---------------四类基本逻辑结构
1、集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系
2、线性结构：结构中的数据元素之间存在着一对一的线性关系
3、树形结构：结构中的数据元素之间存在着一对多的层次关系
4、图形结构或网状结构：结构中的数据元素之间存在着多对多的任意关系
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U7fxVxu8-1639009050111)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20211206213047979.png)]
存储结构的种类
四种基本的存储结构
-
顺序存储结构
-
用一组连续的存储单元一次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
逻辑关系可能有多个，线性，非线性(树形，图形)，存储单元表示前趋和后继
-
C语言中用数组来实现顺序存储结构
例子：存储字符串 (bat cat eat…)有先后顺序 线性结构
-
-
链式存储结构
-
用一组任意的存储单元（可连续，可不连续）存储数据元素，数据元素之间的逻辑关系用指针（地址）来表示
存储这个元素本身的同时，也会把下一个元素的指针（地址）也存上
-
C语言中用指针来实现链式存储结构
-
-
索引存储结构
- 在存储结点信息的同时，还建立附加的索引表。
- 索引表中每一项成为一个索引项
- 索引项的一般形式是(关键字，地址)
- 关键字是能唯一标识一个结点的那些数据项
- 若每个节点在索引表中都有一个索引项，则该索引表称为稠密索引，若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引
比如说通信录，根据首字母列出联系人名字，然后每个名字后面又对应的联系人的具体信息（名字，电话，住址，邮箱…）
-
散列存储结构
- 根据结点的关键字直接计算出该节点的存储地址
顺序存储典型就是顺序表（不等于有序表和线性表），链式存储典型就是链表（单链，双链。。），索引存储（一般不考，除非题目贱），散列存储典型就是哈希表（也叫散列表）
1.2.3数据类型和抽象数据类型
在使用高级程序设计语言编写程序时，必须对程序中出现的每一个变量、常量或表达式，明确说明他们所属的数据类型。
例如，go语言中
- 提供int，string，float等基本数据类型
- 数组，结构体，接口等构造数据类型
- 还有指针，nil类型
- 用户也可以自定义数据类型
一些最基本的数据结构可以用数据类型来实现，如数组，字符串等；
而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
-
高级语言中的数据类型明显的或隐含的规定了在程序执行期间变量和表达的所有可能的取值范围，以及在这些数值范围上所允许进行的操作。
- 数据类型的作用
- 约束变量或常量的取值范围
- 约束变量或常量的操作
- 数据类型的作用
-
数据类型(Data Type)
定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称
数据类型=值的集合+值集合上的一组操作 -
抽象数据类型（Abstract Data Type ADT）
是指一个数学模型以及定义在此数学模型上的一组操作。
- 由用户定义，从问题抽象出数据模型（逻辑结构）
- 还包括定义在数据模型上的一组抽象运算（相关操作）
- 不考虑计算机内的具体存储结构与运算的具体实现算法
抽象数据类型的形式定义
抽象数据类型可以用（DSP）三元组表示
其中 D：是数据对象
S：是D上的关系集
P：是对D的基本操作集
定义格式
ADT 抽象数据类型名{
数据对象:< 数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
}ADT 抽象数据类型名
其中
数据对象、数据关系的定义用伪代码描述
-
基本操作的定义格式为
-
基本操作名：（参数表）
-
说明
参数表：赋值参数 只为操作提供输入值
引用参数以&大头，除可供输入值外，还将返回操作结果。
初始条件：描述操作执行之前的数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始值为空，则省略之。
操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果
-
初始时间：（初始条件描述）
-
操作结果：（操作结果描述）
-
总结复习：
-
说明
参数表：赋值参数 只为操作提供输入值
引用参数以&大头，除可供输入值外，还将返回操作结果。
初始条件：描述操作执行之前的数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始值为空，则省略之。
操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果
-
初始时间：（初始条件描述）
-
操作结果：（操作结果描述）
总结复习：
扫一扫
422
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
