一、链表

链表是一种数据结构。
链表有一个“头指针”变量,以head表示,只要有头指针就可以得到这条链表的所有信息。它不存储数据只存放一个地址,该地址指向下一个元素。
链表中每一个元素称为“结点”,每个结点都应包括两个部分:

  1. 数据域:用户需要用的实际数据
  2. 指针域:存放下一个结点的地址

head指向第一个元素,第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束,单链表示意图如下:
单链表

二、slist/list

slist/list是STL对于链表的一种实现。
slist:迭代器属于单向的Forward Iterator(可读写)。
list :迭代器属于双向的Bidirectional Iterator(可以双向读写)。
看起来slist的功能应该会不如list,但由于其单向链表的实现,其消耗的空间更小,某些操作更快。
这里重点介绍list,双向链表示意图如下:
在这里插入图片描述
1、list的构造函数

list<int>a{1,2,3}
list<int>a(n)    //声明一个n个元素的列表,每个元素都是0
list<int>a(n, m)  //声明一个n个元素的列表,每个元素都是m

2、push_back()和push_front()
插入一个元素到list中
push_back():从list的末端插入(尾***r>push_front():从list的头部插入。(头***r>调用list容器的成员函数begin():得到一个指向容器起始位置的iterator可以调用list容器的end()函数:得到list末端下一位置

3、clear()
清空list中的所有元素

4、front()和back(),pop_back()和pop_front()
front():获得list容器中的头部元素
back():获得list容器的最后一个元素
pop_back():删掉尾部第一个元素
pop_front():删掉头部第一个元素
链表为空时调用不会报错,故最好先调用empty()函数判断。

5、reverse()
可以实现list的逆置

6、insert()
在指定位置插入一个或多个元素

a.insert(a.begin(),100);  //在a的开始位置(即头部)插入100
a.insert(a.begin(),2, 100);   //在a的开始位置插入2个100

7、erase()
用迭代器遍历删除,执行后it会指向下一个元素。

list<int>::iterator it;
for(it = List.begin(); it != List.end() ; ) {
  it =  List.erase(it);  //it指向了下一个元素
}

三、例题

HDOJ-1276士兵队列训练问题

Problem Description
某部队进行新兵队列训练,将新兵从一开始按顺序依次编号,并排成一行横队,训练的规则如下:从头开始一至二报数,凡报到二的出列,剩下的向小序号方向靠拢,再从头开始进行一至三报数,凡报到三的出列,剩下的向小序号方向靠拢,继续从头开始进行一至二报数。。。,以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。

Input
本题有多个测试数据组,第一行为组数N,接着为N行新兵人数,新兵人数不超过5000。

Output
共有N行,分别对应输入的新兵人数,每行输出剩下的新兵最初的编号,编号之间有一个空格。

Sample Input

2
20
40

Sample Output

1 7 19
1 19 37
#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main() {
    fio 
    int n, m;
    cin >> n;
    while (n--) {
      list<int> l;
      list<int>::iterator it;
      cin >> m;
      for (int i = 1; i <= m; i++)
        l.push_back(i);//注意插入链表操作的关键词
    int flag = 2, count;
    while (l.size() > 3) { 
      count = 1;//报数每次由1开始
      for (it = l.begin(); it != l.end(); ) {
        if (count++ % flag == 0) 
          it = l.erase(it);//执行后迭代器自动指向下一个元素,故需要“it=”
        else 
          it++;
      }
      flag == 2 ? flag = 3: flag = 2;//2、3交替轮流进行
    }
    for (it = l.begin(); it != l.end(); it++) {
      if (it != l.begin()) {
        cout << " ";
      }
      cout << *it; 
    }
    cout <<endl;
  }
}