目录

list

list头文件

1. list定义和初始化

2. list的元素赋值和交换

3. list的大小操作

4. list的元素插入和删除操作

5. list的数据存取

6. list的数据反转排序

7.list合并两个链表

        你们是否使用过链表去存储和操作数据，在数据结构中，链表分好几种，像单链表、双链表、循环链表等等。在这一章节中，我们就来了解一下C++的STL提供给我们用的list容器，他的底层实现是双向链表。

        数据结构如下图所示：

        采用双向链表来实现容器list，它在物理存储单元上是非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由上面的图可以看到一个结点由三部分组成，分别是数据域和两个指针域。链表结构的优点有：

（1）这种结构采用了动态存储分配，不会造成空间的浪费和溢出问题；

（2）链表在删除和插入元素的时间复杂度非常喜人，修改指针就好了；

list

list头文件

# include

1. list定义和初始化

// list lstT;//list采用采用模板类实现,对象的默认构造形式：// list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。// list(n,val);//构造函数将n个val拷贝给本身。// list(const list &lst);//拷贝构造函数。int arrays[7] = {1,2,3,4,5,6,7};list serven_1;   // 默认构造函数list serven_2(serven_1);// 拷贝构造函数list serven_3(arrays, arrays+sizeof(arrays)/sizeof(int));  // 构造函数将arrays数组拷贝给serven_3list serven_4(serven_3.begin(), serven_3.end());    // 构造函数将[begin,end)区间中的元素拷贝给serven_4list serven_5(5,2);     // 定义一个5个2的链表

2. list的元素赋值和交换

• assign(begin, end)：将区间[begin, end)中的元素赋值给链表；

• assign(n, val)：将重复n个val数值赋值给链表；

• operator=：重载operator=，用户赋值给链表；

• swap()：交换两个链表。

// assign(begin, end);//将[beg, end)区间中的数据拷贝赋值给本身。// assign(n, val);//将n个elem拷贝赋值给本身。// list& operator=(const list &lst);//重载等号操作符//swap(lst);//将lst与本身的元素互换。/* list 数据元素的赋值和交换 */list serven_6(arrays, arrays+sizeof(arrays)/sizeof(int));list serven_7, serven_8, serven_9; // 通过重载operator进行赋值serven_7 = serven_6;cout<<"serven_7列表的数据为：";iterator_list(serven_7);cout<<endl;// 通过[begin,end)区间中的数据拷贝赋值serven_8.assign(serven_6.begin(), serven_6.end());cout<<"serven_8列表的数据为：";iterator_list(serven_8);cout<<endl; // 赋值5个2的链表serven_9.assign(5,2);cout<<"serven_9列表的数据为：";iterator_list(serven_9);cout<<endl;// 交换serven-8和serven_9的值serven_8.swap(serven_9);cout<<"交换后serven_8列表的数据为：";iterator_list(serven_8);cout<<"交换后serven_9列表的数据为：";iterator_list(serven_9);cout<<endl;

运行结果：

3. list的大小操作

• size()：返回容器中的元素个数；

• empty()：判断容器是否为空；

• resize(n)：重新指定容器的长度为n，若容器变长，则以默认值0填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

• resize(n,val)：重新指定容器的长度为n，若容器变长，则以val值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

// size();//返回容器中元素的个数// empty();//判断容器是否为空// resize(n);//重新指定容器的长度为n，// resize(n, val);//重新指定容器的长度为n，/* list 的大小操作*/cout<<"serven_9列表的数据为：";iterator_list(serven_9);cout<<"serven_9的大小为："<<serven_9.size()<<endl<<endl;//判断列表serven_9是否为空cout<<"serven_9是否为空："<<serven_9.empty()<<endl<<endl;//resize(num)重新指定容器的大小长度为numserven_9.resize(5);cout<<"指定后serven_9的元素为：";iterator_list(serven_9);cout<<"指定后serven_9的长度为："<<serven_9.size()<<endl<<endl;//resize(num,val)重新指定容器的大小长度为num,用val填充多余的位置serven_9.resize(8,0);cout<<"指定后serven_9的元素为：";iterator_list(serven_9);cout<<"指定后serven_9的长度为："<<serven_9.size()<<endl<<endl;

运行结果：

4. list的元素插入和删除操作

• push_back(val)：在容器的结尾添加元素val；

• push_front(val)：在容器的头部插入元素val;

• pop_back()：去掉容器的结尾元素；

• pop_front()：去掉容器的开头元素；

• insert(pos, val)：在pos位置插入元素val；

• insert(pos, n, val)：在pos位置插入n个值为val；

• insert(pos, begin, end)：在pos位置插入区间[begin,end)的数值；

• erase(begin, end)：擦除区间[begin, end)中的数据；

• erase(pos)：擦除位置pos的数据；

• remove(val)：移除链表中所有等于val的数值；

• clear()：清空整个链表。

注意：insert，erase，clear，remove都会让原本的迭代器的指向失效

