目录数据结构中的基本概念数据结构的三要素逻辑结构的4种类型二元组表示法怎么描述一个数据结构存储结构的4种类型数据类型 vs 抽象数据类型ADT本章小结 常见考点———————————————————————————————————————————————————————————————数据结构中的基本概念1.1 什么是数据数据是信息的载体是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。简单说只要能输入计算机、能被程序处理的东西都是数据。Word文档是数据图片、视频是数据我们平时写的代码也是数据注意数据结构中主要讨论的是结构化数据比如表格、数组这种有规律的数据。1.2 三个核心概念数据 数据元素 数据项这三个概念是层层包含的关系一定要分清楚概念 定义 举例学生成绩表数据 信息的载体所有能被计算机处理的符号集合 整个学生成绩表数据元素 数据的基本单位通常作为一个整体考虑和处理 每一行一个学生的所有成绩数据项 构成数据元素的不可分割的最小单位 姓名、学号、语文成绩、数学成绩…一句话记住数据 数据元素 数据项班级成绩表 个人成绩记录 姓名、学号、成绩…1.3 什么是数据对象数据对象是具有相同性质的数据元素的集合是数据的一个子集。举个例子海底捞所有门店的排队顾客信息 数据A门店的排队顾客信息 一个数据对象B门店的排队顾客信息 另一个数据对象同一个数据对象里的数据元素都具有相同的性质。1.4 什么是数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。简单理解一堆数据放在一起光有元素还不够元素和元素之间有关系这个关系就是结构比如排队你前面是谁、后面是谁这就是关系就是结构。数据结构的三要素讨论一种数据结构必须从三个方面入手2.数据结构三要素├── 逻辑结构数据元素之间的逻辑关系面向用户├── 物理结构存储结构数据在计算机存储器中的存储方式面向程序员└── 数据的运算施加在数据上的操作增删改查等三要素 含义 面向谁逻辑结构 数据元素之间的逻辑关系是什么样的 用户存储结构 这些数据在内存里怎么存 程序员数据运算 对这些数据能做什么操作 程序员3.逻辑结构的4种类型逻辑结构是从用户的角度看数据元素之间的关系一共分4种3.1 集合元素之间关系无特点数据元素之间除了属于同一个集合的关系外别无其他逻辑关系。就像火锅里的食材都在一个锅里但彼此之间没什么顺序关系。● ● ● ● ● ●3.2 线性结构结构体数组不等于线性结构元素之间关系一对一特点开始元素和终端元素都是唯一的除此之外其余元素都有且仅有一个前驱元素和一个后继元素。就像排队买奶茶一个接一个每个人前面只有一个人后面也只有一个人。● → ● → ● → ● → ●常见的线性结构线性表、栈、队列、字符串…3.3 树形结构元素之间关系一对多特点开始元素唯一终端元素不唯一。除终端元素以外每个元素有一个或多个后继元素除开始元素外每个元素有且仅有一个前驱元素。就像家族族谱一个爸爸可以有多个孩子但每个孩子只有一个爸爸。●/ |● ● ●/ \ /● ● ● ●常见的树形结构二叉树、B树、堆…3.4 图形结构图结构元素之间关系多对多特点所有元素都可能有多个前驱元素和多个后继元素。就像微信好友关系你有很多好友每个好友又有其他好友关系错综复杂。● — ●/ \ /● — ● — ●\ / \ /● — ●常见的图形结构有向图、无向图、网…四种逻辑结构对比表类型 元素关系 特点 举例集合 无关系 同属一个集合即可 火锅食材拼盘线性结构 一对一 一个前驱一个后继 排队、链表树形结构 一对多 一个前驱多个后继 族谱、文件夹图形结构 多对多 多个前驱多个后继 微信好友、地图二元组表示法怎么描述一个数据结构4.1 什么是二元组二元组是一种通用的逻辑结构表示方法。一个二元组表示为B (D, R)其中B数据结构D数据元素的集合元素有限集RD上关系的有限集4.2 序偶怎么表示关系每个关系用若干个序偶来表示x, y x, y ∈ D含义x 是第一元素y 是第二元素x 是 y 的直接前驱元素y 是 x 的直接后继元素注意序偶 x, y 表示 x、y 是有向的有箭头方向序偶 (x, y) 表示 x、y 是无向的双向箭头4.3 开始元素 vs 终端元素开始元素没有前驱元素的元素终端元素没有后继元素的元素4.4 举个例子假设有学生表学号 姓名 性别 班号1 张斌 男 99018 刘丽 女 990234 李英 女 990120 陈华 男 990212 王奇 男 990126 董强 男 99025 王萍 女 9901用二元组表示B (D, R)D {1, 8, 34, 20, 12, 26, 5}R {1,8, 8,34, 34,20, 20,12, 12,26, 26,5}画成图就是1 → 8 → 34 → 20 → 12 → 26 → 5很明显这是一个线性结构存储结构的4种类型存储结构物理结构是数据在计算机内存中的存储方式。逻辑结构是面向用户的存储结构是面向程序员的。同一种逻辑结构可以用不同的存储结构来实现。5.1 顺序存储在内存存储时地址必须相邻连续存储空间。补充一下数组是找连续空间。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。就像电影院的座位按编号一排一排紧挨着坐。特点所有元素占用一整块内存空间逻辑上相邻的元素物理上也相邻通过存储单元的邻接关系来体现元素间的关系C语言实现举例struct{intno;// 学号charname[8];// 姓名charsex[2];// 性别charclass[4];// 班号}Stud[7]{{1,张斌,男,9901},{8,刘丽,女,9902},// ...};5.2 链式存储在内存存储时地址可以不相邻逻辑上相邻的元素在物理位置上可以不相邻借助指示元素存储地址的指针来表示元素之间的逻辑关系。就像找朋友不用住在隔壁靠微信保持联系就行。特点一个逻辑元素用一个结点存储每个结点单独分配所有结点的地址不一定是连续的用指针来表示逻辑关系C语言实现举例typedefstructstudnode{intno;// 学号charname[8];// 姓名charsex[2];// 性别charclass[4];// 班号structstudnode*next;// 指向结点的指针}StudType;5.3 索引存储在存储元素信息的同时还建立附加的索引表。就像书后面的索引目录告诉你某个关键词在第几页。索引项的一般形式 关键字地址特点查找速度快但需要额外的索引表空间5.4 散列存储哈希存储根据元素的关键字直接计算出该元素的存储地址又称 Hash 存储。就像你有一个公式输入学号直接算出这个人存在内存的哪个位置。特点查找速度极快O(1)但可能会有冲突不同关键字算出同一个地址四种存储结构对比存储方式 特点 优点 缺点顺序存储 连续存储 随机存取存储密度高 插入删除慢需要连续空间链式存储 指针连接 插入删除方便不要求连续 存储密度低只能顺序存取索引存储 加索引表 查找速度快 额外索引表开销散列存储 Hash计算地址 查找极快 可能有冲突数据类型 vs 抽象数据类型ADT6.1 什么是数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。就像int类型值的集合-2147483648 ~ 2147483647可进行的操作加、减、乘、除、模运算…数据类型分两种1原子类型其值不可再分的数据类型。比如bool、int、char、float…bool 类型值范围 true/false 可操作与、或、非int类型值范围-2147483648~2147483647可操作加、减、乘、除、模运算...2结构类型其值可以再分解为若干成分分量的数据类型。比如结构体 structstructCustomer{intnum;// 号数intpeople;// 人数// ...};6.2 什么是抽象数据类型ADT抽象数据类型ADT指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算抽象运算而不考虑计算机的具体实现。一句话总结抽象数据类型 逻辑结构 抽象运算ADT只关心做什么不关心怎么做。举个例子复数 ComplexADT Complex {数据对象 D {e1, e2 | e1, e2均为实数}数据关系 R {e1, e2 | e1是复数的实部e2是复数的虚部}基本操作 加法、减法、乘法…}我们只需要知道复数能做加减乘除不用关心它在计算机里具体怎么存、怎么算。本章小结 常见考点核心知识点回顾数据结构的定义相互之间存在特定关系的数据元素的集合三要素逻辑结构 存储结构 数据运算逻辑结构4种集合、线性、树形、图形存储结构4种顺序、链式、索引、散列ADT逻辑结构 抽象运算常见考试题型填空题数据的基本单位是______。答案数据元素______是构成数据元素的最小单位。答案数据项______是具有相同性质的数据元素的集合。答案数据对象数据结构的三要素、、______。答案逻辑结构、物理结构/存储结构、数据的运算多选题逻辑结构类型包括ABCDA. 树形B. 图C. 集合D. 线性E. 非线性这是按关系复杂程度分的大类不是具体类型1.单选题在数据结构中,从逻辑上可以把数据结构分成CA 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构2.用图形表示下列数据结构并指出它们是属于线性结构还是非线性结构。AS(D,R)D{ a,b,c,d,e,f }R{(a,e), (b,c), (c,a), (e,f), (f,d)}A 线性结构B 树形结构C 图形结构D 集合解析上述表达式可用图形表示为b→c→a→e→f→d3.BS(D,R)D{di | 1≤i≤5}R{(di , dj ), ij}A 线性结构B 图形结构C 集合D 树形结构4.线性结构有下列几种用二元组表示的数据结构画出它们分别对应的图形表示并指出它们分别属于何种结构A(K,R),其中K{a,b,c,d,e,f,g,h}R{r}r{a,b,b,c,c,d,d,e,e,f,f,g,g,h}解a→b →c →d →e →f →g →h5.树形结构B(K,R),其中K{a,b,c,d,e,f,g,h}R{r}r{d,b,d,g,d,a,b,c,g,e,g,h,e,f}6.图形结构C(K,R)K{1,2,3,4,5,6}R{r}r{(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}跟我一步步学慢慢走。未完待续。。。。
