数据结构基本概念和术语

• (1)数据结构是啥？
• (2)数据结构的两个方面的内容
• • 1.逻辑结构
  • 2.存储结构
  • 3.两者关系
• (3)抽象数据类型？
• (4)算法具有五个特性
• (5)算法分析的两个方面
• • 1.时间复杂度
  • 2.空间复杂度

导读：以C语言的数据结构学习总结为例
参考书：《数据结构（C语言）》 --严蔚敏
电子参考书：https://www.jb51.net/books/690409.html

(1)数据结构是啥？

Tips：数据结构其实就是研究如何更好、更快、更准确的组织数据的一种方法（也就是如何把数据用编程工具来组织起来，以便于操作数据）

数据结构: 是一门研究非数值计算程序设计中操作对象， 以及这些对象之间的关系和操作的学科。

(2)数据结构的两个方面的内容

1.逻辑结构

简单来说：逻辑结构就是理论上的东西，是抽象的计算方法

逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。（当然无关，只是逻辑上说得通就行，跟实践关系不大）
根据数据元素之间关系的不同特性， 通常有四类基本逻辑结构：

• 集合结构
• 线性结构
• 树形结构
• 图状结构

2.存储结构

存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：

• 顺序存储结构
• 链式存储结构

（这就是具体实现了）程序运行时，数据放在内存里，根据数据在内存分配地址连续还是离散的方式，顺序就是连续数据大块儿（用数组、或malloc()函数手动申请内存空间），链式就是离散的数据小块儿（用指针串联起来，或建立索引表）

3.两者关系

同一逻辑结构采用不同的 存储方法， 可以得到不同的存储结构。

（条条大路通罗马；实现的方式有多样）

(3)抽象数据类型？

抽象数据类型 是指由用户定义的、表示应用问题的数学模型 ， 以及定义在这个模型上的 一组操作的总称， 具体包括三部分：数据对象、数据对象上关系的集合， 以及对数据对象的基本操作的集合。

(4)算法具有五个特性

• 有穷性
• 确定性
• 可行性
• 输入
• 输出

一个算法的优劣应该从以下四方面来评价

正确性、可读性、健壮性、高效性。

(5)算法分析的两个方面

算法分析考察算法的时间和空间效率。一般情况下， 鉴于运算空间较为充足， 故将算法的时间复杂度作为分析的重点。

1.时间复杂度

执行时间的数量级称为算法的渐近时间复杂度，T(n) = 0(/(n) ), 它表示随着问题规模n的增大， 算法执行时间的增长率和.f(n)的增长率相同， 简称时间复杂度。（使用同阶缩放比较）

2.空间复杂度

对千输入数据所占的具体存储量取于·问题本身，与算法无关，这样只需分析该算法在实现时所需要的辅助空间就可以了。