《审普通程序》课件

审普通程序审计程序是审计师为了获取审计证据，并形成审计意见而执行的一系列步骤。审计程序分为两种：实质性程序和控制测试程序。课程介绍学习目标掌握基本程序设计概念、算法思想和编程技巧。课程内容涵盖数据结构、算法、程序设计语言基础等内容。课程特色理论与实践结合，注重培养学生解决问题的能力。普通程序的特点顺序执行程序按照代码的顺序一步一步执行，指令之间严格按照顺序执行，不会跳跃执行。固定流程执行流程是预先确定的，程序执行过程中的流程是固定的，不会根据条件进行改变。普通程序的结构1数据结构数据组织方式2算法解决问题步骤3控制结构程序执行流程4模块化代码复用程序由数据结构、算法、控制结构和模块化组成。数据结构组织数据，算法实现程序功能，控制结构决定程序执行流程，模块化则提高代码复用性。算法概述问题求解算法是解决特定问题的一系列步骤或指令。它描述了解决问题所需的具体操作顺序。数据组织算法通常与数据结构密切相关，它们共同协作以有效地处理和操作数据。代码实现算法可以用编程语言实现，将抽象的步骤转换为计算机可执行的指令。算法的特性11.确定性算法的每一步都必须是明确的，不会产生歧义。同一个算法在相同条件下执行，结果应始终一致。22.有穷性算法必须在有限步骤内完成，不能无限循环。经过有限次操作后，算法能够终止。33.可行性算法的步骤必须是可执行的，可以被计算机或人执行，即算法中的每个步骤都能够被计算机或人用有限的时间和空间完成。44.输入/输出算法必须有输入，并产生相应的输出结果。输入可以是零个或多个，输出也可以是零个或多个。算法效率评判算法效率是指算法执行的时间和空间复杂度，可以衡量算法的优劣。时间复杂度是指算法执行所需要的计算时间，空间复杂度是指算法执行所需要的内存空间。时间复杂度时间复杂度衡量算法执行时间随输入规模增长变化趋势。常用大O记号表示，例如O(n)、O(n^2)、O(logn)等。时间复杂度增长趋势示例算法O(1)常数时间数组访问O(n)线性时间线性查找O(n^2)平方时间冒泡排序O(logn)对数时间二分查找空间复杂度空间复杂度衡量算法在运行时所使用的额外存储空间。它描述了算法对内存的需求。空间复杂度与输入数据的规模有关，算法需要的存储空间会随着输入规模的增长而改变。例如，线性查找需要额外的空间来存储中间结果，而二分查找只需要常数大小的额外空间。评估算法的空间复杂度对于优化内存使用、避免内存溢出和提高效率至关重要。算法分析算法分析主要通过以下步骤进行：1确定问题首先需要明确问题的目标和约束条件。2设计算法根据问题性质，设计出具体的算法步骤。3算法验证使用测试用例验证算法的正确性和效率。4优化改进对算法进行优化，提高其执行效率和资源利用率。线性结构线性结构的特点线性结构是一种简单的数据结构，元素之间存在唯一的线性关系，可以进行顺序访问。线性结构的类型数组链表栈队列线性结构的应用线性结构广泛应用于各种程序中，例如，用于存储和管理数据，实现排序算法，以及构建其他复杂的数据结构。栈后进先出栈是一种线性数据结构，遵循后进先出的原则。数据存储栈使用一个指针，称为栈顶指针，指向当前栈顶元素。常见操作入栈出栈获取栈顶元素队列先进先出队列是一种线性数据结构，遵循先进先出的原则。数据从队尾插入，从队头删除。应用场景队列广泛应用于各种程序设计领域，例如：任务调度、缓冲区管理、打印机管理等。数据结构队列通常用数组或链表实现。数组实现通常使用循环数组来提高效率。链表节点链接每个节点包含数据和指向下一个节点的指针。链表通过节点之间的链接来组织数据。单向链表节点只能指向下一个节点，形成线性结构。双向链表每个节点同时包含指向下一个节点和上一个节点的指针，允许双向遍历。循环链表最后一个节点指向第一个节点，形成闭环结构，方便循环访问。递归1定义递归是一种函数调用自身的编程技巧。它通过将问题分解为更小的、类似的问题来解决复杂问题。2关键要素递归包含两个关键部分：基本情况和递归情况。基本情况定义了递归结束的条件，而递归情况则将问题分解为更小的子问题并递归调用自身。3应用递归广泛应用于各种算法中，例如排序、查找和树遍历等，它提供了一种简洁而优雅的解决问题的方案。4优缺点递归可以使代码更简洁，但它可能导致性能问题，例如堆栈溢出，需要谨慎使用。排序算法排序算法排序算法是一种重要的算法，用于将一组无序的数据按照特定的顺序排列。它们在各种应用程序中都有广泛的应用，包括数据库管理、搜索引擎和数据可视化。排序算法类型排序算法的类型很多，常见的有插入排序、选择排序、冒泡排序、归并排序、快速排序等等。每种排序算法都有其优缺点和适用场景。查找算法11.线性查找从头到尾依次遍历列表，查找目标元素。22.二分查找对有序列表，每次查找目标元素所在区间的一半。33.哈希表查找使用哈希函数将元素映射到哈希表，通过索引快速查找。44.树形查找通过树结构组织数据，快速查找目标元素。图论基础图的定义图论是用点和边来表示对象及其关系的数学分支。图的类型无向图和有向图，连通图和非连通图等。图的表示方法邻接矩阵，邻接表等。最小生成树定义最小生成树(MST)是一个连通图的生成树，其中所有边上的权重之和最小。应用最小生成树在网络设计、路线规划和电路板设计等领域有广泛的应用。算法常用的最小生成树算法包括Prim算法和Kruskal算法。步骤算法通过逐步添加边来构建MST，直到所有顶点都连接。最短路径1概念最短路径问题是图论中的一个经典问题，它旨在找到图中两个节点之间最短的路径。2算法常见的算法包括迪杰斯特拉算法和弗洛伊德算法，它们分别适用于单源最短路径和所有节点对之间的最短路径问题。3应用最短路径问题在现实生活中有着广泛的应用，例如交通导航、网络路由、物流配送等等。拓扑排序1定义拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得对于图中任意一条边(u,v)，u在排序中都位于v之前。2应用场景拓扑排序在现实世界中有着广泛的应用，例如：任务调度、项目管理、课程安排等。3算法实现常用的拓扑排序算法有：深度优先搜索（DFS）和Kahn算法，两者都能有效地找到一个合法的拓扑排序序列。动态规划最优子结构将问题分解成子问题，子问题的最优解可以用来构建原问题的最优解。重叠子问题多个子问题重复出现，可以利用记忆化技术避免重复计算。动态规划步骤定义状态找出状态转移方程确定边界条件自底向上计算贪心算法贪心策略贪心算法在每一步都选择当前最佳的选择。它不考虑全局最优解，只关注局部最优解。应用场景贪心算法适用于寻找最优解的问题。例如，最短路径问题、最小生成树问题、背包问题等。分治算法将问题分解分治算法将问题分解成多个子问题，这些子问题与原问题形式相同，但规模更小。递归解决子问题递归地解决这些子问题，直到子问题规模足够小，可以直接求解。合并子问题解将子问题解合并成原问题的解。回溯算法系统性搜索回溯算法是一种探索所有可能的解决方案的方法。它通过尝试所有可能的路径，逐步构建解决方案，并回溯到之前的状态，直到找到最佳解决方案。剪枝优化通过判断当前路径是否可能导致最佳解决方案，回溯算法可以有效地避免不必要的搜索。这种策略被称为“剪枝”，可以显著提高算法效率。字符串匹配11.蛮力匹配逐字符比较模式串和目标串，效率较低，但易于理解。22.KMP算法利用模式串自身的信息，避免不必要的回溯，提高效率。33.BM算法从模式串末尾开始匹配，效率更高，适用于较长模式串。44.Rabin-Karp算法利用哈希函数将字符串转换为数字，快速比较，适用于海量数据。散列表概念散列表是将键值对映射到一个数组的结构，每个键值对存储在数组的特定索引位置。散列函数散列函数将键转换为一个数值，用于确定该键值对在数组中的位置。碰撞处理当多个键映射到同一个索引时，需要使用碰撞处理机制，例如链式地址法或开放地址法。应用散列表广泛应用于缓存、数据库索引、密码存储等领域，能够高效地进行查找、插入和删除操作。树树的结构树是一种非线性数据结构，由节点和边组成，并具有层次结构。根节点树只有一个根节点，作为树的起点，没有父节点。子节点和父节点树中每个节点可以有多个子节点，而每个子节点只有一个父节点。堆堆数据结构堆是一种特殊的二叉树，满足堆性质，即父节点的值大于等于（或小于等于）所有子节点的值。优先级队列堆常被用于实现优先级队列，该数据结构支持高效地插入和删除元素，并始终维护元素