您的位置:首页 > 新闻 > 资讯 > 第二周 线性表-数组

第二周 线性表-数组

2025/5/11 0:38:51 来源:https://blog.csdn.net/tjl521314_21/article/details/139609114  浏览:    关键词:第二周 线性表-数组

前言

数组 array」是一种线性数据结构,其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的
位置称为该元素的「索引 index」。从简单数组开始正式的算法学习之路

线性表-数组

下面是其相关操作


class MyArray {
private:int* data;      // 存储数组元素的指针int size;       // 数组的当前大小int capacity;   // 数组的容量public:MyArray(int initialCapacity = 10) : size(0), capacity(initialCapacity) {data = new int[capacity];}// 析构函数,释放动态分配的内存~MyArray() {delete[] data;}// 添加元素到数组末尾void append(int value) {if (size >= capacity) {resize();}data[size++] = value;}// 在指定位置插入元素void insert(int value, int index) {if (index < 0 || index > size) {std::cout << "index is wrong" << std::endl;return;}if (size >= capacity) {resize();}for (int i = size; i > index; i--) {data[i] = data[i - 1];}data[index] = value;size++;}// 删除指定位置的元素void remove(int index) {if (index < 0 || index >= size) {std::cout << "index is wrong" << std::endl;return;}for (int i = index; i < size - 1; i++) {data[i] = data[i + 1];}size--;}// 修改指定位置的元素void modify(int value, int index) {if (index < 0 || index >= size) {std::cout << "index is wrong" << std::endl;return;}data[index] = value;}// 查找元素的位置int find(int value) const {for (int i = 0; i < size; i++) {if (data[i] == value) {return i;}}return -1;}// 获取数组大小int getSize() const {return size;}// 获取数组容量int getCapacity() const {return capacity;}// 重新分配内存以增加容量void resize() {capacity *= 2;int* newData = new int[capacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}delete[] data;data = newData;}// 打印数组元素void print() const {std::cout << "array: ";for (int i = 0; i < size; i++) {std::cout << data[i] << " ";}std::cout << std::endl;}
};

数组的优点和局限性

数组存储在连续的内存空间内,且元素类型相同。这种做法包含丰富的先验信息,系统可以利用这些信息来
优化数据结构的操作效率。
‧ 空间效率高:数组为数据分配了连续的内存块,无须额外的结构开销。
‧ 支持随机访问:数组允许在 𝑂(1) 时间内访问任何元素。
‧ 缓存局部性:当访问数组元素时,计算机不仅会加载它,还会缓存其周围的其他数据,从而借助高速缓
存来提升后续操作的执行速度。
连续空间存储是一把双刃剑,其存在以下局限性。
‧ 插入与删除效率低:当数组中元素较多时,插入与删除操作需要移动大量的元素。
‧ 长度不可变:数组在初始化后长度就固定了,扩容数组需要将所有数据复制到新数组,开销很大。
‧ 空间浪费:如果数组分配的大小超过实际所需,那么多余的空间就被浪费了。

应用

数组是一种基础且常见的数据结构,既频繁应用在各类算法之中,也可用于实现各种复杂数据结构。
‧ 随机访问:如果我们想随机抽取一些样本,那么可以用数组存储,并生成一个随机序列,根据索引实现
随机抽样。
‧ 排序和搜索:数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数
组上进行。
‧ 查找表:当需要快速查找一个元素或其对应关系时,可以使用数组作为查找表。假如我们想实现字符到
ASCII 码的映射,则可以将字符的 ASCII 码值作为索引,对应的元素存放在数组中的对应位置。
‧ 机器学习:神经网络中大量使用了向量、矩阵、张量之间的线性代数运算,这些数据都是以数组的形式
构建的。数组是神经网络编程中最常使用的数据结构。
‧ 数据结构实现:数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如,图的邻接矩阵表示实
际上是一个二维数组。

参考书籍:hello 算法

版权声明:

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

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