Fade away

Appearance

数组 ​

1.概念 ​

数组是在内存中的一片连续的存储区域，用来存储若干个相同类型

  • 数组可以用来存储任意类型的数据，但是每个数组中的数据类型必须相同

  • 数组是一个定长的容器，一旦初始化完成，长度不能改变

  • 数组中每个值称为元素

  • 每个元素在数组的位置成为下标，下标从0开始递增

定义数组

c++
修饰符 数组名[数组长度];
修饰符 数组名[数组长度] = {值1, 值2, 值3,....}

2.基本使用 ​

2.1 定义数组 ​

定义指定长度的数组，因为没有初始值，所以此时数组中的元素是不安全的

c++
int arr[10];
cout << arr[0] << endl; // 可能会打印地址中残留的数据

定义数据的同时，给出初始值

c++
int arr[5] = {1, 2, 3, 4, 5};

若数组中元素的数量小于数组的长度，后面的值会自动填充为 0

c++
int arr[5] = {1, 2, 3};  // {1,2,3,0,0}

若定义数组不指定长度，此时数组的大小则为初始化时元素的个数

c++
int arr[]={1,2,3,4,5};

2.2 下标 ​

2.2.1 下标的概念 ​

每个元素在数组的位置成为下标，也可成为索引，下标从0开始递增，通常用index来表示

通过下标，我们可以访问和修改数组中的值

c++
int arr[5]={1,2,3,4,5};

image-20240716104905886

2.2.2 访问元素 ​

通过数组名[下标]的语法访问数组中特定下标的值，数组访问不可越界

c++
#include<iostream>
using namespace std;

int main() {
	int arr[10] = { 1,2,3,4,5 };

	cout << arr[0] << endl;	// 1
	cout << arr[1] << endl;	// 2
	cout << arr[2] << endl;	// 3
	cout << arr[3] << endl;	// 4
	cout << arr[4] << endl;	// 5

	cout << arr[5] << endl;	// 0
	cout << arr[6] << endl;	// 0
	cout << arr[7] << endl;	// 0
	cout << arr[8] << endl;	// 0
	cout << arr[9] << endl;	// 0


	// cout << arr[10] << endl;	// 越界访问

	return 0;
}

3.数组的长度 ​

在c++中，数组没有一个现成的长度属性供我们使用，但可以通过计算获取数组的长度

sizeof()方法可以获取一个数据类型或者一个变量的空间占用大小

那么一个数组的空间大小除以数组中变量类型的空间大小，就是数组的长度

c++
int len = sizeof(数组名)/sizeof(数组类型)

例如

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	int len = sizeof(arr) / sizeof(int);
	cout << len << endl;	// 5

	double arr1[10] = { 1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0 };
	cout << sizeof(arr1) / sizeof(double) << endl;	// 10

	return 0;
}

4.数组的内存分析 ​

4.1 元素的地址规律 ​

我们定义一个数组，并打印每个值的地址

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	
	cout << &arr[0] << endl;	
	cout << &arr[1] << endl;	
	cout << &arr[2] << endl;	
	cout << &arr[3] << endl;	
	cout << &arr[4] << endl;	

	return 0;
}

出来的是一串16进制的地址，看不出什么名堂

image-20240716110920417

把地址转化为int10进制

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	
	cout << (int)&arr[0] << endl;	
	cout << (int)&arr[1] << endl;	
	cout << (int)&arr[2] << endl;	
	cout << (int)&arr[3] << endl;	
	cout << (int)&arr[4] << endl;	

	return 0;
}

每次打印的值肯定不同，但是可以发现，每个值相差4，也就是一个int所占的空间

image-20240716111245917

所以可以得出：数组是在内存中的一片连续的存储空间

4.2 数组的地址 ​

打印下数组的地址

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	
	cout << (int)&arr[0] << endl;	
	cout << (int)&arr[1] << endl;	
	cout << (int)&arr[2] << endl;	
	cout << (int)&arr[3] << endl;	
	cout << (int)&arr[4] << endl;	

	cout << (int)arr << endl;

	return 0;
}

