数据结构(c描述)电子教案第5章

数据结构(c描述)电子教案第5章目录绪论线性表栈与队列串与数组树与二叉树图论基础查找技术排序技术01绪论数据元素数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据项数据的不可分割的最小单位。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据对象性质相同的数据元素的集合，是数据的一个子集。数据结构基本概念数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型表示算法算法的特性算法设计的要求算法分析算法和算法分析是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。正确性、可读性、健壮性、效率与低存储量需求。有穷性、确定性、可行性、输入、输出。时间复杂度、空间复杂度。02线性表线性表是由n（n>=0）个具有相同类型的数据元素（结点）a1，a2，...，an组成的有序序列，其中n为表长，当n=0时该线性表是一个空表。线性表的基本操作包括创建、插入、删除、查找、遍历等。这些操作都可以通过相应的算法来实现。线性表定义及基本操作基本操作线性表定义顺序存储结构是用一段连续的存储空间来存放线性表中的数据元素，逻辑上相邻的元素在物理位置上也相邻。存储方式顺序存储结构的优点是存储密度大、可以随机存取；缺点是插入和删除操作需要移动大量元素。优缺点顺序存储结构链式存储结构是用一组任意的存储空间来存放线性表中的数据元素，这组存储空间可以是连续的，也可以是不连续的。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。存储方式链式存储结构的优点是插入和删除操作不需要移动元素，只需要修改指针；缺点是存储密度小、不可以随机存取。优缺点链式存储结构03栈与队列栈的定义：栈（Stack）是一种特殊的线性数据结构，其操作只能在一端进行，遵循后进先出（LIFO,LastInFirstOut）的原则。入栈（Push）：在栈顶插入一个元素。出栈（Pop）：删除栈顶元素并返回其值。查看栈顶（Top）：返回栈顶元素的值，但不删除。判断栈空（Empty）：检查栈是否为空。栈定义及基本操作队列的定义：队列（Queue）也是一种特殊的线性数据结构，其操作在两端进行，遵循先进先出（FIFO,FirstInFirstOut）的原则。入队（Enqueue）：在队尾插入一个元素。出队（Dequeue）：删除队头元素并返回其值。查看队头（Front）：返回队头元素的值，但不删除。判断队空（Empty）：检查队列是否为空。0102030405队列定义及基本操作表达式求值利用栈的后进先出特性，可以方便地处理算术表达式中的括号和运算符。函数调用在程序执行过程中，函数调用会形成一个调用栈，用于保存函数调用的上下文信息。栈与队列应用举例浏览器前进后退：浏览器历史记录可以用两个栈来实现前进和后退功能。栈与队列应用举例打印机中的打印任务可以看作是一个队列，按照先进先出的原则进行打印。打印任务管理CPU任务调度网络数据传输操作系统中的CPU任务调度可以采用队列结构，按照任务的优先级和时间顺序进行调度。在网络通信中，数据的传输可以采用队列结构，确保数据按照发送顺序进行接收和处理。030201栈与队列应用举例04串与数组串的定义01串（string）是由零个或多个字符组成的有限序列，又名叫字符串。串的基本操作02串的基本操作包括串的赋值、串的比较、串的连接、串的求长度、串的复制、串的清空等。串的存储结构03串的存储结构包括顺序存储结构和链式存储结构。其中，顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列；链式存储结构则是用链表来存储串中的字符序列。串定义及基本操作数组的定义数组（Array）是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组的基本操作数组的基本操作包括数组的创建、数组的初始化、数组的访问、数组的遍历、数组的排序等。数组的存储结构数组的存储结构通常采用顺序存储结构，即使用一块连续的存储空间来存放数组的所有元素。数组定义及基本操作特殊矩阵是指具有特殊形状或特殊性质的矩阵，如对称矩阵、三角矩阵、稀疏矩阵等。特殊矩阵的定义对于特殊矩阵，可以采用压缩存储方法来节省存储空间。常见的压缩存储方法包括对称矩阵的压缩存储、三角矩阵的压缩存储和稀疏矩阵的压缩存储等。其中，稀疏矩阵的压缩存储通常采用三元组表示法或十字链表表示法。特殊矩阵的压缩存储方法特殊矩阵压缩存储方法05树与二叉树树是一种非线性数据结构，由节点和边组成，具有层次结构。树定义根节点、子节点、父节点、叶子节点、节点的度、树的度、深度、高度等。树的基本术语树中任意两个节点之间有且仅有一条路径；树中无环；除根节点外，每个节点有且仅有一个父节点。树的性质树基本概念和性质二叉树定义和性质二叉树定义二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的性质二叉树中每个节点的度最大为2；二叉树是有序的，即左子树和右子树是有区别的；满二叉树和完全二叉树是二叉树的两种特殊形态。二叉树遍历算法设计先访问根节点，然后遍历左子树，最后遍历右子树。先遍历左子树，然后访问根节点，最后遍历右子树。先遍历左子树，然后遍历右子树，最后访问根节点。按照树的层次自上而下、自左至右遍历每个节点。先序遍历中序遍历后序遍历层次遍历06图论基础图是由顶点集和边集构成的数据结构，表示对象及其之间的关系。图的基本概念连通性、有向性、无向性、稀疏性、稠密性等。图的性质邻接矩阵、邻接表、边集数组等。图的表示方法图论基本概念和性质

