### 数据结构复习要点详解
#### 一、绪论
**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. 线性表链接存储的结构和特点**
- **结构**:链表由一系列结点组成,每个结点包含数据域和指向下一个结点的指针域。
- **特点**:链表不需要连续的内存空间,因此可以方便地进行插入和删除操作。但是,查找操作相对较慢,因为需要从头结点开始遍历整个链表。