数据结构之数组

发表于 | 更新于: | 分类于 |
字数统计: 2,259 | 阅读时长 ≈ 10

什么是数组

数组（array），是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。
组成数组的各个变量称为数组的分量，也称为数组的元素（element），有时也称为下标变量。
用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按无序的形式组织起来的一种形式。
数组，是由相同类型的元素的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。
数组是最早期和最重要的数据结构之一，很多程序都会用到数组。
它们也用于实现许多其他数据结构，譬如列表（list）和字符串（string）。

点击这里查看博客对应的完整代码

一维数组

一维数组是计算机程序中最基本最简单的数据结构类型，由数字组成的以单纯的排序结构排列的结构单一的数组。

一维数组常规操作

静态一维数组
1
2
3
4
5
6
7
8
9
10
11
12
cout << "静态创建一维数组" << endl;
int a[3] = {1,2,3};
cout << "查询" << endl;
cout << a[0] << endl;
cout << a[1] << endl;
cout << a[2] << endl;
cout << "修改" << endl;
a[0] = 4;
cout << "查询" << endl;
cout << a[0] << endl;
cout << a[1] << endl;
cout << a[2] << endl;
动态一维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cout << "动态创建一维数组" << endl;
int length = 3;
int *a1 = (int *)malloc(length * sizeof(int));
cout << "初始化" << endl;
a1[0] = 1;
a1[1] = 2;
a1[2] = 3;
cout << "查询" << endl;
cout << "下标=" << 0 << "值=" << a1[0] << endl;
cout << "下标=" << 1 << "值=" << a1[1] << endl;
cout << "下标=" << 2 << "值=" << a1[2] << endl;
cout << "修改" << endl;
*(a1+1) = 4;
cout << "查询" << endl;
cout << "下标=" << 0 << "值=" << a1[0] << endl;
cout << "下标=" << 1 << "值=" << a1[1] << endl;
cout << "下标=" << 2 << "值=" << a1[2] << endl;

二维数组

二维数组本质上是以数组作为数组元素的数组，即“数组的数组”。

二维数组的常规操作

静态二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cout << "静态创建二维数组" << endl;
int b[2][2] =
{
    {11,22},
    {33,44}
};
cout << "查询" << endl;
cout << b[0][0] << endl;
cout << b[0][1] << endl;
cout << b[1][0] << endl;
cout << b[1][1] << endl;
cout << "修改" << endl;
b[0][1] = 55;
cout << "查询" << endl;
cout << b[0][0] << endl;
cout << b[0][1] << endl;
cout << b[1][0] << endl;
cout << b[1][1] << endl;
动态二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cout << "动态创建二维数组" << endl;
//一维长度/行长度
int x = 2;
//二维长度/列长度
int y = 2;
//数组总长度
int length1 = x * y;
int *b1 = (int *)malloc(length1 * sizeof(int));
cout << "初始化" << endl;
b1[0 * y + 0] = 11;
b1[0 * y + 1] = 22;;
b1[1 * y + 0] = 33;;
b1[1 * y + 1] = 44;;
cout << "查询" << endl;
cout << "下标=" << "值=" << b1[0 * y + 0] << endl;
cout << "下标=" << "值=" << b1[0 * y + 1] << endl;
cout << "下标=" << "值=" << b1[1 * y + 0] << endl;
cout << "下标=" << "值=" << b1[1 * y + 1] << endl;
cout << "修改" << endl;
b1[0*2+0] = 55;
cout << "查询" << endl;
cout << "下标=" << "值=" << b1[0 * y + 0] << endl;
cout << "下标=" << "值=" << b1[0 * y + 1] << endl;
cout << "下标=" << "值=" << b1[1 * y + 0] << endl;
cout << "下标=" << "值=" << b1[1 * y + 1] << endl;

多维数组

三维及其以上的数组称为多维数组，三维数组具有高、宽、深的概念，或者说行、列、层的概念，由于其可以用来描述三维空间中的位置或状态而被广泛使用。

多维数组的常规操作

