Fabian备忘录

人类资格证考核中

数组

发表于 更新于 分类于
本文字数： 2.4k

数组

声明和数组下标

数组代表内存里一组连续的同类型的存储区，可以用来把多个存储区合并成一个整体。 int arr[10] = {1,2,3,4,5,6,7,8};

数组声明：

  • int arr[10];
  • 类型名int表示数组里所有元素的类型
  • 整数10表示数组里包含的元素个数
  • 数组元素个数不可以改变，是常量

使用注意：

  • 每个元素都有下标，标识一个元素在当前数组容器中的位置。通过下标可以直接访问数组内任意元素
  • 下标从零开始
  • 超过范围的下标不可以使用，会内存错误。一定要注意，内存溢出是程序中经常出现的BUG
  • 数组名和下标可以表示数组里的元素，如a[2]表示第三个元素

数组优点：

  • 可以编写循环程序，依次处理数组里的所有元素
  • 循环变量依次代表所有元素

数组使用常见错误：off-by-one error(差一错误)

考虑一个问题，假定整数x满足边界条件x>=16且x<=37，那么此范围内的整数x可能的取值有多少？

  1. 首先考虑最简单的情况（特例），然后将结果外推
  2. 仔细计算边界问题

特例：x的上界与下界重合，即x>=16与x<=16，显然其中的x个数为1；那么假定下界位low，上界位high；当low与high重合，个数为1，即共有high-low+1个元素。那么外推，这里共有37-16+1=22个元素。 最容易出错的地方就是+1，很容易就仅仅计算high-low。

编程技巧：

  • 用数学上的左闭右开[,)区间表示，上述问题可以看作[16,38)，即38-16=22
  • C++中，我们编程也遵循这个原则，从0开始，使用非对称区间，让下界可以取到值，上界取不到值。这样设计程序，可以直接用上界-下界来取得范围大小；当取值范围为空的时候，上界值=下界值；即使取值范围为空，上界值也永远不可能小于下界值。
1
2
3
4
5
6
7
8
9
10
11
//推荐的方式：
for(int index=0;index < 10;++index)
{
	cout<<a[index]<<" ";
}

//不推荐的方式
for(int index=0;index <= 9;++index)
{
	cout<<a[index]<<" ";
}

增删改查

  • 在尾部添加和删除操作，时间复杂度为O(1)。只需要操作尾部元素即可，对与其他元素没有干扰。

  • 在数组中间进行添加和删除操作，时间复杂度为O(n)。在中间操作，会对其他元素造成影响，操作元素后面的每一个元素都需要进一步操作

  • 数组的访问用遍历很高效，时间复杂度为O(1)；

1
2
3
4
5
6
//下标访问
a[2] = 5;

//指针访问
int* p = a;
*(p+2) = 5;

数组的查找时间复杂度并不低，一般取绝与数组自身容量(数组容量很大的时候并不适合遍历查找，时间复杂度太高，可以用二分查找)：

1
2
3
4
5
6
7
8
9
//寻找a[]中第一个值为3的目标：
int len = sizeof(a)/sizeof(a[0]);
for(int index = 0;index<len;++index)
{
	if(a[index] == 3)
	{
		return index;
	}
}

二维数组

二维数组包含了两个维度的数组。

二维数组访问：

1
2
3
4
5
6
7
8
9
int a[2][4] = {{1,2,3,4},{5,6,7,8}};
for(int row=0;row<2;++row)
{
	for(int col = 0;col<4;++col)
	{
		cout<<a[row][col]<<" ";
	}
	cout<<endl;
}

  二维数组我们一般按照一行一行的遍历，虽然可以进行一列一列的遍历的，但是实际操作中不建议这么做：因为在一个小的时间窗口内，访问的地址越接近越好，这样执行的速度快；即我们一般把时间最长的循环放在内层，最短的循环放在外层，以减少CPU跨切循环的次数。

std::vector

Vector是面向对象方式的动态数组。

我们经常使用的简单的数组，因为定义的时候就有固定容量，无法实现动态扩容插入元素。

使用vector容器，可以轻松实现动态扩容添加元素。

添加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<vector>
using namespace std;

int main()
{
	vector<int> vec = { 1,2,3,4 };

	//尾添加
	vec.push_back(5);  //尾添加，不会出现下标越界 {1,2,3,4,5}


	//指定位置添加
	//insert方法，传入位置和值
	vec.insert(--vec.end(), 4);   //{1,2,3,4,4,5}
	return 0;
}

遍历

1
2
3
4
for(int index = 0;index < vec.size();++index)
{
	cout<<vec[index]<<endl;
}

我们可以使用vector中的capacity()方法来查看vector当前的容量，用size()的方法来查看已经存储的元素的个数。这两者有区别。

删除

  • vec.pop_back(); //尾删除
  • vec.eraser(pos); //指定位置删除

要注意如果打算使用eraser的方法进行尾删除，要注意end()的位置。数组的区间往往是左闭右开，end()指向的是尾元素的后面的地址，并不是尾元素自身。

1
2
vec.pop_back();
vec.eraser(vec.end()-1);   //这两者等价