数据结构——（一）绪论

---

👉数据元素整体思维导图 欢迎补充

一、基本概念❤️

1.1基本术语⭐️

（1）数据
客观事务属性的数字、字符。

（2）数据元素
数据元素是数据的基本单位，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分的最小单元。
下面我们举一个例子来说明一下，下面就是一个学生表

学号	姓名
0711	小唐

如图所示，其中的学生表就是我们的数据元素，然后学号和姓名分别对应的就是我们的数据项。

（3）数据对象
数据对象，也就是我们相同数据元素的集合，例如下面这个学生表

学号	姓名
0711	小唐
0403	小宋
0219	小黄

如图所示，这样多条记录的合集就是我们数据对象啦

（4）数据类型

1）原子类型：其值不可再分数据类型

2）结构类型：其值可以再分的数据类型

列如上面面这个结构体，还可以分为 int和string

3）抽象数据类型：抽象数据组织及其相关操作 这个你就可以理解为刚刚学生表+学生表对于的操作（增删改查）

---

1.2数据结构三要素⭐️⭐️⭐️

数据结构是相互之间，一种或者多种，特定关系的元素集合，数据元素之间的相互关系，我们称只为结构，数据元素主要分为以下三要素

1.逻辑结构

2.物理（存储）结构

顺序结构：相邻的元素存储在物理结构上的位置也相邻，只能使用相邻的一整块存储结构，可能会有较多的外部碎片。使用数组来存，就是一个非常明显的顺序结构。

链式结构：逻辑相邻，但是我们的物理结构的位置可以不相邻，因为借助指针，所以会占有额外的存储空间，读取元素时，也只能进行顺序读取。

索引结构：外部建立索引表，通过索引表读取，每一项被称之为索引项【index：key】，比如省会的索引【湖南：长沙】

散列结构：根据元素的关键字来计算出元素的存储位置，又称Hash存储，在后续散链表的学习中，index=元素%key，我们会进行进一步讲解

tips：说到这里，部分读者逻辑和物理结构有点区分不了，我们可以这样来理解，比如在树形结构中，我可以既可以采取顺序存储，也可以采取链式存储的方式，逻辑结构独立于我们的存储结构，我们后续章节，也基本由顺序存储讲到链式存储

3.数据的运算
对于我们数据结构的操作：运算的定义正对于逻辑结构，实现针对于物理结构

二、算法及其评价❤️

2.1主要特性⭐️

1.输入：有0个或者多个输入
2.输出：有1个或者多个输出
3.可行性：所描述操作可以通过已经实现的基本运算执行有限次操作来实现
4.正确性：相同输入得到相同输出
5.有穷性：算法不是死循环

2.2算法评价⭐️

1.可读性：可以让接触到的人便于理解
2.正确性：算法可以正确的解决问题
3.健壮性：对于非法的数据可以自己进行处理
4.高效率和低容量需求：效率高，存储空间小

2.3 时间复杂度⭐️⭐️⭐️

给大家推荐这个视频，讲的很清楚
单层基本思路
1.写出每一趟的躺数t
2.写出每一次躺数t，里面元素的变化
3.求元素和躺数的关系
4.找到元素的终止条件
5.求解

多层基本思路
1.从i开始一直到循环结束
2.写出每一个i中经理多少次循环
3.求和

数据结构——时间复杂度计算

2.4 空间复杂度⭐️

依据算法规模来进行求解，S（n）=O（g(n)）,一般来说所使用的辅助空间都是常量，这里的空间复杂度会在学邻接矩阵的时候有一个比较详细的了解