数据结构基本概念术语学习

数据结构

• 第一章 绪论
• 一、什么是数据结构/li>
• 二、基本概念和术语
• 三、算法和算法分析
• • 算法
  • 算法效率的度量
  • 怎么测试算法效果/li>
  • • 一、在事前分析估算的方法下：
    • 二、实践中，结合事前和事后两种办法一起计算。
  • 空间复杂度

第一章 绪论

最近为了考软件设计师在补知识，先从数据结构、算法这些没有系统学习的部分下刀。
写这个系列是为了加深和整理对数据结构学习的印象。

一、什么是数据结构/h2>

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

eg:一个父亲三个儿子，一个儿子两个孙子。
           Group=(P,R)
其中：P={A,B₁,…B_N,C₁₁,…,C_NM,1≤N≤3,1≤M≤2}
           R={R₁,R₂}
           R₁={A,B_i,1≤i≤N,1≤N≤3}
           R₂={B_i,C_ij,1≤i≤N,1≤N≤3,1≤j≤M,1≤M≤2}
P为数据元素的有限集，R为P上关系的有限集
A为父亲，B为儿子，C为孙子

二、基本概念和术语

1、数据：是客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称
eg:图像，声音，文件等。

2、数据元素：是数据的基本单位 。
一个数据元素可由若干个数据项组成，数据项是数据不可分割的最小单位。
eg:一本书的书目信息是一个数据元素，其中书名，作者名等为一个数据项。

3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。
eg:包子数据对象是集合A={‘牛肉包’,‘鲜肉包’,‘脆笋包’,…}

4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
这种数据元素之间的关系称为结构。
数据元素之间的关系多种多样，通常有4类基本结构：
（1）集合，是数据元素之间关系及为松散的一种结构。
（2）线性结构： 结构中的数据元素之间存在一个对一个的关系。
（3）树形结构：结构中的数据元素之间存在一个对多个的关系。
（4）图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。

5、逻辑结构：结构定义中的关系描述的是数据元素之间的逻辑关系。
为了在计算机中表示并实现所研究的逻辑结构，又有一个概念：

6、存储结构：数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。

可以用由若干位组合形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。
当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

这里讲一下我理解的顺序存储结构和链式存储结构：
eg:存入两个位串：豆浆、油条。
顺序存储结构：借助元素在存储器中的相对位置来表示元素之间的逻辑关系。
当想要取出 豆浆油条 时，豆浆油条就要按相邻顺序存入存储器。如图（a）

7、数据类型：数据类型是和数据结构密切相关的一个概念。是一个值的集合和定义在这个值集上的一组操作的总称。
eg:整形，其值集为一系列整数，可以进行加减乘除等运算。

按值的不同特性，高级程序语言中的数据类型可分为两种：
一类是非结构的原子类型：原子类型的值是不可分解的。
eg:整形、字符型、枚举类型，位，字节，字等。

另一类是结构类型：结构类型的值是由若干成分按某种结构组成的，是可以分解的，它的成分可以是非结构的，也可以是结构的。
eg:数组

8、抽象数据类型（ADT）：抽象数据类型的定义仅取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。

就是说，现在的高级语言，在1+2=3这样的运算中，不需要管底层位的操作及数据表示，只需要管数学上求和的抽象逻辑。

抽象数据类型和数据类型实质上是同一个概念，抽象的意义在于数据类型的数学抽象性。

抽象数据类型按其值的不同特性，分为一下3种类型：
原子类型： 值是不可分解的。
eg:个位整数。

固定聚合类型：值由确定数目的成分按某种结构组成
eg:豆浆，可以由豆和浆按一定的次序组成。

可变聚合类型：值的数目不确定。
eg:值个数不确定、可变的数组。

后两种类型为结构类型。

抽象数据类型可表示为：
ADT{ 数据对象，数据关系，基本操作 }

基本操作 {   操作名（参数）
                    初始条件
                    操作结果 }

多型数据类型：是指其值的成分不确定的数据类型。但是不论其元素具有何种特性，元素之间的关系相同，基本操作也相同。
eg:int,float…等其他可以进行关系运算的数据类型，具有相同的数学抽象特性故称为多型数据类型。

三、算法和算法分析

算法

算法： 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

有5个重要特性：有穷性，确定性，可行性，输入，输出。

算法设计的要求：正确性，可读性，健壮性，效率与低存储量需求。

就是要写个人能看得懂的，能应对非法输入的，逻辑正确，还不占空间，执行效率还高的完美程序。

算法效率的度量

1、事后统计的方法：缺点（1）必须先运行程序。（2）依赖计算机硬件、软件等环境因素，容易掩盖算法本身的优劣。

2、事前分析估算的方法：
   （1）依据的算法采用何种策略。
   （2）问题的规模。
   （3）书写程序的语言，语言越高级，执行效率就越低。
   （4）编译程序所产生的机器代码的质量。
   （5）机器执行指令的速度。

因为程序运行依赖于硬件和编程语言，所以使用绝对的时间单位衡量算法的效率是不合适的，算法运行工作量的大小依赖于问题的规模。

一个算法是由控制结构（顺序，分支和循环3种）和原操作（指固有数据类型的操作）构成，算法时间取决于两者的综合效果。

怎么测试算法效果/h2>

一、在事前分析估算的方法下：

1、在同一问题的不同算法里，选取对于问题来说是基本操作的原操作，
多数情况下它是最深层循环语句中的原操作，以该操作重复执行的次数 n （频度）作为算法的时间量度。

随着问题规模 n 的增大，算法执行时间的增长率和 次数 n 的增长率相同，这就叫做算法的渐进时间复杂度又叫时间复杂度。
这就是项目越大越复杂，用的时间就越多。

eg:  ①{++x;}
       ②for(i=1;i        ③for(i=1;i             for(k=1;k

含基本操作 ++x 的频度分别为：1，n，n² ，那么他们的时间复杂度为 O(1), O(n), O(n² ),分别叫做 常量阶，线性阶，平方阶。如果项目规模n特别大的时候，建议少用指数阶O(2ⁿ)的算法。

2、如果难以计算频度，只需求出关于n的增长率或阶即可。

eg： 输入数据集的冒泡排序，随着输入的数据不同，基本数据的执行次数可能为0也可能特别多次。

那这种情况下，可以计算它的平均值，即考虑所有可能的输入数据集的期望值，此时时间复杂度为平均时间复杂度。

也可以做最坏的打算，看算法在最坏的情况下它的运行效率。

二、实践中，结合事前和事后两种办法一起计算。

eg: 事后算出执行时间为12秒的10 * 10的算法。时间复杂度为n³
那么31*31 的时间复杂度可以为 （31/10)³ * 12=358 秒
31 * 31 中有3.1³个12秒

空间复杂度

空间复杂度： 算法所需存储空间的量度。

一个程序除了需要存储空间来寄存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

若额外空间相对于输入量来说是常数，则称此算法为原地工作。

第一章学习了一些笼统的概念，后期希望能在程序设计里对应上这些概念，进一步学习。
2021-02-19

来源：蜉蝣杂技