图灵普及1班A知识点总结：
第一课：
1.顺序存储和链式存储是计算机常见的两种储存结构。
2.顺序存储：
优点：操作方便，随机存取，查找元素时间复杂度为O（1）。
缺点：1.要预先开辟数组空间，会有空间浪费，溢出的情况。2.插入，删除元素不方便，时间复杂度为O（n）。
3.链式存储：
优：1.存储空间动态分配，只要计算机内存空间空闲，就不会溢出。2.插入，删除元素方便，时间复杂度为O（1）。
缺：查找元素不方便，时间复杂度为O（n）。
4.链表分为单向链表，循环链表和双向链表。
5. 链表中第一个结点：头结点，最后一个结点：尾结点，头结点通常不储存数据，尾结点指针为空（null）。
第二课：
1.栈（stack）：又称堆栈，是只能在某一端插入，删除的特殊线性表。具有先进后出的特性。
2.栈在STL中的定义：stack<typename> name。
3.常用函数（时间复杂度均为O（1）））：
push（x）将x入栈。
pop（）(弹出栈顶元素)
top（）（获得栈顶元素）
empty（）（判空，true为空，false为非空）
size（）（返回栈内元素个数）
4.队列（queue）：先进先出的线性表。
常用（函数时间复杂度均为O（1）））：
push（x）将x入队。
pop（）(队首元素出队)
front（）（获得队首元素）
back（）（获得队尾元素）
empty（）（判空，true为空，false为非空）
size（）（返回队列内元素个数）
5.优先队列：和队列一样，先进先出。特性：队列中优先级最大的元素总是位于队首。通过优先队列能快速获取极值<最大，最小>。
6.命名：priority_queue<int,vector<int>,greater<int> > q;
7.常用函数：
push（x）将x入队。
pop（）(队首元素出队)
top（）（获得队列优先级最高的元素）
empty（）（判空，true为空，false为非空）
size（）（返回队列内元素个数）
8.优先队列没有back（），不会将元素去重。
9.vector（动态数组）定义：vector<int> name。
10.常用函数：
push_back（x）添加元素x。
pop_back（）删除尾元素；
insert（it,x）插入元素x；
size（）（返回vector内元素个数）
erase（）删除一个区间所有元素。
clear（）清空所有元素。
11.set（集合）c++STL的一种关联式容器。
定义：set name。
12.常用函数：
insert（x）插入元素x；
find（x）返回对应迭代器，否则返回end（）。
size（）（返回vector内元素个数）
erase（first，last）删除一个区间所有元素。
clear（）清空所有元素。
13.map（映射）常用的STL 容器。
定义：map<key,value> mp;
常用函数：
find（key）返回键为key的迭代器。
size（）获得map中映射的个数。
erase（）删除迭代器，键。
clear（）清空所有元素。
第三课：差分：对于给每个区间序列加值的问题，可以利用差分解决。
双指针：一种优化时间复杂度的算法。
2 个赞
老师，请您看看如何
1 个赞
666
秀儿
管理员打破老铁封印
1 个赞