如何实现4.1 C STL中的动态链表容器功能？

本文共计4048个文字，预计阅读时间需要17分钟。

List和SList都是C++ STL中的容器，都基于双向链表实现，可以存储可重复元素。其中，List内部的节点结构包含两个指针，一个指向前一个节点，一个指向下一个节点，而SList只有一个指向前一个节点的指针。

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; }

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