自1946年，第一台计算机问世以来，计算机产业飞速发展。为了编写出一个好得程序，必须分析待处理的对象的特征以及各处理对象之间存在的关系。这就是数据结构这门学科形成和发展的背景。
1.1什么是数据结构
数据结构是计算机科学中组织和存储数据的特定方式，它使得数据能够被高效地访问和修改。数据结构定义了数据元素之间的关系以及可以对这些数据执行的操作。
数据结构的核心组成包括：
逻辑结构：描述数据元素之间的逻辑关系，主要有四种基本类型：
- 集合结构：元素间除了"同属一个集合"外，无其他关系
- 线性结构：元素之间是一对一的关系（如数组、链表）
- 树形结构：元素之间是一对多的关系（如二叉树、B树）
- 图形结构：元素之间是多对多的关系（如有向图、无向图）
物理结构（存储结构）：数据在计算机中的实际存储方式，主要有：
- 顺序存储：在内存中连续存储（如数组）
- 链式存储：通过指针或引用连接（如链表）
- 索引存储：使用索引表来标识元素位置
- 散列存储：通过散列函数直接计算位置
操作：在数据结构上可执行的基本操作，如：
- 插入、删除元素
- 查找、访问元素
- 排序、遍历
- 合并、分割等
选择合适的数据结构对于算法效率至关重要。不同数据结构在不同操作上有各自的优缺点，例如：
- 数组支持快速随机访问，但插入删除操作可能需要移动大量元素
- 链表支持高效的插入删除，但随机访问效率低
- 哈希表提供接近常数时间的查找，但可能存在冲突问题
1.2基本概念和术语
核心概念
- 数据：是对客观事物的符号表示，在计算机科学中，是指所有能输入到计算机中并被计算机程序处理的符号的总称。
- 数据元素：是数据的基本单位，通常被视为一个整体进行考虑和处理。在不同的应用场景中，数据元素可以是一个数字、一个字符，也可以是一条完整的记录。
- 数据项：构成数据元素的最小单位，是数据元素中具有独立含义的数据单位。例如，学生记录中的姓名、学号、性别等都是数据项。
- 数据结构：指数据元素之间的关系集合，包括数据元素之间的逻辑关系、数据的存储表示和对数据的操作。
数据的逻辑结构
- 集合结构：数据元素同属一个集合，除此之外无其他关系。元素之间是"属于同一集合"的关系。
- 线性结构：元素之间存在一对一的关系。除了第一个和最后一个元素，其他每个元素都有唯一的前驱和后继。例如：线性表、栈、队列、字符串等。
- 树形结构：元素之间存在一对多的关系。除了根节点外，每个元素都有唯一的前驱（父节点），但可能有多个后继（子节点）。例如：树、二叉树、森林等。
- 图形结构：元素之间存在多对多的关系。任意两个元素之间可能存在联系。例如：有向图、无向图等。
数据的存储结构（物理结构）
- 顺序存储结构：将数据元素存储在地址连续的存储单元里，元素之间的逻辑关系通过物理位置的相邻关系来体现。例如：数组。
- 链式存储结构：不要求数据元素在物理位置上相邻，而是通过指针来表示元素之间的逻辑关系。例如：链表。
- 索引存储结构：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项包含关键字和指向元素的指针。
- 散列存储结构：根据元素的关键字直接计算出该元素的存储地址，适用于快速查找。
数据的基本操作
- 创建（Create）：建立一个新的数据结构。
- 销毁（Destroy）：删除一个数据结构，释放其占用的所有空间。
- 插入（Insert）：在数据结构中增加新的数据元素。
- 删除（Delete）：从数据结构中移除指定的数据元素。
- 查找/检索（Search/Retrieve）：在数据结构中查找满足给定条件的元素。
- 修改（Modify）：更改数据结构中指定元素的值。
- 遍历（Traverse）：按某种顺序访问数据结构中的每一个元素。
1.3算法和算法分析
算法的定义
算法是解决特定问题的一系列操作步骤，具有以下五个基本特性：
- 有穷性：算法必须在有限步骤后终止
- 确定性：每个步骤都有明确的定义
- 可行性：每个步骤都可以被执行
- 输入：有零个或多个输入
- 输出：有一个或多个输出
算法设计的要求
- 正确性：算法应当满足具体问题的需求。
- 可读性：：算法主要是为了人的阅读与交流，其次才是机器执行。
- 健壮性：当输入数据非法时，算法也能适当做出反应或进行处理，而不会产生莫名其妙的输出结果。
- 效率与低存储量需求：通俗的说，效率是指算法的执行时间。
算法效率的度量
时间复杂度
时间复杂度描述算法执行所需时间与问题规模n的关系，通常用大O符号表示。
常见的时间复杂度（按效率从高到低）：
- O(1)：常数时间，与问题规模无关
- O(log n)：对数时间，如二分查找
- O(n)：线性时间，如线性查找
- O(n log n)：如归并排序、快速排序
- O(n²)：如冒泡排序、插入排序
- O(n³)：如某些矩阵运算
- O(2ⁿ)：指数时间，如穷举法
- O(n!)：阶乘时间，如全排列算法
空间复杂度
空间复杂度描述算法执行所需的额外空间与问题规模n的关系。
常见的空间复杂度：
- O(1)：常数空间，与问题规模无关
- O(n)：线性空间，如创建长度为n的数组
- O(n²)：如创建n×n的矩阵
最好、最坏和平均情况分析
- 最好情况：算法在最有利的输入下的性能
- 最坏情况：算法在最不利的输入下的性能
- 平均情况：算法在随机输入下的期望性能
渐进分析
关注算法在问题规模足够大时的行为，忽略常数和低阶项。
例如：T(n) = 3n² + 2n + 1 的渐进时间复杂度为O(n²)
