数组是一种线性数据结构,把相同数据类型的元素存储在连续的内存空间中,数组的索引(元素在数组中的位置)从0开始。
一、常用操作:
1、初始化
# 给定初始值
arr:list[int] = [0] * 5
nums:list[int] = [1, 2, 3, 4, 5]
2、查询/访问元素
数组的首元素对应的索引为0,这与现实生活中的序号有些不太一样,但可以从地址计算的角度分析看,索引本质是内存地址的偏移量。
元素对应的内存地址=数组首元素地址+地址偏移量
地址偏移量=(每个元素对应的大小/长度)* 元素索引
def random_visit(nums:list[int]) -> int:"""随机访问nums中的任意一个元素"""random_index = random.randint(0,len(nums) - 1)return nums[random_index]
3、插入元素
定义:有效数字表示为有用的存储数据;无效数据表示初始化的数据(比如:全部初始化为0)。
由于数组中的数据为连续存储,所以当在第i个位置(i不是当前数组的最后一位有效数字的索引)插入新的数据时,并没有地方存储,因此需要将当前数组中第i个数据之后的数据依次向后移动(索引i+1)一个单元,但又由于数组长度不可变,有可能会导致数组后面被初始化为0的元素产生丢失,此问题可通过后续的列表解决。
def insert(nums:list[int], num:int, index:int):"""在数组的索引index处插入元素num"""# 1、从后向前遍历nums到索引index处# 2、把num插入到索引index处for i in range(len(nums) - 1,index,-1):nums[i] = nums[i-1]nums[index] = num# before insert:nums = [1, 2, 3, 4, 5]
# after insert 0 in index 0:num = [0, 1, 2, 3, 4]
4、删除元素
同样的,删除顺序存储的任意索引i处的元素时,把索引i+1的元素依次向前移动。由于数组大小固定不变,因此删除中间某个元素值后,会依次向前移动,但最后一个元素并未删掉。
def remove(nums:list[int],index:int):"""在数组的索引index处删除索引index的元素"""for i in range(index,len(nums) - 1):nums[i] = nums[i+1]# before delete:nums = [1, 2, 3, 4, 5]
# after delete index 0:nums = [2, 3, 4, 5, 5]
5、遍历及访问数组元素
def traverse(nums:list[int]) -> int:"""遍历数组"""number = 0# 1、通过下标访问for i in range(len(nums)):number += nums[i]# 2、直接遍历数组元素for i in nums:number += i# 3、同时遍历索引及数组元素:for i,num in enumerate(nums):number += nums[i]number += numreturn numberprint(number) # number = 60
6、数组扩容
数组的长度是不可变的,对其扩容实际就是新建一个数组(容量扩大),然后将原数组的值拷贝到新数组中即可。
def expand(nums:list[int],enlarge:int) -> list[int]:"""数组扩容"""# 1、初始化一个扩展长度的数组arrarr = [0] * (len(nums) + enlarge)# 2、将原数组中所有元素复制到新数组for i in range(len(nums)):arr[i] = nums[i]return arrbefore expand:nums = [1, 2, 3, 4, 5]
after expand capicity:nums = [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]