天勤考研高分笔记 个人笔记

### 数据结构与算法知识点概述 #### 一、绪论 **数据的物理结构**：主要分为四种类型，分别是顺序、链接、索引和散列。 - **顺序存储**：利用一组地址连续的存储单元依次存储线性表中的各元素，元素间的逻辑关系由存储单元的邻接关系来体现。 - **链接存储**：通过为每个数据元素设置指针域来表示元素之间的逻辑关系。需要注意的是，链式存储结构中的结点内的存储单元地址不一定是连续的。 - **索引存储**：除了数据元素本身外，还包括附加的索引表，索引表中的每一项称为索引项，通常包含数据元素的键值和该数据元素的存储地址。 - **散列存储**：根据元素的关键字直接计算出该元素的存储地址，从而实现快速查找。 **算法五特性**：有穷性、确定性、可行性、输入性和输出性。 - **有穷性**：算法必须在有限步骤后停止。 - **确定性**：算法中的每一步都必须有确切的含义。 - **可行性**：算法中描述的操作可以通过已经实现的基本操作执行有限次来完成。 - **输入性**：至少有一个输入。 - **输出性**：至少有一个输出。 **C/C++语法注意点**： 1. **指针的引用**：`int*&x` 表示 x 是一个指向 int 的引用，而不是一个 int 指针。 2. **内存分配**：使用 `malloc()` 函数在堆上分配内存，使用完毕后需要调用 `free()` 释放内存。 3. **二维数组**：如 `int a[4][5]` 表示一个具有 4 行 5 列的二维数组。 4. **遍历字符数组**：可以使用指针 `char *p = f;` 并通过 `while(*p != '\0') { p++; }` 来遍历字符数组。 5. **switch-case 结构**：使用 `switch(a)` 并在 `case` 中根据条件执行相应的代码块。 6. **字符串定义**：如 `char str[] = "abcdef";` 字符串长度为 6，但数组长度为 7，包括一个空字符 `'\0'` 作为结束标志。 7. **指针数组与指向数组的指针**：`int *a[max]` 表示一个元素为指针的数组，而 `int (*a)[max]` 表示一个指向数组的指针。 **算法的复杂度**：主要关注算法中基本运算的频度 (重复执行次数 f(n)) 的数量级 (O)，记为问题规模 n 的函数 T(n) = O(f(n))。 - **时间复杂度**：取决于问题规模 n 和输入数据的初始状态。常见的复杂度排序为：O(1) < O(log2n) < O(n) < O(n log2n) < O(n^2) < O(n^k) < O(2^n) < O(n!)。 - **空间复杂度**：问题规模 n 的函数 S(n)，如果算法所需的辅助空间为常量，则 S(n) = O(1)。 #### 二、线性表 **顺序表**：支持随机访问，存储空间需要预先分配 (静态分配)，插入操作需要移动多个元素，存储密度为 1。 **链表**：不支持随机访问，存储空间动态分配，存储密度小于 1。 - **单链表**：每个结点包含一个指针域指向下一个结点。 - **双链表**：每个结点包含两个指针域，分别指向前驱结点和后继结点。 - **循环单链表/循环双链表**：最后一个结点的指针指向头结点。 - **静态链表**：利用数组模拟链表，每个数组元素包含数据部分和指针部分。 #### 三、栈队列和数组 **栈**：一种只允许在一端进行插入和删除操作的线性结构，遵循 FILO (先进后出) 原则，有记忆功能。 - **顺序栈**：利用数组实现，栈顶元素位于数组末尾。 - **链栈**：利用链表实现，新元素插入到链表头部。 - **共享栈**：在一个数组中实现两个栈，一个从左向右增长，另一个从右向左增长。 **队列**：一种只允许在一端进行插入操作，在另一端进行删除操作的线性结构，遵循 FIFO (先进先出) 原则。 - **循环顺序队列**：通过对数组的指针进行模运算实现队列的循环，避免了队列中的空间浪费。 - **链队列**：利用链表实现，新元素插入到链表尾部，删除操作发生在链表头部。 - **双端队列**：允许在队列两端进行插入和删除操作。 这些概念和细节对于深入理解数据结构和算法设计至关重要，对于准备考研的学生来说尤其重要。通过理解并掌握这些核心概念，可以帮助学生更好地应对考试，并在未来的学习和工作中解决实际问题。