408 数据结构知识点汇总

数据结构知识点总结

数据结构是计算机科学的基础，涉及到数据的存储、处理和运算。主要涵盖了数据结构的基本概念、逻辑结构、存储结构、算法和算法评价、线性表等方面。

1. 数据结构的基本概念

• 数据元：数据的基本单位，一个数据元素由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。

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

• 数据类型：一个值的集合和定义在该集合上的一组操作。

2. 数据结构的三要素

数据结构有三要素：逻辑结构、存储结构和数据的运算。

• 逻辑结构：指数据元素之间的逻辑关系，独立于计算机，分为线性结构和非线性结构。

• 存储结构：指数据结构在计算机中的表示（物理结构），包括顺序存储、链式存储、索引存储和散列存储。

• 数据的运算：包含运算的定义（针对逻辑结构）和运算的实现（针对存储结构）。

3. 算法和算法评价

算法是对特定问题求解步骤的描述，具有五个特性：有穷性、确定性、可行性、输入、输出。主要包括时间复杂度和空间复杂度两个评价标准。

4. 线性表

线性表是具有相同数据类型的 n 个数据元素的有限序列。逻辑上相邻的两个元素之间存在一对一关系，顺序表和链表是线性表的不同存储结构。

5. 线性表的顺序表示

顺序表是用连续的存储单元依次存储线性表中的数据元素，特点是随机访问性能好，但插入和删除操作需移动大量元素。

6. 线性表的链式表示

链式存储的线性表不需要连续的存储单元，插入和删除操作较为方便。头结点与头指针在带头结点的链表中有明显的区分。单链表的时间复杂度为 O(n)。