数据结构总复习资料

数据结构总复习资料引言数据结构，作为计算机科学与技术领域的基石，其重要性不言而喻。它不仅是程序设计的灵魂，更是高效算法实现的前提。无论是进行系统开发、算法优化，还是应对各类技术面试，扎实的数据结构功底都是不可或缺的。本资料旨在梳理数据结构的核心知识，帮助读者构建清晰的知识框架，巩固理解，提升应用能力。我们将从基本概念出发，逐步深入各类经典数据结构的特性、操作及应用场景，力求做到深入浅出，兼顾理论与实践。一、数据结构基本概念1.1数据与数据结构数据是信息的载体，是对客观事物的符号表示，例如数字、文本、图像等。数据元素是数据的基本单位，而数据项则是构成数据元素的最小不可分割单位。数据结构指的是相互之间存在一种或多种特定关系的数据元素的集合。它主要研究数据的逻辑结构、物理结构（存储结构）以及施加在数据上的运算。1.2逻辑结构逻辑结构描述的是数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。常见的逻辑结构可分为：*线性结构：数据元素之间存在一对一的线性关系。例如：数组、链表、栈、队列。*非线性结构：数据元素之间存在一对多或多对多的关系。例如：树、图。1.3物理结构（存储结构）物理结构指数据元素及其关系在计算机存储器中的具体表示方式。它是依赖于计算机的。主要有：*顺序存储结构：将数据元素存放在连续的存储单元中，其逻辑关系由存储单元的邻接关系来体现。例如：数组。*链式存储结构：数据元素可以存放在不连续的存储单元中，通过指针或引用表示元素之间的逻辑关系。例如：链表。*索引存储结构：在存储数据元素的同时，建立附加的索引表。索引表中的每一项称为索引项，包含关键字和该关键字对应的数据元素的存储地址。*散列存储结构：根据数据元素的关键字直接计算出该元素的存储地址，又称哈希存储。1.4算法与算法复杂度算法是解决特定问题的步骤的有限序列。一个好的算法应具备正确性、可读性、健壮性、高效率和低存储量需求。算法复杂度分析是评估算法效率的重要手段，主要包括：*时间复杂度：指算法执行过程中所需要的基本操作次数与问题规模之间的函数关系，通常用大O符号（O）来渐进表示，如O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等。分析时通常关注最坏情况下的时间复杂度。*空间复杂度：指算法在执行过程中所需要的额外存储空间与问题规模之间的函数关系，同样用大O符号表示。二、线性表线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的线性关系。2.1线性表的定义与基本操作线性表是具有相同特性的数据元素的一个有限序列。其基本操作包括：初始化、判空、求长度、获取元素、查找元素、插入元素、删除元素等。2.2顺序表（数组）顺序表是线性表的顺序存储结构，即把线性表中的所有元素按照其逻辑顺序依次存储在计算机内存中一块连续的存储空间内。*特点：元素地址连续，可随机访问（通过下标），存储密度高；但插入和删除操作可能需要移动大量元素，且存储空间大小固定，可能存在溢出问题。*基本操作实现：*访问：O(1)，通过下标直接定位。*插入：平均O(n)，需移动插入位置之后的元素。*删除：平均O(n)，需移动删除位置之后的元素。2.3链表链表是线性表的链式存储结构，它不需要用连续的存储空间，而是通过“指针”将分散的节点连接起来。每个节点包含数据域和指针域。*特点：存储空间灵活，插入和删除操作无需移动大量元素（只需修改指针）；但不能随机访问，需从头指针开始遍历，存储密度较低（需额外存储指针）。*常见类型：*单链表：每个节点只有一个指针域，指向下一个节点。*双链表：每个节点有两个指针域，分别指向前一个和后一个节点，可双向遍历。*循环链表：链表的最后一个节点的指针指向头节点（或第一个节点），形成一个环，可从任一节点出发遍历整个链表。*基本操作实现：*访问：O(n)，需从头遍历。*插入：O(1)（在已知前驱节点的情况下）。*删除：O(1)（在已知前驱节点的情况下）。2.4顺序表与链表的比较与选择选择何种存储结构，需根据具体应用场景权衡。若需频繁随机访问，较少插入删除，顺序表更合适；若插入删除频繁，且元素个数不确定，链表更为灵活。三、栈与队列栈和队列是两种特殊的线性表，它们的操作受到一定的限制，属于受限的线性结构。3.1栈(Stack)栈是一种“先进后出”（LIFO,LastInFirstOut）的线性表。仅允许在表的一端（称为栈顶，Top）进行插入和删除操作，另一端称为栈底（Bottom）。*基本操作：*入栈(Push)：在栈顶插入元素。*出栈(Pop)：删除并返回栈顶元素。*取栈顶元素(Top/Peek)：返回栈顶元素，不删除。*判空(IsEmpty)：判断栈是否为空。*存储实现：*顺序栈：用数组实现，需注意栈满溢出问题。*链栈：用链表实现，通常以头节点作为栈顶，便于操作。*典型应用：表达式求值（中缀转后缀、后缀表达式计算）、括号匹配、函数调用与递归、浏览器历史记录等。3.2队列(Queue)队列是一种“先进先出”（FIFO,FirstInFirstOut）的线性表。仅允许在表的一端（队尾，Rear）进行插入操作，在另一端（队头，Front）进行删除操作。*基本操作：*入队(Enqueue)：在队尾插入元素。*出队(Dequeue)：删除并返回队头元素。*取队头元素(Front)：返回队头元素，不删除。*判空(IsEmpty)：判断队列是否为空。*存储实现：*顺序队列：用数组实现。为解决“假溢出”问题，通常采用循环队列的形式。循环队列中，队满和队空的判断需要特别处理（如少用一个元素空间或设置标志位）。*链队列：用链表实现，通常设置头指针和尾指针分别指向队头和队尾。*典型应用：进程调度、消息缓冲、广度优先搜索（BFS）等。*特殊队列：*双端队列(Deque)：允许在两端进行插入和删除操作。*优先级队列(PriorityQueue)：元素的出队顺序由其优先级决定，而非插入顺序。通常基于堆实现。四、树与二叉树树形结构是一类重要的非线性结构，它以分支关系定义层次结构，在客观世界中广泛存在，如组织机构、家族谱系等。4.1树的基本概念*树(Tree)：n(n≥0)个节点的有限集。当n=0时，称为空树。在任意一棵非空树中：有且仅有一个特定的称为根(Root)的节点；当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每个集合本身又是一棵树，称为根的子树(Subtree)。*基本术语：节点的度、树的度、叶子节点、分支节点、父节点、子节点、兄弟节点、祖先、子孙、节点的层次、树的深度（高度）、森林等。4.2二叉树(BinaryTree)二叉树是每个节点最多有两棵子树的树结构，通常子树被称为“左子树”和“右子树”。二叉树的子树有左右之分，次序不能颠倒。*特殊二叉树：*满二叉树：所有叶子节点都在同一层，且非叶子节点都有两个子节点。*完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。完全二叉树通常采用顺序存储方式，可高效地通过数组下标计算父子节点位置。*二叉树的性质：*性质1：在二叉树的第i层上至多有2^(i-1)个节点(i≥1)。*性质2：深度为k的二叉树至多有2^k-1个节点(k≥1)。*性质3：对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。*二叉树的存储结构：*顺序存储结构：适用于完全二叉树。将节点按层序编号，依次存入数组。*链式存储结构(二叉链表)：每个节点包含数据域和两个指针域（左孩子指针、右孩子指针）。*二叉树的遍历(Traversal)：*先序遍历(Pre-order)：根->左子树->右子树。*中序遍历(In-order)：左子树->根->右子树。*后序遍历(Post-order)：左子树->右子树->根。*层序遍历(Level-order)：从根节点开始，按层次从上到下，同一层从左到右依次访问。遍历是树结构中最基本的操作，是许多复杂操作的基础。遍历可以通过递归或非递归（借助栈或队列）的方式实现。4.3树、森林与二叉树的转换树和森林可以通过特定的规则转换为二叉树，以便利用二叉树的存储和操作算法。常用的转换方法为“孩子-兄弟表示法”，即将树中第一个孩子作为左子树，下一个兄弟作为右子树。4.4哈夫曼树(HuffmanTree)与哈夫曼编码哈夫曼树，又称最优二叉树，是一类带权路径长度最短的树。所谓树的带权路径长度，是树中所有叶子节点的权值乘以其到根节点的路径长度之和。*哈夫曼算法：构造哈夫曼树的方法。基本思想是：1.根据给定的n个权值{w1,w2,...,wn}构造n棵只有根节点的二叉树，形成森林F。2.在F中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，新树的根节点权值为其左右子树根节点权值之和。3.从F中删除这两棵树，并将新构造的树加入F。4.重复步骤2和3，直到F中只剩下一棵树为止，该树即为哈夫曼树。*哈夫曼编码：利用哈夫曼树进行的一种不等长前缀编码。将出现频率高的字符用短编码表示，频率低的用长编码表示，可有效减少总编码长度，实现数据压缩。编码过程中，左分支标记为0，右分支标记为1，从根到叶子节点的路径上的0和1序列即为该叶子节点字符的编码。4.5常用树结构及其应用*二叉搜索树(BST,BinarySearchTree)：*特点：左子树上所有节点的值均小于根节点的值；右子树上所有节点的值均大于根节点的值；左右子树也分别为二叉搜索树。*操作：插入、删除、查找。在平均情况下，这些操作的时间复杂度为O(logn)，最坏情况下（退化为单链表）为O(n)。*平衡二叉树(AVLTree)：*特点：是一种自平衡的二叉搜索树。它要求左右子树的高度差（平衡因子）的绝对值不超过1。*目的：通过旋转操作（LL,RR,LR,RL）来维持树的平衡，确保在最坏情况下操作的时间复杂度仍为O(logn)。*红黑树：一种高效的平衡二叉搜索树，通过颜色（红或黑）的约束来维持树的近似平衡，插入、删除、查找操作的时间复杂度均为O(logn)，在很多高级语言的库实现中被广泛应用（如C++STL的map,set）。*B树与B+树：*应用：数据库索引的实现。*堆(Heap)：*特点：一种特殊的完全二叉树。大顶堆（最大堆）中每个父节点的值都大于或等于其孩子节点的值；小顶堆（最小堆）则相反。*操作：建堆、插入、删除（堆顶元素）、堆排序。主要应用于优先队列、堆排序算法。五、图(Graph)图是一种比树更为复杂的非线性数据结构。在图结构中，节点之间的关系可以是任意的，每个节点都可以与其他多个节点相关联。5.1图的基本概念*图(Graph)：由顶点集(VertexSet)V和边集(EdgeSet)E组成，记为G=(V,E)。*顶点(Vertex/Node)：图中的数据元素。*边(Edge)：顶点之间的逻辑关系。*有向图与无向图：边有方向的图称为有向图，边无方向的图称为无向图。*顶点的度、入度、出度：无向图中，顶点的度是依附于该顶点的边的数目；有向图中，入度是指向该顶点的边的数目，出度是从该顶点出发的边的数目。*路径与回路：路径是顶点序列，其中相邻顶点之间有边相连。起点和终点相同的路径称为回路或环。*连通图与强连通图：无向图中，任意两个顶点都有路径相通，则为连通图；有向图中，任意两个顶点都双向可达，则为强连通图。*子图：由图的部分顶点和部分边组成的图。*网(Network)：边带权值的图。5.2图的存储结构*邻接矩阵(AdjacencyMatrix)：*表示：用一个n阶方阵A来表示具有n个顶点的图。A[i][j]表示顶点i和顶点j之间的关系（是否有边，边的权值）。*特点：结构简单，查找边快速（O(1)）；但存储空间大（O(n²)），不适合稀疏图。*邻接表(AdjacencyList)：*表示：为每个顶点建立一个单链表，链表中存储与该顶点相邻接的顶点信息和相关边的信息。*特点：存储空间小（O(n+e)），适合稀疏图；查找与一个顶点相关的边方便，但判断两顶点间是否有边需遍历对应链表。*其他存储方式：十字链表（有向图）、邻接多重表（无向图）等，用于特定场景以提高操作效率。5.3图的遍历图的遍历是从图中某一顶点出发，按照某种搜索方式沿着图中的边访问