最小生成树算法设计最小生成树定义一个连通图的最小生成树是包含图中所有顶点的极小连通子图，且其所有边的权值之和最小。普里姆算法从某一顶点开始，每次选择一条与已选择顶点集合相连且权值最小的边，直到所有顶点都加入生成树中。克鲁斯卡尔算法每次选择一条权值最小的边，若这条边不会与已选择的边构成回路，则将其加入生成树中，直到生成树包含所有顶点。迪杰斯特拉算法适用于没有负权边的有向图，通过逐步确定起点到各顶点的最短路径，直到到达终点。最短路径问题定义给定一个带权有向图和无向图，找到从起点到终点的最短路径。弗洛伊德算法适用于带负权边的有向图和无向图，通过动态规划思想求解任意两点间的最短路径。最短路径算法设计07查找技术顺序查找法的适用情况适用于线性表等数据结构，当数据量不大时，查找效率较高。顺序查找法的实现方法通过循环遍历数据元素，逐个比较，直到找到目标元素或遍历结束。顺序查找法的基本思想从数据结构的一端开始，顺序扫描，直到找到所查元素为止。顺序查找法折半查找法的基本思想将已排序的数据结构分成大致相等的两部分，取中间元素与目标元素比较，若相等则查找成功；若目标元素小于中间元素，则在左半部分继续折半查找；若目标元素大于中间元素，则在右半部分继续折半查找。折半查找法的适用情况适用于已排序的线性表等数据结构，当数据量较大时，查找效率较高。折半查找法的实现方法通过递归或循环实现折半查找过程，每次比较中间元素与目标元素的大小关系，缩小查找范围。折半查找法通过哈希函数将数据元素的关键字映射为哈希表中的地址，然后根据地址直接访问哈希表中的元素。哈希表查找法的基本思想适用于关键字集合较大且关键字之间无明显规律的数据结构，当数据量较大时，查找效率较高。哈希表查找法的适用情况设计合适的哈希函数和处理冲突的方法，将关键字映射到哈希表中，然后通过哈希函数计算出的地址直接访问哈希表中的元素。哈希表查找法的实现方法哈希表查找法08排序技术将待排序的元素插入到已排序的序列中，从而达到排序的目的。从第一个元素开始，认为该元素已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。最好情况下为O(n)，最坏情况下为O(n^2)，平均情况下为O(n^2)。插入排序法的基本思想插入排序法的具体步骤插入排序法的时间复杂度插入排序法要点三选择排序法的基本思想在未排序的序列中找到最小（或最大）的元素，将其放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（或最大）的元素，放到已排序序列的末尾，如此反复，直到所有元素均排序完毕。要点一要点二选择排序法的具体步骤首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；重复第二步，直到所有元素均排序完毕。选择排序法的时间复杂度无论最好、最坏还是平均情况，时间复杂度均为O(n^2)。要点三选择排序法交换排序法的基本思想：通过不断地交换相邻的两个元素（如果它们的顺序错误）来把最小的元素交换到序列的最前端，然后再把次小的元素交换到序列的第二位置，以此类推，直到整个序列都排好序为止。交换排序法的具体步骤：从第一个