●list基本概念
简要介绍：将数据进行链式存储，list（链表）是一种物理存储单元上的非连续的存储单元，数据元素的逻辑顺序是通过链表中的指针链接实现的。链表是由一系列结点组成；结点由两部分组成，一个是存储数据元素的数据域，一个是存储下一个结点地址的指针域。
list的优点：
①采用动态存储分配，不会造成内存浪费和溢出
②链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list的缺点：
①空间（指针域）和时间（遍历）额外耗费较大
1.普通链表
2.STL链表
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。
●list构造函数
函数原型：
■list<T>lst //list采用采用模板类实现,对象的默认构造形式
■list(beg,end) //构造函数将[beg, end)区间中的元素拷贝给本身
■list(n,elem) //构造函数将n个elem拷贝给本身
■list(const hist &lst) //拷贝构造函数
#include<iostream> #include<list> using namespace std; void printlist(list<int>& L) { for (list<int>::iterator i = L.begin(); i != L.end(); i++) { cout << *i<<" "; } cout << endl; } void text() { //默认构造 list<int>L1; for (int i = 1; i <= 10; i++) { L1.push_back(i); } printlist(L1); //区间构造 list<int>L2(L1.begin(), L1.end()); printlist(L2); //拷贝构造 list<int>L3(L2); printlist(L3); //n个elem list<int>L4(10, 1); printlist(L4); } int main() { text(); }
●list赋值和交换
函数原型：
■assign(beg，end) //将[beg,end)区间中的数据拷贝赋值给本身
■assign(beg，end) //将[beg,end)区间中的数据拷贝赋值给本身
■list& operator=(const list &lst) //重载等号操作符
■swap(lst) //将lst与本身的元素互换
#include<iostream> #include<list> using namespace std; void printlist(list<int>&L) { for (list<int>::iterator i = L.begin(); i != L.end(); i++) { cout << *i << " "; } cout << endl; } void text() { list<int>L1; L1.push_back(1); L1.push_back(2); L1.push_back(3); L1.push_back(4); L1.push_back(5); //operator =赋值 list<int>L2; L2 = L1; printlist(L2); //assign 赋值 list<int>L3; L3.assign(L1.begin(), L1.end()); printlist(L3); list<int>L4; L4.assign(5, 1); printlist(L4); //交换 list<int>L; L.push_back(6); L.push_back(7); L.push_back(8); L.push_back(9); L.push_back(10); cout << "交换前" << endl; printlist(L1); printlist(L); L1.swap(L); cout << "交换后" << endl; printlist(L1); printlist(L); } int main() { text(); }
● list大小操作
函数原型：
■size() //返回容器中元素的个数
■empty() //判断容器是否为空
■resize(num) //重新指定容器的长度为num，若容器变长，则以默认值填充新位置
//如果容器变短，则末尾超出容器长度的元素被删除
■resize(num, elem) //重新指定容器的长度为num，若容器变长，则以elem值填充新位置
//如果容器变短，则末尾超出容器长度的元素被删除
#include<iostream> #include<list> using namespace std; void printlist(list<int>&L) { for (list<int>::iterator i = L.begin(); i != L.end(); i++) { cout << *i << " "; } cout << endl; } void issize(list<int>&L) { cout << "L1元素个数为：" <<L.size()<< endl; } void isempty(list<int>&L) { if (L.empty()) { cout << "L1为空" << endl; } else { cout << "L1不为空" << endl; issize(L); } } void text() { list<int>L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_back(4); L.push_back(5); isempty(L); //重新指定大小 L.resize(10); printlist(L); L.resize(4); printlist(L); } int main() { text(); }
●list插入和删除
函数原型：
■push_back(elem) //在容器尾部加入一个元素
■pop_back() //删除容器中最后一个元素
■push_front(elem) //在容器开头插入一个元素
■pop_front() //从容器开头移除第一个元素
■insert(pos,elem) //在pos位置插elem元素的拷贝，返回新数据的位置
■insert(pos,n,elem) //在pos位置插入n个elem数据，无返回值
■insert(pos,beg,end) //在pos位置插入[beg,end)区间的数据，无返回值
■clear() //移除容器的所有数据
■erase(beg,end) //删除[beg,end)区间的数据，返回下一个数据的位置
■erase(pos) //删除pos位置的数据，返回下一个数据的位置
■remove(elem) //删除容器中所有与elem值匹配的元素
#include<iostream> #include<list> using namespace std; void printlist(list<int>&L) { for (list<int>::iterator i = L.begin(); i != L.end(); i++) { cout << *i << " "; } cout << endl; } void text() { list<int>L; //头插 L.push_front(1); L.push_front(2); L.push_front(3); L.push_front(4); L.push_front(5); //5 4 3 2 1 //尾插 L.push_back(6); L.push_back(7); L.push_back(8); L.push_back(9); L.push_back(10); //5 4 3 2 1 6 7 8 9 10 printlist(L); //头删 L.pop_front(); //4 3 2 1 6 7 8 9 10 //尾删 L.pop_back(); //4 3 2 1 6 7 8 9 printlist(L); //insert插入 L.insert(L.begin(), 0); L.insert(L.end(), 0); //0 4 3 2 1 6 7 8 9 0 printlist(L); list<int>::iterator i = L.begin(); //迭代器 L.insert(++i, 10); // 0 10 4 3 2 1 6 7 8 9 0 printlist(L); //删除 i = L.begin(); ++i; L.erase(i); //0 4 3 2 1 6 7 8 9 0 printlist(L); //移除 L.remove(0); // 4 3 2 1 6 7 8 9 printlist(L); //清空 L.clear(); printlist(L); } int main() { text(); }
●list数据存取
函数原型：
■front() //返回第一个元素
■back() //返回最后一个元素
#include<iostream> #include<list> using namespace std; void text() { list<int>L; for (int i = 1; i <= 10; i++) { L.push_back(i); } cout << "第一个元素：" << L.front() << endl; cout << "最后一个元素：" << L.back() << endl; } int main() { text(); }
●list反转和排序
函数原型：
■reverse() //反转链表
■sort() //链表排序，list为不支持随机访问迭代器的容器，不可以用标准算法，内部将会提供算法
#include<iostream> #include<list> #include<algorithm> using namespace std; void printlist(list<int>&L) { for (list<int>::iterator i = L.begin(); i != L.end(); i++) { cout << *i << " "; } cout << endl; } void text1() { list<int>L; for (int i = 1; i <= 10; i++) { L.push_back(i); } cout << "反转前：" << endl; printlist(L); cout << "反转后：" << endl; L.reverse(); printlist(L); } bool compare(int L1,int L2) { return L1 > L2; } void text2() { list<int>L; L.push_back(54); L.push_back(23); L.push_back(59); L.push_back(321); L.push_back(34); L.push_back(9); L.push_back(76); L.push_back(87); L.push_back(51); L.push_back(65); cout << "排序前：" << endl; printlist(L); cout << "排序后：" << endl; L.sort(); //默认升序 printlist(L); L.sort(compare); //降序操作 printlist(L); } int main() { text1(); text2(); }
