面向对象程序设计之链表 list 的简析(C++)

2024-09-02 23:36
文章标签 c++ 链表 list 程序设计 面向对象 简析

本文主要是介绍面向对象程序设计之链表 list 的简析(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简介：链表是一个双向的结构，与string与vector不同的是他不支持[]访问，因为链表是由一个节点一个节点连接而成的，并不连续。我们可以在常数量级内对于链表进行插入与删除数据

1.构造函数

我们在cplusplus.com中可以查到链表总共有四种构造的方式：1.无参构造(默认构造)；2.使用n个val构造；3.迭代器区间构造；4.拷贝构造

接下来让我们简单创建一个链表并对其进行遍历 

//n个val构造
list<int> lt(5, 1);
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

2.迭代器的简要了解

2.1按照功能分类

iterator：迭代器

reverse_iterator：反向迭代器

const iterator：只读迭代器

const reverse_iterator：只读反向迭代器

2.2按照性质分类 

单向迭代器：forward_list/unordered_map/unorder_set......只支持 ++ 操作

双向迭代器：list/map/set........支持 ++ 、-- 操作

随机迭代器：string/vector/deque.........支持 ++ 、-- 、+ 、-  操作

还有两种迭代器可以作为了解，他们就是只读与只写迭代器，根据箭头各种迭代器之间可以近似理解为包含关系，即若一个函数参数要求单项迭代器，那么双向迭代器的参数同样可以，但是反之则不可以

 比如如果我们使用不匹配的迭代器就有可能出错，例如库函数中的sort要求随机迭代器，因为其底层函数需要进行 - 的操作，如果是双向迭代器就无法进行该操作，就会报错 

list<int> lt(5, 1);
sort(lt.begin(), lt.end());//错误,库函数中的sort要求使用随机迭代器类型

 

3.常用接口以及注意事项 

3.1push_back

尾插函数，注意push_back只能插入单个数据，无法直接插入(1,1)这样类型的函数

//n个val构造
list<int> lt(5, 1);lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

3.2emplace_back

尾插函数，与push_back不同的是，emplace_back可以直接插入(2,2)这样的数据

struct A
{
public:A(int a1 = 1,int a2 = 1):_a1(a1),_a2(a2){}int _a1;int _a2;};list<A> lt;
A aa1(1, 1);
lt.push_back(aa1);
lt.push_back(A(2, 2));//匿名对象
//lt.push_back(2, 2);//报错lt.emplace_back(aa1);
lt.emplace_back(A(2, 2));
lt.emplace_back(2, 2);//可以直接尾插//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

 3.3insert

在指定位置之前插入数据，可以使用循环实现在任意位置插入数据

list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);lt.insert(lt.begin(), 10);//在首位前插入数据//在第k个位置之前插入数据
auto it = lt.begin();
int k = 3;
while (k--)
{it++;
}
lt.insert(it, 30);//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

3.4erase 

删除指定位置数据

list<int> lt(5, 1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);int x = 0;cin >> x;auto it = find(lt.begin(), lt.end(), x);//如果find没有找到就会返回第二个参数也就是lt.end()while (it != lt.end()){lt.erase(it);}//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

3.5reverse 

逆置链表

list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);lt.reverse();//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

 3.6sort

库函数中的sort函数不支持链表，所以链表自实现了一个sort函数来进行排序，默认是升序，可以使用仿函数来进行降序的调整即lt.sort(greater<int>())与lt.sort(less<int>())

list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);lt.sort();//迭代器遍历
list<int>::iterator it = lt.begin();
while (it != lt.end())
{cout << *it << " ";++it;
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

3.7merge

将两个有序链表进行合并，如果将second链表合并到first链表，则second链表就会置空，其合并的原理就是取小尾插到被合并链表

list<int> first;
first.push_back(1);
first.push_back(2);
first.push_back(3);
first.push_back(4);list<int> second;
second.push_back(10);
second.push_back(20);
second.push_back(30);
second.push_back(40);first.merge(second);
//范围for遍历
for (auto e : first)
{cout << e << " ";
}
cout << endl;
//范围for遍历
for (auto e : second)
{cout << e << " ";
}
cout << endl;

3.8unique

去重，注意只能对有序数据去重 

list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;lt.unique();//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

3.9splice

剪切另一链表的指定数据到被粘贴链表，被剪切链表中被剪切的数据会直接删除，也可以对自身进行操作，即变化自身链表数据的顺序

list<int> first;
first.push_back(1);
first.push_back(2);
first.push_back(3);
first.push_back(4);list<int> second;
second.push_back(10);
second.push_back(20);
second.push_back(30);
second.push_back(40);auto it = first.begin();
it++;first.splice(it, second);//在First链表的第一个位置之后粘贴剪切后的数据
//范围for遍历
for (auto e : first)
{cout << e << " ";
}
cout << endl;
//范围for遍历
for (auto e : second)
{cout << e << " ";
}
cout << endl;list<int> lt(5, 1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;int k = 0;
cin >> k;
auto it = find(lt.begin(), lt.end(), k);
if(it != lt.end())
{lt.splice(lt.begin(), lt, it);
}
cout << endl;
//范围for遍历
for (auto e : lt)
{cout << e << " ";
}
cout << endl;

 

 

这篇关于面向对象程序设计之链表 list 的简析(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1131389。

相关文章

C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...
C# 比较两个list 之间元素差异的常用方法

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》：本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2