数组基础

特点：内存是连续的

• 优点

  • 下标访问（随机访问）时间复杂度是O(1)
  • 末尾位置增加/删除元素时间复杂度是O(1)
  • 访问元素前后相邻位置的元素非常方便

• 缺点

  • 非末尾位置增加/删除元素需要进行大量的数据移动O(n)

  • 搜索的时间复杂度

    • 无序数组-线性搜索O(n)
    • 有序数组-二分搜索O(logn)

  • 数组扩容消耗比较大

    • 扩容

数组的实现

#include <iostream>
#include <time.h>	//time()
#include <stdlib.h>	//srand()
#include <string.h>	//memcpy()

using std::cout;
using std::endl;
//using std::time;
//using std::srand;

class Arrary {
public:
    Arrary():_size(0), _capacity(10) {	//默认容量大小为10
        _data = new int[10]();
    }
    ~Arrary() {
        delete[] _data;
        _data = nullptr;
    }
public:
    //尾插
    void push_back(int val) {
        if(_size == _capacity) {
            expand(2 * _capacity);	// O(n)
        }
        _data[_size] = val;	//O(1)
        //操作完，看一下是否需要修改属性
        ++_size;
    }
    
    //尾删
     void pop_back() {
        if(_size == 0) {
            return;
        }
        --_size;
    }
    
    //按位置插
    void insert(int pos, int val) {	//pos下标
        //注意应先判断下标的有效性
        if(pos < 0 || pos > _size) {
            return;	// throw "pos invalid!";
        }
		if(_size == _capacity) {
            expand(2*_capacity);
        }
        
        // 移动元素  O(n)
        for(int i = _size - 1; i >= pos; --i) {	//_size 不要写size_t（unsigned int）这里无法停止
            _data[i + 1] = _data[i];
        }
        _data[pos] = val;
        ++_size;
    }
    
    //按位置删除
    void erase(int pos){
        if(pos < 0 || pos >= _size) {
            return;
        }
        
        // O(n)
        for(int i = pos + 1; i < _size; ++i) {
            _data[i - 1] = _data[i];
        }
        --_size;
    }
    
    //查找元素的位置
    size_t find(int data) {
        for(int i = 0; i < _size; ++i) {
            if(_data[i] == data) {
                return i;
            }
        }
        return -1;
    }
    
    //打印
    void show(){
        for(int i = 0; i < _size; ++i) {
            cout << _data[i] << " " ;
        }
        cout << endl;
    }
    
private:
    void expand(size_t size) {	//扩容
        int* temp = new int[size];
        /*for(int i = 0; i < _size; ++i) {
            temp[i] = _data[i];
        }*/
        memcpy(temp, _data, sizeof(int) * _size);
        delete[] _data;
        _data = temp;
        _capacity = size;//记得修改属性
    }
private:
    size_t _size;//大小
    size_t _capacity;//容量
    int* _data;
};

int main() {
    Arrary arr;
    
    srand(time(nullptr));
    for(int i = 0; i < 10; ++i) {
        arr.push_back(rand()%100);
    }
    arr.show();
    cout << "arr.push_back(666);arr.erase(0) = " ;
    arr.push_back(666);
    arr.erase(0);
    arr.show();
    cout << "arr.erase(2);arr.insert(0, 100);arr.pop_back() = ";
    arr.erase(2);
    arr.insert(0, 100);
    arr.pop_back();
    arr.show();
    cout << "arr.erase(arr.find(100)); = ";
    int pos = arr.find(100);
    if(-1 != pos) {
        arr.erase(pos);
    }
    arr.show();
    return 0;
} 

$./main
77 22 76 81 53 96 48 11 45 34 
arr.push_back(666);arr.erase(0) = 22 76 81 53 96 48 11 45 34 666 
arr.erase(2);arr.insert(0, 100);arr.pop_back() = 100 22 76 53 96 48 11 45 34 
arr.erase(arr.find(100)); = 22 76 53 96 48 11 45 34 

注意：

2.下标访问先判断下标的有效性

3.成员函数执行完操作后，要注意是否需要修改属性