【数据结构导论】第 1 章：概论

浅浅的花香味﹌ 2022-08-28 06:44 171阅读 0赞

# 一、学习大纲 #

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16][]

--------------------

# 二、引言 #

## （1）数据结构的概念 ##

> 数据结构(Data structure）是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

--------------------

## （2）计算机解决问题的步骤 ##

> ➢ 建立数学模型
> 
> ➢ 设计算法
> 
> ➢ 编程实现算法

--------------------

## （3）数据结构主要研究 ##

> ① 数据（计算机加工对象）的逻辑结构。
> 
> ② 实现各种基本操作的算法。
> 
> ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

--------------------

## （4）学习数据结构的目的 ##

> ➢ 掌握常用的数据结构及其应用。
> 
> ➢ 学会合理地组织数据， 有效地表示数据和处理数据。
> 
> ➢ 掌握算法设计技术和分析技术。
> 
> ➢ 掌握使用计算机解决问题的方法和技能，提高程序设计水平。

--------------------

# 三、基本概念和术语 #

## （1）数据 ##

> **数据（Data)：****所有被计算机存储、处理的对象。**

--------------------

## （2）数据元素 ##

> **数据元素（Data Element）：** **数据的基本单位， 是运算的基本单位。常常又简称为元素。**

--------------------

## （3）数据项 ##

> **数据项（Data Item）：** **数据元素常常还可分为若干个数据项，数据的不可分割的最小标识单位。**
> 
> 在数据库中 **数据项** 又称为  **字段**  或  **域** 。它是数据的 **不可分割的最小** **标识单位** 。

> 实际问题中的数据称为 **原始数据**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_16_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

--------------------

## （4）数据结构 ##

> 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_15_color_FFFFFF_t_70_g_se_x_16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

--------------------

## （5）数据的逻辑结构 ##

> **逻辑结构（Logical Structure）：**
> 
> 指数据元素之间的结构关系。
> 
> **与数据元素本身的形式、内容、相对位置、所含节点个数无关。**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_17_color_FFFFFF_t_70_g_se_x_16][]

--------------------

## （6）数据的存储结构 ##

> **存储结构 / 物理结构（Physical Structure）：** 
> 
> 指数据结构在机内的表示，数据的逻辑结构在计算机中的实现。

> 数据在计算机内的表示形式称为  数据的存储结构

> 存储结构的主要部分：
> 
> ❖ 存储结点（每个存储结点存放一个数据元素）
> 
> ❖ 数据元素之间关联方式的表示

> **数据结构的存储**包含：数据元素的存储、数据元素逻辑关系的存储

> **存储结构**可分为： 顺序存储结构 、 链式存储结构 、 索引存储方式 和 散列存储方式  等。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

> 最基本的存储结构分类：顺序存储结构 、链式存储结构

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

--------------------

## （7）运算 ##

> 运算是指在某种逻辑结构上施加的操作，即**对逻辑结构的加工**。

> **线性表、栈和队列** 中的元素具有相同的逻辑结构（即 **线性结构** ），但有不同的运算集，它们是不同的数据结构。

--------------------

# 四、算法及描述 #

> **算法** **规定了求解给定类型问题所需的** **所有“处理步** **骤”** **及** **执行顺序** **，使给定类型问题能在** **有限时间** **内** **被机械的求解。**

> **算法必须使用某种语言描述：** 
> 
> ❖ **程序** 
> 
> ❖ **介于自然语言和程序设计语言的伪代码** 
> 
> ❖ **非形式算法（自然语言）** 
> 
> ❖ **框图(N-S图)** 
> 
> *《数据结构导论》教材中使用了 类C语言描述算法*

--------------------

# 五、算法分析 #

## （1）评价算法好坏的因素 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 9][]

--------------------

## （2）选出最优算法通常考虑的两个度量 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 10][]

--------------------

## （3） 时间复杂度 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 11][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_15_color_FFFFFF_t_70_g_se_x_16 1][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 12][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 13][]

--------------------

### **【示例】①**  ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 14][]

--------------------

### **【示例】②** ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 15][]

--------------------

### **【示例】③**  ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 16][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 17][]

--------------------

### **【示例】④**  ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 18][]

--------------------

### **【示例】⑤** ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 19][]

--------------------

### **【示例】⑥** ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 20][]

--------------------

## （4）空间复杂度 ##

> 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

> 一个算法在执行期间所需要的存储空间量包括以下部分：
> 
> ➢ 程序代码所占用的空间；
> 
> ➢ 输入数据所占用的空间；
> 
> ➢ 辅助变量所占用的空间；

> 估算算法空间复杂度时，一般**只分析辅助变量所占用的空间**

--------------------

### **【示例】①**  ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 21][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ffb593444c1f4c1cb2978a5596366ec5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/fa78713ed3b04d7db8e707478c4ee06e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7d0d4fdc19ee4d45939cbd68c9f27a95.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/e2d04ce46dc4473ebf7cf81248c1e97a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/bf2d31504cf04bc1bdf28e55a58b75e9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/67ea8f932a7a41069ec069b1d69a3c5f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/fb0b52bc56b540ba8bc16c52fc4e41db.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/25be5b20119e42e5b0a25dd52dca8aeb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/c3e04226120847aba68610f99dcb97f0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/6639cf1c803d4433b92a2b30f5eb27ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/fee9a0739b374ad2b4a8298b15d10d20.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/cc349f3f933d44b6b4da978fdfc345a0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/245a7220106142a69a4a8d1c0528aedc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/643c798e2e1d450294d468d78a6c1d17.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/183ceaa8ebf943b78c56ad6065141635.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_15_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/6f346a10c8db4401b800092ec7fd5fe5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/5d02d30d6612457f919bfbef62f3f9e0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/fd96f050b8874df6b71511e05c8a2454.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/18e270c2775748dfb9886b0b0e86d2e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/c09476416a6848adae8c12050f0cf467.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/9902fedb7e8a47d99cd21431e1d9cb14.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 17]: /images/20220828/193973728be74f6db1f132bab3455622.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 18]: /images/20220828/1da0f8fc504f408eb88b721afcf54e0a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 19]: /images/20220828/092cd316513846d1b61433da31ea7805.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 20]: /images/20220828/1ea3849587624224a56177821864b241.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6aG-5LiJ5q6H_size_20_color_FFFFFF_t_70_g_se_x_16 21]: /images/20220828/f5d66fde0f704d9ebb7271923140926b.png