// push_back(val);//在容器尾部加入一个元素// pop_back();//删除容器中最后一个元素// push_front(val);//在容器开头插入一个元素// pop_front();//从容器开头移除第一个元素// insert(pos,val);//在pos位置插elem元素的拷贝，返回新数据的位置。// insert(pos,n,val);//在pos位置插入n个val数据，无返回值。// insert(pos,begin,end);//在pos位置插入[begin,end)区间的数据，无返回值。// clear();//移除容器的所有数据// erase(begin,end);//删除[begin,end)区间的数据，返回下一个数据的位置。// erase(pos);//删除pos位置的数据，返回下一个数据的位置。// remove(val);//删除容器中所有与elem值匹配的元素。/* list的元素插入和删除操作 */cout<<"serven_6列表的数据为：";iterator_list(serven_6);serven_6.push_back(3);   // 在容器的尾部插入元素3serven_6.push_front(3);  // 在容器的头部插入元素3cout<<"在头尾加上3元素后serven_6的元素为：";iterator_list(serven_6);serven_6.pop_back();     // 去掉尾部的元素serven_6.pop_front();    // 去掉头部的元素cout<<"在头尾去掉元素后serven_6的元素为：";iterator_list(serven_6);cout<<endl;// 假设要在列表serven_6的第二个位置插入元素9//serven_6.insert(serven_6.begin()+2,9); // 这种方法是不正确的，因为列表的元素存储数据结构是链表的方式，所以不支持随机获取元素，只能++，--，+1，-1//所以在第二个位置插入元素的步骤为：int i=0;list::iterator it = serven_6.begin();while(i<2){ it++; i++; }serven_6.insert(it,9);  // 调用insert插入元素后，迭代器会失效，迭代器的指向失灵了cout<<"在第三个位置插入元素9后serven_6的元素为：";iterator_list(serven_6);it = serven_6.begin(); i=0;while(i<2){ it++; i++; }serven_6.insert(it,3,8);cout<<"在第三个位置之后插入三个元素8后serven_6的元素为：";  iterator_list(serven_6);it = serven_6.begin(); i=0;while(i<2){ it++; i++; }serven_6.insert(it,arrays,arrays+3);     // 插入数组的前三个元素[arrays,arrays+3)cout<<"在第三个位置插入数组的前三个元素8后serven_6的元素为：";iterator_list(serven_6);// 删除第二个位置的数据it = serven_6.begin(); i=0;while(i<2){ it++; i++; }serven_6.erase(it);cout<<"擦除第三个元素后serven_6的元素为：";iterator_list(serven_6);serven_6.erase(++serven_6.begin(), ----serven_6.end());// 删除[begin++,end----)区间的元素cout<<"擦除第三个元素到末尾第三个元素区间元素后serven_6的元素为：";iterator_list(serven_6);serven_6.push_front(6);serven_6.push_back(6);cout<<"serven_6的元素为：";iterator_list(serven_6);serven_6.remove(6);  // 删除所有等于3的元素，remove后会导致迭代器失效cout<<"移除列表中所有等于3的元素后serven_6的元素为：";iterator_list(serven_6);cout<<endl;

运行结果：

5. list的数据存取

• front()：获取链表的头结点；

• back()：获取链表的尾结点。

// front();//返回第一个元素。// back();//返回最后一个元素。/* list的数据存取 */cout<<"serven_7列表的数据为：";iterator_list(serven_7);cout<<"serven_7的表头元素为："<<serven_7.front()<<endl;cout<<"serven_7的表尾元素为："<<serven_7.back()<<endl;

运行结果：

6. list的数据反转排序

• reverse()：链表反转；

• sort()：排序。

/* list反转列表排序 */cout<<"serven_7列表的数据为：";iterator_list(serven_7);serven_7.reverse();cout<<"serven_7列表反转后的数据为：";iterator_list(serven_7);serven_7.sort();cout<<"serven_7列表排序后的数据为：";serven_7.sort();

运行结果：

7.list合并两个链表

• merge()： 合并两个有序链表，前提是两个链表都是有序的，合并后的链表才是有序的，并且合并后的元素是不会去重的，假如链表serven_1中有个元素4，serven_2中个元素4，那么合并后的链表就有两个元素4。

/* list合并两个链表 */list serven_1, serven_2;int arrays_1[3] = {1,3,8};int arrays_2[3] = {1,2,5};serven_1.assign(arrays_1, arrays_1 + sizeof(arrays_1)/sizeof(int));serven_2.assign(arrays_2, arrays_2 + sizeof(arrays_2)/sizeof(int));//cout<<"还未合并前的两个链表：";cout<<"before:";iterator_list(serven_1);iterator_list(serven_2);// 合并两个链表list::iterator it_1 = serven_1.begin();list::iterator it_2 = serven_2.begin();serven_1.merge(serven_2); // 将两个链表合并，并且进行排序，且不会去掉重复的元素//cout<<"还未合并后的两个链表：";cout<<"after:";iterator_list(serven_1);// 迭代器打印有数值存在，那就说明了合并后的链表不会改变内存的存储位置，只是改变了链表的指向问题，// 而且链表serven_2会变为空，所以serven_2的指针会失效cout<<"打印链表serven_1的迭代器开始指向的地方："<<*it_1<<endl;

运行结果：

注意：

• assign()，resize()，erase()和remove()方法可能会对iterator造成影响，其他方法均不改变iterator原本指向的空间。

• 与容器 array、vector、deque 的迭代器不同的是，list 容器迭代器配备的迭代器类型为双向迭代器，而不再是随机访问迭代器。
  这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1--、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：

            (1) p1[i]：不能通过下标访问 list 容器中指定位置处的元素。

            (2) p1-=i、 p1+=i、 p1+i 、p1-i：双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。

            (3) p1<p2、 p1>p2、 p1=p2：双向迭代器 p1、p2 不支持使用 、 = 比较运算符。

欢迎关注微信公众号 “三贝勒文子”，每天学习C++

毕业设计范文站