数据结构绪论

由于几天后数据结构要期末考试，最近几天会出数据结构相关的教程，以作复习。

参考资料：

数据结构(C语言版) –严蔚敏，吴伟民

数据结构与算法分析 –Mark Allen Weiss

2025年数据结构考研复习指导 –王道论坛

数据结构的基本概念

基本术语

数据元素：数据的基本单位，由若干数据项组成

数据对象：具有相同性质的数据元素的集合

抽象数据类型：一组操作的集合

​ 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素之间的关系称为结构。数据结构包括三方面内容：逻辑结构、存储结构和数据的运算

数据结构三要素

1.数据的逻辑结构

​ 逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，分为线性结构和非线性结构

集合：结构中的数据元素除“同属一个集合”外，别无其他关系。

线性结构：结构中的数据存在一对一的关系

树形结构：结构中的数据存在一对多的关系

图状结构：结构中的数据存在多对多的关系

2.数据的存储结构

​ 存储结构是指数据结构在计算机中表示(又称映像)，也称物理结构。

• 顺序存储：逻辑上相邻的元素存储在物理位置也相邻的存储单元中
• 链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系
• 索引存储：建立附加的索引表
• 散列存储：根据元素的关键字直接计算出该元素的存储地址

算法效率的度量

一般情况下，算法中基本操作重复执行的次数是关于n的某个函数f(n), 算法的时间量度记作

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

O的含义是T(n)的数量级，如果存在正常数c和n⁰，使得当n >= n₀时,T(n) <= c f(n),则记为T(n) = O(f(n))

我们通过这样的方式表示了算法执行时间的增长率，它主要是由O(f(n))决定的。

例如，若存在f(n) = 2ⁿ + n² , 则 O(f(n)) = 2ⁿ 。显然，当n很大时，相比于2ⁿ ,n²无足轻重了。

像这样，我们称O(f(n))为渐进时间复杂度，简称时间复杂度

同理，空间复杂度S(n) = O(g(n))

使用g(n)是为了区别于f(n)