《审普通程序》课件

审普通程序审计程序是审计师为了获取审计证据，并形成审计意见而执行的一系列步骤审计程序分为两种实质性程序和控制测试程序课程介绍学习目标课程内容掌握基本程序设计概念、算涵盖数据结构、算法、程序法思想和编程技巧设计语言基础等内容课程特色理论与实践结合，注重培养学生解决问题的能力普通程序的特点顺序执行固定流程程序按照代码的顺序一步一步执行，指令之间严格按照顺执行流程是预先确定的，程序执行过程中的流程是固定的序执行，不会跳跃执行，不会根据条件进行改变普通程序的结构数据结构1数据组织方式算法2解决问题步骤控制结构3程序执行流程模块化4代码复用程序由数据结构、算法、控制结构和模块化组成数据结构组织数据，算法实现程序功能，控制结构决定程序执行流程，模块化则提高代码复用性算法概述问题求解数据组织代码实现算法是解决特定问题的一系列步骤或算法通常与数据结构密切相关，它们算法可以用编程语言实现，将抽象的指令它描述了解决问题所需的具体共同协作以有效地处理和操作数据步骤转换为计算机可执行的指令操作顺序算法的特性确定性有穷性

1.

2.12算法的每一步都必须是明算法必须在有限步骤内完确的，不会产生歧义同成，不能无限循环经过一个算法在相同条件下执有限次操作后，算法能够行，结果应始终一致终止可行性输入输出

3.

4./34算法的步骤必须是可执行算法必须有输入，并产生的，可以被计算机或人执相应的输出结果输入可行，即算法中的每个步骤以是零个或多个，输出也都能够被计算机或人用有可以是零个或多个限的时间和空间完成算法效率评判算法效率是指算法执行的时间和空间复杂度，可以衡量算法的优劣时间复杂度是指算法执行所需要的计算时间，空间复杂度是指算法执行所需要的内存空间时间复杂度时间复杂度衡量算法执行时间随输入规模增长变化趋势常用大记号表示，例如、、等O OnOn^2Olog n时间复杂度增长趋势示例算法常数时间数组访问O1线性时间线性查找On平方时间冒泡排序On^2对数时间二分查找Olog n空间复杂度空间复杂度衡量算法在运行时所使用的额外存储空间它描述了算法对内存的需求空间复杂度与输入数据的规模有关，算法需要的存储空间会随着输入规模的增长而改变例如，线性查找需要额外的空间来存储中间结果，而二分查找只需要常数大小的额外空间评估算法的空间复杂度对于优化内存使用、避免内存溢出和提高效率至关重要算法分析算法分析主要通过以下步骤进行确定问题1首先需要明确问题的目标和约束条件设计算法2根据问题性质，设计出具体的算法步骤算法验证3使用测试用例验证算法的正确性和效率优化改进4对算法进行优化，提高其执行效率和资源利用率线性结构线性结构的特点线性结构是一种简单的数据结构，元素之间存在唯一的线性关系，可以进行顺序访问线性结构的类型•数组•链表•栈•队列线性结构的应用线性结构广泛应用于各种程序中，例如，用于存储和管理数据，实现排序算法，以及构建其他复杂的数据结构栈后进先出数据存储常见操作栈是一种线性数据结构，遵循后进先栈使用一个指针，称为栈顶指针，指入栈•出的原则向当前栈顶元素出栈•获取栈顶元素•队列先进先出应用场景队列是一种线性数据结构，队列广泛应用于各种程序设遵循先进先出的原则数据计领域，例如任务调度、从队尾插入，从队头删除缓冲区管理、打印机管理等数据结构队列通常用数组或链表实现数组实现通常使用循环数组来提高效率链表节点链接单向链表双向链表循环链表每个节点包含数据和指向下节点只能指向下一个节点，每个节点同时包含指向下一最后一个节点指向第一个节一个节点的指针链表通过形成线性结构个节点和上一个节点的指针点，形成闭环结构，方便循节点之间的链接来组织数据，允许双向遍历环访问递归定义关键要素12递归是一种函数调用自身递归包含两个关键部分的编程技巧它通过将问基本情况和递归情况基题分解为更小的、类似的本情况定义了递归结束的问题来解决复杂问题条件，而递归情况则将问题分解为更小的子问题并递归调用自身应用优缺点34递归广泛应用于各种算法递归可以使代码更简洁，中，例如排序、查找和树但它可能导致性能问题，遍历等，它提供了一种简例如堆栈溢出，需要谨慎洁而优雅的解决问题的方使用案排序算法排序算法排序算法类型排序算法是一种重要的算法，用于将一组无序的数据排序算法的类型很多，常见的有插入排序、选择排序按照特定的顺序排列它们在各种应用程序中都有广、冒泡排序、归并排序、快速排序等等每种排序算泛的应用，包括数据库管理、搜索引擎和数据可视化法都有其优缺点和适用场景查找算法线性查找二分查找

