自考02331数据结构重点总结

自考02331数据结构重点总结一、基本概念与术语本章是整个课程的基础，理解并牢记相关概念是后续学习的前提。1.数据、数据元素、数据项：数据是信息的载体；数据元素是数据的基本单位，通常由若干数据项组成；数据项是构成数据元素的最小单位。需明确三者之间的层次关系。2.数据结构：指相互之间存在一种或多种特定关系的数据元素的集合。它包含三个方面的内容：逻辑结构、存储结构和数据的运算。*逻辑结构：从逻辑关系上描述数据，与数据的存储无关。主要分为线性结构（如线性表、栈、队列）和非线性结构（如树、图）。*存储结构（物理结构）：数据元素及其关系在计算机存储器中的表示。常见的有顺序存储、链式存储、索引存储和散列存储。需理解不同存储结构的特点及适用场景。*数据的运算：对数据施加的操作，如插入、删除、查找、排序等。运算的实现依赖于数据的存储结构。3.算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有有穷性、确定性、可行性、输入和输出五个基本特性。4.算法的时间复杂度：度量算法执行时间随问题规模增长的趋势，通常用大O符号表示。重点掌握常见的时间复杂度类型（如O(1)、O(logn)、O(n)、O(nlogn)、O(n²)等）及其分析方法。5.算法的空间复杂度：度量算法执行过程中所需存储空间随问题规模增长的趋势。二、线性表线性表是最基本、最常用的数据结构之一，其特点是数据元素之间存在一对一的线性关系。1.线性表的定义与基本操作：理解线性表的逻辑结构特性，掌握初始化、插入、删除、查找、遍历等基本操作的逻辑描述。2.线性表的顺序存储结构（顺序表）：*特点：用一段连续的存储单元依次存储线性表的数据元素。*优点：随机存取（通过下标直接访问），存储密度高。*缺点：插入和删除操作可能需要移动大量元素，存储空间固定，可能造成浪费或溢出。*重点掌握顺序表插入和删除操作的实现原理及时间复杂度分析。3.线性表的链式存储结构（链表）：*特点：用任意的存储单元存储数据元素，通过指针（或引用）表示元素间的逻辑关系。*优点：插入和删除操作无需移动元素，只需修改指针，存储空间动态分配。*缺点：不能随机存取，需从头指针开始遍历，存储密度较低。*单链表：掌握头指针、头结点的概念，以及单链表的创建（头插法、尾插法）、插入、删除、查找等操作的实现。*双链表：理解双向指针的作用，掌握其插入和删除操作的特点。*循环链表：理解首尾相接的特点，以及如何判断链表的结束。4.顺序表与链表的比较：根据实际问题需求，能够选择合适的线性表存储结构。三、栈和队列栈和队列是两种特殊的线性表，它们的操作遵循特定的规则。1.栈（Stack）：*定义：只允许在表的一端（栈顶）进行插入和删除操作的线性表，遵循“后进先出”（LIFO）原则。*基本操作：入栈（Push）、出栈（Pop）、取栈顶元素（GetTop）、判空等。*存储结构：顺序栈（数组实现）和链栈（链表实现）。重点掌握顺序栈的实现及可能出现的上溢和下溢问题。*应用：表达式求值（中缀转后缀、后缀表达式求值）、括号匹配、函数调用与递归等。2.队列（Queue）：*定义：只允许在表的一端（队尾）插入，在另一端（队头）删除的线性表，遵循“先进先出”（FIFO）原则。*基本操作：入队（Enqueue）、出队（Dequeue）、取队头元素（GetHead）、判空等。*存储结构：顺序队列（数组实现）和链队列（链表实现）。重点理解顺序队列中“假溢出”问题及循环队列的解决方案（利用模运算）。*应用：缓冲处理、层次遍历、任务调度等。四、串串是由字符构成的特殊线性表。1.串的定义与基本操作：理解串的概念，掌握串的赋值、连接、比较、求子串、查找子串位置（模式匹配）等操作。2.串的存储结构：顺序存储和链式存储。3.模式匹配算法：*朴素的模式匹配算法：理解其基本思想和实现过程，分析其时间复杂度。*KMP算法：理解其改进思路，即利用已匹配的部分信息避免不必要的回溯。重点掌握部分匹配值（或失效函数）的概念及计算方法，以及KMP算法的实现步骤。五、数组和广义表数组和广义表可视为线性表的扩展。1.数组：*定义：n维数组是一种“同构”的数据结构，每个元素由n个下标唯一确定。*存储结构：重点掌握二维数组的按行优先和按列优先存储方式，以及数组元素地址的计算方法。*特殊矩阵的压缩存储：理解对称矩阵、三角矩阵、对角矩阵等特殊矩阵的特点及其压缩存储方法，以节省存储空间。*稀疏矩阵：了解稀疏矩阵的概念及其三元组表示法和十字链表表示法。2.广义表：*定义：是线性表的推广，其元素可以是原子，也可以是子表。六、树和二叉树树型结构是一类重要的非线性结构，其中二叉树是最常用且最重要的类型。1.树的基本概念：节点、度、叶子节点、分支节点、双亲、孩子、兄弟、层次、深度、森林等。2.二叉树：*定义：每个节点最多有两棵子树，且有左右之分，次序不能颠倒。*性质：掌握二叉树的五个重要性质（如第i层最多有2^(i-1)个节点；深度为k的二叉树最多有2^k-1个节点等）。*特殊二叉树：满二叉树、完全二叉树。理解完全二叉树的特点及其节点编号的规律。*存储结构：顺序存储（适用于完全二叉树）和链式存储（二叉链表、三叉链表）。3.二叉树的遍历：这是重点和难点。*前序遍历（根-左-右）*中序遍历（左-根-右）*后序遍历（左-右-根）*层序遍历*掌握这四种遍历的递归和非递归实现方法，并能根据遍历序列还原二叉树（尤其是已知前序和中序，或中序和后序序列）。4.线索二叉树：理解线索化的目的（充分利用空指针域，提高遍历效率），掌握线索二叉树的构造和遍历方法。5.树和森林：*树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法（重点，可将树转换为二叉树）。*树和森林与二叉树的转换：掌握树转换为二叉树、森林转换为二叉树的方法，以及二叉树还原为树或森林的方法。*树和森林的遍历：先根遍历、后根遍历。6.哈夫曼树（最优二叉树）：*定义：带权路径长度（WPL）最小的二叉树。*哈夫曼算法：掌握构造哈夫曼树的步骤。*哈夫曼编码：利用哈夫曼树进行编码，实现数据的压缩，理解其前缀编码特性。七、图图是一种比树更为复杂的非线性结构，节点之间的关系可以是任意的。1.图的基本概念：顶点、边、有向图、无向图、完全图、稀疏图、稠密图、度（入度、出度）、路径、路径长度、回路、连通图、连通分量、强连通图、强连通分量、权、网等。2.图的存储结构：*邻接矩阵：用二维数组表示顶点间的邻接关系。优点是查找方便，缺点是空间复杂度高。*邻接表：对每个顶点建立一个单链表，存储其所有邻接顶点。优点是节省空间，缺点是查找不如邻接矩阵方便。*理解两种存储结构的构造方法及其适用场景。3.图的遍历：*深度优先搜索（DFS）：类似于树的前序遍历，可递归或借助栈实现。*广度优先搜索（BFS）：类似于树的层序遍历，借助队列实现。*掌握两种遍历算法的实现过程，并能根据给定图写出遍历序列。4.最小生成树：*定义：在连通网中，生成树是包含所有顶点的极小连通子图。最小生成树是各边权值之和最小的生成树。*Prim算法：从一个顶点开始，逐步添加权值最小的边，形成最小生成树。*Kruskal算法：按边的权值从小到大排序，依次添加不构成回路的边，形成最小生成树。*理解两种算法的基本思想和步骤。5.最短路径：*Dijkstra算法：求从一个源点到其他各顶点的最短路径。*Floyd算法：求图中任意两对顶点之间的最短路径。*理解算法的基本思想和适用场景。6.拓扑排序：针对有向无环图（DAG），将所有顶点排成一个线性序列，使得对图中任意一条有向边(u,v)，在序列中u都出现在v之前。掌握拓扑排序的步骤（借助入度和队列）。八、查找查找是数据处理中最常用的操作之一。1.基本概念：查找表、关键字、平均查找长度（ASL）。2.静态查找表：*顺序查找：从表的一端开始，逐个比较。优点是对表结构无要求，缺点是效率低（ASL=(n+1)/2）。*折半查找（二分查找）：要求表是有序的顺序表。优点是效率高（ASL≈log2(n+1)-1），缺点是只适用于有序顺序表。掌握其实现过程。*分块查找（索引顺序查找）：结合了顺序查找和折半查找的优点，将表分成若干块，块内无序，块间有序。3.动态查找表：*二叉排序树（BST）：定义（左子树所有节点值小于根节点值，右子树所有节点值大于根节点值），掌握其插入、删除、查找操作。理解二叉排序树的查找效率与树的形态有关。*平衡二叉树（AVL树）：定义（左右子树深度之差的绝对值不超过1），理解其平衡调整的基本思想（LL、RR、LR、RL四种旋转类型）。4.哈希表（散列表）：*基本思想：通过哈希函数将关键字映射到表中的一个位置进行存储。*哈希函数的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法等。*处理冲突的方法：开放定址法（线性探测、二次探测、伪随机探测）、链地址法（拉链法）。*理解哈希表的查找过程、成功与不成功的平均查找长度，以及影响哈希表查找效率的因素（负载因子、哈希函数、冲突处理方法）。九、排序排序是将一组数据元素按关键字递增或递减的顺序重新排列的过程。1.基本概念：排序、稳定排序与不稳定排序、内排序与外排序。2.插入排序：*直接插入排序：将待排序元素插入到已排序序列的合适位置。时间复杂度O(n²)，稳定。*折半插入排序：在直接插入排序的基础上，用折半查找确定插入位置。时间复杂度O(n²)，稳定。*希尔排序（缩小增量排序）：按增量将序列分组，对每组进行直接插入排序，逐步缩小增量。时间复杂度与增量序列有关，不稳定。3.交换排序：*冒泡排序：重复比较相邻元素，将大的元素“冒泡”到末尾。时间复杂度O(n²)，稳定。*快速排序：选择一个基准元素，将序列分割成两部分，左部小于基准，右部大于基准，再递归排序。平均时间复杂度O(nlogn)，最坏O(n²)，不稳定。掌握其划分思想。4.选择排序：*简单选择排序：每次从待排序序列中选择最小（或最大）元素，放到已排序序列的末尾。时间复杂度O(n²)，不稳定。*堆排序：利用堆（大根堆或小根堆）的特性进行排序。时间复杂度O(nlogn)，不稳定。理解堆的定义、建堆、堆调整过程。5.归并排序：将两个或多个有序子序列合并成一个有序序列。二路归并排序的时间复杂度O(nlogn)，稳定，但需要额外的辅助空间。6.基数排序：按照关键字的各位值进行排序，属于分配式排序。时间复杂度O(d*(n+r))，稳定，d为关键字位数，r为基数。7.各种排序算法的比较与应用：从时间复杂度、空间复杂度、稳定性、适用场景等方面对各种排序算法进行比较，能够根据实际问题选择合适的排序算法。十、总结与备考建议数据结构课程概念抽象，算法灵活，需要在理解的基础上多做练习。建议考生：1.梳理知识体系：以