LIST的结构
list：链表。与vector与deque不同，它不要求计算机申请一片连续的空间。每个list都是由若干个结点构成的，而每个结点也包括三个部分：
- 存储的元素
- 指向前一个结点的指针
- 指向后一个结点的指针
list没有下标，因此需要使用迭代器进行访问。list不支持sort，但是其支持sort成员函数。
算法来源于生活，链表的结构，与灯笼类似。
LIST的一些函数
remove(val)—— 删除与val相等的所有元素empty()—— 判断链表是否为空reverse()—— 翻转链表sort(链表对象) ——sort成员函数
LIST的基本操作
#include <iostream>
#include <list>
using namespace std;
void print(list<int> L)//遍历函数
{
list<int>::iterator it2;
for (it2 = L.begin();it2 != L.end();it2 ++) cout << *it2 << " ";
cout << endl;
}
int main()
{
int a[] = {10,20,30,40,50};
list<int> L(a,a + 5);//将数组a中的值赋给链表
print(L);//10 20 30 40 50
L.insert(L.begin(),100);
L.insert(L.end(),100);//在链表首位插入元素100
print(L);//100 10 20 30 40 50 100
//在第x个位置插入元素y
//需要先找到第x个位置的迭代器
int x,y;
cin >> x >> y;//3 33
list<int>::iterator it = L.begin();
for (int i = 1;i < x;i++) it++;
L.insert(it,y);//insert函数中传入的是迭代器
print(L);//100 10 33 20 30 40 50 100
L.remove(100);//删除链表中所有的100
print(L);//10 33 20 30 40 50
L.sort();//排序
print(L);//10 20 30 33 40 50
return 0;
}
LIST习题
题目描述(原题链接)
给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。
操作1：在第X个数之后插入一个数Y。
操作2：删除第X个数。
操作3：对区间[X，Y]进行排序。
操作4：对区间[X，Y]进行翻转。
操作5：删除区间[X，Y]中值为Z的数。
输入
第一行两个整数N，M（N，M≤100000）含义见试题描述。
第二行N个整数，表示原来的数组。
接下来M行，每行第一个数OPT，表示操作类型。
对于操作1，接下来两个数X，Y，含义见题面描述，保证0≤X≤当前数的个数，若X=0，表示在数组开头插入。
对于操作2，接下来一个数X，含义见题面描述，保证1≤X≤当前数的个数。
对于操作3，接下来两个数X，Y，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作3不超过10个。
对于操作4，接下来两个数X，Y，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作4不超过10个。
对于操作5，接下来三个数X，Y，Z，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作5不超过10个。
输出
输出若干个数，表示最后的数组。
样例输入
5 5
1 4 3 2 5
3 2 4
4 4 5
5 2 3 2
5 2 3 1
1 0 9
样例输出
9 1 3 5 4
解题思路：模拟过程即可。对于不太熟悉的操作，可在C++ reference中查找
AC代码：
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <list>
using namespace std;
const int N = 1e5 + 10;
int a[N],opt;
void print(list<int> L)//遍历函数
{
list<int>::iterator it;
for (it = L.begin();it != L.end();it ++) cout << *it << " ";
cout << endl;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0;i < m;i++) scanf("%d",&a[i]);//数据量大,scanf较快
list<int> L(a,a + m);//将数组赋值给链表
while (m --)
{
scanf("%d",&opt);
if (opt == 1)
{
int x,y; scanf("%d%d",&x,&y);
if (x == 0)
{
L.insert(L.begin(),y);
continue;
}
list<int>::iterator it1 = L.begin();
for (int i = 0;i < x;i++) it1++;
L.insert(it1,y);
}
else if (opt == 2)
{
}
else if (opt == 3)
{
}
else if (opt == 4)
{
}
else if (opt == 5)
{
}
}
print(L);
return 0;
}
