一、什么是数据结构

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。
2. 主要分类：数据的逻辑结构、数据的存储结构及其对应的算法

• 逻辑结构：反映数据之间的逻辑关系，是对数据之间关系的描述，主要有集合、线性表、树、图等四种结构。
• 物理结构：反映数据在计算机内部的存储安排，是数据结构在计算机中的实现方法。主要有顺序、链接、散列、索引等四种基本存储结构，并可以根据需要组合成其它更复杂的结构。
• 算法：数据进行处理的方法。

3. 涵盖内容联系图：
   

二、基本概念

1. 数据(Data)
数据是对信息的一种符号表示，是输入到计算机中并被计算机程序处理的符号的总称。包括文字、表格、图象等。
2. 数据元素(Data Element)
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。
3. 数据对象(Data Object)
数据对象：是性质相同的数据元素的集合。是数据的一个子集。
4. 数据结构(Data Structure)
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
5. 抽象数据类型（Abstract Data Type，简称ADT）
ADT是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

• 系统开发时，很多时候需要按需自主定义ADT。
• 主要包括：原子类型、固定聚合类型、可变聚合类型。
• 线性表、栈、数组、二叉树都属于抽象数据类型。

6. 数据结构(Data Structure)
数据结构是研究数据元素（Data Element）之间抽象化的相互关系（逻辑结构）和这种关系在计算机中的存储表示（物理结构），并对这种结构定义相适应的运算，设计出相应的算法。
（1）逻辑结构：数据之间的相互关系称为逻辑结构。通常分为 4 类基本结构：

• 集合：结构中的数据元素除了同属于一种类型外，别无其它关系。

• 线性结构：结构中的数据元素之间存在一对一的关系。

• 树型结构：结构中的数据元素之间存在一对多的关系。

• 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
  图示如下：依次为：集合、线性结构、树型结构、图型结构
  
  （2）存储结构：数据结构在计算机中的存储表示称为数据的存储结构。它包括数据元素的表示和关系的表示。

• **顺序存储结构：**是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。（在C语言中通常用数组来表示）
  优点：占用较少的存储空间；
  缺点：由于只能使用相邻的一整块存储单元，因此可能产生较多的碎片现象。

• **链式存储结构：**将结点所占的存储单元分为两部分，一部分存放结点本身的信息，另一部分存放结点的后继结点地址，结点间的逻辑关系由附加的指针字段表示。
  链式存储结构常借助于程序语言的指针类型描述。
  优点：不会出现碎片现象，充分利用所有的存储单元；
  缺点：每个结点占用较多的存储空间。

• **索引存储方式：**是用结点的索引号来确定结点的存储地址。
  在储存结点信息的同时，要建立附加的索引表。
  优点：检索速度快。
  缺点：增加了附加的索引表，占用较多的存储空间；在增加和删除数据时需要修改索引表而花费较多时间。

• **散列存储方式：**是根据结点的关键字值直接计算出该结点的存储地址。通过散列函数把结点间的逻辑关系对应到不同的物理空间。
  优点:检索、增加和删除结点的操作都很快；
  缺点:当采用不好的散列函数时可能出现结点存储单元的冲突，为解决冲突需要附加时间和空间的开销。

7. 数据的运算
数据运算定义在数据的逻辑结构上，即施加于数据的操作。
例如对一张表的记录进行查找、增加、删除、修改，这就是对数据的运算。

8. 数据结构三方面的关系
数据的逻辑结构、数据的存储结构及数据的运算三方面构成一个数据结构的整体。
存储结构是对数据项的存储。同一逻辑结构可用不同存储结构就对应不同的存储标识。
例如，线性表若采用顺序存储方式，称为顺序表；若采用链式存储方式，称为链表；若采用散列存储方式，可称为散列表。

三、算法及度量

1. 算法：
   算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外算法还具有：
   有穷性；确定性；可行性；输入；输出。
2. 性能度量：

• 正确性 （计算准确性，基本要求）
• 可读性 （面向设计友好，基本要求）
• 健壮性 （鲁棒性、容错性，基本要求）
• 时间复杂度（重点优化点）
• 空间复杂度（目前的计算机空间基本都有足够内存，空间复杂度考虑较少）

时间的度量统计方法：
（1）事后统计的方法
受硬件、网络的影响，实际难以准确度量算法优劣。
（2）事前分析估算的方法
影响算法耗时的因素：算法选用的计算策略、问题规模、程序语言（实现语言级别越高，执行效率越低）、编译程序锁产生的机器代码的质量、机器执行指令的速度。控制结构（顺序、分支、循环）和原操作（固定数据类型操作）共同决定算法时间。

文章来源: blog.csdn.net，作者：JeckXu666，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_45396672/article/details/110357491