《数据结构数组》课件

数据结构与算法数组-数组是计算机科学中最基本、最常用的数据结构之一数组是一种线性数据结构，它按顺序存储一组相同类型的数据by数组的概念定义类型12数组是一种线性数据结构，它是一系列元素的集合，这些元数组可以是相同类型数据的集合，例如整型数组、字符数组素按顺序存储在连续的内存位置中、浮点型数组索引用途34数组中的每个元素都与一个唯一的索引相关联，可以通过索数组广泛用于程序设计中，例如存储数据、排序数据、查找引访问元素数据等数组的特点顺序存储固定大小数组的元素在内存中连续存储，方便随机访问元素数组在创建时需要指定大小，大小固定，无法动态改变类型一致效率高数组的元素类型必须一致，有利于编译器优化数组在访问、插入、删除元素时效率较高，适合随机访问和大量数据存储一维数组的定义连续内存地址索引访问数据类型一致一维数组是一组具有相同数据类型且连续分数组中的每个元素都由一个唯一的索引标识数组中的所有元素必须具有相同的数据类型配内存地址的元素集合，索引从0开始，例如整数、浮点数、字符串等一维数组的存储连续存储1数组元素在内存中按照顺序连续存储，每个元素占用固定大小的空间地址计算2每个元素的地址可以通过基地址和偏移量计算，方便随机访问任何元素索引映射3数组索引与元素在内存中的位置一一对应，方便管理和操作一维数组的操作访问元素1通过索引访问数组元素插入元素2在指定位置添加新元素删除元素3从数组中移除指定元素查找元素4在数组中搜索特定元素一维数组的操作包括访问、插入、删除和查找元素这些操作是数组的基本功能，支持各种数据处理任务一维数组的访问元素索引访问代码示例通过索引直接访问数组元素，效率很高使用索引访问数组元素，代码简洁易懂一维数组的插入元素插入操作时间复杂度在数组中插入元素需要将指定位置后的元素向后移动一位，并将插入操作的时间复杂度为On，其中n为数组的长度因为需要移新元素插入到指定位置动n-i个元素，i为插入位置删除元素移除元素位置移除空间重组删除数组中的特定元素，会改变数组长度通过索引位置删除元素，移动后续元素释放被删除元素占用的内存空间，保持数组完整性一维数组的查找元素线性查找二分查找从数组第一个元素开始依次比较适用于有序数组，通过不断缩小，找到目标元素则返回其下标，查找范围，找到目标元素则返回否则返回其下标，否则返回-1-1哈希查找通过哈希函数将元素映射到哈希表中，实现快速查找，但可能存在哈希冲突二维数组的定义定义二维数组，也称为矩阵，是由多个相同数据类型元素组成的二维结构，每个元素都有唯一的行和列索引例如，一个的二维数组表示一个有行列的表格，每个元3x434素对应表格中一个特定的单元格二维数组的存储行优先存储将二维数组按行顺序存储，每个元素依次存储在内存中列优先存储将二维数组按列顺序存储，每个元素依次存储在内存中选择合适的存储方式，取决于具体应用场景和编程语言的实现二维数组的操作访问元素1通过索引访问二维数组中的特定元素，例如a[i][j]插入元素2在二维数组中添加新的元素，需要调整已有元素的位置，例如在指定位置插入元素删除元素3移除二维数组中特定的元素，需要更新元素索引，例如删除指定位置的元素查找元素4在二维数组中搜索特定元素，可以使用遍历或其他算法，例如查找特定元素的索引二维数组的操作包括访问、插入、删除和查找元素这些操作需要考虑二维数组的结构和元素索引，并根据具体的操作类型进行相应的处理二维数组的访问元素下标访问指针访问循环访问123二维数组元素通过行索引和列索引访使用指针访问二维数组元素时，需要使用循环可以遍历整个二维数组，例问，例如，数组arr

[2]

[3]中，元素先获得指向数组首地址的指针，然后如，使用两层循环访问每个元素，并arr

[1]

[2]表示第二行第三列的元素通过指针偏移量来访问特定元素进行相应的操作插入元素数组插入插入位置之前的元素需要向后移动，腾出空插入元素后，数组的长度会增加间在数组中插入元素需要移动已有元素删除元素确定位置移动元素调整长度

11.

22.

33.首先需要确定要删除的元素在数组中将待删除元素后面的元素向前移动一最后，将数组的长度减一，表示删除的位置索引位，覆盖掉被删除的元素了一个元素二维数组的查找线性查找二分查找从数组的第一个元素开始，逐个比较元素的值与目标值前提是数组必须有序找到目标值时，返回其索引；否则返回-1每次将目标值与中间元素比较，根据结果缩小搜索范围，直到找到目标值或搜索范围为空多维数组的定义多个数组组合存储方式索引访问多维数组是由多个一维数组组合而成的结构多维数组可以用于存储多维数据，例如矩阵每个元素使用多个索引访问，例如三维数组或表格使用三个索引访问多维数组的存储内存地址连续1多维数组在内存中是以连续的地址空间存储的，类似一维数组的线性存储方式，只不过是将数组的每个元素进行排成一个矩阵，然后依次存储在内存中列优先存储2存储时，将每一列的元素依次存储在内存中，类似于矩阵的列优先存储方式，例如，对于一个二维数组，先存储第一列的所有元素，然后再存储第二列的所有元素，依此类推行优先存储3另一种常见的存储方式是行优先存储，即先存储第一行的所有元素，然后再存储第二行的所有元素，以此类推多维数组的操作访问元素1使用索引访问特定元素插入元素2在数组中添加新元素删除元素3移除数组中的特定元素查找元素4在数组中定位指定元素多维数组的操作与一维数组类似，但需要使用多个索引来访问元素多维数组的访问元素索引嵌套指针多维数组使用多个索引来访问元素，每个索多维数组可以通过嵌套的方式访问元素，例可以使用指针来访问多维数组元素，指针指引对应一个维度如使用循环遍历每个维度向内存中的特定位置插入元素动态内存分配元素移动如果数组容量不足，需要在堆内插入位置之后的元素需要向后移存中申请新的空间，将原数组元动，腾出空位来放置新元素素复制到新空间，然后释放旧空间数组大小调整插入元素后，数组的大小需要更新，以反映新元素的数量删除元素删除操作内存移动数组删除元素是指从数组中移除指定位置的元素删除元素后，需要将后面的元素向前移动，以填补空缺多维数组的查找元素线性查找二分查找逐个比较数组元素与目标值适用于有序数组，效率更高时间复杂度为，效率较低时间复杂度为On Olog n数组的应用场景数据库管理图像处理游戏开发编程语言数组用于存储数据表中的行和数组存储图像像素值，可进行数组用来表示游戏场景、角色数组是编程语言中重要的数据列，便于数据检索和操作图像旋转、缩放、滤波等操作位置、动画帧等数据结构，广泛应用于各种算法和程序数组的优缺点优点缺点随机访问固定大小••内存连续插入删除慢••实现简单内存浪费••时间复杂度分析时间复杂度是衡量算法效率的重要指标它描述了算法执行时间随输入规模增长的变化趋势O1On常数时间线性时间执行时间与输入规模无关执行时间与输入规模线性增长OlognOn^2对数时间平方时间执行时间随输入规模的对数增长执行时间随输入规模的平方增长例如，访问数组元素的时间复杂度为O1遍历数组的时间复杂度为On总结与思考数组是一种简单而强大的数据结构，广泛应用于各种编程语言和算法深入理解数组的特点、操作和时间复杂度，可以帮助我们更高效地利用数组，解决实际问题。