image-20240716111741299

可以发现，数组中首元素的地址就是数组本身的地址

TIP

通过指针访问数组

因为数组中首元素的地址就是数组本身的地址，所以将指针指向数组不需要加&

c++
int main() {
	int arr[5] = { 1,2,3,4,5 };
	int* p = arr; // 相当于 int* p = &arr[0];
	
	cout << *p << endl;  // 1
	cout << ++*p << endl;  // 2

	return 0;
}

4.3 数组作为函数参数 ​

将数组作为参数，并在函数中打印此数组

c++
#include<iostream>
using namespace std;

void printArray(int arr[]) {
	cout << arr << endl;
}

int main() {
	int arr[5] = { 1,2,3,4,5 };
	printArray(arr);

	return 0;
}

发现打印的是一个地址

image-20240716112823352

既然是地址，就可以使用指针指向这个地址，并可访问其中的值。我们使用指针来打印这个地址中的值

c++
#include<iostream>
using namespace std;

void printArray(int* arr) {
	cout << *arr << endl;
}

int main() {
	int arr[5] = { 1,2,3,4,5 };
	printArray(arr);

	return 0;
}

发现打印的是数组中第一个元素的值

image-20240716112933608

所以可以得出：数组在函数中作为参数传递时，传递的是数组第一个元素的地址

因此，如果需要在函数中遍历数组，需要再传递一个数组的长度

c++
#include<iostream>
using namespace std;

void printArray(int* arr,int len) {
	for (int i = 0;i < len;i++) {
		cout << arr[i] << endl;
	}
}

int main() {
	int arr[5] = { 1,2,3,4,5 };
	printArray(arr,sizeof(arr)/sizeof(int));

	return 0;
}

image-20240716113332585

4.4 总结 ​

  1. 数组是在内存中的一片连续的存储空间
  2. 数组中首元素的地址就是数组本身的地址
  3. 数组在函数中作为参数传递时，传递的是数组第一个元素的地址

5.数组的遍历 ​

5.1 下标遍历 ​

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	int length = sizeof(arr) / sizeof(int);
	for (int i = 0;i < length;i++) {
		cout << arr[i] << endl;
	}

	return 0;
}

5.2 元素迭代 ​

c++
#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 1,2,3,4,5 };
	for (int ele : arr) {
		cout << ele << endl;
	}

	return 0;
}

ele：迭代元素，也就是数组每一项的值，ele名是自己定义的

TIP

  • 只有在定义数组的部分才能使用此方法遍历数组，若通过函数传参，那么函数的形参只是一个值，不可遍历
  • 在迭代过程中不可通过迭代元素修改数组中元素的值，因为迭代元素和数组元素地址不同
c++
int main() {
	int arr[5] = { 1,2,3,4,5 };
	for (int ele : arr) {
		ele++;
		cout << ele << endl;	// 2,3,4,5,6
	}
	
	for (int ele : arr) {
		cout << ele << endl;	// 1,2,3,4,5
	}
	return 0;
}

上面代码，看似修改了元素的值，但修改的只是当前循环中迭代元素的值，元素本身内部的值没有改变。

通过引用可以修改数组本身元素的值

c++
int main() {
	int arr[5] = { 1,2,3,4,5 };
	for (int &ele : arr) {
		ele++;
	}
	
	for (int ele : arr) {
		cout << ele << endl;		// 2,3,4,5,6
	}
	return 0;
}

6.数组中的算法 ​

6.1 排序 ​

6.1.1 选择排序 ​

选择排序的思想是先从第一位往后找，找出数组中的最小值，把他和第一位交换位置，再从第二位找出数组中的最小值，把他和第二位交换，以此类推

img

c++
#include<iostream>
using namespace std;


void swap(int& num1, int& num2) {
	int temp = num1;
	num1 = num2;
	num2 = temp;
}