静态多维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
cout << "静态创建多维数组" << endl;
int c[2][2][2] =
{
    {
        {111,222},
        {333,444}
    },
    {
        {555,666},
        {777,888}
    }
};
cout << "查询" << endl;
cout << c[0][0][0] << endl;
cout << c[0][0][1] << endl;
cout << c[0][1][0] << endl;
cout << c[0][1][1] << endl;
cout << c[1][0][0] << endl;
cout << c[1][0][1] << endl;
cout << c[1][1][0] << endl;
cout << c[1][1][1] << endl;
cout << "修改" << endl;
c[1][0][0] = 666;
cout << "查询" << endl;
cout << c[0][0][0] << endl;
cout << c[0][0][1] << endl;
cout << c[0][1][0] << endl;
cout << c[0][1][1] << endl;
cout << c[1][0][0] << endl;
cout << c[1][0][1] << endl;
cout << c[1][1][0] << endl;
cout << c[1][1][1] << endl;
动态多维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
cout << "动态创建多维数组" << endl;
//一维长度/高度
int h = 2;
//二维长度/宽度
int w = 2;
//三维长度/深度
int d = 2;
//数组总长度
int length2 = h * w * d;
int *c1 = (int *)malloc(length2 * sizeof(int));
cout << "初始化" << endl;
c1[0 * h * w + 0 * d + 0] = 111;
c1[0 * h * w + 0 * d + 1] = 222;
c1[0 * h * w + 1 * d + 0] = 333;
c1[0 * h * w + 1 * d + 1] = 444;
c1[1 * h * w + 0 * d + 0] = 555;
c1[1 * h * w + 0 * d + 1] = 666;
c1[1 * h * w + 1 * d + 0] = 777;
c1[1 * h * w + 1 * d + 1] = 888;
cout << "查询" << endl;
cout << "下标=" << (0 * h * w + 0 * d + 0) << "值=" << c1[0 * h * w + 0 * d + 0] << endl;
cout << "下标=" << (0 * h * w + 0 * d + 1) << "值=" << c1[0 * h * w + 0 * d + 1] << endl;
cout << "下标=" << (0 * h * w + 1 * d + 0) << "值=" << c1[0 * h * w + 1 * d + 0] << endl;
cout << "下标=" << (0 * h * w + 1 * d + 1) << "值=" << c1[0 * h * w + 1 * d + 1] << endl;
cout << "下标=" << (1 * h * w + 0 * d + 0) << "值=" << c1[1 * h * w + 0 * d + 0] << endl;
cout << "下标=" << (1 * h * w + 0 * d + 1) << "值=" << c1[1 * h * w + 0 * d + 1] << endl;
cout << "下标=" << (1 * h * w + 1 * d + 0) << "值=" << c1[1 * h * w + 1 * d + 0] << endl;
cout << "下标=" << (1 * h * w + 1 * d + 1) << "值=" << c1[1 * h * w + 1 * d + 1] << endl;
cout << "修改" << endl;
c1[0 * w * d + 0 * d + 0] = 666;
cout << "查询" << endl;
cout << "下标=" << (0 * h * w + 0 * d + 0) << "值=" << c1[0 * h * w + 0 * d + 0] << endl;
cout << "下标=" << (0 * h * w + 0 * d + 1) << "值=" << c1[0 * h * w + 0 * d + 1] << endl;
cout << "下标=" << (0 * h * w + 1 * d + 0) << "值=" << c1[0 * h * w + 1 * d + 0] << endl;
cout << "下标=" << (0 * h * w + 1 * d + 1) << "值=" << c1[0 * h * w + 1 * d + 1] << endl;
cout << "下标=" << (1 * h * w + 0 * d + 0) << "值=" << c1[1 * h * w + 0 * d + 0] << endl;
cout << "下标=" << (1 * h * w + 0 * d + 1) << "值=" << c1[1 * h * w + 0 * d + 1] << endl;
cout << "下标=" << (1 * h * w + 1 * d + 0) << "值=" << c1[1 * h * w + 1 * d + 0] << endl;
cout << "下标=" << (1 * h * w + 1 * d + 1) << "值=" << c1[1 * h * w + 1 * d + 1] << endl;

元素标识符和定址公式

首先我们先明确几个概念

  • 数组名 = 数组首元素地址 = 元素基址
  • 元素地址 = 元素基址 + 元素下标
  • 元素基址 + 元素下标 的值 会被解析成 定址公式
  • 元素标识符和定址公式体现出了数组的内存连续性

下面所有代码全部使用”下标优先”规则，并且内存连续，实际实现 二维 多维数组和本例子可能有所不同，比如可能维度之间内存不连续等，以下例子只为表达概念。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//验证一维数组 定址公式 = (a1+0) + i * sizeof(DataType)
cout << "验证一维数组 定址公式" << endl;
cout << "打印元素基址" << a1 << endl;
cout << "打印元素基址" << a1+0 << endl;
//根据上面我们说的公式 假设 元素基址 = 0x7ffc39400340
//那么 0x7ffc39400340 + 1 * 4 = 0x7ffc39400344;
cout << "打印第二个元素的地址" << a1+1 << endl;

//验证二维数组 定址公式 = (b1+0) + (x * 2 + y) * sizeof(DataType)
//注意公式里的 x y 和上面打印的不一样，上面的 x y 分别代表每个维度的长度，公式里面是每个维度的下标
cout << "验证二维数组 定址公式" << endl;
cout << "打印元素基址" << b1 << endl;
cout << "打印元素基址" << (b1 + 0 * y + 0) << endl;
//根据上面我们说的公式 假设 元素基址 = 0x7ffc39400340
//那么 0x7ffc39400340 + (x * 2 + y) = 0x7ffc39400344;
cout << "打印第二个元素的地址" << (b1 + 0 * y + 1) << endl;

//验证三维数组 定址公式 = (c1+0) + (h * 2 * 2 + w * 2 + d) * sizeof(DataType)
//注意公式里的 h w y 和上面打印的不一样，上面的 h w y 分别代表每个维度的长度，公式里面是每个维度的下标
cout << "验证三维数组 定址公式" << endl;
cout << "打印元素基址" << c1 << endl;
cout << "打印元素基址" << c1+0 << endl;
//根据上面我们说的公式 假设 元素基址 = 0x7ffc39400340
//那么 0x7ffc39400340 + 0 * 2 * 2 + 0 * 2 + 1 = 0x7ffc39400344;
cout << "打印第二个元素的地址" << c1 + 0 * 2 * 2 + 0 * 2 + 1 << endl;

总结

数组就是数量固定且类型相同的元素集合。
数组的的内存空间是连续的，有规律的，所以可以直接使用下表访问相应的元素。
数组的查询是非常快的，因为它可以直接根据下标计算出内存地址，不用像 链表 一样，每次查询都需要遍历。
数组的插入和删除是比较慢的，因为每次插入或删除一个元素的时候，都需要重新维护序号指针，除非操作的是最后一个元素。

Choice wechat
关注公众号，获取文章更新通知。
-------------本文结束感谢您的阅读-------------
坚持原创技术分享，您的支持将鼓励我继续创作！