| c语言动态数组 | 您所在的位置：网站首页 › foreach索引从几开始 › c语言动态数组 |
c语言动态数组
|
数组是什么呢？数组是一种线性表数据结构，它用一组连续的内存空间存储一组具有相同类型的数据。
现在直奔主题， 因为数组是连续存储的所以有了随机访问的特性，因此数组可以用索引来访问，时间复杂度是O(1)。既然可以用索引访问那么现在请看，假如我现在要访问a[k]： 下标从0开始： a[k]_add = base_add + k * type_size 下标从1开始： a[k]_add = base_add + (k-1)*type_size type_size是数组存储数据类型在内存中占据的字节，base_add 就是数组起始位置在内存中的标识。 看到上面的表达式大家发现什么了没有？其实很简单啦，从0开始就是为了少做一次减法运算而已，有没有感觉被骗了，事实就是这样，大规模计算中，少做一次减法，提升的就是效率。 数组缺点：内存中的连续存储导致了插入和删除就很低效，复杂度是O(n)，插入或删除一个元素，后面的全部元素都要移动它们在内存中的位置。 数组在c++ stl中 叫做vector，在python中就是list 。这里要强调一点，访问数组元素通过索引(下标)，需要注意数组越界问题，一般越界都会报错，不过c语言却有个坑，不信你试试，c语言中数组索引越界，是不会给你抛出错误的。
现在介绍动态数组的概念。动态数组要求可以随时插入、删除元素。所以动态数组的底层实现涉及到数组动态扩容和动态缩容。当插入到数组中的元素的个数达到数组类初始化的空间大小capacity的时候，直接2倍扩充即变成2*capacity。那删除元素的时候，空出来了那么多内存，我要怎么去释放掉呢？这里我只简单说一下怎么操作，就是当数组中剩余的元素个数是原来capacity的1/4的时候，选择缩容，缩容为capacity/2。大家看到这可能很疑惑，为什么不是元素个数删除到是原来容量的1/2的时候就缩容，这里就涉及到一个均摊时间复杂度的问题了，会造成均摊时间复杂度震荡，后面再细讲。 最后给大家附上一个简单的动态数组实现： using namespace std;template class MyVector{private: T* data ; int capacity ; int size ; void resize( int newCapacity){ assert(newCapacity >= size) ; T* newData = new T[newCapacity] ; for(int i = 0; i< size ; i++) newData[i] = data[i] ; delete[] data; data = newData ; capacity = newCapacity; }public: MyVector(){ data = new T[10]; capacity =10 ; size = 0; } ~MyVector(){ delete[] data ; } void push_back(T e){ //assert(size < capacity) ; if(size == capacity) resize( 2*capacity); data[size++] = e ; } T pop_back(){ assert( size > 0); T ret = data[size-1] ; //防止下面if(size == capacity/2)时候 data[size-1]数据被抹掉. size-- ; // if(size == capacity/2) if(size == capacity/4) //除以4防止均摊复杂度震荡 resize(capacity/2); return ret ; }}; |
【本文地址】