【水滴计划】数据结构入门竟如此简单？
🌕写在前面
Hello🤗大家好啊，我是kikokingzz，名字太长不好记，大家可以叫我kiko哦～
从今天开始，我将正式开启一个新的打卡专题——【数据结构·水滴计划】，没错！这是今年上半年的一整个系列计划！本专题目的是通过百天刷题计划，通过题目和知识点串联的方式，刷够1000道题！完成对数据结构相关知识的全方位复习和巩固；同时还配有专门的笔记总结和文档教程哦！想要搞定，搞透数据结构的同学
🎉🎉欢迎订阅本专栏🎉🎉
🍊博客主页：kikoking的江湖背景🍊
目录
🌕写在前面
🍺知识点1：数据结构的基本概念
🥝1.1 基本术语
🍺1.2 数据结构的三要素
🥝要素1：逻辑结构
（1）集合结构
（2）线性结构
（3）树形结构
（4）图状结构
🥝要素2：存储结构
（1）顺序存储
（2）链式存储
（3）索引存储
（4）散列存储（哈希存储）
🥝如何区分逻辑结构与存储结构？
🥝要素3：数据的运算
📜习题检测
🥝附加内容：抽象数据类型
（1）原子类型
（2）结构类型
（3）抽象数据类型（ADT）
🌕写在最后
热爱所热爱的， 学习伴随终生，kikokingzz与你同在！❥(^_-)
🍺知识点1：数据结构的基本概念
🥝1.1 基本术语
🍊1.数据
数据是信息的载体，是计算机程序加工的原料。数据不仅仅包括整型、实型等数值类型，还包括字符、声音、图像、视频等非数值类型。
🍊2.数据元素
数据元素是数据的基本单位，在计算机中通常作为整体处理，一个数据元素可以由若干个数据项组成。比如在人类中，人就是数据元素，可以有眼、耳、鼻、嘴、手、脚这些数据项；也可以有姓名、年龄、性别、出生地址、联系电话等数据项。
🍊3.数据项
数据项是构成数据元素的不可分割的最小单位
🍊4.数据对象
数据对象是性质相同的数据元素的集合，是数据的子集。
Q1：什么叫性质相同呢？
A1：指数据元素具有相同数量和类型的数据项；例如下图中，“学生”这个数据对象，就是这三个学生数据元素的集合。
🍊5.数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，这种数据元素相互之间的关系称为结构(Structure)。
数据结构包括三个方面的内容：逻辑结构、存储结构、数据的运算。
一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
🍺1.2 数据结构的三要素
🥝要素1：逻辑结构
Q1：逻辑结构是什么？
A1：逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构，集合、图、树是典型的非线性结构。
（1）集合结构
（2）线性结构
除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
（3）树形结构
（4）图状结构
📜001.题目难度 ⭐️
001.以下数据结构中，（ ）是非线性数据结构。A.树B.字符串C.队列D.栈🍊详细题解：
树和图是典型的非线性结构，其他选项都属于线性数据结构。
✅正确答案：A
✨✨✨我是分割线✨✨✨
🥝要素2：存储结构
Q1：存储结构是什么？
A1：存储结构是指数据结构在计算机中的表示，也称物理机构。它包括数据元素的表示、关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据结构的存储结构主要有：顺序存储、链式存储、索引存储、散列存储。
（1）顺序存储
定义：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
优点：可以实现随机存取；每个元素占用最少的存储空间。
缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
案例：采用顺序存储结构，来实现逻辑结构为线性结构的元素关系（如下图）。
（2）链式存储
定义：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
优点：不会出现碎片现象，能充分利用所有存储单元。
缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
案例：采用链式存储结构，来实现逻辑结构为线性结构的元素关系（如下图）。
（3）索引存储
定义：在存储元素信息的同时，还建立附加的索引表：索引表中的每项称为索引项，其一般形式为(关键字，地址）。
优点：检索速度快。
缺点：附加的索引表额外占用存储空间；增加和删除数据时也要修改索引表，因此会花费较多时间。
案例：采用索引存储结构，来实现逻辑结构为线性结构的元素关系（如下图）。
（4）散列存储（哈希存储）
定义：根据元素的关键字直接计算出该元素的存储地址。
优点：检索、增加和删除结点的操作都很快。
缺点：若散列函数不好，可能会出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
✨✨✨我是分割线✨✨✨
🥝如何区分逻辑结构与存储结构？
首先，我们要知道算法的设计取决于逻辑结构，而算法的实现取决于所采用的存储结构。
题目：将打乱的4个英文字母按字母顺序存储排列（c、b、d、a）step1.设计的思路第一步那肯定就是考虑以什么形式去排列这4个英文字母。
通常来说，顺序排列我们会采用线性的逻辑结构，也就是上图右侧的方式，而不会采用集合的逻辑结构，因为集合没办法体现出数据元素的先后逻辑关系。
step2.确定了逻辑结构是线性结构后，就要考虑如何实现这个逻辑结构，即确定存储结构。
这边考虑了两种存储结构来实现：（1）链式存储、（2）顺序存储；两种存储方式各有特点。如果内存中有一段连续空间，那么可以采用顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中；如果内存空间不连续，可以借助指示元素存储地址的指针来表示元素之间的逻辑关系。
综上可见，算法的设计首先得想出一个逻辑结构；然后针对这个逻辑结构去选择更好的存储结构来实现算法！同时数据的存储结构也会影响存储空间分配的方便程度。
📜002.题目难度 ⭐️⭐️⭐️
002.以下关于数据结构的说法中，正确的是（ ）。A.数据的逻辑结构独立于其存储结构B.数据的存储结构独立于其逻辑结构C.数据的逻辑结构唯一决定其存储结构D.数据结构仅由其逻辑结构和存储结构决定🍊详细题解：
A. 数据的逻辑结构是以面向问题的角度出发的，只采用抽象表达方式，独立于存储结构的。例如：在解决字母排序问题时，我们首先确定的应当是逻辑结构，即各数据元素的逻辑关系，而存储结构是依赖于我们确定完了的逻辑结构才选定的。
B. 数据的存储结构是逻辑是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。如下图：右侧两种不同的存储结构，都是线性逻辑结构在计算机存储上的不同反映，即存储结构是逻辑结构在计算机上的映射。
C. 由上图可见，同一个逻辑结构，可以对应两种不同的存储结构。
D. 数据结构包括三个要素（逻辑结构、存储结构、数据的运算），缺一不可。
✅正确答案：A
✨✨✨我是分割线✨✨✨
🥝要素3：数据的运算
Q1：数据的运算是什么？
A1：施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
题目：在该序列中的元素a后插入e（a、b、c、d）step1.运算的定义是针对逻辑结构的，指出运算的功能。
通过上图可以明显看出，该运算的功能是插入功能，是在逻辑结构上对该功能进行定义的。
step2.运算的实现是针对存储结构的，指出运算的具体操作步骤。
上图两种不同存储结构实现同一运算，可以发现，不同存储结构实现插入功能的实现步骤是不同的，即运算的实现随存储结构的不同而改变：
- 采用链式存储：运算的实现是通过改变元素的指针得意完成的。
- 采用顺序存储：运算的实现是通过将后续元素统一下移完成的。
📜习题检测
📜003.题目难度 ⭐️⭐️
003.在存储数据时，通常不仅要存储各数据元素的值，而且要存储（ ）。A.数据的操作方法B.数据元素的类型C.数据元素之间的关系D.数据的存取方法🍊详细题解：
数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，这种数据元素相互之间的关系称为结构(Structure)。
A. 存储数据时无需存储操作方法，存储数据结构时才需要。
B. 数据元素的类型隐含于数据元素中。
C. 存储数据时，不仅要存储数据元素的值，更应该要存储数据元素之间的关系，即存储逻辑结构，这样才可以将数据有效地存储利用。
D. 数据的存取方法是A项操作方法的一部分。
✅正确答案：C
📜004.题目难度 ⭐️⭐️
004.对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？🍊详细题解：
应该注意到，数据结构是由三要素组成的：逻辑结构、存储结构、数据运算。因此两种不同的数据结构，它们的逻辑结构与物理结构可以相同，这是因为，虽然逻辑结构与物理结构相同，但它们的数据运算不同，其最后组成的数据结构也不同。
例如：二叉树与二叉排序树，是两种不同的数据结构。二者可均可以使用二叉树的逻辑结构与物理结构，但是建立树、插入结点、删除结点和查找结点等数据运算是不同的。
📜005.题目难度 ⭐️⭐️
005.试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。🍊详细题解：
对于相同的逻辑结构——线性结构来说，我们可以采取两种不同的存储方式：（1）链式存储、（2）顺序存储。
当我们进行插入元素的操作时，链式存储只需要更改元素的后向指针，时间复杂度为O(1)；而对于顺序存储来说，需要将插入位置的后面的全部元素统一移动，时间复杂度为O(n)。
✨✨✨我是分割线✨✨✨
🥝附加内容：抽象数据类型
Q1：什么是数据类型？
A1：数据类型是一个值的集合和定义在此集合上的一组操作的总称。
Q2：数据类型有哪些？
A2：数据类型一般有三种，主要有原子类型、结构类型和抽象数据类型；例如：
（1）原子类型
原子类型是一种其值不可再分的数据类型；例如整型、字符型、指针、枚举值、逻辑值都属于原子类型。
原子类型 值的范围 可进行的操作 bool类型 true、false 与、或、非 int 类型 -2147····~2147··· 加、减、乘、除、模 （2）结构类型
结构类型是一种其值可以再分解为若干成分（分量）的数据类型；例如结构体。
struct Coordinate{ //这是一个表示坐标的结构类型 int x; //横坐标 int y; //纵坐标};
结构类型 值的范围 可进行的操作 struct 类型 内部分量的范围（int的范围） 加、减··· 对于上面这个结构体，该结构体（结构类型）可以拆分成两个分量（两个int型-原子类型），且这两个分量是有一定逻辑关系（横纵坐标关系）。
（3）抽象数据类型（ADT）
抽象数据类型是抽象数据组织及与之相关的操作。对于数据结构而言，定义抽象数据组织，就相当于定义了数据结构的逻辑结构；定义了抽象数据类型的相关操作，就好比定义了数据结构的存储结构与数据的运算。因此我们说：定义了一个ADT，就是在定义一种数据结构。
📜006.题目难度 ⭐️
006.可以用（ ）定义一个完整的数据结构。A.数据元素B.数据对象C.数据关系D.抽象数据类型🍊详细题解：
D. 抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象、数据关系、基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义。
B、C：是抽象数据类型的三元组中的一部分。
A. 数据元素是数据的基本单位，在计算机中通常作为整体处理，一个数据元素可以由若干个数据项组成。而数据结构是彼此构成特定关系的数据元素的集合。
✅正确答案：D
🌕写在最后
数据结构的世界是相当丰富的，内容方向繁多，但只要一步一个脚印，跟随【水滴计划】，水滴石穿，吃透、搞懂、拿捏住数据结构是完全没有问题的！后期该系列还会有视频教程和经验分享，关于更多这方面的内容，请关注本专栏哦！
热爱所热爱的， 学习伴随终生，kikokingzz与你同在！❥(^_-)
