复合数据类型
本文作者：程序员飞云
数组
相同类型的数据存放在里面，内存地址是连续的，占用相同大小的空间
- 定义
// 数组定义
int a[2] ;
// 外界设置长度
const int n = 3;
double a2[n];- 初始化
int a3[4] = { 1,2,3,4 };
int a4[] = { 1,2,3 };
int a5[10] = { 1,2,3 };// 其余初始值为0
//int a6[2] = { 1,2,3 };//错误，个数不对
//int a6[4] = a3; // 错误不能使用一个数组给另一个数组赋值如果没有进行初始化，默认的数组值是0xCC
- 数组访问
下表默认从0开始到len-1
int a[3] = { 1,2,3 };
cout << "a[0]=" << a[0] << endl;
cout << "a[1]=" << a[1] << endl;
cout << "a[2]=" << a[2] << endl;- 计算数组长度
这里面没有设置对应的size，所以只能手动计算
int aSize = sizeof(a) / sizeof(a[0]);- 遍历数组
int aSize = sizeof(a) / sizeof(a[0]);
// 下标遍历
for (int i = 0; i < aSize; i++) {
cout << "a[" << i << "]=" << a[i] << endl;
}
// 增强for
for (int num : a) {
cout << num << endl;
}多维数组
- 初始化
int arr[3][4] = { {1,2,3} ,{4,5,6} };
int arr2[3][4] = { 1,2,3,4,5,6 }; // 和上面的一样
int arr3[][4] = { 1,2,3,4,5,6 }; // 第一个可以省略- 访问元素
cout << arr[1][2] << endl;- 计算行，列长度
int rowSize = sizeof(arr) / sizeof(arr[0]);
int colSize = sizeof(arr[0]) / sizeof(arr[0][0]);
cout << "行个数" << colSize<<endl;
cout << "列个数" << rowSize << endl;- 遍历
下标遍历
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
cout << "arr[" << i << "][" << j << "]=" << arr[i][j] << endl;
}
}增强for遍历
for (auto& row : arr) {
for (auto num : row) {
cout << num << endl;
}
}&引用
auto:由编辑器自动分析
数组排序
选择排序
选择排序是从当前数组里面选出最小（最大）元素放在初始位置，再从剩余的元素里面取出最小（最大）元素，继续放在已经排序好的元素后面，直到所有的数据都排序完成
int main() {
// 选择排序
int arr[7] = { 4,2,5,6,1,3,2 };
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[i]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for (int num : arr) {
cout << num << "\t" << endl;
}
}冒泡排序
会将最小（最大）的线排列到数组的最后，然后再次判断剩下来的元素，重复相同的操作。
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}模板类vector
因为数组使用极为不方便，每次都需要手动计算数组长度，而且必须要指定数组的大小，vector长度不是固定的。
引入vector
#include<vector>
using namespace std;- 默认初始化
vector<int> v1;- 列表初始化
vector<char> v2 = { 'a','b','c' };
vector<char> v3 { 'a','b','c' };- 直接初始化
vector<short> v4(5);// 创建5个元素
vector<long> v5(5, 100); // 默认值都是100- 访问元素
cout<<v2[2]<<endl;- 修改元素
v2[2] = 'x';
cout << v2[2] << endl;- 遍历元素
for (int i = 0; i < v2.size(); i++)
{
cout<<"v2["<<i<<"]=" << v2[i] << endl;
}
for (char ch : v2) {
cout << ch<< endl;
}- 添加倒序元素
v2.push_back('r');- 删除倒序元素
v2.pop_back();vector是数组的上层抽象，长度不固定，运行效率低。
C++11里面还增加了array，数组类似，长度固定，方便。
字符串
string
- 引入string
#include<string>;
using namespace std;- 默认初始化
string s1;- 拷贝初始化
string s2 = "Hello world";- 直接初始化
string s3("hello word");
string s4(8, 's');// 8个s连接在一起- 访问字符
cout << s4[4] << endl;- 修改字符
s4[5] = 'h';- 遍历字符
for (int i = 0; i < s4.size(); i++) {
cout << s4[i]<<"\t" ;
}
cout << endl;
for (char ch : s4) {
cout << ch << "\t";
}
cout << endl;- 大小写转换
for (int i = 0; i < s4.size(); i++) {
s4[i] = toupper(s4[i]);
}- 字符串拼接
string s5 = "hello";
string s6 = "world";
string s7 = s5 + s6;
cout << s7 << endl;
string s8 = s5 + "," + s6;
cout << s8 << endl;
//string s9 = "hello" + "world";错误- 字符串比较
s5 = "hello";
s6 = "hello world";
s7 = "hhh";
cout << (s5 == s6 ? "true" : "false") << endl;
cout << (s5 < s6 ? "true" : "false") << endl;
cout << (s5 < s7 ? "true" : "false") << endl;总结
使用string的时候，如果进行比较，==只会比较当前位数上的字符值的大小。
字符串拼接的时候，不能使用两个纯字符串相加，否则会报错
字符数组
- 字符数组初始化
char str[] = { 'h','e','l','l','o' };- 字符数组转换为字符串初始化
char str2[] = { 'h','e','l','l','o','\0' };- 计算长度
char str3[] = "hello"; // size=6，后面还有一个\0
cout << sizeof(str3) << endl;一般不推荐使用这个，因为如果是字符串的话，直接使用string就可以，但是string底层是char数组，所以这个还是有必要学习一下的。
读取输入字符串
- 简单读取多个字符串
string str1, str2;
cin >> str1 >> str2;
cout << str1 << str2 << endl;- getline读取多个单词
string str3;
getline(cin,str3);
cout << str3 << endl;- cin.get()读取单个单词
char ch;
ch = cin.get();
cout << "ch=" << ch << endl;char str4[20];
cin.get(str4, 20);读写文件
ifstream
ofstream
- 引入头文件
#include<fstream>- 读取文件
ifstream input("vector.cpp");- 逐词读取
string word;
while (input >> word) {
cout << word << endl;
}
- 逐行读取
string line;
while (getline(input, line)) {
cout << line << endl;
}
- 逐个字符读取
char ch;
while (input.get(ch)) {
cout << ch << endl;
}
- 写入文件
没有指定路径，写入到当前项目里面，需要在资源管理器里面
ofstream output("output.txt");
char ch;
while (input.get(ch)) {
output << ch << endl;
}完整代码
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int main() {
ifstream input("vector.cpp");
// 逐词读取
//string word;
//while (input >> word) {
// cout << word << endl;
//}
//// 逐行读取
//string line;
//while (getline(input, line)) {
// cout << line << endl;
//}
//// 逐字符读取
//char ch;
//while (input.get(ch)) {
// cout << ch << endl;
//}
ofstream output("output.txt");
char ch;
while (input.get(ch)) {
output << ch << endl;
}
}结构体
有点类似Java里面的类
1. struct定义
struct student
{
string name;
int age;
double score;
};2. 创建对象和初始化对象
可以在创建struct时候创建
struct Student
{
string name;
int age;
double score;
}stu2, stu3{"test",22,88};也可以在方法里面创建
Student student = { "hello",20,100 };
Student stu1{ "hello",20,100 };
// 拷贝复制
Student student4 = student;3. 访问对象数据
cout << "姓名：" << student.name << "\t年龄：" << student.age << "\t分数：" << student.score << endl;也可以定义函数直接调用就可以
void printInfo(Student student) {
cout << "姓名：" << student.name << "\t年龄：" << student.age << "\t分数：" << student.score << endl;
}4. 赋值
stu2.name = "ww";
stu2.age = 22;
stu2.score= 100;
5.结构体数组
Student stu[] = { {"张三",12,88},{"里斯",44,34} };
for (Student stu5 : stu) {
printInfo(stu5);
}#include<iostream>
using namespace std;
struct Student
{
string name;
int age;
double score;
}stu2, stu3{ "wz",21,60.0 };
void printInfo(Student student) {
cout << "姓名：" << student.name << "\t年龄：" << student.age << "\t分数：" << student.score << endl;
}
int main9() {
// 创建数据对象初始化
Student student = { "hello",20,100.0 };
Student stu1{ "hello",20,100.0 };
// 拷贝复制
Student student4 = student;
// 访问数据
//cout << "姓名：" << student.name << "\t年龄：" << student.age << "\t分数：" << student.score << endl;
printInfo(student);
// 赋值
stu2.name = "ww";
stu2.age = 22;
stu2.score= 100;
printInfo(stu2);
// 结构体数组
Student stu[] = { {"张三",12,88},{"里斯",44,34} };
for (Student stu5 : stu) {
printInfo(stu5);
}
return 0;
}枚举类型
enum week {
Mon,Tue,Wed,Thu,Fri,Sat,Sun
};#include<iostream>
using namespace std;
enum week {
Mon,Tue,Wed,Thu=10,Fri,Sat,Sun
};
int main() {
week w1 = Mon;
// 强制转换
week w3 = week(3);
// 获取的是对应的下标 0
cout << w1 << endl;
// 值为3
cout << w3 << endl;
week w4 = Thu;
// 值为10，后续的下标都是从10开始
cout << w4 << endl;
week w5 = week(100);
cout << w5 << endl;
}指针
指针的用法
可以通过指针访问指向那个数据对象，间接访问对象
int* p1;
long* p2;
long long* p3;64位默认的字节长度是8
内存具体存放方式
#include<iostream>
using namespace std;
int main() {
int* p1;
long* p2;
long long* p3;
cout << "p1的内存长度为" << sizeof(p1) << endl;
cout << "p2的内存长度为" << sizeof(p2) << endl;
int a = 10;
int b = 20;
long c = 35;
// a的地址拿出来给p1
p1 = &a;
p2 = &c;
cout << "a的地址是" << &a << endl;
cout << "b的地址是" << &b << endl;
cout << "c的地址是" << &c << endl;
cout << "p1=" << p1 << endl;
cout << "p2=" << p2<< endl;
}
内存调试
解引用操作符*
cout << "p1的值为" << *p1 << endl;
// 修改p1
*p1 = 12;
cout << "p1的值为" << *p1 << endl;
无效指针/野指针
定义一个指针，如果不进行初始化，内容是不确定的，如果此时把这个指针的内容当作一个地址访问，就有可能访问的是一个无效的对象，如果是内存核心区域，修改内容就可能导致系统崩溃。
int* p3;
*p3 = 100;
空指针
我们不想要初始化指针，可以使用如下三种方法
int* p4 = nullptr;
p4 = NULL;
p4 = 0;void指针
可以存放任意对象的地址
int i = 10;
char ch = 'c';
long s = 100;
void* vp = &i;
vp = &ch;
vp = &s;
// 不能使用*,无法推测只能存储对应的地址，和比较，不能用来解引用
二级指针
指针也有自己的内存地址，一个指针指向另一个内存的地址。
int i = 10;
int* pi = &i;
int** ppi= π
cout << "i="<<i << endl;
cout << "pi=" << pi << endl;
cout << "ppi=" << ppi << endl;
cout << "*pi的值是" << *pi << endl;
cout << "*ppi的值是" << *ppi << endl;
cout << "**ppi的值是" << **ppi << endl;
指针和const
- 指向常量的指针
const int c1 = 10, c2 = 56;
const int* pc = &c1;
pc = &c2;
//*pc = 100; 常量不可修改
pc == &i; // 可以指向变量- 指针常量
不能再次指向其他的变量,但是可以修改变量的值
// 指针常量，必须是变量
int* const cp = &i;也可以结合，变成指向常量的指针常量
const int* const cpp = nullptr;指针和数组
数组本质上也是一个指针，而数组名就是一个指针
int arr[] = { 1,2,3,4,5,6 };
cout << arr << endl;
cout <<"&arr[0]" << &arr[0] << endl;
cout << "&arr[0]" << &arr[1] << endl;
int* arrp = arr;
cout << "* arrp=" << *arrp << endl;
*arrp = 100;
cout << "* arrp=" << *arrp << endl;数组元素操作
cout << "arrp=" << arrp << endl;
cout << "arrp+1=" << arrp + 1 << endl;
cout << *arrp + 3 << endl;
cout << *(arr + 3) << endl;
*(arr + 3) = 122;
for (int num : arr) {
cout << num<<"\t";
}数组指针和指针数组
// 指针数组
int* pa[5] = {};
// 数组指针
int(*ap)[5] = {};指针数组：是数组，指向数组的指针，存放元素（长度是5*8）当前数组长度
数组指针：是指针，指针存放地址，（长度是8）
// 指针数组
int* pa[5] = {};
// 数组指针
int(*ap)[6] = {};
int arrt[] = { 1,2,3,4,5,6 };
pa[0] = &i;
pa[1] = arrt;
pa[2] = arrt + 2;
ap = &arrt; // 指向arrt整个数组 // 指针数组
int* pa[5] = {};
// 数组指针
int(*ap)[6] = {};
int arrt[] = { 1,2,3,4,5,6 };
pa[0] = &i;
pa[1] = arrt;
pa[2] = arrt + 2;
ap = &arrt;
// 得到arr的地址
cout << "*ap=" << *ap << endl;
// 获取第一个元素
cout << "**ap=" << **ap << endl;
// 获取第二个元素
cout << "*(*ap+1)=" << *(*ap+1) << endl;引用
引用的使用
在变量前面添加符号&,表示另一个变量的引用。引用必须被初始化。
引用不会存储对象，而是和初始值绑定在一起，之后无法绑定其他的对象,相当于别名，快捷方式，操作引用就是操作原对象
int main() {
int a = 10;
int b = 12;
int& ref = a;
cout << "ref=" << ref << endl;
cout << "a的地址=" << &a << endl;
cout << "ref的地址=" << &ref << endl;
ref = b;
cout << "ref的地址=" << &ref << endl;
ref = 15;
cout << "a=" <<a << endl;
}
引用的引用，也是指向的原来的引用
int & rref = ref对常量的引用
常量是不可以修改的，所有常量引用也是不可修改的
const int zero = 0;
const int& cref = zero;常量引用初始化要求很低，和变量引用不一样，只要是转换为它指定类型的所有表达式，都可以初始化
double d = 3.14;
const int& ref4 = d;引用和指针
- 引用和指针常量
引用类似于指针常量
int main() {
int a = 10;
// 指针常量
int* const p = &a;
// 引用
int& ref = a;
cout << "查看值--------------------" << endl;
cout << "a=" << a << endl;
cout << "p=" << p << endl;
cout << "ref=" << ref << endl;
cout << "修改值------------------" << endl;
ref = 20;
cout << "a=" << a << endl;
*p = 30;
cout << "a=" << a << endl;
}
但是引用和指针常量还是有区别的
引用没有内存地址，保存另一个对象的内存地址，而指针需要创建内存地址的。
cout << "a地址=" << &a << endl;
cout << "p的值=" << &p << endl;
cout << "p地址=" << &p << endl;
cout << "ref地址=" << &ref<< endl;
绑定指针的引用
int* ptr = &a;
int*& pref = ptr;没有指向引用的指针
案例
1. 翻转数组
将数组里面的元素都翻转
例如{1,2,3,4,5,6,7,8}->
- 最简单的方法就是创建一个新的数组，然后逆序填充这个数组
int main() {
const int n = 8;
int arr[n] = { 1,2,3,4,5,6,7,8 };
// 1. 创建新数组
int newArr[n];
for (int i = 0; i < n; i++) {
newArr[n-1-i] = arr[i];
}
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; i++) {
cout << newArr[i] << "\t";
}
cout << endl;
return 0;
}- 双指针，定义左右位置，交换左右位置的值，然后左指针往右走，右指针往左走
int left = 0;
int right = n - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
int size = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < size; i++) {
cout << arr[i] << "\t";
}
cout << endl;2. 检验幻方
不同的数字组成方阵，并且每行，每列，每个对角线的和都相等。
#include<iostream>
using namespace std;
int main() {
const int n = 3;
int arr[n][n] = { {4,9,2},{3,5,7},{8,1,6} };
int rowSize = sizeof(arr) / sizeof(arr[0]);
int colSize = sizeof(arr[0]) / sizeof(arr[0][0]);
// 计算目标和
int target = (1 + n * n) * (n * n) / 2 / n;
bool isValid = true;
for (int i = 0 ; i < rowSize; i++) {
int sum = 0;
// 检验每一行
for (int j = 0; j < colSize; j++) {
sum += arr[i][j];
}
if (sum != target) {
isValid = false;
break;
}
else {
sum = 0;
continue;
}
// 检验每一列
sum += arr[i][0];
if (sum != target) {
isValid = false;
break;
}
else {
sum = 0;
continue;
}
// 检验对角线
for (int j = 0; j < colSize; j++) {
sum += arr[j][j];
sum += arr[i][i];
}
if (sum != target) {
isValid = false;
break;
}
else {
sum = 0;
continue;
}
}
string res = isValid == true ? "符合" : "不符合";
cout << res << endl;
}以上代码过于冗余，重复的判断，以及多个for循环，我们可以进行优化
#include<iostream>
using namespace std;
int main() {
const int n = 3;
int arr[n][n] = { {4,9,2},{3,5,7},{8,1,6} };
int rowSize = sizeof(arr) / sizeof(arr[0]);
int colSize = sizeof(arr[0]) / sizeof(arr[0][0]);
// 计算目标和
int target = (1 + n * n) * n / 2 ;
bool isValid = true;
// 对角线的和
int sumLeft = 0;
int sumRight = 0;
for (int i = 0 ; i < rowSize; i++) {
// 每行每列的和
int sumRow = 0;
int sumCol = 0;
// 检验
for (int j = 0; j < colSize; j++) {
sumRow += arr[i][j];
sumCol += arr[j][i];
}
if (sumRow != target || sumCol !=target ) {
isValid = false;
break;
}
// 这个必须完成所有的遍历后才能进行判断
sumLeft += arr[i][i];
sumRight += arr[i][n - i - 1];
}
if (sumLeft != target || sumRight != target) {
isValid = false;
}
string res = isValid == true ? "符合" : "不符合";
cout << res << endl;
}3. 大整数相加
两个字符串形式的非负大整数num1和num2，计算和。
我们需要从最后一位进行相加，判断是否有进位，如果有进位就记录下来。
#include<iostream>
#include<string>
using namespace std;
int main() {
string num1 = "32535943020935527435432875";
string num2 = "9323298429842985843509";
string result;
// 指向个位
int p1 = num1.size() - 1;
int p2 = num2.size() - 1;
// 进位
int carry = 0;
// 两数的末尾位数相加,carry还有进位
while (p1 >= 0 || p2 >= 0 || carry == 1) {
// 判断遍历是否完成，完成就补0
int number1 = (p1 >= 0) ? (num1[p1] - '0') : 0;
int number2 = (p2 >= 0) ? (num2[p2] - '0') : 0;
int sum = number1 + number2 + carry;
carry = sum / 10;
sum = sum % 10;
result += sum + '0'; // 和个位保存到结果中
// 指针移动
p1--;
p2--;
}
// 结果反转
int left =0;
int right = result.size()-1;
while(left<right){
char ch = result[left];
result[left] = result[right];
result[right] = ch;
left++;
right--;
}
cout << "值为" << result << endl;
return 0;
}4. 旋转图像
给定二维数组，将这个二维数组顺时针旋转90°
{
{5,1,9,11},
{2,4,8,10},
{13,3,6,7},
}
转换为
{
{15,13,2,5},
{14,3,4,1},
{12,6,8,9},
}
根据数学方法
我们可以先进行矩阵转置（以对角线为对称轴，两边元素互换），然后再反转每一行里面的数组元素
#include<iostream>
using namespace std;
int main() {
int n = 4;
int arr[4][4] = {
{5,1,9,11},
{2,4,8,10},
{13,3,6,7},
{15,14,12,16}
};
int rowSize = sizeof(arr) / sizeof(arr[0]);
int colSize = sizeof(arr[0]) / sizeof(arr[0][0]);
int newArr[4][4];
// 矩阵转置
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j <= i ; j++) {
// 对角线为对称轴，互换元素
int temp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = temp;
}
}
// 每一行前后反转
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize/2; j++) {
int temp = arr[i][j];
arr[i][j] = arr[i][n-j-1];
arr[i][n-j-1] = temp;
}
}
// 打印
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i][j] << "\t";
}
cout << endl;
}
return 0;
}里面有一个关键点是进行转置的时候，我们只需要转换一半，如果全部转置，就右变回了原来的数据
5. 反转链表
力扣题目 反转链表
定义链表，可以在头文件里面定义链表，避免重复创建,list_node.h
#pragma once
struct ListNode
{
int value;
ListNode* next;
};简单的定义链表和打印链表
#include<iostream>
using namespace std;
#include "list_node.h"
int main() {
// 定义链表 1->2->3->4->5
ListNode node5 = { 5,nullptr };
ListNode node4 = { 4, &node5 };
ListNode node3 = { 3, &node4 };
ListNode node2 = { 2, &node3 };
ListNode node1 = { 1, &node2 };
// 头节点
ListNode* head = &node1;
// 打印
ListNode* np = head;
while (np) {
cout << (*np).value << "->";
np = (*np).next;
}
cout << "NULL" << endl;
}反转链表
我们可以定义两个指针,pre指向前一个节点,cur指向当前节点，通过操作原链表反转,详情步骤在算法，链表反转专题里面。
#include<iostream>
using namespace std;
#include "list_node.h"
int main() {
// 定义链表 1->2->3->4->5
ListNode node5 = { 5,nullptr };
ListNode node4 = { 4, &node5 };
ListNode node3 = { 3, &node4 };
ListNode node2 = { 2, &node3 };
ListNode node1 = { 1, &node2 };
// 头节点
ListNode* head = &node1;
// 打印
ListNode* np = head;
while (np) {
cout << (*np).value << "->";
np = (*np).next;
}
cout << "NULL" << endl;
// 指向前一个节点
ListNode* pre = nullptr;
// 遍历当前节点
ListNode* cur = head;
// 反转链表
while (cur) {
ListNode* next = (*cur).next;
(*cur).next = pre;
// 两个节点移动
pre = cur;
cur = next;
}
ListNode* newList = pre;
// 打印
np = newList;
while (np) {
cout << (*np).value << "->";
np = (*np).next;
}
cout << "NULL" << endl;
}里面的(*cur).next都可以转换为cur->next的形式，方便编写
#include<iostream>
using namespace std;
#include "list_node.h"
int main() {
// 初始化链表 1->2->3->4->5->6
ListNode node5 = { 5,nullptr };
ListNode node4 = { 4,&node5 };
ListNode node3 = { 3,&node4 };
ListNode node2 = { 2,&node3 };
ListNode node1 = { 1,&node2 };
ListNode* head = &node1;
ListNode* np = head;
while (np) {
cout << np->value << "\t";
np = np->next;
}
cout << "NULL" << endl;
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
ListNode* newList = pre;
np = newList;
while (np) {
cout << np->value << "\t";
np = np->next;
}
cout << "NULL" << endl;
}贡献者
flycodeu
版权所有
版权归属：