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

2024-09-02 23:36

本文主要是介绍面向对象程序设计之链表 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++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.