您的位置:首页 > 房产 > 家装 > 从零开始学习c++全套通关系列(第三章)万字总结,建议收藏!

从零开始学习c++全套通关系列(第三章)万字总结,建议收藏!

2024/12/23 7:53:14 来源:https://blog.csdn.net/2302_80329073/article/details/140474335  浏览:    关键词:从零开始学习c++全套通关系列(第三章)万字总结,建议收藏!

 数组的定义

在C++中,定义数组涉及到声明数组的类型和大小。

数组的抽象表示:

数组就是一个存放相同数据类型的大盒子。

 数组的定义格式:

type arrayName[arraySize];
  • type 表示数组中元素的数据类型,可以是基本类型(如int, float, double等)、结构体、类或者其他数据类型。
  • arrayName 是数组的名称,你可以根据需要给数组取一个合适的名字。
  • arraySize 是数组的大小,即数组可以容纳的元素数量。这个值必须是一个正整数常量或者一个常量表达式,用来指定数组的长度。

整数数组定义

int arr1[5]; // 定义一个包含5个整数的数组

这将创建一个名为numbers的数组,它可以存储5个整数。

字符数组定义

char arr2[5]={'a','b','c','d','e'};// 定义一个包含5个字符的数组

这里创建了一个名为arr2的字符数组,初始化为abcde。

二维整数数组定义

int arr3[3][3]={{1,2,3},{4,5,6},{7,8,9}};; // 定义一个3x3的整数数组

这将创建一个名为matrix的二维数组,可以存储3行3列的整数。

 

结构体数组定义

struct Person {string name;int age;
};Person people[3]; // 定义一个包含10个Person结构体的数组

这里创建了一个名为people的结构体数组,每个元素都是一个Person结构体,包含姓名和年龄属性。

初始化数组

除了定义数组的大小外,还可以在定义时初始化数组元素。例如:

int arr1[5] = {1, 2, 3, 4, 5}; // 使用列表初始化数组int arr2[] = {10, 20, 30}; // 自动确定数组大小为3char name[] = "John"; // 初始化字符数组double matrix[2][2] = {{1.0, 2.0}, {3.0, 4.0}}; // 初始化二维数组

初始化数组时可以使用花括号 {} 进行列表初始化,如果没有显式指定数组大小,编译器会根据初始化列表自动确定数组大小。

注意事项

  • 数组索引从0开始:数组的第一个元素的索引是0,最后一个元素的索引是数组大小减一。
  • 数组长度在编译时确定:数组的大小必须在编译时确定,并且无法在运行时更改。
  • 越界访问:访问数组元素时要确保索引在有效范围内,否则会导致未定义的行为。

数组的特点

相同数据类型的元素集合

数组是由相同类型的元素组成的有序集合。这意味着在定义数组时,所有元素都必须是相同的数据类型,例如整数、浮点数、字符等。

固定大小

数组在创建时必须指定固定的大小,即数组能够容纳的元素数量。这个大小在编译时确定,并且不能在运行时更改。例如,如果定义了一个大小为5的数组,那么它将始终包含5个元素,无法动态增加或减少。

int num[5];
int num[]={1,2,3,4,5};

c++不会做数组边界检查,及时下标越界了也能继续执行,所以要固定数组的大小,这点十分重要。 

连续的内存空间

数组中的元素在内存中是连续存储的。这使得对数组元素的访问效率很高,因为可以通过索引直接计算出元素的内存地址。

字节数:

  • char 1字节
  • int 4字节
  • double 8字节

零基础索引

数组的索引是从0开始的。例如,第一个元素的索引是0,第二个是1,依此类推。这种从零开始的索引方式在C++和其他许多编程语言中都是常见的。

缺乏越界检查

C++中的数组没有内建的越界检查机制。这意味着如果访问超出数组边界的元素,程序不会报错,而是会导致未定义行为。因此,使用数组时必须确保不会访问超出数组范围的元素。

注:如果越界会出现乱码,但是不会报错

多维数组

C++支持多维数组,即数组的元素本身也可以是数组。例如,二维数组可以看作是一个表格,包含行和列,三维数组则可以看作是立方体,包含深度、行和列等。

一维数组:

二维数组:

灵活的初始化方式

在定义数组时,可以使用初始化列表 {} 来为数组元素赋初值。这使得在定义数组的同时进行初始化操作变得简洁和方便。

数组的遍历

传统的通用循环方式

 高级for循环

for(int i:arr){cout<<i<<" ";}
  • 通过临时变量,在每一次循环体中,记录数组的每一个元素。
  • 数组有几个元素,循环体就执行几次。 

字符数组

在C++中,字符数组是由字符组成的数组,通常用于存储和操作文本数据。字符数组可以是一维的,也可以是多维的,但一般用来存储字符串或字符序列。

一维字符数组

多维字符数组

 

测试题

最大子数组和

问题描述:给定一个整数数组,找到其中具有最大和的连续子数组,并返回其最大和。

解决方案:可以使用Kadane算法,时间复杂度为O(n)。生成相应的代码

习题代码部分:

