【C++编程启蒙】第五章 数的存储与组织

第50课 认识一维数组

一、一维数组的定义

数组：一组有序数据的集合，每个元素都属于同一数据类型。

一维数组的定义格式：

类型标识符 数组名[常量表达式];
int a[5];

注意：

1. 数组名的命名规则与变量名的命名规则一致；
2. 常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量；
3. int a[10]; 表示数组a有10个int类型的元素，分别为a[0]~a[9]；

二、一维数组的引用

通过给出数组名称和元素下标，程序可以引用数组中的任何一个元素。

一维数组的引用格式：

数组名[下标]
a[5] 或 a[2+3] 或 a[i] 或 a[i+j] 都是合法的

注意：

1. 下标可以是任意值为整型的表达式，该表达式可以包含变量和函数调用。
2. 数组的巧妙之处在于可以使用变量作为下标，来实现灵活处理数组元素；
3. 数组元素可以像同类型的普通变量那样使用，对其赋值和运算（和普通变量完全相同）；

int a[5]; // 定义一个长度为5的int类型数组
a[0]=1; // 给下标为0的数组元素赋值1
a[4]=2; // 给下标为4的数组元素赋值2
a[2]=a[0]+a[4]; // a[0]与a[4]求和并赋值给a[2]

三、一维数组的初始化

可以在定义数组的同时初始化

类型标识符 数组名[常量表达式]={值1, 值2, ……}
int a[5]={0, 1, 2, 3, 4};

注意：

1. 在初值列表中，没有列出初始值的元素默认初始值为0；

int a[5]={1, 2, 3};
// 以上代码的效果是：定义长度为5的int类型数组a，并初始化a[0]=1, a[1]=2, a[2]=3, a[3]=0, a[4]=0
int a[5]={};
// 以上代码的效果是：定义长度为5的int类型数组a，并初始化所有元素的值为0

第51课 认识vector

一、vector介绍

1. vector是一种可变大小的序列容器；
2. vector和数组一样采用连续存储空间来存储元素——意味着可以用下标来对vector的元素进行访问。

形象地比喻：数组就像线段，定义之后大小固定；vector就像射线，可以延伸或缩短；

二、vrctor的几种常用语法

参考书本P224

vector<int> v;
// 创建空vector
v.push_back(x)
// 向尾部增加一个元素x
v.insert(pos, x)
// 向pos地址指向的元素前增加一个元素x
v[i]
// 访问i位置的元素
v.pop_back()
// 删除向量中最后一个元素
v.clear()
// 清空向量中所有元素
v.empty()
// 判断向量是否为空
v.size()
// 返回向量中元素的个数
v.begin()
// 返回向量头指针（迭代器），指向第一个元素
v.end()
// 返回向量尾指针（迭代器），指向最后一个元素+1位置
v.erase(v.begin()+i)
// 删除第i位位置的元素

第52课 数组指针与容器迭代器

一、指针与数组的关系

一个数组是一块连续的内存单元组成的，数组名就是这块连续内存单元的首地址。

int a[5]={0, 1, 2, 3, 4}; // 定义int类型数组a
int *pa=a; //定义int类型数组指针，赋予初值a，即数组a的首地址，也是a[0]的地址
// pa、a、&a[0]均指向同一单元，即a[0]的地址
// pa+1、a+1、&a[1]均指向同一单元，即a[1]的地址

二、指向数组的指针

数组指针变量定义的一般形式：

类型说明符 *指针变量名;
int a[5];
int *pa=a;

可以通过 *(pa+i) 来访问a[i]

三、容器的迭代器

迭代器（iterator）就是访问容器的统一访问接口，它的作用是提供一个遍历 容器内部所有元素 的接口。

int x;
vector<int> v;
while(cin>>x){
        v.push_back(x);
}
for(vector<int>::iterator it=v.begin(); it!=v.end(); ++it){
        cout<<*it<<" ";
}

第53课 找最值

一、找最小值

// param begin : 序列起始地址（迭代器）
// param end：序列结束地址（迭代器）
// return : 序列中最小元素地址（迭代器）
min_element(begin, end);

二、找最大值

// param begin : 序列起始地址（迭代器）
// param end：序列结束地址（迭代器）
// return : 序列中最大元素地址（迭代器）
max_element(begin, end);

第54课 默认排序函数

一、概念

将杂乱无章的数据，按一定顺序排列，叫排序。

常见的排序方法有：快速排序、希尔排序、堆排序、直接选择排序称为不稳定的排序算法，基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序被称为稳定的排序算法。

二、如何判断排序是否稳定

稳定的排序

排序前后，大小相同元素的顺序不变，称为稳定的排序

不稳定的排序

排序前后，大小相同元素的顺序可能变化，称为不稳定的排序

三、Sort函数详解

默认排序

sort(序列起始地址, 序列结束地址);
// 效果：按默认规则升序排列

自定义排序

sort(序列起始地址, 序列结束地址, 自定义排序规则)
// 效果：按自定义规则排列

第55课 自定义规则的排序