1、数组

数组的定义

数组（array）是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。
从上面的定义中有几个关键词
首先它是一个线性表
线性表
线性表就是数据排列成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。除了数组，链表，队列，栈等也是线性表结构
非线性表
二叉树，堆，图等。之所以是非线性，是因为数据之间并不是简单的前后关系。

其次它是连续的内存空间和相同的数据类型
有了这两个限制，才能让数组可以随机访问。当然有利就有弊，这两个限制也让数组的很多操作变得低效，比如删除和插入操作，为了保证连续性需要做大量的数据搬移工作。

数组是如何根据下标实现随机访问的？

a[k]_address = base_address + k * type_size

为什么大多数编程语言中，数组要从0开始编号，而不是1开始呢？
如果从1开始，计算位置就变成了：

a[k]_address = base_address + (k-1)*type_size

对计算机而言就多了一次减法指令。

数组的特点

-随机访问，查找速度快
-删改数据复杂，要移位

一维数组

定义：相同类型的数据元素的集合，类似于向量。
分类：分为静态数组与动态数组。
静态数组长度必须为确定的常数

int a[10];//正确

动态数组通过new来动态开辟空间

int n;
cin>>n; 
int *a=new int[n];//这样整数数组的长度不需要在程序中确定，可以在程序运行的时候由用户输入

由于调用了new，程序最后一定delete掉

for(int i=0;i<size;i++)
   {
           delete []  p[i];   // 要在指针前加[] ， 否则的话 只释放p[i]所指的第一个单元所占的空间
   }

二维数组

一般所说的二维数组是定义在栈上的二维数组，例如array[3][4]，而实际上此二维数组在内存中是像一维数组一样存储连续的，如图：

定义：

//直接定义
int array[3][4] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int array[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
//定义数组指针
int array[][4];
int (*array)[4];
//动态分配行列
/*  malloc方式  */
int **array // array[M][N]
array = (int **)malloc(M * sizeof(int *));
for(int i = 0; i < M; i++) {
    array[i] = (int *)malloc(N * sizeof(int));
}
// 释放
for(int i = 0; i < M; i++)
    free(array[i]);
free(array);
/*  new方式  */
int **array // array[M][N]
array = new int*[M];
for(int i = 0; i < M; i++) {
    array[i] = new int[N];
}
// 释放
for(int i = 0; i < M; i++) 
    delete [] array[i];
delete [] array;