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的元素的个数)
这里后者是所有元素的原因是,每次都要判断所有元素,即判断列是否为现在处理的这一列。