初识数据结构（概念篇）

落日映苍穹つ 2023-07-11 11:03 22阅读 0赞

## 1.1 数据结构是什么 ##

数据结构+算法=程序

数据结构是计算机存储、组织数据的方式

## 1.2 数据结构基本概念 ##

### 1.2.1 基本概念 ###

1.  数据（data）：所有能输入到计算机中的描述客观事物的符号
    
     *  数值型数据
     *  非数值型数据
2.  数据元素（data element）：数据的基本单位。（类似于数据库的一条数据（一整行））
3.  数据项（data item）：独立含义的数据最小单位，也称域（类似于数据库中表的一条属性）

> 三者的关系：数据 > 数据元素 > 数据项  
> 例如：学生表 > 个人纪录 > 学号，姓名……

1.  数据对象（Data Object）：相同特数据元素的集合，是一个数据的子集
    
     *  整数数据对象：N=\{0,-1，+1，+2，-2……\}
     *  学生数据集合：学生记录的集合
2.  数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合

### 1.2.2 数据结构的两种层次及分类 ###

*  逻辑结构:数据元素之间抽象化的相互关系，与数据的存储无关，是一种从具体问题中抽象出来的数学模型（个人理解:抽象化的一种关系）
    
    逻辑结构可分为：集合，线性结构，树形结构，图形结构  
    1. 集合：数据元素除“同属于一个集合”外，无其他关系（个人理解：就是没有其他运算或者操作）  
    2. 线性结构：一个对一个，例如线性表，栈，队列，串等等

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TbcIvjzL-1583368582986)(图1-1.png)\]][img-TbcIvjzL-1583368582986_1-1.png]  
3. 树形结构：一个对多个，即树

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MU7TWBIQ-1583368582987)(图1-2.png)\]                            图1-2        树形结构简图][img-MU7TWBIQ-1583368582987_1-2.png_ _1-2]  
4. 图形结构：多个对多个，即图  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-26xKTSa2-1583368582988)(图1-3.png)\]                            图1-3        图形结构简图][img-26xKTSa2-1583368582988_1-3.png_ _1-3]

> 也可分为：线性结构和非线性结构  
> 线性结构：有且只有一个开始和一个终端结点，且所有结点都最多只有一个直接前趋和一个后继。如：线性表，队列，栈，串，数组，广义表 .  
> 非线性结构：一个节点可能有多个直接前趋和直接后继。如：树，图

*  存储结构：数据元素及其关系在计算机存储器中的存储方式

1.  顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系（即一段连续的内存空间，如数组）
2.  链式储存结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系（离散的内存空间，通过直接进行联系，如链表）

> 逻辑结构和存储结构都相同，但运算规则不同，则是不同的数据结构。如栈和队列

数据结构基本运算：插入，删除，修改，查找，排序

> 对于一种数据结构来说，它的逻辑结构唯一，但数据结构不唯一，而运算的实现依赖于存储结构

## 1.3 抽象数据类型（ADT） ##

ADT：Abstract Data Type

表示一种更高层次的数据抽象，由用户定义表示问题的数据模型，由基本数据类型组成，并包括一组相关的操作。（类似于离散数学中自定义的代数系统）

ADT = （D，S，P）

D：数据对象

S：D上的关系集

P：D上的操作集

常用定义格式：

ADT抽象数据类型名{
        数据对象：<数据对象的定义>
        数据关系:<数据关系的定义>
        基本操作：<基本操作的定义>
    }ADT抽象数据类型名

## 1.4 算法分析入门 ##

> 算法的定义：一个有穷的指令集，为解决某一特定任务规定了一个运算序列。

### 1.4.1 认识算法 ###

*  **算法的特性**  
    输入：0至多个输入  
    输出：一个或多个输出  
    确定性：每一步都是确切的。  
    有穷性：应该在运行有穷步数后结束  
    可行性:所有操作能通过已实现的基本操作运算来实现
 *  **如何评价一个算法**  
    两种考虑  
    第一种：首先满足正确性，其次考虑高效性（即时间空间复杂度），其次是健壮性，最后是可读性  
    第二种：首先满足正确性，其次考虑可读性，其次是健壮性，最后是高效性

> 两种考虑来讲反映了计算机硬件的快速发展，不在吝啬于内存空间。

### 1.4.2 时间复杂度 ###

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：

T(n)=O(f(n))

表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6z6tuS2u-1583368582988)(图1-4.png)\]图1-4       渐进时间复杂度图][img-6z6tuS2u-1583368582988_1-4.png_1-4]

数学符号“O”的定义为：

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n) = O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤Cf(n)。

> n越大算法的执行时间越长 排序：n为记录数 矩阵：n为矩阵的阶数 多项式：n为多项式的项数 集合：n为元素个数 树：n为树的结点个数 图：n为图的顶点数或边数

**一般考虑时间复杂度时不考虑f（n）的真实函数，而只需要计算出它的量级即可**

如：

for( i = 0; i < n; i++)
        for( j = 0; j <= i; j++)
            c[i][j] = a[i][j] + b[i][j];
    /*先寻找基本语句，不难看出c[i][j] = a[i][j] + b[i][j];为基本语句，解下来找出他的语句频度即f(n)，这个语句执行的次数为n*(n+1)/2,但我们只需要它的量级也就是n^2,所以它的时间复杂度为O(n^2)
    */

**一般来说，算法的时间复杂度由嵌套最深层语句的频度决定。**

**时间复杂度的递增顺序为：**

**O(1) < O(logn) < O(n) < O(n\*logn) < O(n^2) < O(……) < O(n^k) < O(2^n)**

有时候也会有达到O(n^1/2)根号n的复杂度

### 1.4.3 空间复杂度 ###

空间复杂度的判断比较简单。考虑两个因素

1.  算法本身要占据的空间
2.  算法要使用的辅助空间（开辟一个新的数组等等）

[img-TbcIvjzL-1583368582986_1-1.png]: https://img-blog.csdnimg.cn/202003050837416.png
[img-MU7TWBIQ-1583368582987_1-2.png_ _1-2]: https://img-blog.csdnimg.cn/20200305083817646.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70
[img-26xKTSa2-1583368582988_1-3.png_ _1-3]: https://img-blog.csdnimg.cn/20200305083832180.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70
[img-6z6tuS2u-1583368582988_1-4.png_1-4]: https://img-blog.csdnimg.cn/20200305084009574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1,size_16,color_FFFFFF,t_70