c++ list数据结构及双链表
list的应用
要了解c++的list实现细节可以参考C++链表的C实现（查找中间节点、判断是否存在环）[1]
#include <list>
#include <list>
#include <iostream>
using namespace std;
int main()
{
list<int> mylist{1,2,3,4,5};
mylist.push_back(10);
for(auto i : mylist){
cout<<i<<endl;
}
cout<<endl;
mylist.assign(3,5);//重新初始化链表为3个5
for(auto i : mylist){
cout<<i<<endl;
}
cout<<endl;
mylist.assign(5,3);//重新初始化链表为5个3
mylist.push_front(9);
for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
cout<<*ib<<endl;
}
cout<<endl;
for(auto rb = mylist.rbegin(), re = mylist.rend();rb!=re;rb++){//倒序
cout<<*rb<<endl;
}
cout<<"第一个L:"<<mylist.front()<<endl;
cout<<"最后一个:"<<mylist.back()<<endl;
cout<<"个数："<<mylist.size()<<endl;
mylist.clear();
cout<<endl;
int a[10] {1,2,3,4,5,6,7,8,9,0};
mylist.assign(a, a+5);//拷贝数组前5个
for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
cout<<*ib<<endl;
}
cout<<endl;
for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//前插
if (*ib==3) {
mylist.insert(ib, 123);
}
if (*ib==3) {
//No matching member function for call to 'erase'
//mylist.erase(3);
mylist.erase(ib);
break;//删除链表节点，应该退出循环
}
}
for(auto ib = mylist.begin(), ie = mylist.end();ib!=ie;ib++){//正序
cout<<*ib<<endl;
}
cout<<endl;
mylist.pop_front();//删头
mylist.pop_back();//删尾
mylist.reverse();//反转
mylist.sort();//排序
}
链表归并、交换，双链表及多链表
•归并merge()
list<int> mylist1{1,2,3,4,5};
list<int> mylist2{6,7,8,9,0,10};
mylist1.merge(mylist2);
for(auto ib = mylist1.begin(), ie = mylist1.end();ib!=ie;ib++){//正序
cout<<*ib<<endl;
}//1,2,3,4,5,6,7,8,9,0,10
•交换swap()
list<int> mylist1{1,2,3,4,5};
list<int> mylist2{6,7,8,9,0,10};
mylist1.swap(mylist2);
for(auto ib = mylist1.begin(), ie = mylist1.end();ib!=ie;ib++){//正序
cout<<*ib<<endl;
}//6,7,8,9,0,10
•多链表
list<int> mylist1{11,12,33,4,5};
list<int> mylist2{6,17,8,12,9,0,10};
list<int> mylist3{6,17,8,12,9,0,10};
list<list<int>> mylist{mylist1,mylist2,mylist3};
for(auto i : mylist){
for(auto j :i){
cout<<j<<" ";
}
cout<<endl;
}
双链表管理一个类对象
类对象即使是空指针可以访问代码区函数，但是如果该函数访问局部变量，会因为没分配内存空间报错：
class MyClass{
public:
int i=0;
void show(){
// Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)
// i = 2;
messages_base();
}
};
int main(){
MyClass *myClass(nullptr);
myClass->show();//代码区共享可以访问
return 1;
}
对于类来说：类的函数共享，数据则是每个类对象私有的，空对象调用成员函数，没有访问数据，可以调用，访问数据不可以。
class MyClass;
struct Info{
MyClass *p;
int n;
};
list<Info> myClasslist;//双链表数据结构，管理一个类所有对象
class MyClass{
public:
void showMessage(){
cout<<"hello"<<endl;
}
MyClass(){
cout<<"MyClass()"<<endl;
}
~MyClass(){
cout<<"~MyClass()"<<endl;
}
void * operator new(size_t size){
void *p = malloc(size);
Info info;
info.p = (MyClass *)p;
if (size == sizeof(MyClass)) {
info.n = 1;
}else{
info.n = (int)(size-8)/sizeof(MyClass);
}
myClasslist.push_back(info);
return p;
}
void operator delete(void *p){
//双链表检索内存，存在就删除，不存在不管
for (auto ib = myClasslist.begin(), ie = myClasslist.end(); ib != ie; ib++) {
if (p==(*ib).p) {
myClasslist.erase(ib);
free(p);
break;
}
}
}
void * operator new[](size_t size){
cout<<"new[]"<<size<<endl;//size = n+8;
return operator new(size);
}
void operator delete[](void *p){
operator delete(p);
}
};
void showmemory(){
for(auto i : myClasslist){
cout<<"内存地址："<<i.p<<" "<<"个数："<<i.n<<endl;
}
}
void callAllObjs(){
for(auto myclass : myClasslist){
if (myclass.n == 1) {
myclass.p->showMessage();
}else{
//对象数组的第一个地址是数组名,要跳过
for (int j=0; j<myclass.n; j++) {
myclass.p[j+1].showMessage();
}
}
}
}
int main(){
MyClass *p1 = new MyClass;
MyClass *p2 = new MyClass;
MyClass *pa1 = new MyClass[2];//size 18
delete p1;
delete p2;
MyClass *pa2 = new MyClass[3];
delete [] pa1;
showmemory();
callAllObjs();//3个
return 1;
}
要是创建树结构
struct ClassInfo{
MyClass *p;
int n;
char name[10];//类的名称
};
list<list<ClassInfo>> myTree;
References
[1] C++链表的C实现（查找中间节点、判断是否存在环）: https://blog.csdn.net/zhuxincheng_1218/article/details/79590368
谢谢大家的关注支持，如果阅读有所获，欢迎点赞，转发。