void choose_sort(int* arr, int len) {
	for (int i = 0;i < len;i++) {
		int minIndex = i;
		for (int j = i + 1;j < len;j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		swap(arr[minIndex], arr[i]);
	}
}

int main() {
	int arr[10] = { 5,2,9,4,1,3,5,10,6,9 };
	int len = sizeof(arr) / sizeof(int);
	choose_sort(arr, len);

	for (int val : arr) {
		cout << val << ",";		// 1,2,3,4,5,5,6,9,9,10,
	}
	return 0;
}

6.1.2 冒泡排序 ​

冒泡排序的思想是两两比较，若前面的值大于后面的值，则交换位置，这样每一轮交换之后，最大的值会依次往数组的最后面排

img

c++
#include<iostream>
using namespace std;

void swap(int& num1, int& num2) {
	int temp = num1;
	num1 = num2;
	num2 = temp;
}

void bubble_sort(int* arr, int len) {
	for (int i = 0;i < len-1;i++) {
		for (int j = 0;j < len-1-i;j++) {
			if (arr[j] > arr[j+1]) {
				swap(arr[j], arr[j+1]);
			}
		}
	}
}

int main() {
	int arr[10] = { 5,2,9,4,1,3,5,10,6,9 };
	int len = sizeof(arr) / sizeof(int);
	bubble_sort(arr, len);

	for (int val : arr) {
		cout << val << ",";		// 1,2,3,4,5,5,6,9,9,10,
	}
	return 0;
}

TIP

j < len-1-i的意义：

每一轮外层循环时，都会拿数组中相邻的两个值相互比较，但是当倒数第二和和倒数第一个值比较完之后，我们不可能再拿倒数第一个值和后面的值比较了，因为后面没值了，所以要-1

每一轮外层循环完成之后，最大的值已经排在了最后面，此时没必要再拿当前循环总最大值和后面的比较，肯定没后面的值大，所以每一轮外层循环之后，就已经找出了i个最大值，就需要-i

6.2 数组元素查找 ​

元素查找就是给定一个值，让我们在一个数组中查找与该值相同的元素，找到就返回该元素的下标，否则返回-1

6.2.1 顺序查询 ​

顺序查询就是从数组的开头往后一个一个找

c++
#include<iostream>
using namespace std;


int indexOf(int* arr, int len,int val) {
	for (int i = 0;i < len;i++) {
		if (val == arr[i]) return i;
	}
	return -1;
}

int main() {
	int arr[10] = { 5,2,9,4,1,3,5,10,6,9 };
	int len = sizeof(arr) / sizeof(int);

	cout << indexOf(arr, len, 6) << endl;		// 8
	cout << indexOf(arr, len, 9) << endl;		// 2
	cout << indexOf(arr, len, 3) << endl;		// 5
	cout << indexOf(arr, len, 22) << endl;		// -1
	cout << indexOf(arr, len, 33) << endl;		// -1
	
	return 0;
}

6.2.2 二分查找 ​

二分查找仅适用于已经排序好的数组，其思想是拿需要查找的值和数组中间的那个值比较，再根据比较的情况，把比较的范围缩小到数组的左半边或者右半边，以下是二分查找和顺序查找的比较图

binay

c++
#include<iostream>
using namespace std;

int binary_search(int* arr,int len,int val) {
	int min = 0, max = len - 1;
	while (min <= max) {
		int mid = (min + max) / 2;
		if (arr[mid]>val) {
			max = mid - 1;
		}
		else if(arr[mid] < val) {
			min = mid+1;
		}
		else {
			return mid;
		}
	}
	return -1;
}

int main() {
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	int len = sizeof(arr) / sizeof(int);
	cout << binary_search(arr,len,2) << endl;	// 2
	cout << binary_search(arr,len,5) << endl;	// 5
	cout << binary_search(arr,len,6) << endl;	// 6
	cout << binary_search(arr,len,7) << endl;	// 7
	cout << binary_search(arr,len,10) << endl;	// -1
	cout << binary_search(arr,len,15) << endl;	// -1
	return 0;
}

7.浅拷贝和深拷贝 ​

7.1 浅拷贝 ​

浅拷贝是地址拷贝，拷贝到的是数组的首元素地址。这样修改一个数组中每个元素的值，另一个数组也会被更改

TIP

如下可以看到，把一个数组直接赋值给另一个数组，当我们修改其中一个数组中的值，另一个数组的值也被修改了

c++
#include<iostream>
using namespace std;

void print_array(int *arr,int len) {
	for (int i = 0;i < len;i++) {
		cout << arr[i];
		if (i < len-1) {
			cout << ',';
		}
		else {
			cout << '\n';
		}
	}
}

int main() {
	int arr[] = { 1,2,3,4,5 };
	int* arr1 = arr;		// 接着赋值地址给arr1

	print_array(arr, sizeof(arr) / sizeof(int));
	print_array(arr1, sizeof(arr) / sizeof(int));

	arr[2] = 666;

	print_array(arr, sizeof(arr) / sizeof(int));
	print_array(arr1, sizeof(arr) / sizeof(int));

	return 0;
}

image-20240717105148879

7.2 深拷贝 ​

深拷贝：定义一个新的数组，长度与原来的数组相同，将原来数组中的每一个元素依次拷贝到新的数组中。

TIP

而一步一步把一个数组里面的值，一个一个的赋值到另一个数组，这样修改任意一个数组，对另一个数组都不会有影响

c++
#include<iostream>
using namespace std;

void copy(int* arr, int len,int* arr2,int len2) {
	if (len2 <= len) {
		for (int i = 0;i < len2;i++) {
			arr2[i] = arr[i];
		}
	}
}

void print_array(int *arr,int len) {
	for (int i = 0;i < len;i++) {
		cout << arr[i];
		if (i < len-1) {
			cout << ',';
		}
		else {
			cout << '\n';
		}
	}
}

int main() {
	int arr[] = { 1,2,3,4,5 };
	int arr1[5];
	copy(arr, sizeof(arr) / sizeof(int), arr1, sizeof(arr1) / sizeof(int));

	print_array(arr, sizeof(arr) / sizeof(int));
	print_array(arr1, sizeof(arr) / sizeof(int));

	arr[2] = 666;
	arr1[3] = 777;

	print_array(arr, sizeof(arr) / sizeof(int));
	print_array(arr1, sizeof(arr) / sizeof(int));

	return 0;
}

image-20240717105733992

8.二维数组 ​

二维数组就是一个数组里面嵌套了若干个小数组

c++
修饰符 数组名[行数][列数] = {
    {值1，值2，...},
    {值1，值2，...},
    {值1，值2，...},
    // ...
};

8.1 定义二位数组 ​

1.声明不赋值

c++
int arr[3][5];

2.声明并赋值

c++
int arr[3][5]={
    {1,2,3,4,5},
    {1,2,3},
    {1,2,3,4,5}
};

TIP

若二维数组中的小数组元素不足时，会自动补0，多了则会报错

3.类似一维数组写法

c++
int arr[3][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

TIP

这种写法会被自动转化为如下写法

c++
int arr[3][5]={
    {1,2,3,4,5},
    {6,7,8,9,10},
    {11,12,13,14,15}
};

也就是说会自动根据行数和列数，转化为一个正常的二维数组，当最后一个小数组元素不足时，会自动补0，多了则会报错

4.只声明列数，不声明行数

c++
int arr[][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

TIP

这种写法会根据每一列元素的数量，自动转化为相应数量的行数

c++
int arr[][5]={
    {1,2,3,4,5},
    {6,7,8,9,10},
    {11,12,13,14,15},
    {16,17}
};

8.2 二维数组的访问 ​

通过指定的行数和列数便可访问二维数组中的指定元素

c++
数组名[行数-1][列数-];

例如

c++
int main() {
	int arr[3][5] = {
		{1,2,3,4,5},
		{6,7,8,9,10},
		{11,12,13,14,15}
	};

	cout<<arr[0][2]<<endl; // 第一行第三列：3
	cout<<arr[1][3]<<endl; // 第二行第四列：9
	cout<<arr[2][4]<<endl; // 第三行第五列：15

	return 0;
}

MIT Licensed

Copyright © 2024-present xarzhi