目录

第一章绪论

1.基本概念和术语

2.数据结构三要素：（逻辑结构，存储结构和数据的运算）

3.算法（P5）

---

第一章绪论

1.基本概念和术语

数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。可以由若干数据项构成。

数据项：数据项是构成数据元素的不可分割的最小单位。

数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型：是一个值的集合和定义在此集合上的一组操作的总称。其包括原子类型，结构类型和抽象数据类型。

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

2.数据结构三要素：（逻辑结构，存储结构和数据的运算）

一、逻辑结构：指数据元素之间的逻辑关系。从逻辑上描述数据，和存储无关。

四种逻辑结构：1.集合、2.线性结构、3.树形结构、4.图状结构

线性表是典型的线性结构；集合、树、图是典型的非线性结构

1.集合：结构中的数据元素之间同属于一个集合外，无其它关系。

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

3.树形结构：数据元素之间存在一对多的关系。

4.图状结构：数据元素之间存在多对多关系。

二、存储结构：指数据结构在计算机中的表示（映像），也称物理结构。

数据的存储结构主要有：顺序存储，链式存储，索引存储，散列存储。

1.顺序存储：把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中。元素间的关系由邻接关系来体现。

优点：可以实现随机存取，每个元素占用最少的存储空间。

缺点：只能使用相邻的一整块存储空间，可能产生较多的外部碎片。

2.链式存储：逻辑上相邻的元素物理上可以不相邻，用指针来表示元素之间的逻辑关系。

优点：不会出现碎片现象，能充分利用所有存储单元。

缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。

3.索引存储：建立元素信息的同时，还附加了索引表。索引表每项被称为索引项（关键字，地址构成）

优点：检索速度快。

缺点：附加的索引表会占用内存空间，且增加和删除数据也要修改索引表，因而会花费较多的时间。

4.散列存储：根据元素的关键字直接计算出该元素的存储地址，又名哈希存储。

优点：检索，增加和删除结点操作都很快。

缺点：若散列函数不好，可能会出现存储单元的冲突，增加时间和空间上的开销。

三、数据的运算：包括数据的定义和实现。运算的定义针对的是逻辑结构，指出运算的功能。运算的实现针对的是存储结构，指出运算的具体操作步骤。

数据结构的三个要素_朽木自雕！！！的博客-CSDN博客_数据结构三要素

可结合以上博主的图结合学习。

3.算法（P5）

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

重要特性：1.有穷性 2.确定性 3.可行性 4.输入 5.输出

好的算法：1. 正确性 2.可读性 3.健壮性 4.效率和低存储量需求

时间复杂度

一套图 搞懂“时间复杂度”_12 26 25的博客-CSDN博客_时间复杂度

这个讲的超详细。

最坏时间复杂度：在最坏情况下的时间复杂度。

平均时间复杂度：期望运行时间。

最好时间复杂度：在最好情况下的时间复杂度。

两条规则：

1.加法：取最大的一个

2.乘法：o(n1)*o(n2)=o(n1*n2)

常见的渐进时间复杂度：

o(1)<o(log2n)<o(n)<o(nlog2n)<o(n2)<o(n3)<o(2n次方)<o(n阶乘)<o(n的n次方)

空间复杂度

算法空间复杂度_张志帅‍的博客-CSDN博客_算法空间复杂度

空间复杂度-简单易懂_傲慢毁人的博客-CSDN博客