数组

1.特点

占用连续存储空间的线性表,表中元素类型相同,下标直接访问方便,插入删除不方便。 二维数组有行优先和列优先两种存储方式,分别先存满行或列。

2.对数组的操作

一般操作包括:

  • 创建数组;
  • 销毁数组;
  • 复制数组;
  • 根据下标访问元素;
  • 获取数组长度;
  • 修改数组容量;
  • 检查下标是否越界。 -因此用动态数组更方便,或引入vector
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <iostream>
using namespace std;

// 极简泛型 vector 模板
template<typename T>
class MyVector {
private:
    T* _data;          // 动态数组首地址
    size_t _size;      // 当前元素个数
    size_t _capacity;  // 当前总容量

public:
    // 默认构造函数
    MyVector() : _data(nullptr), _size(0), _capacity(0) {}

    // 带初始容量的构造函数
    explicit MyVector(size_t cap) : _size(0), _capacity(cap) {
        _data = new T[_capacity];
    }

    // 析构函数:释放整块内存
    ~MyVector() {
        delete[] _data;
        _data = nullptr;
        _size = _capacity = 0;
    }

    // 拷贝构造函数(深拷贝,避免 double free)
    MyVector(const MyVector& other) {
        _size = other._size;
        _capacity = other._capacity;
        _data = new T[_capacity];
        for (size_t i = 0; i < _size; ++i) {
            _data[i] = other._data[i];
        }
    }

    // 下标访问运算符(返回引用,支持读写)
    T& operator[](size_t index) {
        return _data[index];
    }
    const T& operator[](size_t index) const {
        return _data[index];
    }

    // 尾插元素:容量不足自动扩容
    void push_back(const T& val) {
        if (_size ** _capacity) {
            // 扩容策略:空则设为1,否则扩为原来2倍
            size_t newCap = (_capacity ** 0) ? 1 : _capacity * 2;
            reserve(newCap);
        }
        _data[_size++] = val;
    }

    // 预留容量:只扩容,不改变元素个数
    void reserve(size_t newCap) {
        if (newCap <= _capacity) return;
        
        T* newData = new T[newCap];
        // 拷贝原有元素到新空间
        for (size_t i = 0; i < _size; ++i) {
            newData[i] = _data[i];
        }
        // 释放旧空间,更新指针
        delete[] _data;
        _data = newData;
        _capacity = newCap;
    }

    // 调整元素个数
    void resize(size_t newSize) {
        if (newSize > _capacity) {
            reserve(newSize);
        }
        _size = newSize;
    }

    // 辅助接口
    size_t size() const { return _size; }
    size_t capacity() const { return _capacity; }
    bool empty() const { return _size ** 0; }
};

// 测试用例
int main() {
    MyVector<int> vec;
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
        cout << "size=" << vec.size() 
             << "  capacity=" << vec.capacity() << endl;
    }

    cout << "\n元素:";
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;

    vec.resize(5);
    cout << "resize(5)后 size=" << vec.size() << endl;
    return 0;
}

3.区分顺序表与线性表

前者为对后者的具体存储形式类,顺序表需要考虑储存线性表元素,访问,遍历,插入,删除,扩容,清理内存等问题。主要成员有:

  • data:存放元素的数组;
  • MaxSize:最大容量;
  • last:当前最后一个元素的下标;
  • Length():返回当前长度;
  • Find():查找元素;
  • Insert():插入元素;
  • Remove():删除元素;
  • IsEmpty():判断是否为空;
  • IsFull():判断是否已满。

对于顺序表,时间复杂度为: 1.查找:n(最少为1,最多为n) 2.访问:1 3.插入删除:n

4.数组表示多项式

1.对于稠密多项式,即每个次数项系数都不为0: 只用一个一元数组,使用不同的数组下标对应不同的系数,在对应元素位置存储具体的值。

2.对于稀疏多项式: 使用二元数组,一个存储指数,一个存储系数,进行多项式相加时,按照指数顺序相加,当指数相同,对系数进行操作,当一个扫描完之后,复制另一个的剩余项。

3.对于稀疏矩阵:(指矩阵中大部分元素为0) 一般使用三元数组。对应行,列,值。这个数组只存储非零元素,0为隐式存储。 矩阵转置: 对每一列元素进行遍历。在处理每一列时,对于这一列中不为0元素,进行下标互换的操作。 时间复杂度为o(列数✖️所有不为0的元素的个数) 这里后者是所有元素的原因是,每次都要判断所有元素,即判断列是否为现在处理的这一列。

使用 Hugo 构建
主题 Stack 由 Jimmy 设计