数据结构笔记与重点复习资料合集

数据结构笔记与重点复习资料合集前言数据结构是计算机科学的基石，也是程序设计的灵魂。无论是算法设计、系统开发还是求职面试，扎实的数据结构基础都不可或缺。本笔记旨在梳理数据结构的核心概念、重点难点，并结合实际应用场景进行分析，为学习者提供一份系统且实用的复习资料。内容力求精炼，突出重点，帮助读者在短时间内高效回顾与巩固知识。一、数据结构基本概念1.1数据与数据结构的定义数据是信息的载体，是对客观事物的符号表示。数据元素是数据的基本单位，而数据项则是数据元素的最小组成单位。数据结构指的是相互之间存在一种或多种特定关系的数据元素的集合，它包含三个方面：逻辑结构、物理结构（存储结构）和数据的运算。*逻辑结构：描述数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。常见的逻辑结构有集合、线性结构、树形结构和图状结构（网状结构）。*集合结构：元素间除“同属一个集合”外，无其他关系。*线性结构：元素间存在一对一的线性关系，首尾元素特殊，其他元素有唯一前驱和后继。*树形结构：元素间存在一对多的层次关系，有明显的根节点和分支节点。*图状结构：元素间存在多对多的任意关系，任意两个元素都可能相关联。*物理结构：又称存储结构，是数据逻辑结构在计算机中的具体实现方式，涉及数据元素及其关系在存储器中的表示。主要有两种基本存储方式：*顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系，如数组。*数据的运算：对数据结构中的数据元素可以施加的操作，如插入、删除、查找、修改、排序等。运算的实现依赖于数据的存储结构。1.2算法的基本概念与复杂度分析算法是解决特定问题的步骤的有限序列，具有输入、输出、有穷性、确定性和可行性五大特性。*算法设计的要求：正确性、可读性、健壮性（鲁棒性）、高效率与低存储量需求。*时间复杂度：衡量算法执行时间随问题规模增长的变化趋势，通常用大O符号（O）表示。分析时需关注语句的执行次数（频度），并忽略常数项和低阶项，只保留最高阶项。常见的时间复杂度按增长速度排列有：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)。*空间复杂度：衡量算法在执行过程中所需存储空间的大小，同样用大O符号表示。它包括程序本身所占空间、输入数据所占空间以及算法执行过程中所需的额外空间。若额外空间与问题规模无关，则为O(1)（原地工作）。二、线性表2.1线性表的定义与基本操作线性表是具有相同特性的数据元素的有限序列，是一种典型的线性结构。其基本操作包括：初始化、判空、求长度、按位查找、按值查找、插入（指定位置）、删除（指定位置或值）、遍历等。2.2顺序表（数组）*定义：用一组地址连续的存储单元依次存储线性表中的数据元素，是线性表的顺序存储结构。*特点：*随机访问：可通过首地址和元素序号（下标）在O(1)时间内找到指定元素。*存储密度高：无需为表示元素间逻辑关系额外增加存储空间。*插入删除操作效率低：在表中任意位置插入或删除元素，平均需要移动约一半元素，时间复杂度为O(n)。*大小固定：静态数组在编译时确定大小，动态数组虽可扩容，但扩容操作（通常为复制到更大空间）耗时。*适用场景：需频繁随机访问，较少进行插入删除操作的场景。2.3链表*定义：用一组任意的存储单元（可连续或不连续）存储线性表中的数据元素，每个元素（节点）包含数据域和指针域（存放后继节点地址）。*分类：*单链表：每个节点只含一个指针域，指向其后继节点。通常有头指针（指向首节点），为操作方便可增设头结点（数据域可空，指针域指向首节点）。*双链表：每个节点包含两个指针域，分别指向前驱和后继节点，可双向遍历，插入删除操作更灵活。*循环链表：表中最后一个节点的指针域指向头节点（单循环链表）或头指针（双循环链表），整个链表形成一个环，可从任一节点出发遍历整个链表。*静态链表：借助数组来模拟链表，数组元素包含数据域和游标（模拟指针，指向下一元素的数组下标），适用于不支持指针的语言环境。*特点：*动态分配：无需预先分配固定大小的存储空间，可根据需要动态申请和释放节点。*插入删除操作灵活：只需修改相关节点的指针域，无需移动大量元素，时间复杂度为O(1)（已知前驱节点时）。*随机访问效率低：需从头指针开始依次遍历，时间复杂度为O(n)。*存储密度较低：指针域需额外存储空间。*适用场景：数据元素个数不确定，需频繁进行插入删除操作，且不常进行随机访问的场景。2.4顺序表与链表的比较与选择特性顺序表链表:-----------:---------------------------:-----------------------------存储空间静态分配（固定）或动态分配（可能有冗余）动态分配（按需分配，无冗余）时间性能（查找）随机查找O(1)，按值查找O(n)均为O(n)时间性能（插入删除）平均O(n)（需移动元素）O(1)（已知前驱/后继节点时）空间性能存储密度高需额外存储指针信息，存储密度低实现复杂度较简单较复杂（指针操作）选择依据：根据实际应用中对查找、插入删除操作的频率，以及对存储空间的要求综合决定。三、栈与队列3.1栈(Stack)*定义：一种限定仅在表尾进行插入和删除操作的线性表。表尾称为栈顶(Top)，表头称为栈底(Bottom)。*核心特性：后进先出(LIFO-LastInFirstOut)。*基本操作：*`push(x)`：入栈，在栈顶插入元素x。*`pop()`：出栈，删除并返回栈顶元素。*`top()`/`peek()`：获取栈顶元素，不删除。*`isEmpty()`：判断栈是否为空。*`size()`：获取栈中元素个数。*实现方式：*顺序栈：用数组实现，栈顶指针通常用数组下标表示。需注意栈满溢出问题。*链栈：用链表实现，通常以头节点或头指针作为栈顶，操作方便。*典型应用：表达式求值（中缀转后缀、后缀表达式计算）、括号匹配、函数调用与递归、浏览器历史记录、撤销操作等。3.2队列(Queue)*定义：一种限定仅在表尾进行插入，在表头进行删除操作的线性表。表尾称为队尾(Rear)，表头称为队头(Front)。*核心特性：先进先出(FIFO-FirstInFirstOut)。*基本操作：*`enqueue(x)`：入队，在队尾插入元素x。*`dequeue()`：出队，删除并返回队头元素。*`front()`：获取队头元素，不删除。*`isEmpty()`：判断队列是否为空。*`size()`：获取队列中元素个数。*实现方式：*顺序队列：用数组实现。为解决“假溢出”问题（队尾指针到达数组末尾但队头有空余），通常采用循环队列结构。循环队列中，队空条件通常为`front==rear`，队满条件则需特殊处理（如少用一个元素空间，队满条件为`(rear+1)%MaxSize==front`；或增设计数变量/标志位）。*链队列：用链表实现，通常有队头指针（指向头节点或首元素节点）和队尾指针（指向尾节点），便于入队和出队操作。*典型应用：*普通队列：操作系统中的进程调度、打印任务排队、消息缓冲区等。*双端队列(Deque)：允许在两端进行插入和删除操作的队列，结合了栈和队列的特性，用途广泛，如实现滑动窗口最大值等算法。*优先级队列(PriorityQueue)：元素具有优先级，出队时总是优先级最高的元素出队，其底层通常用堆（如二叉堆）实现。四、串4.1串的基本概念串（字符串）是由零个或多个字符组成的有限序列。长度为零的串称为空串。串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。4.2串的存储与基本操作串的存储结构与线性表类似，有顺序存储（定长顺序串、堆分配串）和链式存储（块链结构）。基本操作包括串的赋值、比较、连接、求子串、查找子串（模式匹配）、替换、插入、删除等。4.3模式匹配算法模式匹配是指在主串中查找是否存在与模式串相等的子串，并返回其位置。*朴素模式匹配算法（BF算法）：*思路：从主串的第一个字符起，与模式串的第一个字符比较，若相等则继续比较后续字符；若不等，则从主串的下一个字符起，重新与模式串的第一个字符比较。*时间复杂度：最坏情况下为O(n*m)，其中n为主串长度，m为模式串长度。*KMP算法：*核心思想：利用已经部分匹配的信息，消除主串指针的回溯，仅移动模式串指针。通过计算模式串的部分匹配表（Next数组）来确定模式串失配时的移动位数。*Next数组定义：Next[j]表示模式串中前j个字符组成的子串的最长前缀（不包含最后一个字符）和最长后缀（不包含第一个字符）相等的长度。*时间复杂度：预处理Next数组O(m)，匹配过程O(n)，整体O(n+m)，效率显著高于BF算法。五、树与二叉树5.1树的基本概念*定义：树是n(n≥0)个节点的有限集。当n=0时，称为空树；当n>0时，有且仅有一个特定的称为根(Root)的节点，其余节点可分为m(m≥0)个互不相交的有限集，每个集合本身又是一棵树，称为根的子树(Subtree)。*基本术语：节点的度（拥有子树的个数）、树的度（节点度的最大值）、叶子节点（度为0的节点）、分支节点（度不为0的节点）、孩子、双亲、兄弟、祖先、子孙、节点的层次（根为第一层）、树的深度/高度（节点层次的最大值）、森林（m棵互不相交的树的集合）。*树的性质：*树中节点数等于所有节点的度之和加1（根节点）。*度为k的树中第i层至多有k^(i-1)个节点。*深度为h的k叉树至多有(k^h-1)/(k-1)个节点。*具有n个节点的完全二叉树的深度为⌊log₂n⌋+1。5.2二叉树的定义与性质*定义：二叉树是n(n≥0)个节点的有限集，它或为空树，或由一个根节点和两棵互不相交的、分别称为根的左子树和右子树的二叉树组成。*特点：每个节点至多有两棵子树；左、右子树有顺序，不能随意颠倒。*特殊二叉树：*满二叉树：深度为h且含有2^h-1个节点的二叉树。*完全二叉树：深度为h，除第h层外，其余各层的节点数都达到最大个数，且第h层的节点都集中在该层最左边的若干位置上。完全二叉树适合顺序存储。*二叉排序树(BST)：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值，左右子树也分别为二叉排序树。*平衡二叉树(AVL树)：左右子树的深度之差（平衡因子）的绝对值不超过1，且左右子树也都是平衡二叉树。*二叉树的性质：*非空二叉树的第i层上至多有2^(i-1)个节点(i≥1)。*深度为h的非空二叉树至多有2^h-1个节点(h≥1)。*对任何一棵非空二叉树，若其叶子节点数为n₀，度为2的节点数为n₂，则n₀=n₂+1。*具有n个节点的完全二叉树，按层序编号（从1开始），则对任一节点i(1≤i≤n)：*若i=1，则为根节点，无双亲；否则，其双亲是⌊i/2⌋。*若2i>n，则无左孩子；否则，左孩子是2i。*若2i+1>n，则无右孩子；否则，右孩子是2i+1。5.3二叉树的存储结构*顺序存储结构：适用于完全二叉树。将二叉树的节点按层序编号，依次存放在数组中。对于一般二叉树，需将其补成完全二叉树的形式，可能会浪费存储空间。*链式存储结构（二叉链表）：每个节点包含数据域和两个指针域（左指针lchild指向左孩子，右指针rchild指向右孩子）。n个节点的二叉链表共有n+1个空指针域（可用于构造线索二叉树）。在某些应用中，还会使用三叉链表（增加一个指向双亲的指针域）。5.4二叉树的遍历遍历是指按某种规律对树中的每个节点访问且仅访问一次。二叉树的常见遍历方法有：*前序遍历(DLR)：根节点->左子树->右子树。*中序遍历(LDR)：左子树->根节点->右子树。*后序遍历(LRD)：左子树->右子树->根节点。*层序遍历：从根节点开始，按层次从上到下，同一层从左到右依次访问节点。*遍历实现：前、中、后序遍历可用递归或非递归（借助栈）实现；层序遍历通常借