首页 > 编程语言 >4.1 C++ STL 动态链表容器

4.1 C++ STL 动态链表容器

时间：2023-08-16 09:39:36浏览次数：52  
标签：4.1 STL age 元素 list 链表 int MyList

List和SList都是C++ STL中的容器，都是基于双向链表实现的，可以存储可重复元素的特点。其中，List内部的节点结构包含两个指针一个指向前一个节点，一个指向后一个节点，而SList只有一个指针指向后一个节点，因此相对来说更节省存储空间，但不支持反向遍历，同时也没有List的排序功能。

双向链表的数据元素可以通过链表指针串接成逻辑意义上的线性表，不同于采用线性表顺序存储结构的Vector和Deque容器，双向链表中任一位置的元素，查找，插入和删除，都具有高效的常数阶算法时间复杂度O(1).

List的缺点是无法通过位置来直接访问序列中的元素，也就是说，不能动态跨段索引元素.为了访问 list 内部的一个元素，必须一个一个地遍历元素，通常从第一个元素或最后一个元素开始遍历。

4.1 双向链表遍历整数

这段代码展示了如何通过访问链表节点的指针来遍历链表中的所有元素。

在代码中，首先创建了一个空链表MyList。然后，使用for循环向链表中插入10个整数数据，每个数据使用push_back()函数插入链表的末尾。

接着，代码定义了一个双向链表节点指针node，将其初始化为第一个节点的下一个节点。注意，第一个节点是链表头，没有实际数据值，因此我们需要将node指针指向第二个节点开始。

然后，代码使用for循环和node指针遍历链表中的所有元素，输出每个节点的数据值。每次输出完一个节点，将node指向下一个节点，判断node是否已经回到了链表头的位置，如果是，则将其指向链表头的第二个节点，即能够实现循环遍历整个链表。

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
  list<int> MyList;
  // 生成10个测试数据,并链入链表中.
  for (int x = 0; x < 10; x++)
    MyList.push_back(x);

  // 将node节点初始化为第一个节点的下一个节点,第一个节点是链表头,无数据.
  list<int>::_Nodeptr node = MyList._Myhead->_Next;

  for (int x = 0; x < MyList._Mysize; x++)
  {
    cout << "Node: " << node->_Myval << endl;
    node = node->_Next;         // 每次输出,将node指向下一个链表
    if (node == MyList._Myhead) // 如果到头了,直接指向头结点的第二个节点
    {
      node = node->_Next;     // 由于是双向链表,所以到头了会回到起始位置
    }                               // 此时我们执行 node->_Next 继续指向开头
  }
  system("pause");
  return 0;
}

4.2 双向链表遍历结构体

这段代码展示了如何定义结构体、采用自定义的比较函数进行排序，并遍历链表中的所有元素。

在代码中，首先定义了一个结构体Student，包含三个成员变量：name、age和city。然后，创建了一个Student类型的数组stu，数组中有4个元素，每个元素包含一个name、age和city。

接着，代码定义了一个空链表MyList，使用push_back()函数把stu数组中的元素按顺序插入链表中。然后还定义了一个MyCompare函数，参数为两个Student类型的引用，返回值为bool类型。MyCompare函数实现了从大到小排序的方法，当s1.age大于s2.age时返回true，否则返回false。

通过调用链表的sort()函数，并传入MyCompare函数来对链表进行排序。在本例中，sort()函数按照从大到小的方式对链表中的元素进行排序。

最后，代码使用for循环和迭代器遍历链表中的所有元素，依次输出每个元素的name、age和city属性。

#include <iostream>
#include <list>

using namespace std;

struct Student{
  char * name;
  int age;
  char * city;
};

bool MyCompare(Student &s1, Student &s2)
{   // 实现从大到小排序
  if (s1.age > s2.age)
    return true;
  return false;
}

int main(int argc, char* argv[])
{
  Student stu[] = {
    { "admin", 22, "beijing" },
    { "lisi", 32, "shanghai" },
    { "wangwu", 26, "shandong" },
    {"wangermazi",8,"jinan"}
  };

  list<Student> MyList;
  MyList.push_back(stu[0]);  // 装入链表数据
  MyList.push_back(stu[1]);
  MyList.push_back(stu[2]);
  MyList.push_back(stu[3]);

  // 根据Student结构中的age从大到小排序
  MyList.sort(MyCompare);

  // 遍历链表
  list<Student>::iterator start, end;
  for (start = MyList.begin(); start != MyList.end(); start++)
  {
    cout << (*start).name << " ";
    cout << (*start).age << " ";
    cout << (*start).city << endl;
  }
  system("pause");
  return 0;
}

4.3 实现正反向遍历链表

