XINWUYA

【C++笔记】01 数组

 
  • 2020年 04月29日
  • 0 阅读

1 一维数组的声明与初始化

1.1 一维数组的声明

一维数组的声明包括三点：1）元素类型；2）数组名；3）数组中元素数量（必须≥1）。

其中元素类型可以是内置数据类型、类类型或者除引用以外的其他任意复合类型。

注：元素类型不能是引用的原因是：引用是不能赋值的，而数组中的元素必须可以被赋值。

1.2 一维数组的初始化

声明数组时，可以提供一组用逗号隔开的初值，使用花括号{}括起来，称为初始化列表。

数组元素初始化时，若没有显式提供元素初值，则元素会被像普通变量一样被初始化：

  1. 函数体外定义的内置类型数组（即内置类型的全局数组），元素初始化为0；
  2. 函数体内定义的内置类型数组，元素无初始化（注意：若只初始化部分元素，其后的元素此时也会被初始化为0）；
  3. 如果不是内置类型，则不管其在哪定义，自动调用默认构造函数初始化，若该类无默认构造函数，则报错。

注：在声明数组时，除了宏替换可以用来定义数组的长度，在C++中可以用const常量来定义也是可以的，但该方式不适用于C。

2 C风格字符串与字符数组

2.1 C风格字符串

C风格字符串包括两种：

  • 字符串常量：用双引号括起来的字符序列。如：char *cp = "C++";

    注：为了兼容C语言，C++中所有字符串常量都由编译器自动在末尾添加了一个空字符(null)。

  • 末尾添加了'\0'的字符数组。如：char ch[] = {'C', '+', '+', '\0'};

2.2 字符数组

字符数组的初始化方式有两种：

  • 使用一组用花括号括起来、逗号隔开的字符常量。如：char ch[] = {'C', '+', '+', '\0'};

  • 使用一个字符串常量。如：char ch[] = "C++";

    注：当使用字符串常量进行初始化时，将在新数组末尾加入空字符。

注意：使用标准库函数（strcpy/strcat）处理字符数组时，字符数组必须以null结束。如char ca[] = {'C', '+', '+'}; cout << strlen(ca) << endl; 该计算结果将不可预料。

3 二维数组

3.1 二维数组的声明与初始化

二维数组的初始化分为两种：

  • 按行初始化

    int a[3][4]={
    {0,1,2,3},
    {4,5,6,7},
    {8,9,10,11}
};

  • 顺序初始化

    int a[3][4]={0,1,2,3,4,5,6,7,8,9,10,11};

下面这种声明只初始化了每行的第一个元素，其余元素则会被初始化为0：

int a[3][4]={\{0\},\{4\},\{8\}};

注：在声明和初始化一个二维数组时，如果对二维数组的所有元素都赋值，则第一维（行数）可以省略，但第二维不能省略。同样，在声明更高维的数组时，也只有第一维可以省略。

3.2 二维数组的动态声明

动态声明方法：

int **a = new int*[m];
for(int i = 0; i < m; ++i)
    a[i] = new int*[n];

注：静态声明的数组可以使用一维的方式访问：b[i][j] = b[i*n+j]，这是因为数组是连续的一片内存。但动态声明的数组则不能使用a[i*n+j]这种方式，原因在于每个a[i]都是一个int*类型，即一个地址，因此只能使用a[i][j]或*(*(a+i)+j)来访问。

3.3 二维数组的访问

对于二维数组a[m][n]：

  • a表示指向数组首元素a[0]的指针，为常量，不可进行赋值；

  • a[0]为5个int组成的数组，表示指向数组a[0]首元素a[0][0]的指针；

  • &a表示数组的首地址， &a+1跳过m行n列；

  • 该数组各种指针类型对应：

    指针 类型 备注
    a int(*)[n] a+i的类型也同为int(*)n
    *a或a[0] int* *a为指向数组a[0]首元素a[0][0]的指针
    *(a+1)或a[1] int* *(a+1)或a[1]为指向数组a[1]首元素a[1][0]的指针
    * (* (a+1)+2) int 指向数组a[1][2]的指针
    &a int(*)[m][n]  
    a+i int(*)[n]  
    *(a+i) int*  
    *(*(a+i)+j) int *(a+i)=a[i]; *(*(a+i)+j)=*(a[i]+j)=a[i][j]

4 逗号运算符

多个表达式可以用逗号分开，其中用逗号分开的表达式的值分别结算，但整个表达式的值是最后一个表达式的值。

注：赋值运算符比逗号运算符优先级高。如：int a = (7, 8, 9); 此时a=9；而int a = 7, 8, 9;此时a=7。

5 指针运算与数组指针、指针数组

5.1 指针运算

当一个指针和一个整数进行算术运算时，整数在执行加法运算前始终会根据合适的大小进行调整。这里”合适的大小“指指针所指向类型的大小，”调整“指将整数值与该”合适的大小“相乘。

只有当两个指针都指向同一个数组中的元素时，才允许一个指针减另一指针。减法运算的结果为两个指针在内存中的距离。注意：该距离为之间存在的元素个数。

5.2 指针数组与数组指针

  • 指针数组：为一个数组，其中每个元素都是一个指针。

    int *a[10];

  • 数组指针：指向一个数组的指针，只是一个指针，指向整个数组。

    int (*p)[10];

5.3 指针运算在数组中的应用

char a[] = "hello";
a[0] = 'x';//正确

char *p = "hello";
p[0] = 'x';//错误

char *q = a;
q[0] = 'x';//正确

a为一个数组，内存分配在栈上，可以通过数组名或指向数组的指针进行修改，而p指向的是位于文字常量区的字符串，是不允许被修改的，但使用p[0]访问相应的元素是正确的，只是不能修改。

注：数组的首地址是常量，不可进行赋值操作。

5.4 数组作为元素传递

当数组作为函数实参传递时，传递的是数组首元素的地址。而将数组某一个元素的地址当作实参时，传递的是此元素的地址。

6 数组的应用

6.1 线性表的顺序存储（顺序表）

线性表的顺序存储又称为顺序表。

注：需分清线性表与顺序表的概念。线性表是一种逻辑结构，表示元素之间一对一的相邻关系，而顺序表和链表是存储结构。两者概念不同。

需要注意的是：线性表中的元素的位序是从1开始的，而数组中元素的下标是从0开始的。

顺序表最主要的特点是可以进行随机存取，即通过首地址和元素序号可以在O(1)的时内进行元素查找。但插入和删除操作则需要移动大量元素。

在表长为n的顺序表L中共有n+1个可插入结点的位置。插入操作结点移动的次数不仅与表长n有关，也和插入的位置i有关：1）最好情况：在表尾插入和删除，时间复杂度为O(1)；2）最坏情况：在表头插入和删除，整个数组都将进行平移，时间复杂度为O(n)；3）平均情况：插入和删除的平均移动次数分别为n/2和(n-1)/2，因此顺序表插入和删除的平均时间复杂度为O(n)。

顺序表的按值查找：1）最好情况：在表头查到，仅需比较1次，时间复杂度为O(1)；2）最坏情况：在表尾查到，需比较n次，时间复杂度为O(n)；3）平均情况：需要比较的平均次数为(n+1)/2，因此顺序表按值查找的平均时间复杂度也为O(n)。

6.2 其他应用

  • 对阵矩阵可以压缩后存储到一维数组；
  • 一维数组可以用来实现哈希表；
  • 二维数组可以用来保存图的邻接关系。
搜索