数据结构基本介绍＋数组基本概念＋leetcode704题解

一、数据结构基本介绍数据结构是计算机科学中最核心、最基础的概念之一。它不单是把数据堆放在一起而是研究数据之间存在的逻辑关系、数据在计算机内存中的物理存储形式以及如何对这些数据进行高效操作增、删、改、查等等。1.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素不是孤立存在元素之间的相互关系就是结构。公式数据结构 数据 结构数据一个个独立的数据元素可以理解成数据“素材”结构数据元素之间的邻接/逻辑关系元素怎么组织、怎么相连简单理解数据结构 带结构关系的数据元素的集合。公式图灵奖获得者 尼古拉斯·沃斯(Niklaus Wirth) 提出经典公式程序 数据结构 算法数据结构解决数据怎么存、怎么组织类比做菜的食材调料​ 算法解决怎么处理数据类比做菜的烹饪方式数组完整基础知识二、数组概念1.数组是 n(n1)个相同类型数据元素 a_1,a_2…a_n 构成的有限序列逻辑描述上图例子内存地址1000对应下标0存数值0地址1004对应下标1存数值5。数组在内存中是一段连续的存储空间元素紧紧挨在一起。2.随机访问数组最大特性随机访问随机存取已知首地址可以直接算出任意元素地址不需要遍历前面元素。LOC(a_i)LOC(a_1)(i‑1)*k LOC(ai)LOC(a1)(i-1)*k (0≤i≤n)LOC(a_1)数组第一个元素起始内存地址​k单个元素占用存储字节大小int占4字节​i元素逻辑位置举例首地址1000int占4字节求第3个元素LOC1000(3‑1)*4 10083.Python中的数组列表listPython没有传统静态数组列表list等价数组1.一维列表一维数组2.二维列表二维数组Python列表特殊点列表里面元素允许不同数据类型C语言数组必须全部相同类型。LOC(ai)LOC(a1)(i-1)*k (0≤i≤n)4.数组删除操作1.删除尾部元素操作逻辑不需要移动任何元素只修改有效长度size减一 size‑1原内存数据还在逻辑上不再访问该位置效率很高 O(1)。2.删除数组中间指定下标i位置元素三步1.下标合法性检查 0 ≤ i ≤ len(nums)-1 下标越界直接报错不能删除。​2. 元素移动把下标 i1 直到末尾所有元素整体向左移动一位覆盖被删除位置。3.有效长度计数器 size‑1 。三、二分查找法 对应LeetCode 704