《数组4学时》课件

《数组4学时》PPT课件•数组的基本概念•数组的创建与初始化•数组的遍历与搜索•数组的排序与查找目录•数组的应用案例contents01CATALOGUE数组的基本概念数组的定义总结词描述数组的基本定义详细描述数组是一种用于存储有序数据集合的数据结构，它由相同类型的元素组成，每个元素在数组中都有一个唯一的索引数组的分类总结词描述数组的分类方式详细描述根据数组中元素的类型，可以将数组分为整数数组、浮点数数组、字符数组等；根据数组的维度，可以将数组分为一维数组、二维数组、三维数组等数组的常用操作总结词列举数组的常用操作详细描述数组的操作包括索引、添加、删除、修改和遍历等通过这些操作，可以对数组中的元素进行访问、修改和管理02CATALOGUE数组的创建与初始化静态初始化总结词详细描述总结词详细描述通过直接赋值方式进行数组的静态初始化是指在声明数组时静态初始化适用于固定大小的由于静态初始化在声明时就需初始化直接为其元素赋值，无需使用数组，且在声明时已经知道所要指定所有元素的值，因此无循环或方法调用例如，`int[]有元素的值法在运行时改变数组的大小array={1,2,3,4,5};`这种初始化方式适用于已知元素值的场景，如常量数组或预定义的数据集动态初始化030102总结词04总结词详细描述详细描述动态初始化允许在运行时改变数通过循环或方法调用动态地填组的大小充数组元素动态初始化是指在程序运行过由于动态初始化是在运行时逐个程中，通过循环或方法调用逐赋值给数组元素，因此可以在程个赋值给数组元素例如，使序运行过程中动态地改变数组的用循环结构如`for`或`while`来大小这种初始化方式适用于需遍历数组并为其赋值要根据某些条件或输入来填充数组的场景初始化器列表总结词详细描述总结词详细描述使用花括号括起来的值初始化器列表是一种特初始化器列表适用于固与静态初始化一样，初列表进行数组的初始化殊的静态初始化方式，定大小的数组，且在声始化器列表也需要在声使用花括号`{}`括起来明时已经知道所有元素明时指定所有元素的值，的值列表来初始化数组的值因此无法在运行时改变这种初始化方式与静态数组的大小这种初始初始化类似，但语法上化方式适用于已知元素略有不同例如，`int[]值的场景，如常量数组array={1,2,3};`或预定义的数据集03CATALOGUE数组的遍历与搜索遍历数组顺序遍历按照数组元素顺序，从头到尾依次访问每个元素跳跃搜索法逆序遍历通过跳过一定数量的元素来减少比较次数，按照数组元素顺序，从尾到头依次访问每提高搜索效率个元素线性搜索法二分查找法从数组的第一个元素开始，逐个比较每个在已排序的数组中，通过比较中间元素与元素与目标值，直到找到目标值或遍历完目标值，逐步缩小查找范围，直到找到目整个数组标值或确定不存在于数组中二分查找法适用场景已排序的数组查找过程将数组分成左右两部分，比较中间元素与目标值，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找重复此过程，直到找到目标值或确定不存在于数组中二分查找法时间复杂度Olog n注意事项二分查找法要求数组已排序，否则结果不准确线性搜索法01020304适用场景任何情况下的数组查找过程从头到尾依次比较注意事项线性搜索法适用于每个元素与目标值，直到找到时间复杂度On任何情况下的数组，但当数组目标值或遍历完整个数组较大时，效率较低跳跃搜索法适用场景已排序的数组查找过程通过跳过一定数量的元素来减少比较次数，从而提高搜索效率具体实现时，可以每次跳过固定数量的元素，也可以根据元素的分布情况动态调整跳跃步长时间复杂度On注意事项跳跃搜索法在某些情况下可以提高搜索效率，但并不总是优于线性搜索法和二分查找法同时，跳跃搜索法的实现较为复杂，容易出错04CATALOGUE数组的排序与查找冒泡排序法时间复杂度On^2，其中n是数组的长度适用场景适用于较小的数组或部分有序的数组选择排序法时间复杂度On^2，其中n是数组的长度适用场景适用于数据量较小的情况插入排序法时间复杂度On^2，其中n是数组的长度适用场景适用于数据量较小的情况二分查找法时间复杂度Olog n，其中n是数组的长度适用场景适用于有序数组的查找操作05CATALOGUE数组的应用案例数组在排序算法中的应用冒泡排序通过相邻元素之间的比较和交换，将较大的元素逐步“冒泡”到数组的末尾，从而实现排序选择排序在未排序的序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾以此类推，直到所有元素均排序完毕插入排序将数组分为已排序和未排序两部分，初始时已排序部分包含一个元素从未排序部分取出元素，并在已排序部分找到合适的位置插入，并保持已排序部分一直有序重复此过程，直到未排序部分元素为空数组在动态规划中的应用背包问题01给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，求最大价值可以使用数组来存储物品的价值和重量，以及当前的总重量和总价值最长公共子序列02给定两个字符串，求它们的最长公共子序列可以使用动态规划算法，用一个二维数组来存储子问题的解，最终得到最长公共子序列的长度矩阵链乘法03给定一组矩阵和它们的乘法顺序，求最小乘法次数可以使用动态规划算法，用一个二维数组来存储子问题的解，最终得到最小乘法次数数组在数据结构中的应用数组作为线性表的实现数组作为哈希表的实现线性表是一种具有固定数量元素的数据哈希表是一种通过哈希函数将键映射到桶结构，可以使用数组来实现数组的每中的数据结构，可以使用数组来实现每个元素可以存储线性表中的一个元素，VS个桶可以看作是数组的一个元素，通过哈通过下标访问元素希函数计算出桶的索引来访问元素THANKS感谢观看。