数据结构知识点复习资料

数据结构知识点复习精要：梳理核心概念，夯实编程基础数据结构，作为计算机科学的基石，是每一位从业者必须深耕细作的领域。它不仅是算法设计的骨架，更是高效解决问题的关键。这份复习资料旨在帮助你系统性地回顾核心知识点，巩固理解，提升应用能力。请记住，数据结构的学习不仅在于“知其然”，更在于“知其所以然”，以及“何时用其然”。一、数据结构概览与基本概念1.1数据结构的定义与研究对象数据结构是计算机中组织和存储数据的特定方式，它涉及数据元素之间的逻辑关系、数据在计算机中的存储表示，以及施加在这些数据上的操作。简而言之，它关注“数据如何组织”、“如何存储”以及“如何高效操作”。其研究对象主要包括：*数据的逻辑结构：数据元素之间的抽象关系，独立于计算机，如线性结构、树形结构、图状结构等。*数据的存储结构（物理结构）：逻辑结构在计算机内存中的具体实现，如顺序存储、链式存储、索引存储、散列存储。*数据的运算：对数据元素可以执行的操作，如插入、删除、查找、排序、修改等，这些操作的实现依赖于具体的存储结构。1.2算法与算法复杂度分析数据结构与算法密不可分。算法是解决特定问题的步骤描述，而数据结构为算法提供了操作的对象和空间。*算法的特性：有穷性、确定性、可行性、输入、输出。*算法设计的目标：正确性、可读性、健壮性、高效率（时间复杂度低）、低存储量（空间复杂度低）。复杂度分析是衡量算法优劣的核心：*时间复杂度(T(n))：定量描述算法执行时间随输入规模n增长的趋势。通常关注最坏情况或平均情况。分析时，忽略常数项和低阶项，保留最高阶项。常见量级：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)。*空间复杂度(S(n))：算法在运行过程中临时占用存储空间大小随输入规模n增长的趋势。同样关注数量级。理解复杂度分析，能帮助我们在不同方案间做出明智选择，避免陷入低效的陷阱。二、线性结构线性结构的特点是数据元素之间存在一对一的线性关系，除首尾元素外，每个元素有唯一的前驱和后继。2.1数组(Array)*定义：一组具有相同类型的元素，在内存中连续存储，通过下标（索引）直接访问。*特点：*随机访问能力强，时间复杂度O(1)。*大小固定（静态数组），或在动态数组中虽可扩容但需付出拷贝代价。*插入和删除操作在中间或头部时效率低，需移动大量元素，时间复杂度O(n)。*应用场景：需要频繁随机访问，较少插入删除的场景。2.2链表(LinkedList)*定义：由一系列节点组成，每个节点包含数据域和指向下一节点（或前一节点）的指针（或引用）。逻辑上连续，物理上可不连续。*常见类型：*单链表：每个节点只有指向下一节点的指针。*双链表：每个节点有指向前驱和后继的指针，可双向遍历。*循环链表：首尾节点相连，可用于解决约瑟夫环等问题。*特点：*动态分配内存，无需预先指定大小。*插入和删除操作（已知前驱节点时）效率高，时间复杂度O(1)。*随机访问能力弱，需从头遍历，时间复杂度O(n)。*额外空间存储指针域。*应用场景：频繁进行插入删除操作，且对随机访问要求不高的场景，如实现栈、队列、邻接表等。2.3栈(Stack)*定义：一种特殊的线性表，遵循“后进先出”(LIFO,LastInFirstOut)的操作原则。只允许在表的一端（栈顶）进行插入和删除。*基本操作：*`push(x)`：将元素x压入栈顶。*`pop()`：移除并返回栈顶元素。*`top()`或`peek()`：返回栈顶元素，不删除。*`isEmpty()`：判断栈是否为空。*实现方式：可用数组（顺序栈）或链表（链式栈）实现。*应用场景：表达式求值、括号匹配、函数调用栈、深度优先搜索（DFS）、撤销操作等。2.4队列(Queue)*定义：一种特殊的线性表，遵循“先进先出”(FIFO,FirstInFirstOut)的操作原则。只允许在表的一端（队尾）插入，在另一端（队头）删除。*基本操作：*`enqueue(x)`：将元素x加入队尾。*`dequeue()`：移除并返回队头元素。*`front()`：返回队头元素，不删除。*`isEmpty()`：判断队列是否为空。*常见类型与实现：*顺序队列：用数组实现，易出现“假溢出”。*循环队列：改进的顺序队列，通过取模操作使数组空间循环利用，解决假溢出。*链式队列：用链表实现，无需担心队列大小限制。*应用场景：广度优先搜索（BFS）、任务调度、缓冲处理、生产者-消费者模型等。*特殊队列：*双端队列(Deque)：允许在两端进行插入和删除操作。*优先队列(PriorityQueue)：元素具有优先级，出队时总是优先级最高的元素先出。通常基于堆实现。三、非线性结构非线性结构中，数据元素之间存在一对多或多对多的复杂关系。3.1树(Tree)树是一种重要的非线性数据结构，它由n个节点组成，节点间存在层次关系，有且仅有一个根节点，其余节点分为若干个互不相交的子树。*基本术语：根、叶子、父节点、子节点、兄弟节点、祖先、子孙、深度（从根到节点的路径长度）、高度（从节点到最深叶子的路径长度）、层。*树的性质：（以二叉树为例阐述部分通用思想，具体性质略）3.1.1二叉树(BinaryTree)*定义：每个节点最多有两棵子树（左子树和右子树）的树。*特殊二叉树：*满二叉树：所有叶子节点都在同一层，且非叶子节点都有两个子节点。*完全二叉树：除最后一层外，其余各层节点数均满，最后一层节点从左到右连续排列。适合顺序存储（数组）。*二叉树的遍历（核心操作）：*前序遍历(DLR)：根节点->左子树->右子树*中序遍历(LDR)：左子树->根节点->右子树*后序遍历(LRD)：左子树->右子树->根节点*层序遍历：按层次从上到下，同一层从左到右访问节点。*遍历可以通过递归或借助栈（迭代法）实现；层序遍历通常借助队列。3.1.2特殊二叉树及其应用*二叉搜索树(BST,BinarySearchTree)：*性质：左子树上所有节点值<根节点值；右子树上所有节点值>根节点值；左右子树也分别为BST。*操作：插入、删除、查找。在平均情况下，时间复杂度为O(logn)，最坏情况下（退化为链表）为O(n)。*平衡二叉树(AVLTree)：*性质：左右子树的高度差（平衡因子）的绝对值不超过1。*目的：维持BST的平衡，确保操作的时间复杂度稳定在O(logn)。*核心操作：通过旋转（左旋、右旋、左右旋、右左旋）来恢复平衡。*红黑树：*一种自平衡的二叉查找树，通过颜色（红或黑）规则维持树的“黑平衡”，从而保证大致平衡。*相比AVL树，旋转操作更少，插入删除效率更高，常用于实现集合、映射等。*堆(Heap)：*一种特殊的完全二叉树，分为最大堆（父节点值>=子节点值）和最小堆（父节点值<=子节点值）。*常用数组实现。*核心操作：插入、删除堆顶元素（ExtractMax/ExtractMin）、堆化。*应用：实现优先队列、堆排序。*字典树(Trie,前缀树)：*一种用于高效存储和查找字符串集合的树状结构。*特点：根节点为空，每个节点代表一个字符，从根到某一节点的路径表示一个字符串。*应用：前缀匹配、自动补全、拼写检查。3.2图(Graph)图是一种比树更复杂的非线性结构，由顶点集和边集组成，用于表示多对多的关系。*基本术语：顶点、边、有向图、无向图、权值、网（带权图）、邻接、路径、环、连通图（无向）、强连通图（有向）、度（入度、出度）。*图的存储表示：*邻接矩阵：用二维数组表示顶点间的邻接关系。空间复杂度O(n²)，适合稠密图。*邻接表：为每个顶点建立一个链表，存储其所有邻接顶点。空间复杂度O(n+e)，适合稀疏图。*图的遍历（核心操作）：*深度优先搜索(DFS)：类似树的前序遍历，尽可能深地搜索，用栈（或递归）实现。*广度优先搜索(BFS)：类似树的层序遍历，按层次向外扩展，用队列实现。*图的应用算法：*最短路径：Dijkstra算法（单源最短路径，权值非负）、Floyd-Warshall算法（多源最短路径）、Bellman-Ford算法（可处理负权）。*最小生成树(MST)：Prim算法、Kruskal算法（需借助并查集）。*拓扑排序：针对有向无环图(DAG)，将顶点排成一个线性序列，使得所有有向边均从序列中前面的顶点指向后面的顶点。*关键路径：在有向无环图中，从源点到汇点的最长路径，用于项目管理。四、查找算法查找是数据处理中最基本的操作之一，其效率直接影响程序性能。4.1基本查找方法*顺序查找(LinearSearch)：逐个比较，直到找到或遍历结束。时间复杂度O(n)。简单但低效。*二分查找(BinarySearch)：要求线性表有序。每次将待查区间缩小一半。时间复杂度O(logn)。高效但局限于有序的顺序存储结构。*分块查找(BlockSearch)：结合顺序查找和二分查找的思想，将表分成块，块内无序，块间有序。先确定块，再在块内顺序查找。4.2哈希表(HashTable)哈希表，也称为散列表，是一种通过哈希函数直接将关键字映射到存储位置的数据结构，期望达到O(1)的查找效率。*哈希函数(HashFunction)：将关键字k映射到地址H(k)的函数。设计目标：计算简单、分布均匀。*冲突(Collision)：不同关键字映射到同一地址。*冲突解决方法：*开放定址法：当冲突发生时，按照某种规则在散列表中寻找下一个空位置。如线性探测、平方探测、双散列。*链地址法(SeparateChaining)：将哈希地址相同的元素存储在同一个链表中。*负载因子(LoadFactor)：哈希表中元素个数与表长的比值，是影响冲突概率的重要因素。哈希表的查找效率取决于哈希函数、冲突解决方法和负载因子。五、排序算法排序是将一组数据按特定顺序（通常是升序或降序）重新排列的过程。5.1排序算法分类*内部排序：数据全部在内存中完成排序。*外部排序：数据量大，无法全部装入内存，需借助外部存储。5.2常见内部排序算法*插入类排序：*直接插入排序：将元素逐个插入到已排好序的子序列中。时间复杂度O(n²)，稳定。*希尔排序(ShellSort)：按增量将序列分组，对每组进行直接插入排序，逐步减小增量。时间复杂度受增量序列影响，不稳定。*交换类排序：*冒泡排序(BubbleSort)：重复比较相邻元素，将大（小）的元素“冒泡”到末尾。时间复杂度O(n²)，稳定。*快速排序(QuickSort)：选择基准元素，将序列分割为两部分，递归排序。平均时间复杂度O(nlogn)，最坏O(n²)，不稳定。实际应用中表现优异。*选择类排序：*直接选择排序：每次从待排序部分选出最小（大）元素，放到已排序部分的末尾。时间复杂度O(n²)，不稳定。*堆排序(HeapSort)：利用堆的特性，每次提取堆顶元素（最大或最小）并调整堆。时间复杂度O(nlogn)，不稳定。*归并排序(MergeSort)：分治法思想，将序列分成两半，分别排序后合并。时间复杂度O(nlogn)，稳定，但需要额外空间。*基数排序(RadixSort)：非比较排序，根据数字的每一位进行排序。时间复杂度O(d*(n+r))，d为位数，r为基数，稳定，需额外空间。算法选择需综合考虑数据规模、初始状态、稳定性要求、时空复杂度等因素。六、数据结构设计与选择面对实际问题，如何选择和设计合适的数据结构是关键。*明确操作需求：主要的操作是什么？（查找、插入、删除、排序的频率）*分析数据特性：数据量大小、是否有序、关键字分布等。*权衡时空效率：根据操作需求和数据特性，评估不同数据结构的