数据结构概览

序列式

数组

1. 概述

​ 将相同类型的元素存储于连续的空间，长度不可变。

​ 初始化时需要给定长度同时对每一个索引元素赋值。

2. 可变数组

​ 基于数组和扩容机制实现的数据结构，更为灵活。

​ STL的实现为vector。

3. vector

​ 可变数组的STL实现，动态控件，随着新元素加入，内部机制会自行扩充空间以容纳新元素。

3.1 迭代器

​ 普通指针都可以作为vector的迭代器并且满足所有必要条件，像vector支持的随机存取，普通指针本就具备，所以vector提供Random Access Iterators。

3.2 vector的数据结构

​ image-20210726154816687

​ vector采用连续线性空间，使用两个迭代器start与finish分别指向配置得来的连续空间中已经被使用的范围，并且用迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。

​ 容量（capacity）代表vector整块连续空间的大小，容量总是大于或等于vector的大小，一定容量等于大小，vector即满载，下次新增元素时，容量便扩充至两倍，亦或继续扩充。

3.3 vector的常用操作
3.3.1 初始化
1
2
3
4
5
vector<int> vct(10);
vector<int> vct(10,1);//定义十个int类型元素的vector，值均为1
vector<int> vct(a);//使用vector a来创建vector vct
vector<int> vct(a.begin(),a.begin()+5);//使用vector a的部分元素来创建vector vct
int b[5]={1,2,3,4,5};vector<int> vct(b,b+5);//使用数组来创建vct
3.3.2 元素操作

​ 

1
2
3
4
5
6
7
8
9
10
11
vector<int> vct;
vct.push_back(1);
vct.push_back(2);
vct.push_back(3);//将元素添加至末尾
vct.insert(vct.begin(),1);//在下标1处插入元素1
vct.pop_back();//删除最后一个元素
vct.erase(vct.begin(),vct.begin()+2);//删除元素，包括前不包括后
vct.back();//返回最后一个元素
vct.front();//返回第一个元素
vct.empty();//返回是否为空
vct.clear();//清空

链表

1.概述

​ 以节点为单位，每个元素为独立对象，非连续存储。

1
2
3
4
5
struct ListNode{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL){}
}

​ 构建链表需要实例化每一个节点。