在这一章节中我通过学习后得出了以下关于数据结构的一些相关概念数据结构的概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的而是有着某种关系这种关系构成了某种结构。公式数据结构 数据 结构可以理解为带结构的数据元素的集合。课程视角数据结构讨论数据元素之间的相邻关系。著名公式Pascal 之父 尼古拉斯・沃斯程序 算法 数据结构数组的基本知识1数组概念数组是 (n(n1))个相同类型数据元素(a_1、a_2、…、a_n)构成的有限序列逻辑表示(A(a_1,a_2,…,a_n))。ps.其中ai1≤i≤n表示数组A的第i个元素Python 中没有原生数组使用列表 list模拟数组 / 线性表列表元素可以不同类型一维列表当作一维数组嵌套列表当作二维数组。2随机访问在数组中,一旦a1的存储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出LOC(ai)LOC(a1)(i-1)*k (0≤i≤n)上式说明,数组中任一数据元素的存储地址可直接计算得到,即数组中任一数据元素可直接存取,因此,数组是一种随机存储结构。数组可以直接计算地址存取元素属于随机存储结构。4顺序查找线性查找思路从表头依次遍历逐个比对关键字找到返回位置遍历结束没找到代表查找失败。python运行def sq_search(R, n, k):i 0while i n and R[i] ! k:i 1if i n:return 0else:return i 1二分查找法LeetCode 704. 二分查找前提条件有序顺序表递增只适用于已经排好序的数组。基本思路维护查找区间基本思路设R[low…high]是当前的查找区间首先确定该区间的中点位置mid(lowhigh)/2然后将待查的k值与R[mid].key比较若R[mid].keyk则查找成功并返回该元素的逻辑序号。若R[mid].keyk则由表的有序性可知新的查找区间是左子表R[low…mid-1]。若R[mid].keyk则新的查找区间是右子表R[mid1…high]。在新区间继续循环直到找到或者区间耗尽。左闭右闭区间([\text{left},\text{right}])标准代码对应 LeetCode704区间含义target 的候选下标包含 left 和 right 两个端点循环条件while left rightpython运行from typing import Listclass Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] target:right mid - 1elif nums[mid] target:left mid 1else:return midreturn -1左闭右开class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) # 定义target在左闭右开的区间里即[left, right)while left right: # 因为left right的时候在[left, right)是无效的空间所以使用 middle left (right - left) / 2if nums[middle] target:right middle # target 在左区间在[left, middle)中elif nums[middle] target:left middle 1 # target 在右区间在[middle 1, right)中else:return middle # 数组中找到目标值直接返回下标return -1 # 未找到目标值移除元素4. 移除元素LeetCode27PPT 数组删除逻辑对应本题给数组 nums移除所有值等于 val 的元素原地修改数组返回新数组有效长度。PPT 基础删除逻辑回顾删除数组某个下标 i 元素后面元素全部向前移动覆盖 i 位置。解法思路双指针快慢指针最优解法快指针遍历整个数组寻找不等于 val 的元素慢指针记录新数组需要写入的位置快指针遇到不等于 val 的元素赋值给慢指针位置慢指针向后走最后慢指针的值就是有效数组长度。python运行from typing import Listclass Solution:def removeElement(self, nums: List[int], val: int) - int:slow 0for fast in range(len(nums)):if nums[fast] ! val:nums[slow] nums[fast]slow 1return slow暴力解法遍历数组遇到等于 val 的元素把后面全部元素向前移动一位覆盖每删除一次数组长度减一。def removeElement(self, nums: List[int], val: int) - int:i, l 0, len(nums)while i l:if nums[i] val: # 找到等于目标值的节点for j in range(i1, l): # 移除该元素并将后面元素向前平移nums[j - 1] nums[j]l - 1i - 1i 1return l