数据结构与算法之线性表01

数组是一种线性数据结构，把相同数据类型的元素存储在连续的内存空间中，数组的索引（元素在数组中的位置）从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]