A3阶段 第三课 向量和链表
学习时长
约1.5小时
难度
A3阶段/CSP-J
标签
数据结构
讲师
王骏峣
向量
向量（vector）是可以动态增长的数组，其长度会根据元素个数实时更新
原理：
vector在内部使用一个连续的内存块来存储元素，当需要增加元素时，会判断当前元素数量是否超过了容量，若是，则会重新分配一块更大的内存，并将原有元素复制到新的内存块中，然后释放原有内存块 连续内存块的优势：可以O(1)地访问vector中任意一个元素向量的使用
| 代码 | 说明 |
|---|---|
|
向量的使用
#include <vector>;
|
导入头文件 |
|
向量的使用
vector<int> v;
|
定义一个向量，并规定其内部元素的类型 |
|
向量的使用
v.push_back(x);
|
在末尾插入一个元素x （注：vector支持在任意位置插入元素，但需要移动后面的元素，时间复杂度O(n)，基本不用） |
|
向量的使用
v[i] = x;
|
将第i个元素修改为x |
|
向量的使用
v[i]
|
访问第i个元素 （注意：vector下标从0开始） |
|
向量的使用
v.empty()
|
查询v是否为空 |
|
向量的使用
v.size()
|
查询v的元素个数 |
|
向量的使用
v.clear();
|
清空v |
vector的遍历
方法1
//使用i访问元素
}
方法2
//使用下标（v[i]）访问元素
}
for (int i = v.size() - 1;i >= 0;i --){//逆序
//使用下标（v[i]）访问元素
}
例题
第一题 存包柜
前往第二题 [NOIP2016 普及组] 海港
前往学习要点总结
- vector是动态改变大小的数组
- 下标访问法类比数组
- 使用push_back()函数在尾部添加元素
- 其他函数类比其他STL容器
链表
不仅存储元素的值，还存储元素顺序的数据结构
结构体模拟链表
定义结构体链表
int val; //记录节点的值
int pre, nxt; //记录上一个节点和下一个节点
} a[N];
val存储当前节点的信息，它也可以是多个变量或一个复杂的数据类型
pre和nxt用来保存每一个节点的前继节点编号和后继节点编号
注意：下标的顺序并不是链表的顺序
想要顺利地遍历链表，还需要额外的head变量存储链表首元素的下标，tail变量保存链表尾元素的下标
首节点的pre和尾节点的nxt可以设为-1，方便代码实现
链表的遍历
while(i != -1){
cout << a[i].val;
i = a[i].nxt;
}//顺序
int i = tail;
while(i != -1){
cout << a[i].val;
i = a[i].pre;
}//逆序
链表的插入
a[C].pre = A;
a[C].nxt = a[A].nxt;
a[a[A].nxt].pre = C;
a[A].nxt = C;
//特殊情况
//在首节点前插入元素
a[C].nxt = head;
a[C].pre = -1;
a[head].pre = C;
head = C;
//在尾节点后插入元素
a[C].pre = tail;
a[C].nxt = -1;
a[tail].nxt = C;
tail = C;
链表的插入时间复杂度为O(1)
链表的删除
a[a[C].nxt].pre = a[C].pre;
如果删除的是头或尾节点，那么特判改head和tail就好了
链表的优劣
链表和数组、vector一样可以用来存储元素
优势：可以O(1)地插入或删除任意一个元素
数组和vector需要O(n)
劣势：不支持快速查找第i个元素，只能从头到尾遍历查找，复杂度O(n)
数组和vector支持O(1)查找第i个元素
原因：数组和vector中的元素在内存中是连续存放的，只需要首地址+偏移量就能找到第i个元素的地址，而链表中的元素在内存中不是连续存放的
根据题型需要，选择合适的数据结构