文档文本内容
王道考研——数据结构
WWW.CSKAOYAN.COM
第一章 绪论本节内容
数据结构
基本概念
王道考研/CSKAOYAN.COM知识总览
学习建议:
1. 概念多,比较无聊。抓大放小,重要的是形成框架,不必纠结于细节概念
2. 视频结尾会把最重要的概念串一遍,勿慌
王道考研/CSKAOYAN.COM什么是数据?
数据:
数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别
和处理的符号的集合。数据是计算机程序加工的原料。
二进制0和1
太极生两仪,两仪生
四象,四象生八卦
王道考研/CSKAOYAN.COM数据元素、数据项
数据元素、数据项:
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。
要根据实际的业务需求来确定什
么是数据元素、什么是数据项
一波顾客 另一波顾客
数据元素
号数 号数
数据项1
取号时间 取号时间
数据项2
就餐人数 就餐人数
数据项3
王道考研/CSKAOYAN.COM数据元素、数据项
数据元素、数据项:
数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。
一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位。
要根据实际的业务需求来确定什
么是数据元素、什么是数据项
一个账号 另一个账号
数据元素
昵称
昵称
数据项1
性别
性别
数据项2
生日
年生月日日
组合项
……
……
王道考研/CSKAOYAN.COM数据结构、数据对象
结构
——各个元素之间的关系
曼
粥
沙
左中右结构 上中下结构
左右结构
王道考研/CSKAOYAN.COM数据结构、数据对象
数据结构、数据对象:
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据对象是具有相同性质的数据元素的集合,是数据的一个子集。
一波顾客 另一波顾客
号数 号数
取号时间 取号时间
就餐人数 就餐人数
A门店的
3号 4号 5号 6号
顾客信息
数据结构:某个特定门店的排队顾客信息和它
们之间的关系 B门店的
995 996 997 998
顾客信息
号 号 号 号
数据对象:全国所有门店的排队顾客信息
王道考研/CSKAOYAN.COM数据结构的三要素
讨论一种数据结构时,
要关注的三个方面
王道考研/CSKAOYAN.COM数据结构的三要素
逻辑结构
——数据元素之间的逻辑关系是什么?
王道考研/CSKAOYAN.COM数据结构的三要素
数据的逻辑结构
——数据元素之间的逻辑关系是什么?
集合
各个元素同属一个集
合,别无其他关系
王道考研/CSKAOYAN.COM数据结构的三要素
数据的逻辑结构
——数据元素之间的逻辑关系是什么?
线性结构
数据元素之间是一对一的关系。
除了第一个元素,所有元素都有唯一前驱;
995 996 997 998
除了最后一个元素,所有元素都有唯一后继
号 号 号 号
王道考研/CSKAOYAN.COM数据结构的三要素
数据的逻辑结构
——数据元素之间的逻辑关系是什么?
E:
树形结构
电影 学习资料
*.avi xxx.avi xxx.ppt
数据元素之间是
一对多的关系
王道考研/CSKAOYAN.COM数据结构的三要素
数据的逻辑结构
——数据元素之间的逻辑关系是什么?
大表姐
前女
友
大表
你
哥
闺蜜
图结构
女友
A同学
数据元素之间是
微信好友
多对多的关系
王道考研/CSKAOYAN.COM数据结构的三要素
数据的逻辑结构
——数据元素之间的逻辑关系是什么?
集合
树形结构 图结构
线性结构
第四章 第五章
第二、三章
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——如何用计算机表示数据元素的逻辑关系?
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——如何用计算机表示数据元素的逻辑关系?
内存
a b d e f
a
线性结构
逻辑结构
b
d
e
顺序存储。把逻辑上相邻的元素存储在物理位置
f
上也相邻的存储单元中,元素之间的关系由存储
单元的邻接关系来体现。
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——如何用计算机表示数据元素的逻辑关系?
内存
d
a b d e f a
线性结构 用指针表示下一个数
逻辑结构
据元素的存储地址
e
链式存储。逻辑上相邻的元素在物理位置上可以
b
不相邻,借助指示元素存储地址的指针来表示元
素之间的逻辑关系。
f
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——各个数据元素在内存中如何存储
内存
d
a b d e f
关键字 地址 a
线性结构
逻辑结构
a
b e
d
e
索引存储。在存储元素信息的同时,还建立附加
f
的索引表。索引表中的每项称为索引项,索引项 b
的一般形式是(关键字,地址) 索引表
f
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——各个数据元素在内存中如何存储
a b d e f
线性结构
逻辑结构
散列存储。根据元素的关键字直接计算出该元素
的存储地址,又称哈希(Hash)存储
第六章,散列表
王道考研/CSKAOYAN.COM数据结构的三要素
数据的物理结构(存储结构)
——如何用计算机表示数据元素的逻辑关系?
王道考研/CSKAOYAN.COM数据结构的三要素
绪论部分只需要理解两点:
1. 若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用
非顺序存储,则各个数据元素在物理上可以是离散的。
2. 数据的存储结构会影响存储空间分配的方便程度 Eg:有人想插队
3. 数据的存储结构会影响对数据运算的速度
Eg:想找到第三个人
顺序存储 非顺序存储(离散存储)
王道考研/CSKAOYAN.COM数据结构的三要素
数据的运算
——施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的,
指出运算的功能;运算的实现是针对存储结构的,指出运算的具体操作步骤。
内存 内存
995 996 997 998
号 号 号 号
998
995
996 996
逻辑结构——线性结构(队列)
997
结合现实需求定义队列这种逻辑结构的运算:
998 997
①队头元素出队;
999
②新元素入队;
③输出队列长度;
995
……
999
王道考研/CSKAOYAN.COM数据结构的三要素
讨论一种数据结构时,
要关注的三个方面
王道考研/CSKAOYAN.COM数据类型、抽象数据类型
数据类型、抽象数据类型:
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1)原子类型。其值不可再分的数据类型。
2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
bool 类型 int 类型
值的范围:true、false 值的范围:-2147483648 ~ 2147483647
可进⾏操作:与、或、⾮… 可进⾏操作:加、减、乘、除、模运算…
定义一个具体的结构类型,表示排队顾客信息。
struct Customer{
根据具体业务需求来确定值的范围,可进行的操作
int num; //号数
int people; //人数
…… //其他必要的信息 值的范围:num(1~9999)、people(1~12)
}; 可进行操作:如“拼桌”运算,把人数相加合并
王道考研/CSKAOYAN.COM
抽象数据类型是具有相同性质的数据元素的集合,是数据的一个子集。数据类型、抽象数据类型
数据类型、抽象数据类型:
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1)原子类型。其值不可再分的数据类型。
2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
抽象数据类型(Abstract Data Type,ADT)是抽象数据组织及与之相关的操作。
ADT 用数学化的语言定义数
据的逻辑结构、定义运算。
与具体的实现无关。
王道考研/CSKAOYAN.COM知识回顾与重要考点
数据
数据对象
数据元素 数据元素
数据对象
数 数 数 数 数 数
据 据 据 据 据 据
项 项 项 项 项 项
数据对象
数据结构这门课着重关注的是数据元素之间的关系,和对这
些数据元素的操作,而不关心具体的数据项内容
王道考研/CSKAOYAN.COM知识回顾与重要考点
定义一个ADT,就是定义了数
据的逻辑结构、数据的运算。
也就是定义了一个数据结构。
确定一种存储结构,就意味着在计算机
中表示出数据的逻辑结构。存储结构不
同,也会导致运算的具体实现不同。
确定了存储结构,才能实现数据结构
王道考研/CSKAOYAN.COM知识回顾与重要考点
定义了一个
数据结构
学习任何一种数据结构
时应该关注的三个方面
王道考研/CSKAOYAN.COM