数据结构笔记

Github仓库：My_Ds_Demo

数据的逻辑结构

• 逻辑结构（logical structure）是指在数据中数据元素之间的相互关系。数据元素之间存在不同的逻辑关系构成了以下4种结构类型。

  1. 集合结构：集合的数据元素没有其他关系，仅仅是因为他们挤在一个被称作“集合”的盒子里。

  2. 线性结构：线性的数据元素结构关系是一对一的，并且是一种先后的次序，就像a-b-c-d-e-f- g·····被一根线穿连起来。

  3. 树形结构：树形的数据元素结构关系是一对多的，这就像公司的部门级别，董事长-CEO\CTO-技术部\人事部\市场部.....。

  4. 图结构：图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图，一个城市有很多线路连接不同城市。

数据的存储（物理）结构

• 存储结构（storage structure）也称为物理结构（physical structure），指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构一般可以反映数据元素之间的逻辑关系。分为顺序存储结构和链式存储结构。

  1. 顺序存储结构：是把数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。

  2. 链式存储结果：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。

小结：数据的逻辑结构和物理结构是密切相关的，在学习数据的过程中会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。

算法

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

时间复杂度

• 语句频度：该条语句可能重复执行的次数
• T(n)：所有语句的频度之和，其中n为问题的规模
• 时间复杂度：T(n)=O(f(n))，其中O表示T(n)与f(n)在n->正无穷时为同阶无穷大

规则：

• 加法规则
• 乘法规则

常见时间复杂度
$O(1)$<$O(log_2⁡n)$<$O(n)$<$O(nlog_2n)$<$O(n^2)$<$O(n3)$<$O(2^{n)$<$O(n!)$<$O(n}n)$