C语言常用算法程序汇总.pptx

C语言常用算法程序汇总汇报人：XX2024-01-19排序算法查找算法图形算法数据结构相关算法数学相关算法文件操作相关算法CATALOGUE目录01排序算法冒泡排序算法原理：通过相邻元素之间的比较和交换，使得每一轮比较后最大（或最小）的元素能够“冒泡”到序列的一端。时间复杂度：最好情况下为O(n)，最坏和平均情况下为O(n^2)。空间复杂度：O(1)。稳定性：稳定。选择排序0102算法原理：每次从未排序的元素中选出最小（或最大）的元素，放到已排序序列的末尾。时间复杂度：无论最好、最坏还是平均情况，时间复杂度均为O(n^2)。空间复杂度：O(1)。稳定性：不稳定。0304插入排序01算法原理：将未排序元素插入到已排序序列的合适位置中，以达到排序的目的。02时间复杂度：最好情况下为O(n)，最坏和平均情况下为O(n^2)。03空间复杂度：O(1)。04稳定性：稳定。快速排序算法原理通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度最好情况下为O(nlogn)，最坏情况下为O(n^2)，平均情况下为O(nlogn)。快速排序空间复杂度：O(logn)。稳定性：不稳定。归并排序算法原理：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。时间复杂度：无论最好、最坏还是平均情况，时间复杂度均为O(nlogn)。输入标题020103稳定性：稳定。空间复杂度：O(n)。0402查找算法顺序查找顺序查找算法从数据结构的一端开始，顺序扫描，直到找到所查元素为止。时间复杂度平均时间复杂度和最坏时间复杂度都是O(n)，其中n是数据结构中元素的个数。适用场景适用于数据量较小或数据无序的情况。二分查找二分查找算法01在有序数组中，取中间元素与目标元素比较，若相等则查找成功；若目标元素小于中间元素，则在左半部分继续查找；若目标元素大于中间元素，则在右半部分继续查找。时间复杂度02平均时间复杂度和最坏时间复杂度都是O(logn)，其中n是数据结构中元素的个数。适用场景03适用于数据量较大且数据有序的情况。哈希查找010203哈希查找算法时间复杂度适用场景通过哈希函数将数据映射到哈希表中，然后在哈希表中查找目标元素。平均时间复杂度可以达到O(1)，最坏情况下时间复杂度为O(n)，其中n是哈希表中的元素个数。适用于需要快速查找且数据量大的情况，但需要注意哈希冲突的处理。树形查找树形查找算法1利用树形数据结构（如二叉搜索树、平衡树等）进行查找。时间复杂度2平均时间复杂度和最坏时间复杂度与具体的树形结构有关，但通常可以达到O(logn)的级别，其中n是树中节点的个数。适用场景3适用于数据量较大且需要高效查找的情况，但需要注意树的平衡性和维护成本。03图形算法DFS深度优先搜索DFS深度优先搜索2.弹出栈顶元素，访问该节点。031.创建一个空栈，将起始节点压入栈中。02实现步骤01DFS深度优先搜索3.将该节点的所有未访问过的子节点压入栈中。014.重复步骤2和3，直到栈为空。02应用场景：求解连通图、拓扑排序、寻找图中的环等。03BFS广度优先搜索算法思想：从某个顶点出发，逐层遍历图，先访问离起始节点最近的节点，然后逐层向外扩展。BFS广度优先搜索实现步骤1.创建一个空队列，将起始节点入队。2.弹出队首元素，访问该节点。BFS广度优先搜索013.将该节点的所有未访问过的子节点入队。024.重复步骤2和3，直到队列为空。03应用场景：求解最短路径、连通分量、网络爬虫等。最短路径算法Dijkstra算法适用于没有负权边的有向图或无向图，通过维护一个已确定最短路径的顶点集合和一个距离数组，不断更新距离数组中的值，直到所有顶点的最短路径都被确定。Floyd算法适用于任意有向图或无向图，通过动态规划的思想，不断更新任意两点之间的最短路径，直到所有顶点之间的最短路径都被确定。Bellman-Ford算法适用于有负权边的有向图，通过对所有边进行松弛操作，不断更新起点到各顶点的最短路径长度，直到没有边可以再被松弛为止。最小生成树算法Prim算法从任意一个顶点开始，每次选择一条连接已选顶点和未选顶点中权值最小的边，将这条边连接的未选顶点加入已选顶点集合中，直到所有顶点都被选中为止。Kruskal算法将所有边按照权值从小到大排序，然后从权值最小的边开始选择，每次选择一条连接两个未连通分量的边，将这条边加入最小生成树中，直到所有顶点都在同一个连通分量中为止。04数据结构相关算法链表操作算法链表的创建与销毁通过动态内存分配创建链表，并在使用完毕后释放链表占用的内存空间。链