### 数据结构复习要点详解
#### 一、绪论
**1. 数据结构的主要研究内容**
- **数据的逻辑结构**：研究数据项之间的逻辑关系，而不关心这些数据是如何存储的。例如，在数组中，虽然数据在内存中是连续存储的，但从逻辑上看，数组中的元素可以通过索引直接访问，这体现了其逻辑结构。
- **数据的存储结构**：讨论如何在计算机中有效地存储数据结构。主要分为顺序存储和链式存储。
**2. 数据逻辑结构的种类**
- **集合**：集合结构中的元素是独立存在的，元素之间没有明确的前后关系。例如，一个班级的学生名单就是一个典型的集合结构。
- **线性表**：线性结构的特点是每个元素都有唯一的前驱和后继（除了头尾元素）。如数组和链表都属于线性结构。
- **树**：树结构是一种层次结构，其中根节点没有前驱，其他节点都有一个唯一的父节点。例如，文件系统的目录结构就是一种树结构。
- **图**：图结构是最复杂的一种数据结构，节点之间可以有复杂的连接关系，每个节点都可以有任意数量的前驱和后继节点。社交网络的好友关系就是一个典型的图结构例子。
**3. 数据结构的二元组定义**
- **集合结构**：集合结构中元素集合`K={A，B，C，D，E，F，G}`和二元关系`R={}`表明这些元素之间不存在任何关系。
- **线性结构**：元素集合`K={A，B，C，D，E，F，G}`和二元关系`R={<A,B>，<B,C>，<C,D>，<D,E>，<E,F>，<F,G>}`表示A是B的前驱，B是A的后继，以此类推。
- **树结构**：元素集合`K={A，B，C，D，E，F，G}`和二元关系`R={<A,B>，<A,C>，<A,D>，<C,E>，<C,F>，<D,G>}`说明A是B、C、D的父节点，而C是E、F的父节点等。
- **图结构**：元素集合`K={A，B，C，D，E，F，G}`和二元关系`R={<A,B>，<A,C>，<A,G>，<D,G>，<D,F>，<C,E>，<C,F>，<G,F>}`表示节点间有多条边相连。
**4. 数据的几种存储结构**
- **顺序存储**：利用数组来实现，逻辑上相邻的元素物理上也相邻。适用于线性结构，如数组。
- **链式存储**：通过指针链接各个节点，每个节点包含数据域和指针域。适用于更复杂的数据结构，如链表、树和图。
- **散列存储**：利用哈希函数将关键字映射到特定的存储位置。这种方法可以快速访问数据，但可能会出现冲突问题。
**5. 数据的逻辑结构、存储结构和总的数据结构之间的关系**
逻辑结构和存储结构共同决定了一个数据结构。即使逻辑结构相同，如果存储结构不同，也会构成不同的数据结构。例如，顺序表和链表具有相同的逻辑结构（线性表），但由于存储方式不同，因此被视为两种不同的数据结构。
**6. 算法的设计要求**
- **正确性**：算法必须能够针对有效的输入产生正确的输出结果。
- **可读性**：良好的编程习惯和清晰的代码结构有助于提高代码的可读性。
- **健壮性**：算法需要具备处理异常输入的能力，以防止程序崩溃。
- **效率**：包括时间和空间效率，高效的算法能够更快地完成任务，占用较少的资源。
**7. 时间复杂度的概念**
- **平均复杂度**：考虑所有可能的输入情况，求得平均执行时间。
- **最坏情况复杂度**：评估算法在最不利情况下的执行时间，通常是评估复杂度的标准。
- **最好复杂度**：考虑最优情况下的执行时间，一般作为参考。
#### 二、线性表
**1. 线性表的定义及性质**
- **定义**：线性表是一种基本的线性结构，其中数据元素是有序的，且每个元素除了第一个和最后一个外，都有唯一的直接前驱和直接后继。
- **性质**：线性表长度为n，则存在n+1个位置可以插入新的元素。
**2. 顺序线性表的存储方式及其表单元的定位和计算**
- **存储方式**：顺序表通过连续的内存空间来存储数据元素。
- **表单元定位**：可以通过下标i来直接访问第i个元素，计算公式为LOC(ai) = LOC(a1) + (i-1)*d，其中d为每个元素占用的空间大小。
**3. 顺序线性表的插入、删除和查找**
- **插入操作**：需要移动元素以腾出空位。
- **删除操作**：需要将后续元素向前移动覆盖被删除的元素。
- **查找操作**：可以从头到尾遍历整个表，直到找到目标元素为止。
**4. 线性表链接存储的结构和特点**
- **结构**：链表由一系列结点组成，每个结点包含数据域和指向下一个结点的指针域。
- **特点**：链表不需要连续的内存空间，因此可以方便地进行插入和删除操作。但是，查找操作相对较慢，因为需要从头结点开始遍历整个链表。
VIP享7折，此内容立减5.97元 