这段代码展示了如何正向和反向遍历链表，其中使用了list容器的begin()、end()、rbegin()和rend()函数。

在代码中，首先创建了一个list<int>类型的链表MyList，并使用花括号列表初始化的方式插入了9个整数元素。

然后，采用for循环和迭代器的方式来正向遍历链表MyList中的所有元素，将每个元素依次打印到控制台上。

最后，采用for循环和反向迭代器的方式来反向遍历链表MyList中的所有元素，将每个元素依次反向打印到控制台上。

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
  list<int> MyList{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  // 正向打印链表元素
  for (list<int>::iterator item = MyList.begin(); item != MyList.end(); item++)
    cout << *item << endl;
  // 反向打印链表元素
  for (list<int>::reverse_iterator item = MyList.rbegin(); item != MyList.rend(); item++)
    cout << *item << endl;
  system("pause");
  return 0;
}

4.4 遍历链表中指定元素

这段代码展示了如何定义结构体、构造链表并遍历链表中指定元素的属性。

在代码中，定义了一个Student结构体，有两个成员变量，分别是id和name。然后，定义了一个列表MyList，存放Student类型的数据。

接下来，代码定义了一个包含4个元素的Student数组stu，每个元素包含一个id和一个name。然后，使用for循环把stu数组中的元素按照顺序插入链表MyList中。在插入时，每个结构体通过push_back()函数被加入到链表的末尾。

代码使用迭代器遍历MyList链表中的所有元素，查找其中ID为3的元素。如果找到了ID为3的元素，则使用cout语句输出该元素的name属性，否则什么也不做。

#include <iostream>
#include <list>
#include <string>

using namespace std;

struct Student{
  int id;
  string name;
};

int main(int argc, char* argv[])
{
  list<Student> MyList;
  // 定义列表中的元素集合
  Student stu[] = {
    { 1,"aaddm"},
    { 2,"admin"},
    { 3,"waann" },
    { 4,"ruiii" }
  };

  for (int x = 0; x < 4; x++)
  { // 循环插入测试结构 stu[0] - stu[4]
    MyList.push_back(stu[x]);
  }

  // 遍历链表中ID=3的元素
  list<Student>::iterator start, end;
  for (start = MyList.begin(); start != MyList.end(); start++)
  {
    if ((*start).id == 3) // 寻找ID是3的结构体,找到后输出其name属性
    {
      cout << "UName: " << (*start).name << endl;
    }
  }
  system("pause");
  return 0;
}

4.5 插入/删除链表元素

这段代码展示了如何插入、删除和移除链表中的元素。在代码中，首先创建了一个list<int>类型的链表MyList，并使用大括号列表初始化的方式插入了9个整数元素。

然后，代码连续调用了链表的成员函数push_back()、push_front()来向链表的尾部和头部插入一个10和0，使用pop_front()、pop_back()来从链表的头部和尾部删除元素。

接着，代码通过调用链表的成员函数insert()，从开头或结尾插入元素，参数为位置迭代器和要插入的数据值。并使用remove()函数移除链表中的元素(这里是7), remove()函数的参数为需要移除的数据。

最后，代码调用了自定义的MyPrint函数打印了修改后的链表元素。

#include <iostream>
#include <list>

using namespace std;

void MyPrint(list<int> &MyList)
{
  list<int>::iterator start, end;
  for (start = MyList.begin(); start != MyList.end(); start++)
    cout << *start << " ";
  cout << endl;
}

