加猛挣钱免费做网站软件,家政公司在哪个平台推广效果好,百度百家号注册,搜索引擎分哪三类文章目录 前言数组数组的定义数组的基本操作增加元素删除元素修改元素查找元素 C STL 中的数组arrayvector Python3 中的列表访问更改元素值遍历列表检查列表中是否存在某元素增加元素删除元素拷贝列表总结 Python3 列表的常用操作 参考资料写在最后 前言
本系列专注更新基本数… 文章目录 前言数组数组的定义数组的基本操作增加元素删除元素修改元素查找元素 C STL 中的数组arrayvector Python3 中的列表访问更改元素值遍历列表检查列表中是否存在某元素增加元素删除元素拷贝列表总结 Python3 列表的常用操作 参考资料写在最后 前言
本系列专注更新基本数据结构现以更新
【算法与数据结构】数组.
【算法与数据结构】哈希表. 数组
数组的定义
数组是一种在内存中有着一块连续的内存空间的并且由相同类型的元素组成的线性数据结构。以整数数组为例数组的存储方式如下图所示 在上图中可以看出数组在计算机中就是内存中一块连续的存储单元。数据元素的内存地址表示的就是该元素存放在内容中的地址因为整型数据占据四个字节大小的内存所以相邻两个元素地址之间相差 4。
在上图所示的数组中数据元素的个数为 7并且数组中都是整型元素。数组中每一个元素都可以通过「下标索引」来获取。下标索引从 0 开始在计算机中数数都是从 0 开始到数据元素的个数减一。
之所以称数组是一种线性数据结构是因为数组中所有数据元素排成像一条线一样的结构每个数据元素最多只有前、后两个方向。链表、栈、队列这几种数据结构也有这样的线性特征。 数组的基本操作
几乎所有的数据结构都会涉及到增、删、改、查四个基本操作数组也不例外。
增加元素
增加元素之前需要先检查数组是否已经满了达到最大容量如果满了就需要重新在内存中找到一块连续的地方放置原来数组中的元素以及新加入的元素。如果使用的是 C 中的 vector 容器就不用担心容量不够的问题因为在数组容量不够时 vector 会自动扩容。通常在数组尾部增加元素的时间复杂度为 O ( 1 ) O(1) O(1)。
如果在数组 nums 中位置 i 处插入一个新的元素 val通常有以下步骤
先检查 i 是否有效即在数组的下标范围内确认有效后检查数组 i 处是否已经存在元素了 没有元素当然好直接更新 nums[i] val但是通常会有元素这时候就需要将 i 及之后位置的元素向后挪动一个位置然后将 val 放在空出来的位置 i 处。 这种插入情况最坏的时间复杂度为 O ( n ) O(n) O(n) n n n 是整个数组的长度。
这里就不考虑插入元素时数组满了的问题了因为在 C 程序中通常都使用 vector 作为数组这样一旦满了就会自动扩容。
删除元素
删除元素也分几种情况
删除数组尾部元素直接将数字计数值减一即可这通常是 C 语言中的做法。前面已经说了 C 中几乎都用 vector 这个可动态扩容的数组于是删除尾部元素直接 pop_back()。在 Python3 中直接 pop()。删除数组 nums 中位置 i 的元素通常有两个方法当然在使用两个方法之前都要先检查 i 是否有效 借助临时数组将原数组 nums 中除了 i 位置表示的元素之外的所有元素复制到临时数组中然后清空数组 nums最后再将临时数组中元素复制到 nums 中。这种方法需要遍历两次数组渐进时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( n ) O(n) O(n)。原地操作利用 i 位置后一位置的元素去覆盖 i 位置即 i1 位置的元素去覆盖 i 位置的元素i2 位置的元素去覆盖 i1 位置的元素以此类推直到 i n最后再把最有一个元素删掉。时间复杂度为 O ( n ) O(n) O(n)空间复杂度为 O ( 1 ) O(1) O(1)。通常有关原地删除数组中元素的操作指的就是 覆盖。 最后一种情况就是「基于特定条件进行删除」那就需要遍历数组根据条件筛选出需要删除的元素或位置一个个删除就好了。
通常删除操作的时间复杂度为 O ( n ) O(n) O(n)。
修改元素
这种操作就简单了。通过遍历数组找到需要修改的元素直接修改即可。这种操作的时间复杂度为 O ( n ) O(n) O(n)。
查找元素
这种操作也很简答。如果是查找指定下标的元素直接进行索引查找即可时间复杂度为 O ( 1 ) O(1) O(1)。如果需要查找指定元素那也不难一次遍历即可时间复杂度为 O ( n ) O(n) O(n)。 C STL 中的数组
在 C 标准库中定义两种类型的数组array 和 vector。
array
array 是一种定长数组也就是 C/C 中描述并使用的那种数组使用之前要定义数组中的数据类型和固定的数组长度。
初始化
#include iostream
#include array // array 的头文件using namespace std;int main() {// 初始化列表 初始化 arrayint, 7 myArr {1, 4, 6, 8, 9, 1, 3};// 拷贝初始化arrayint, 7 myArr2 myArr;for (const auto num : myArr2) {cout num ;}return 0;
}array 有两种初始化方法初始化列表初始化和拷贝初始化。
重要的成员函数
成员函数释义begin首迭代器end尾后迭代器size数组大小empty数组是否为空operator[]索引元素at索引元素font数组的第一个元素back数组的最后一个元素fill填充数组swap两个数组交换
vector
vector 是一种容器是一种可变长的数据。当向 vector 容器中增加数据时如果容器已经满了那么它会重新在内存中找一块更大的连续内存来存放原来的数据。通常是按照原来内存的两倍大小进行扩容的。得益于自动扩容的特性C 中多使用 vector 来构造数组。
初始化构造函数
#include iostream
#include vectorint main () {// constructors used in the same order as described above:std::vectorint first; // empty vector of intsstd::vectorint second (4,100); // four ints with value 100std::vectorint third (second.begin(),second.end()); // iterating through secondstd::vectorint fourth (third); // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] {16,2,77,29};std::vectorint fifth (myints, myints sizeof(myints) / sizeof(int) );std::cout The contents of fifth are:;for (std::vectorint::iterator it fifth.begin(); it ! fifth.end(); it)std::cout *it;std::cout \n;return 0;
}重要的成员函数
成员函数释义begin首迭代器end尾后迭代器size数组大小capacity当前数组的存储容量empty数组是否为空reserve更改容量operator[]索引元素at索引元素font数组的第一个元素back数组的最后一个元素push_back在数组末尾增加元素pop_back删除最后一个元素clear清空容器swap两个数组交换 Python3 中的列表
python 中没有固定长度的数组只有类似于 vector 容器的列表。
列表是一个有序且可更改的集合。集合中可以混合放置任意类型的元素比如文本类型、数值类型和布尔类型不要求必须放置同一类型的元素。
list1 [8, srt, 98, True]此例中列表 list1 包含了数值类型文本类型和布尔类型的数据元素。
访问
可以通过索引来访问列表。
list1 [8, str, 98, True]print(list1[0]) # 输出 str在 Python3 中索引可以是负值负值索引表示从列表的末尾开始访问-1 表示列表的最后一个元素-2 表示列表的倒数第二个元素等等。
list1 [8, str, 98, True]print(list1[-1]) # 输出列表的最后一个元素 True范围索引
可以对列表指定起点、终点取不到和步长进行范围索引。
list2 [1, 4, 5, 6]print(list2[0 : 3 : 2]) # 输出 [1, 5]此例子对列表 list2 进行范围索引从索引 0 开始到索引 3 结束每次在上一个索引的基础上 2 进行访问。
负范围索引
范围索引还可以是负值。
list2 [1, 4, 5, 6]print(list2[-4 : -1 : 2]) # 仍然输出 [1, 5]此例子对列表 list2 进行负的范围索引从倒数第 4 个元素开始索引到倒数第一个元素结束取不到每次在上一个索引的基础上 2 进行访问。
更改元素值
通过使用索引轻松更改元素值。
list2 [1, 4, 5, 6]
list2[0] 0 # 将列表第一个元素更改为 0print(list2) # 输出 [0, 4, 5, 6]遍历列表
可以像 C/C 一样使用索引进行遍历Python3 有自己的一种 for 遍历方法C 中的 for 范围遍历对应的就是 Python3 中的范围遍历。
list3 [apple, pear, pineapple]for x in list3:print(x)# 输出apple
pear
pineapple检查列表中是否存在某元素
如果需确定列表中是否存在指定的元素使用 in 关键字
list3 [apple, pear, pineapple]if apple in list3:print(Yes, apple is in the fruits list3.)在此例中如果文本 “apple” 在列表 list3 中则 if 条件语句为 True执行对应的语句输出 Yes, apple is in the fruits list3..
增加元素
如需将元素添加到列表的末尾使用 append() 方法
list3 [apple, pear, pineapple]
list3.append(banana)print(list3) # 输出 [apple, pear, pineapple, banana]要在指定的索引处添加元素使用 insert() 方法
list4 [apple, pear, pineapple]
list4.insert(1, cherry)print(list4) # 输出 [apple, cherry, pear, pineapple]此例中在列表 lsit4 的索引 1 处插入 “cherry”。
删除元素
通过 remove() 删除指定元素
list5 [apple, cherry, pear, pineapple]
list5.remove(apple)print(list5) # 输出 [cherry, pear, pineapple]通过 pop() 删除指定索引的元素如果没有指定索引则删除最后一项
list6 [cherry, pear, pineapple]
list6.pop()print(list6) # 输出 [cherry, pear]使用 del 关键字删除指定的索引del 关键字也能完整地删除列表
list7 [cherry, pear, pineapple]
del list7[0]
print(list7) # 输出 [pear, pineapple]del list7 # 直接删除 list7 使用 clear() 方法清空列表这一点和 vector 中的 clear() 一样
list8 [apple, banana, cherry]
list8.clear()print(list8) # 输出 []拷贝列表
拷贝列表分为浅拷贝和深拷贝。见 Python之赋值、深拷贝与浅拷贝
总结 Python3 列表的常用操作
关键字释义list()生成列表append()在列表尾追加元素insert()在指定位置插入元素pop()移除列表尾元素remove()移除列表中指定元素clear()清空列表del清空指定元素或列表合并两个列表extend()在一个列表后追加另一个列表len()列表的长度sort()排序默认升序reverse()反转列表copy()浅拷贝copy.deepcopy()深拷贝 参考资料
【文章】01. 数组基础知识
【文章】Python 列表 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家觉得有些地方需要补充欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
