#include <iostream>
#include <cstdlib> // 添加rand()和srand()所需头文件
#include <ctime> // 添加time()所需头文件
using namespace std;
// 函数声明
int randomAccess(int *nums, int size);
int main() {
/* 初始化数组 */
// 存储在栈上
int arr[5]; // 未初始化的栈数组
int nums[5] = {1,2,3,4,5}; // 已初始化的栈数组
// 存储在堆上
int* arr1 = new int[5]; // 未初始化的堆数组
int* nums1 = new int[5] {1,3,2,5,4}; // 已初始化的堆数组
// 设置随机种子
srand(time(0));
// 测试随机访问
cout << "Stack random: " << randomAccess(nums, 5) << endl;
cout << "Heap random: " << randomAccess(nums1, 5) << endl;
// 释放堆内存
delete[] arr1;
delete[] nums1;
return 0;
}
// 随机访问元素
int randomAccess(int *nums, int size) { // 修正逗号为英文
// 在区间[0, size)中随机抽取索引
int randomIndex = rand() % size; // 添加rand()函数调用
int randomNum = nums[randomIndex];
return randomNum;
}
//插入元素(在数组nums的index位置处插入num)
void insert(int *nums,int num,int index,int size){
for(int i = size-1;i> index;i--){
nums[i] = num[i-1];
}
nums[index] = num;
}//删除元素(删除数组nums的index处的元素))
void remove(int *nums,int size,int index){
//将index位处后一个元素向前移动一位
for(int i = index; i < size - 1;i++){
nums[i] = nums[i+1];
}
}
/*总的来看，数组的插入与删除操作有以下缺点。
·时间复杂度高：数组的插入和删除的平均时间复杂度均为O（n）,其中n为数组长度。
·丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
·内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做会造成部分内存空间浪费。
*/
//查找元素(遍历数组为size大小数组，返回值为target的数组索引i)
int find(int *nums，int size，int target){
for(int i=0;i < size;i++){
if(nums[i] ==target){
return i;
}
}
return -1;
}
//扩充数组())
int *extend（int *nums,int size ,int enlarge){
int *res = new int[size + enlarege];
//(申请一片大小为size（数组nums的长度）加enlaerge的空间)
//遍历nums数组将nums中的元素一一搬运到res中
for(int i=0;i<size;i++){
res[i] = nums[i];
}
//释放nums的内存
delete[]nums;
return res;
}
/*4.1.2数组的优点与局限性1
数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数
据结构的操作效率。
·空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
·支持随机访问：数组允许在O(1)时间内访问任何元素。
·缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提
升后续操作的执行速度。
连续空间存储是一把双刃剑，其存在以下局限性。
·插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
·长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
·空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。
4.1.3数组典型应用1
数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。
·随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽
样。
·排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进
行。
·查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到ASC川
码的映射，则可以将字符的ASC川码值作为索引，对应的元素存放在数组中的对应位置。
·机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建
的。数组是神经网络编程中最常使用的数据结构。
·数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是
一个二维数组。
*/