2022年C++存储数据结构之一List .pdf

C+ 存储数据结构之一List 双向循环链表list list 是双向循环链表，每一个元素都知道前面一个元素和后面一个元素。在STL 中， list和 vector 一样， 是两个常被使用的容器。和 vector 不一样的是， list 不支持对元素的任意存取。 list 中提供的成员函数与vector 类似，不过list 提供对表首元素的操作push_front 、pop_front ，这是 vector 不具备的。和vector 另一点不同的是，list 的迭代器不会存在失效的情况，他不像vector 会保留备份空间，在超过容量额度时重新全部分配内存，导致迭代器失效； list 没有备份空间的概念，出入一个元素就申请一个元素的空间，所以它的迭代器不会失效。还是举C+之 vector 中的例子：int data6=3,5,7,9,2,4; listlidata(data, data+6); lidata.push_back(6); . list 初始化时，申请的空间大小为6，存放下了data 中的 6 个元素，当向lidata 插入第 7 个元素 “6”时， list 申请新的节点单元，插入到list 链表中，数据存放结构如图1 所示：图 1 list 的存储结构list 每次增加一个元素，不存在重新申请内存的情况，它的成本是恒定的。而vector 每当增加关键元素的时候，都需要重新申请新的更大的内存空间，会调用元素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数，存在析构成本。所以在存储复杂类型和大量元素的情况下，list 比 vector 更有优势！List是一个双向链表, 双链表既可以向前又向后链接他的元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - List 将元素按顺序储存在链表中. 与向量 (vector)相比 , 它允许快速的插入和删除，但是随机访问却比较慢。assign() 给 list 赋值back() 返回最后一个元素begin() 返回指向第一个元素的迭代器clear() 删除所有元素empty() 如果 list 是空的则返回true end() 返回末尾的迭代器erase() 删除一个元素front() 返回第一个元素get_allocator() 返回 list 的配置器insert() 插入一个元素到list 中max_size() 返回 list能容纳的最大元素数量merge() 合并两个 list pop_back() 删除最后一个元素pop_front() 删除第一个元素push_back() 在 list 的末尾添加一个元素push_front() 在 list 的头部添加一个元素rbegin() 返回指向第一个元素的逆向迭代器remove() 从 list 删除元素remove_if() 按指定条件删除元素rend() 指向 list 末尾的逆向迭代器resize() 改变 list 的大小reverse() 把 list 的元素倒转size() 返回 list 中的元素个数sort() 给 list 排序splice() 合并两个list 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - swap() 交换两个 list unique() 删除 list 中重复的元素附 List 用法实例：#include #include #include #include using namespace std; /创建一个list 容器的实例LISTINT typedef list LISTINT; /创建一个list 容器的实例LISTCHAR typedef list LISTCHAR; void main(void) /- /用 list 容器处理整型数据/- /用 LISTINT 创建一个名为listOne 的 list 对象LISTINT listOne; /声明 i 为迭代器LISTINT:iteratori; /从前面向listOne 容器中添加数据listOne.push_front (2); listOne.push_front (1); /从后面向listOne 容器中添加数据listOne.push_back (3); listOne.push_back (4); /从前向后显示listOne 中的数据coutlistOne.begin()- listOne.end():endl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - for (i = listOne.begin(); i != listOne.end(); +i) cout *i ; coutendl; /从后向后显示listOne 中的数据LISTINT:reverse_iteratorir; coutlistOne.rbegin()-listOne.rend():endl; for (ir =listOne.rbegin(); ir!=listOne.rend();ir+) cout *ir ; coutendl; /使用 STL 的 accumulate( 累加 )算法int result = accumulate(listOne.begin(), listOne.end(),0); coutSum=resultendl; cout-endl; /- /用 list 容器处理字符型数据/- /用 LISTCHAR 创建一个名为listOne 的 list 对象LISTCHAR listTwo; /声明 i 为迭代器LISTCHAR:iterator j; /从前面向listTwo 容器中添加数据listTwo.push_front (A); listTwo.push_front (B); /从后面向listTwo 容器中添加数据listTwo.push_back (x); listTwo.push_back (y); /从前向后显示listTwo 中的数据coutlistTwo.begin()-listTwo.end():endl; for (j = listTwo.begin(); j != listTwo.end(); +j) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - cout char(*j) ; coutendl; /使用 STL 的 max_element算法求 listTwo 中的最大元素并显示j=max_element(listTwo.begin(),listTwo.end(); cout The maximum element in listTwo is: char(*j)endl; #include #include using namespace std; typedef list INTLIST; /从前向后显示list 队列的全部元素void put_list(INTLIST list, char *name) INTLIST:iteratorplist; cout The contents of name : ; for(plist = list.begin(); plist != list.end(); plist+) cout *plist ; coutendl; /测试 list 容器的功能void main(void) /list1 对象初始为空INTLIST list1; /list2 对象最初有10 个值为 6 的元素INTLIST list2(10,6); /list3 对象最初有3 个值为 6 的元素INTLIST list3(list2.begin(),-list2.end(); /声明一个名为i 的双向迭代器INTLIST:iteratori; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - /从前向后显示各list 对象的元素put_list(list1,list1); put_list(list2,list2); put_list(list3,list3); /从 list1 序列后面添加两个元素list1.push_back(2); list1.push_back(4); coutlist1.push_back(2) and list1.push_back(4):endl; put_list(list1,list1); /从 list1 序列前面添加两个元素list1.push_front(5); list1.push_front(7); coutlist1.push_front(5) and list1.push_front(7):endl; put_list(list1,list1); /在 list1 序列中间插入数据list1.insert(+list1.begin(),3,9); coutlist1.insert(list1.begin()+1,3,9):endl; put_list(list1,list1); /测试引用类函数coutlist1.front()=list1.front()endl; coutlist1.back()=list1.back()endl; /从 list1 序列的前后各移去一个元素list1.pop_front(); list1.pop_back(); coutlist1.pop_front() and list1.pop_back():endl; put_list(list1,list1); /清除 list1 中的第 2 个元素list1.erase(+list1.begin(); coutlist1.erase(+list1.begin():endl; put_list(list1,list1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - /对 list2 赋值并显示list2.assign(8,1); coutlist2.assign(8,1):endl; put_list(list2,list2); /显示序列的状态信息coutlist1.max_size(): list1.max_size()endl; coutlist1.size(): list1.size()endl; coutlist1.empty(): list1.empty()endl; /list 序列容器的运算put_list(list1,list1); put_list(list3,list3); coutlist3: list3)endl; coutlist1list3: (list1list3)endl; /对 list1 容器排序list1.sort(); put_list(list1,list1); /结合处理list1.splice(+list1.begin(), list3); put_list(list1,list1); put_list(list3,list3); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -