还记得约瑟夫问题吧, 本来他们报数的顺序是固定的, 那么能否任意选择顺时针或者逆时针呢?
只需要加一个反向的指针就可以了, next之外加个prev.
其实能加一个, 也能加2个, 加3个 … 我们就可以随意使用指针, 随意建立复杂的数据关系. 理论上, 建模这块就获得了自由.
算法竞赛中, 数据的关系链, 我们更多的是用数据数组的下标来表示, 避免使用魔鬼般的指针.
双向链表
定义
struct Node {
int data;
Node *prev;
Node *next;
}
Node *mylist;- 插入
s = new Node;
s->data = x;
s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;- 删除
p->prev->next = p->next;
p->next->prev = p->prev;
delete(p);完整程序
#include <stdio.h>
#include <stdlib.h>
//双向循环链表
struct Node {
int data; //数据域
Node *prev; //指向前驱结点的指针
Node *next; //指向后继结点的指针
};
void init(Node **mylist)
{
*mylist = new Node;
(*mylist)->data = 0;
(*mylist)->prev = *mylist;
(*mylist)->next = *mylist;
}
//插入元素操作
bool insert(Node *mylist, int i, int data)
{
//判断链表是否存在
if (!mylist)
{
printf("list not exist!\n");
return false;
}
//只能在位置1以及后面插入，所以i至少为1
if (i < 1)
{
printf("i is invalid!\n");
return false;
}
//找到i位置所在的前一个结点
Node *front = mylist; //这里是让front与i不同步，始终指向j对应的前一个结点
for (int j = 1; j < i; j++) {
front = front->next;
if (front == mylist)
{
printf("don't find front!\n");
return false;
}
}
//创建一个空节点，存放要插入的新元素
Node *s = new Node;
s->data = data;
//插入结点
s->prev = front;
s->next = front->next;
front->next->prev = s;
front->next = s;
return true;
}
//删除元素操作
Node * deleteNode(Node *mylist, int i)
{
//找到i位置所在的前一个结点
Node *front = mylist, *s;
for (int j = 1; j < i; j++)
{
front = front->next;
if (front->next == mylist)
{
printf("don't find front!\n");
return NULL;
}
}
s=front->next;
s->next->prev = front;
front->next = s->next;
return s;
}
//头部插入元素操作
bool insert(Node *mylist, int data)
{
Node *head;
Node *s;
head = mylist;
//创建存放插入元素的结点
s = new Node;
s->data = data;
//头结点后插入结点
s->prev = head;
s->next = head->next;
head->next->prev = s;
head->next = s;
return true;
}
//遍历链表操作
void print(Node *mylist)
{
Node *cur = mylist->next;
while (cur != mylist)
{
printf("<-->%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main(){
Node *mylist;
//初始化链表
init(&mylist);
for (int i = 0; i < 6; i++){
insert(mylist, i+1);
}
print(mylist);
//插入结点
insert(mylist, 1, 9);
print(mylist);
printf("\n");
//删除结点
deleteNode(mylist, 2);
print(mylist);
printf("\n");
return 0;
}STL list
❝list 由双向链表（doubly linked list）实现而成，元素也存放在堆中，每个元素都是放在一块内存中，他的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载(不能用下标随机访问任一一个元素)。但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。❞
头文件
#include <list>
定义
list<int> a; //定义一个int类型的列表a
list<int> a(10); //定义一个int类型的列表a，并设置初始大小为10
list<int> a(10, 1); //定义一个int类型的列表a，并设置初始大小为10且初始值都为1
list<int> b(a); //定义并用列表a初始化列表b
//除此之外，还可以直接使用数组来初始化向量：
int n[] = { 1, 2, 3, 4, 5 };
list<int> a(n, n + 5);基本操作
大小
- 容器大小：
lst.size(); - 容器最大容量：
lst.max_size(); - 更改容器大小：
lst.resize(); - 容器判空：
lst.empty();
添加函数
- 头部添加元素：
lst.push_front(const T& x); - 末尾添加元素：
lst.push_back(const T& x); - 任意位置插入一个元素：
lst.insert(iterator it, const T& x);
list<int> lst; //定义一个list
lst.push_front(4); //队头增加元素
lst.push_back(5); //队尾添加元素
list<int>::iterator it=lst.begin(); //定义一个迭代器指针在第一个位置
lst.insert(it,2); //在第一个位置插入数据2
lst.insert(lst.begin(),3,9); //任意位置插入n个相同元素
//插入另一个向量的[forst,last]间的数据
list<int> lst2(5,8);
lst.insert(lst.begin(),lst2.begin(),++lst2.begin());
删除函数
- 头部删除元素：
lst.pop_front(); - 末尾删除元素：
lst.pop_back(); - 任意位置删除一个元素：
lst.erase(iterator it); - 清空所有元素：
lst.clear();
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[])
{
list<int> lst;
for(int i=0;i<8;i++){
lst.push_back(i); //初始化list
}
lst.pop_front(); //头部删除元素
lst.pop_back(); //末尾删除元素
//定义一个迭代器指针指向头部
list<int>::iterator it=lst.begin();
lst.erase(it); //删除指针指向的元素
//删除[first,last]之间的元素
lst.erase(lst.begin(),++lst.begin());
//遍历显示
for(it=lst.begin();it!=lst.end();it++){
cout<<*it<<" "; //输出：3 4 5 6
}
cout<<endl;
lst.clear(); //清空所有元素
//判断list是否为空
if(lst.empty()){
cout <<"元素为空"<<endl; //输出：元素为空
}
return 0;
}访问函数
- 访问第一个元素：
lst.front(); - 访问最后一个元素：
lst.back();
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[]){
list<int> lst;
for(int i=0;i<6;i++){
lst.push_back(i);
}
cout<<lst.front()<<endl; //访问第一个元素，输出：0
cout<<lst.back()<<endl; //访问最后一个元素，输出：0
return 0;
}其他函数
删除容器中相邻的重复元素：lst.unique();
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[])
{
//多个元素赋值s
list<int> lst1;
lst1.assign(3, 1);
list<int> lst2;
lst2.assign(3, 2);
//交换两个容器的元素
//swap(lst1, lst2); // ok
lst1.swap(lst2);
//遍历显示
cout << "交换后的lst1: ";
list<int>::iterator it;
for (it = lst1.begin(); it!=lst1.end(); it++)
cout << *it << " "; // 输出：2 2 2
cout << endl;
//遍历显示
cout << "交换后的lst2: ";
for (it = lst2.begin(); it != lst2.end(); it++)
cout << *it << " "; // 输出：1 1 1
cout << endl;
list<int> lst3;
lst3.assign(3, 3);
list<int> lst4;
lst4.assign(3, 4);
//合并两个列表的元素
lst4.merge(lst3); //不是简单的拼接，而是会升序排列
cout << "合并后的lst4: ";
for (it = lst4.begin(); it != lst4.end(); it++)
cout << *it << " "; // 输出：3 3 3 4 4 4
cout << endl;
list<int> lst5;
lst5.assign(3, 5);
list<int> lst6;
lst6.assign(3, 6);
//在lst6的第2个元素处，拼接入lst5
lst6.splice(++lst6.begin(), lst5);
cout << "拼接后的lst6: ";
for (it = lst6.begin(); it != lst6.end(); it++)
cout << *it << " "; // 输出：6 5 5 5 6 6
cout << endl;
//删除容器中相邻的重复元素
list<int> lst7;
lst7.push_back(1);
lst7.push_back(1);
lst7.push_back(2);
lst7.push_back(2);
lst7.push_back(3);
lst7.push_back(2);
lst7.unique();
cout << "删除容器中相邻的重复元素后的lst7: ";
for (it = lst7.begin(); it != lst7.end(); it++)
cout << *it << " "; // 输出：1 2 3 2
cout << endl;
return 0;
}迭代器
- 开始迭代器指针：
lst.begin(); - 末尾迭代器指针：
lst.end(); - 反向迭代器指针，指向最后一个元素：
lst.rbegin(); - 反向迭代器指针，指向第一个元素的前一个元素：
lst.rend();
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[]){
list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
cout<<*(lst.begin())<<endl; // 输出：1
cout<<*(--lst.end())<<endl; // 输出：3
cout<<*(lst.rbegin())<<endl; // 输出：3
cout<<*(--lst.rend())<<endl; // 输出：1
cout<<endl;
return 0;
}算法
- 遍历元素
list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); it++)
cout << *it << endl;- 元素翻转
#include <algorithm>
lst.reverse();- 元素排序
#include <algorithm>
lst.sort(); // 采用的是从小到大的排序- 查找
find(lst.begin(), lst.end(), a);顺序表
单向链表/线性链表
双向链表
循环链表
