数据结构概念

博主： wmicheng
发布时间：2025 年 02 月 10 日
32 次浏览
暂无评论
2582字数
分类：数据结构

## 数据结构概念

### 数据基本概念

`数据`是**信息的载体**，是描述客观事物属性的数、字符以及所有能**输入到计算机并且被计算机程序识别**和处理的符号的集合，数据是计算机程序加工的原料

> **数据元素、数据项**

**数据元素**是数据的基本单位，通常作为一个整体进行考虑和处理。
一个数据元素可由若干个**数据项**组成，数据项是构成数据元素的不可分割的最小单位

> **数据结构和数据对象**

- `结构`
 各个元素之间的关系![数据结构](https://wmicheng.top/images/note/img\数据结构.jpg)
- `数据结构`
 相互之间存在一种或者多种特定**关系**的数据元素的集合
- `数据对象`
 具有**相同性质**的数据元素的集合，是数据的一个子集![数据对象](https://wmicheng.top/images/note/img\数据对象.jpg)

### 数据结构三要素

**逻辑结构（数据元素之间的逻辑关系是什么）**

- **集合**
 各个元素`同属于一个集合`，别无其它关系
- **线性结构**
 数据元素之间是`一对一的关系`。 除了第一个元素，其它所有结构都有唯一的前驱； 除了最后一个元素，所有元素都有唯一后继
- **树形结构**
 
 数据元素之间是`一对多的关系`
- **图状结构**（网状结构）
 
 数据元素之间是`多对多`的关系

![数据结构三要素](https://wmicheng.top/images/note/img/数据结构三要素.jpg)

> **数据的物理结构（存储结构，计算机表示数据元素的逻辑关系）**

**顺序存储**
把**逻辑上相邻的元素存储在物理位置上也相邻的存储单元中**，元素之间的关系由存储单元的邻接关系来体现

**链式存储**
**逻辑上相邻的元素在物理位置上可以`不相邻`，借助指示元素存储地址的指针来表示元素之间的逻辑关系

**索引存储**
在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为`索引项`，索引项的一般形式是`（关键字，地址）`

**散列存储**
根据元素的关键字直接计算出该元素的存储地址，又称**哈希(Hash)存储**

- ### 数据的物理结构的特点
 
 - 若采用**顺序存储**，则各个数据元素在物理上必须是**连续的**；若采用**非顺序存储**，则各个元素在物理上可以是**离散的**。
 - 数据的**存储结构**会**影响存储空间分配的方便程度**
 - 数据的**存储结构**会**影响对数据运算的速度**

> **数据的运算**

- 概念
 施加在数据上的运算包括运算的定义和实现。
 **运算的定义**是**针对逻辑结构**，指出运算的功能；
 **运算的实现**是**针对存储结构**，指出运算的具体操作步骤。

### 数据类型和抽象数据类型

- 数据类型
 - 定义
 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
 - 原子类型
 **这个值不可再分的数据类型**
 比如`bool`类型和`int`类型
 - 结构类型
 **其值可以再分为若干成分（分量）的数据类型**
 比如C语言的结构体
- 抽象数据类型 **(ADT)**
 - 定义
 **抽象数据组织**及**与之相关的操作**
 使用数学化的语言定义数据的逻辑结构、定义运算，与具体实现无关
 - 涉及
 只涉及逻辑结构和数据的运算，不参与物理结构（存储结构）

### 小结

- 在探讨一种数据结构时
  - 定义逻辑结构（数据元素之间的关系）
  - 定义数据的运算（针对现实需求，应该对这种逻辑结构进行什么样的运算）
  - 确定某种存储结构，实现数据结构，并实现一些对数据结构的基本运算

---

## 算法概念

### 算法基本概念

`程序=数据结构+算法`
其中数据结构用于**把现实世界的问题信息化，将信息存进计算机。同时实现对数据结构的基本操作**。
算法用于处理这些信息以**解决实际问题**

### 算法的五大特性

- `有穷性`
 一个算法必须总在**执行有穷步之后结束**，并且每一步都可以在 **有穷的事件内完成**
 **算法是有穷的**，但是 **程序可以是无穷的**
- `确定性`
 算法中的每一条指令必须有确切的含义对于 **相同的输入**只能得出**相同的输出**
- `可行性`
 算法中描述的操作都可以通过已经实现的**基本运算执行有限次**来实现
- `输入`
 一个算法有**零个或者多个输入**，这些输入取自于某个特定的对象的集合
 注意：随机数的输入是电脑
- `输出`
 一个算法有**一个或者多个输出**，这些输出是与输入有某种特定关系的量

### 好算法的特质（`设计算法的目标`）

- `正确性`
 算法应该能够正确地解决问题
- `可读性`
 算法应具有良好的可读性，以帮助人们理解
 算法可以用**伪代码**描述甚至是可以用文字描述，重要的没有歧义地描述出解决问题的步骤
- `健壮性`
 输入**非法数据**的时候，算法**能适当地作出反应或者调整**，而不会产生莫名其妙的结果
- `高效率和低存储需求`
 
 - 高效率
 **执行速度快，时间复杂度低**
 - 低存储需求
 **不占用内存，空间复杂度低**

### 小结

![时间复杂度](https://wmicheng.top/images/note/img\时间复杂度.png)

![空间复杂度](https://wmicheng.top/images/note/img\空间复杂度.png)

---

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

数据结构概念

wmicheng • 2025 年 02 月 10 日

## 数据结构概念

### 数据基本概念

> **数据元素、数据项**

> **数据结构和数据对象**

### 数据结构三要素

**逻辑结构（数据元素之间的逻辑关系是什么）**

![数据结构三要素](https://wmicheng.top/images/note/img/数据结构三要素.jpg)

> **数据的物理结构（存储结构，计算机表示数据元素的逻辑关系）**

**顺序存储**
把**逻辑上相邻的元素存储在物理位置上也相邻的存储单元中**，元素之间的关系由存储单元的邻接关系来体现

**链式存储**
**逻辑上相邻的元素在物理位置上可以`不相邻`，借助指示元素存储地址的指针来表示元素之间的逻辑关系

**索引存储**
在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为`索引项`，索引项的一般形式是`（关键字，地址）`

**散列存储**
根据元素的关键字直接计算出该元素的存储地址，又称**哈希(Hash)存储**

> **数据的运算**

### 数据类型和抽象数据类型

### 小结

---

## 算法概念

### 算法基本概念

### 算法的五大特性

### 好算法的特质（`设计算法的目标`）

### 小结

![时间复杂度](https://wmicheng.top/images/note/img\时间复杂度.png)

![空间复杂度](https://wmicheng.top/images/note/img\空间复杂度.png)

---

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构概念

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款