#include <vector>
#include <climits>// 函数定义:求解最大子数组和
int maxSubArraySum(const std::vector<int>& nums) {int maxSoFar = INT_MIN; // 初始化最大和为最小整数int maxEndingHere = 0;  // 当前子数组的最大和for (int num : nums) {maxEndingHere += num;if (maxSoFar < maxEndingHere)maxSoFar = maxEndingHere;if (maxEndingHere < 0)maxEndingHere = 0;}return maxSoFar;
}// 测试函数
void testMaxSubArraySum() {std::vector<int> test1 = {-2,1,-3,4,-1,2,1,-5,4};std::vector<int> test2 = {1};std::vector<int> test3 = {5,4,-1,7,8};assert(maxSubArraySum(test1) == 6); // 子数组 [4,-1,2,1] 的和最大,为 6assert(maxSubArraySum(test2) == 1); // 只有一个元素,最大和即为该元素assert(maxSubArraySum(test3) == 23); // 子数组 [5,4,-1,7,8] 的和最大,为 23
}int main() {testMaxSubArraySum();return 0;
}

代码分析:

#include <vector>
#include <climits>

#include <vector> 引入了STL中的vector容器,用于存储整数数组。
#include <climits> 引入了C标准库中的limits.h头文件,提供了整型变量的极限值,如INT_MIN表示整型的最小值

int maxSubArraySum(const std::vector<int>& nums) {

定义了一个名为maxSubArraySum的函数,接受一个std::vector<int>类型的引用参数nums,表示输入的整数数组。

    int maxSoFar = INT_MIN; // 初始化最大和为最小整数int maxEndingHere = 0;  // 当前子数组的最大和

maxSoFar用于存储遍历过程中遇到的最大子数组和。
maxEndingHere用于存储当前遍历位置为止的子数组的最大和。

    for (int num : nums) {maxEndingHere += num;if (maxSoFar < maxEndingHere)maxSoFar = maxEndingHere;if (maxEndingHere < 0)maxEndingHere = 0;}

遍历数组中的每一个元素num。
每次迭代时,maxEndingHere加上当前元素的值。如果maxEndingHere大于maxSoFar,则更新maxSoFar。
如果maxEndingHere变为负数,则重置为0,因为负数作为子数组的起点不会带来更大的和。

数组中的最长递增子序列


问题描述:在给定的无序数组中找到最长的递增子序列的长度。
解决方案:动态规划或二分查找结合动态规划,时间复杂度为O(n^2)或O(n log n)。

习题代码部分

#include <vector>
#include <algorithm>int lengthOfLIS(const std::vector<int>& nums) {std::vector<int> tails;for (int x : nums) {auto it = std::lower_bound(tails.begin(), tails.end(), x);if (it == tails.end())tails.push_back(x);else*it = x;}return tails.size();
}int main() {std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};std::cout << "Length of LIS: " << lengthOfLIS(nums) << std::endl;return 0;
}

动态规划方法

  • 创建一个dp数组,其中dp[i]表示以nums[i]结尾的最长递增子序列的长度。
  • 对于每个元素nums[i],遍历之前的所有元素nums[j],如果nums[i] > nums[j],则可能形成更长的递增子序列。
  • 更新dp[i]为dp[j] + 1和当前dp[i]中的较大值。
  • 最终返回dp数组中的最大值。

二分查找结合动态规划方法

  • 维护一个tails数组,它将存储所有可能的递增子序列的“尾巴”元素。

  • 对于每个元素x,使用std::lower_bound找到第一个大于等于x的位置。

  • 如果x大于tails中的所有元素,将其添加到tails的末尾。

  • 否则,替换tails中找到的位置的元素为x。

  • 最终tails的大小就是最长递增子序列的长度。这种方法利用了二分查找来优化查找过程,从而降低了时间复杂度。

旋转数组的最小数字


问题描述:一个数组先升序后降序排列,找出最小的数字。
解决方案:使用二分查找,时间复杂度为O(log n)。

习题代码部分:

#include <iostream>
#include <vector>int findMin(const std::vector<int>& nums) {if (nums.empty()) return -1;int left = 0, right = nums.size() - 1;// 如果数组没有旋转,直接返回第一个元素if (nums[left] < nums[right]) return nums[left];while (left < right) {int mid = left + (right - left) / 2;// 如果中间元素大于右边元素,说明最小值在mid的右侧if (nums[mid] > nums[right])left = mid + 1;// 否则,最小值在mid的左侧或就是midelseright = mid;}// 当left == right时,找到了最小值return nums[left];
}int main() {std::vector<int> nums = {4, 5, 6, 7, 0, 1, 2};std::cout << "Minimum element is: " << findMin(nums) << std::endl;return 0;
}

代码分析: 

  • 初始化:设置两个指针left和right分别指向数组的开始和结束位置。
  • 未旋转情况:如果数组的第一个元素小于最后一个元素,说明数组没有旋转,最小值即为数组的第一个元素。
  • 循环条件:当left小于right时,继续查找。
  • 计算中间点:mid为left和right之间的中间索引。
  • 比较与更新:
  • 如果nums[mid]大于nums[right],说明最小值在mid的右侧,因此更新left = mid + 1。
  • 否则,最小值可能在mid或mid的左侧,所以更新right = mid。
  • 退出条件:当left == right时,退出循环,此时left或right指向最小值。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com