1.

2.12从头到尾依次遍历列表，对有序列表，每次查找目查找目标元素标元素所在区间的一半哈希表查找树形查找

3.

4.34使用哈希函数将元素映射通过树结构组织数据，快到哈希表，通过索引快速速查找目标元素查找图论基础图的定义图的类型图的表示方法图论是用点和边来表示对象及其关系无向图和有向图，连通图和非连通图邻接矩阵，邻接表等的数学分支等最小生成树定义最小生成树MST是一个连通图的生成树，其中所有边上的权重之和最小应用最小生成树在网络设计、路线规划和电路板设计等领域有广泛的应用算法常用的最小生成树算法包括Prim算法和Kruskal算法步骤算法通过逐步添加边来构建MST，直到所有顶点都连接最短路径概念1最短路径问题是图论中的一个经典问题，它旨在找到图中两个节点之间最短的路径算法2常见的算法包括迪杰斯特拉算法和弗洛伊德算法，它们分别适用于单源最短路径和所有节点对之间的最短路径问题应用3最短路径问题在现实生活中有着广泛的应用，例如交通导航、网络路由、物流配送等等拓扑排序定义1拓扑排序是对有向无环图（）的顶点进行线性排序，使得对于图DAG中任意一条边，在排序中都位于之前u,v uv应用场景2拓扑排序在现实世界中有着广泛的应用，例如任务调度、项目管理、课程安排等算法实现3常用的拓扑排序算法有深度优先搜索（）和算法，两者都DFS Kahn能有效地找到一个合法的拓扑排序序列动态规划最优子结构重叠子问题动态规划步骤将问题分解成子问题，子问题的最优多个子问题重复出现，可以利用记忆定义状态•解可以用来构建原问题的最优解化技术避免重复计算找出状态转移方程•确定边界条件•自底向上计算•贪心算法贪心策略应用场景贪心算法在每一步都选择当前最佳的选择贪心算法适用于寻找最优解的问题它不考虑全局最优解，只关注局部最优解例如，最短路径问题、最小生成树问题、背包问题等分治算法将问题分解递归解决子问题分治算法将问题分解成多个递归地解决这些子问题，直子问题，这些子问题与原问到子问题规模足够小，可以题形式相同，但规模更小直接求解合并子问题解将子问题解合并成原问题的解回溯算法系统性搜索剪枝优化回溯算法是一种探索所有可能的解决方案的方法它通过通过判断当前路径是否可能导致最佳解决方案，回溯算法尝试所有可能的路径，逐步构建解决方案，并回溯到之前可以有效地避免不必要的搜索这种策略被称为剪枝，“”的状态，直到找到最佳解决方案可以显著提高算法效率字符串匹配蛮力匹配算法

1.

2.KMP12逐字符比较模式串和目标利用模式串自身的信息，串，效率较低，但易于理避免不必要的回溯，提高解效率算法算法

3.BM

4.Rabin-Karp34从模式串末尾开始匹配，利用哈希函数将字符串转效率更高，适用于较长模换为数字，快速比较，适式串用于海量数据散列表概念散列函数散列表是将键值对映射到一散列函数将键转换为一个数个数组的结构，每个键值对值，用于确定该键值对在数存储在数组的特定索引位置组中的位置碰撞处理应用当多个键映射到同一个索引散列表广泛应用于缓存、数时，需要使用碰撞处理机制据库索引、密码存储等领域，例如链式地址法或开放地，能够高效地进行查找、插址法入和删除操作树树的结构根节点子节点和父节点树是一种非线性数据结构，由节点和树只有一个根节点，作为树的起点，树中每个节点可以有多个子节点，而边组成，并具有层次结构没有父节点每个子节点只有一个父节点堆堆数据结构堆是一种特殊的二叉树，满足堆性质，即父节点的值大于等于（或小于等于）所有子节点的值优先级队列堆常被用于实现优先级队列，该数据结构支持高效地插入和删除元素，并始终维护元素的优先级顺序堆排序堆排序是一种基于堆数据结构的排序算法，其时间复杂度为On logn，并且原地排序，不需要额外的空间综合案例分析案例选择选择具有代表性的案例，涉及多个算法和数据结构分析步骤分解问题，识别核心算法和数据结构代码实现使用编程语言实现算法和数据结构结果验证测试代码，验证算法和数据结构的正确性总结反思分析案例，总结算法和数据结构的优缺点。