Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

数组和字符串-01

数组是数据结构中的基本模块之一。因为字符串是由字符数组形成的,所以二者是相似的。大多数面试问题都属于这个范畴。需要掌握的内容如下:

  1. 理解数组的基本概念及其操作方式
  2. 理解二维数组的基本概念,熟悉二维数组的使用;
  3. 了解字符串的概念以及字符串所具有的不同特性;
  4. 理解字符串匹配中的KMP算法;
  5. 能够运用双指针解决实际问题。

数组简介

  • 数组和列表、集合之间有什么不同?
  • 如何理解数组的读取、查找、插入、删除等操作?
  • 数组在内存中是如何存放的?
  • 在编程语言中,如何对数组执行初始化、数据访问、修改、迭代、排序、添加、删除等操作?

集合、列表和数组

文中介绍的概念是适用于所有编程语言的抽象理论,具体实现会因为编程语言的不同而有差别。

集合

集合一般被定义为:由一个或多个确定的元素所构成的整体。
通俗来讲,集合就是将一组事物组合在一起。如题库中的题,商店中的商品,甚至桌面上的物品。

集合有什么特性呢?
首先,集合里的元素类型不一定相同。你可以将商品看作一个集合,也可以将整个商店看作一个集合,这个商店中有人或者其他物品也没有关系。
其次,集合里的元素没有顺序。我们不会这样讲:我想要集合中的第三个元素,因为集合是没有顺序的。

事实上,这样的集合并不直接存在于编程语言中。然而,实际编程语言中的很多数据结构,就是在集合的基础上添加了一些规则形成的。

列表

列表(又称线性列表):是一种数据项构成的有限序列,即按照一定的线性顺序,排列而成的数据项的集合。
列表的概念在集合的特征上形成,它具有顺序,且长度可变。例如一张购物清单:

  • 一本算法书
  • 一个笔记本
  • 两包咖啡

在这张购物清单中:

  • 购物清单中的条目代表的类型可能不同,但是按照一定顺序进行了排列;
  • 购物清单的长度是可变的,你可以向购物清单中增加、删除条目。

在编程语言中,列表最常见的表现形式有数组和链表,而我们熟悉的栈和队列则是两种特殊类型的列表。除此之外,向列表中添加、删除元素的具体实现方式会根据编程语言的不同而有所区分。

数组

数组是列表的实现方式之一,也是面试中经常涉及到的数据结构。
正如前面提到的,数组是列表的实现方式,它具有列表的特征,同时也具有自己的一些特征。然而,在具体的编程语言中,数组这个数据结构的实现方式具有一定差别。比如 C++和 Java 中,数组中的元素类型必须保持一致,而 Python 中则可以不同。Python 中的数组叫做 list,具有更多的高级功能。
那么如何从宏观上区分列表和数组呢?这里有一个重要的概念:索引
首先,数组会用一些名为索引的数字来标识每项数据在数组中的位置,且在大多数编程语言中,索引是从 0 算起的。我们可以根据数组中的索引,快速访问数组中的元素。

而列表没有索引,这是数组与列表最大的不同。
其次,数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存。
相反,列表中的元素在内存中可能彼此相邻,也可能不相邻。比如列表的另一种实现方式——链表,它的元素在内存中则不一定是连续的。

数组的操作

数组主要操作有如下四种:

读取元素

读取元素很好理解,通过数组的索引来访问数组中存储的元素。索引就是内存地址,计算机可以跳跃到任何内存地址,也就是说,只要提供了索引,就可以访问对应的元素。

计算机会在内存中申请一段连续的空间用来存放数组,并且会记下索引 0 所在的内存。例如我们要获取索引 3 的值,首先获取 0 所在的内存地址,假设每个元素只占用一个字节,将地址加 3 就可以获取到相应的值,因为这个过程很快,所以可以任务时间复杂度为O(1)

查找元素

由于计算机只会保存数组中索引为 0 处元素的内存地址,因此当计算机想要知道数组中是否包含某个元素时,只能从索引 0 处开始,逐步向后查询。

还是上面的例子,如果我们要查找数组中是否包含元素 pears,计算机会从索引 0 开始,逐个比较对应的元素,直到找到该元素后停止搜索,或到达数组的末尾后停止。

我们发现,如果数组的长度为 N,最坏情况下(比如我们查找最后一个元素或查找数组中不包含的元素),我们需要查询数组中的每个元素,因此时间复杂度为O(N),N 为数组的长度。

插入元素

如果我们想在原有的数组中再插入一个元素呢?
要将该元素插入到数组的末尾,只需要一步,得到数组的长度和位置计算出即将插入元素的内存地址,然后将该元素插入到指定位置即可。
但是将该元素插入到数组中的其他位置,会有区别。首先需要为该元素所要插入的位置腾出空间,然后进行插入操作。需要将插入位置之后的所有数据向后移动,如果需要频繁地对数组元素进行插入操作,会造成时间的浪费。

事实上,另一种数据结构,即链表可以有效解决这个问题,之后会进行学习。

删除元素

删除元素与插入元素的操作类似,当我们删除掉数组中的某个元素后,数组中会留下空缺的位置,而数组中的元素在内存中是连续的,这就使得后面的元素需对该位置进行填补操作。

声明:本文为学习记录,参考之处较多,如果有侵权内容,请联系我立即删除

End~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~