int main(int argc, char* argv[])
{
  list<int> MyList{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  MyList.push_back(10);  // 尾部插入数据
  MyList.push_front(0);  // 头部插入数据

  MyList.pop_front();    // 头删数据
  MyList.pop_back();     // 尾删除数据

  MyList.insert(MyList.begin(), 500); // 从开头插入500
  MyList.insert(MyList.end(), 1000);  // 从结尾插入1000

  MyList.remove(7);    // 移除7这个元素
  MyPrint(MyList);
  system("pause");
  return 0;
}

4.6 整数链表正反向排序

这段代码展示了如何对链表进行翻转以及排序，并使用自定义的回调函数来指定排序规则。

在代码中，首先创建了一个list<int>类型的链表MyList，并使用花括号列表初始化的方式插入了10个整数元素。

然后，代码调用了链表的成员函数reverse()来翻转链表。reverse()函数会将链表中的元素顺序全部翻转过来。

接着，代码又调用了链表的成员函数sort()来进行排序。在本例中，使用默认的从小到大排序方式，由sort()函数自动完成。

最后，代码定义了一个MyCompare回调函数，指定了从大到小排序的规则。MyCompare()函数返回值是bool类型，定义了两个参数value1和value2，分别表示需要比较的两个数。在本例中，如果value1大于value2，则MyCompare()函数返回true，否则返回false。

代码再次调用了链表的成员函数sort()，这次传入了MyCompare()回调函数作为参数，表示按照从大到小的方式对链表进行排序。

#include <iostream>
#include <list>

using namespace std;

void MyPrint(list<int> &MyList)
{
  list<int>::iterator start, end;
  for (start = MyList.begin(); start != MyList.end(); start++)
    cout << *start << " ";
  cout << endl;
}

// 实现的从大到小排序的回调函数
bool MyCompare(int value1, int value2) { return value1 > value2; }

int main(int argc, char* argv[])
{
  list<int> MyList{ 12,56,33,78,9,43,2,1,7,89 };

  MyList.reverse();        // 对链表进行翻转
  MyPrint(MyList);

  MyList.sort();           // 从小到大排序
  MyPrint(MyList);

  MyList.sort(MyCompare);  // 从大到小排序
  MyPrint(MyList);

  system("pause");
  return 0;
}

4.7 类链表正反向排序

这段C++代码定义了一个Person类，展示了如何对list容器的元素进行排序。

在代码中，Person类定义了三个成员变量，代表人名、年龄和身高。在构造函数中，给这三个成员变量进行了初始化。并创建了一个空的list<Person>类型的MyList变量，使用push_back()函数向其中添加了三个Person类型的数据p1、p2和p3。

接下来，代码实现了一个MyCompare函数，作为list容器的排序规则。在本例中，MyCompare函数根据年龄和身高进行排序，如果年龄相同，则按照身高由低到高排列，如果年龄不同，则按照年龄由高到低排列。这里的排序规则是根据具体数据类型而定的。

最后使用sort()函数对MyList变量中的元素进行排序，按照自定义的规则对元素排序。并使用迭代器遍历MyList变量，输出其成员的相关信息，以便查看是否已成功对元素进行排序。

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Person
{
public:
  string m_name;
  int m_age;
  int m_height;

public: Person(string name, int age, int height){
    this->m_name = name;
    this->m_age = age;
    this->m_height = height;
  }
};
// 排序规则为: 如果年龄相同,则按照身高由低到高排列
bool MyCompare(Person &x,Person &y)
{
  if (x.m_age == y.m_age)
    return x.m_height < y.m_height; // 身高升序排列
  else
    return x.m_age > y.m_age;       // 年龄降序排列
}

int main(int argc, char* argv[])
{
  list<Person> MyList;

  Person p1("a", 20, 169);  // 定义元素数据
  Person p2("b", 14, 155);
  Person p3("c", 14, 165);

  MyList.push_back(p1);     // 加到链表里
  MyList.push_back(p2);
  MyList.push_back(p3);

  MyList.sort(MyCompare);  // 排序代码

  // 排序后进行打印
  for (list<Person>::iterator it = MyList.begin(); it != MyList.end(); it++)
    cout << "Name: " << it->m_name << " Age: " << it->m_age << " Height: " << it->m_height << endl;
  system("pause");
  return 0;
}

4.8 类链表成员的删除

这段C++代码展示了list容器的一些基本操作，包括添加元素、删除元素、使用迭代器遍历链表以及运算符重载等。

在代码中，Person类定义了三个成员变量，代表人名、年龄和身高。在构造函数中，为这三个成员变量进行了初始化。代码创建了一个空的list<Person>类型的MyList变量，并使用push_back()函数向其中添加了三个Person类型的数据p1、p2和p3。

代码使用remove()函数从链表中删除了p3这个Person类型的数据。由于Person类中没有提供运算符的重载，我们需要手动重载运算符，以便remove()函数能够正确地删除链表中自定义的Person类型的结构。在本例中，代码重载了==运算符，使得在删除p3时，remove()函数只删除那些成员m_name、m_age和m_height都等于p3的节点。

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Person
{
public:
  string m_name;
  int m_age;
  int m_height;

public: Person(string name, int age, int height){
    this->m_name = name;
    this->m_age = age;
    this->m_height = height;
}
// 重载等于号 == 让 remove() 函数,可以删除自定义的Person类型的结构
public: bool operator==(const Person &p) {
    if (this->m_name == p.m_name && this->m_age == p.m_age && this->m_height == p.m_height)
      return true;
    return false;
  }
};

int main(int argc, char* argv[])
{
  list<Person> MyList;

  Person p1("a", 20, 169);
  Person p2("b", 14, 155);
  Person p3("c", 34, 165); // 初始化并给Person赋值

  MyList.push_back(p1);    // 将参数放入链表中
  MyList.push_back(p2);
  MyList.push_back(p3);

  MyList.remove(p3);   // 删除这个类中的p3成员

  // 删除p3数据后,通过使用迭代器遍历这个链表,查看情况.
  for (list<Person>::iterator it = MyList.begin(); it != MyList.end(); it++)
    cout << "Name: " << it->m_name << " Age: " << it->m_age << " Height: " << it->m_height << endl;
  system("pause");
  return 0;
}

本文作者： 王瑞
本文链接： https://www.lyshark.com/post/5752ce3e.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

标签：4.1,STL,age,元素,list,链表,int,MyList
From： https://www.cnblogs.com/LyShark/p/17633044.html

相关文章

  • 5.1 C++ STL 集合数据容器
    Set/Multiset集合使用的是红黑树的平衡二叉检索树的数据结构，来组织泛化的元素数据，通常来说红黑树根节点每次只能衍生出两个子节点，左面的节点是小于根节点的数据集合，右面的节点是大于根节点的集合，通过这样的方式将数据组织成一颗看似像树一样的结构，而平衡一词的含义则是两边的子节......
  • 1.1 C++ STL 字符串构造函数
    String字符串操作容器是C++标准中实现的重要容器,其主要用于对字符串的高效处理,它和C风格中的string.h并不是同一个库,两个库有极大的差距,C库中的string.h主要面向过程提供一些处理函数,而C++库中的string则是基于类实现的更高效的一种字符串处理方法集,类中提供了非常方便的成......
  • 2.1 C++ STL 数组向量容器
    Vector容器是C++STL中的一个动态数组容器，可以在运行时动态地增加或减少其大小，存储相同数据类型的元素，提供了快速的随机访问和在末尾插入或删除元素的功能。该容器可以方便、灵活地代替数组，容器可以实现动态对数组扩容删除等各种复杂操作，其时间复杂度O(l)常数阶，其他元素的插入和......
  • 3.1 C++ STL 双向队列容器
    双向队列容器（Deque）是C++STL中的一种数据结构，是一种双端队列，允许在容器的两端进行快速插入和删除操作，可以看作是一种动态数组的扩展，支持随机访问，同时提供了高效的在队列头尾插入和删除元素的操作。Deque双向队列容器与Vector非常相似，它不但可以在数组尾部插入和删除元素，还可以在......
  • LeetCode -- 19. 删除链表的倒数第 N 个结点
     一般的删除问题，可以直接删除（找符合条件的，找到了直接删掉），延迟删除（打标记，找完了再删除），栈，双指针 在链表中删除一个节点，要找到其前面一个节点cur,然后cur->next=cur->next->next即可 方法一：直接删除我们先算出链表长度len，要删除倒第n个节点就是删除第len-n......
  • C++ STL iota 使用方法
    C++STLiota用法介绍c++11引入的函数，C++20后小更新使用#include<numeric>头文件引用功能std::iota[aɪ'otə]输入一个值和一个容器的开始地址和结束地址，对该容器进行自增填充。Example点击查看代码#include<numeric>#include<vector>usingnamespacestd;intma......
  • 在AndroidStudio4.1.1上使用GreenDao
    一、概述项目中需要用到数据库的能力，对比以及根据以往的经验，决定使用GreenDao。二、实际操作步骤第一步：在项目下的.gradle文件中加入插件：classpath'org.greenrobot:greendao-gradle-plugin:3.3.0'//addplugin 第二步：在module目录下的.gradle文件夹中进行操......
  • 【C++STL基础入门】string类的基础使用
    @TOC前言本系列文章使用VS2022，C++20版本STL（StandardTemplateLibrary）是C++的一个强大工具集，其中的string类是STL中一个常用的容器。本文将介绍string类的基本使用方法。一、STL使用概述在STL中，我们的每一个容器/string字符串等都是使用面向对象技术来实现的，我们只需要调用里面的函......
  • 7.2 C/C++ 实现动态链表
    动态链表是一种常用的动态数据结构，可以在运行时动态地申请内存空间来存储数据，相比于静态数组和静态链表，更加灵活和高效。在动态链表中，数据元素被组织成一条链表，每个元素包含了指向下一个元素的指针，这样就可以通过指针将所有元素串联起来。使用动态链表存储数据时，不需要预先申请内......
  • 7.4 C/C++ 实现链表栈
    相对于顺序栈，链表栈的内存使用更加灵活，因为链表栈的内存空间是通过动态分配获得的，它不需要在创建时确定其大小，而是根据需要逐个分配节点。当需要压入一个新的元素时，只需要分配一个新的节点，并将其插入到链表的头部；当需要弹出栈顶元素时，只需要删除链表头部的节点，并释放其所占用的内......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99