【数据结构&算法】05-线性表之数组【数据结构&算法】05-线性表之

前言
线性结构与非线性结构
数组
- 数组的两个限制
- 数组的随机访问特性
数组的操作
- 插入操作
删除操作
数组越界
容器
数组下标

前言 【【数据结构&算法】05-线性表之数组】本笔记主要记录数组的一些基础特性及操作。
顺便解答下为什么大部分编程语言的的数组是从 0 开始的。
李柱明博客：https://www.cnblogs.com/lizhuming/p/15487306.html
线性结构与非线性结构线性结构：

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。
包括：数组、链表、队列和栈等。

非线性结构：

在非线性表，数据之间不是简单的前后关系，通过下图对比线性结构和非线性结构
包括：树、图等。

参考图：

文章图片

文章图片

数组数组的两个限制
数组有两个限制：

数组为线性结构。
是连续的内存空间和相同类型的数据。

数组的随机访问特性
基于以上两个限制，使得数组具有随机访问的特性。
小笔记：

计算机通过地址来访问内存中的数据。
寻址通过以下公式寻址：

a[i]_address = base_address + i * data_type_size;

而随机访问是只要知道数组对应的下标，我们就可以直接通过寻址公式知道该数据，不需要查找什么的。使得时间复杂度为 O(1)。
小笔记：

数组和链表的区别：
- 数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
- 链表适合增删，时间复杂度为 O(1)。

数组的操作数组的操作主要是增删。
插入操作
插入数据，若不是尾部且不能留空，则需要搬移部分数据。
分析：

若插入尾部，则不需要搬移数据，插入操作的时间复杂度为 O(1)。
若插入第 k 个位置中。其插入操作的时间复杂度为 O(n)。
- 特定情况下，可以把原有第 k 个位置中的数据挪到最后。这样其插入操作的时间复杂度为 O(1)。

删除操作删除数据，若不是尾部且不能留空，则需要搬移部分数据。
分析：

若删除尾部，则不需要搬移数据，删除操作的时间复杂度为 O(1)。
若删除第 k 个位置中。其删除操作的时间复杂度为 O(n)。
- 特定情况下，若删除的位前面几个，则可以直接修改数组的起始位置即可。

数组越界小笔记：一个由 C/C++ 编译的程序占用的内存分为以下几个部分：

堆区（stack）：
- 生长开口方向向上。（底为低地址、小端）
- 一般由程序员分配释放，若程序员不释放，程序结束时可能
  由 OS 回收。
栈区（heap）：
- 生长开口方向向下。（底为低地址、小端）
- 由编译器自动分配释放，存放函数的参数值，局部变量的值
  等。其操作方式类似于数据结构中的栈。
全局区（静态区）（static）：
- 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。
- 程序结束后有系统释放
文字常量区：
- 常量字符串就是放在这里的。
- 程序结束后由系统释放。
程序代码区：
- 存放函数体的二进制代码。

参考代码：

int main(int argc, char* argv[]) { int i = 0; int arr[3] = {0}; for(; i<=3; i++) { arr[i] = 0; printf("hello world\n"); } return 0; }

分析：

该代码无限打印 hello world\n 。就是因为内存溢出。
整型变量 i 和整型数组 arr[3] 存储在栈空间中。
arr[3] 的存储位置就是 i 的存储位置。
for 循环的合法循环 i 最大为 3，刚好在 i=3 的那次循环把 i 重置为 0 了。

这种数组越界的错误容易导致逻辑混乱。程序跑飞。
容器针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中的 vector。
容器把很多数组操作的细节封装起来，如插入、删除等，且支持扩容。
数组下标为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？