开发者

C++ STL之list双向链表容器方式

目录
  • 1.list技术原理
  • 2.应用基础
    • 2.1元素的遍历访问
    • 2.2元素的插入
    • 2.3元素的反向遍历和删除
    • 2.4list的排序与归并
  • 总结

    不同于采用线性表顺序存储结构的vector和deque容器,list双向链表中任一位置的元素查找、插入和删除,都具有高效的常数阶算法时间复杂度O(1)。

    1.list技术原理

    为了支持前向和反向访问list容器的元素,list采用双向循环的链表结构组织数据元素,链表的每个节点包括指向前驱的指针、实际数据和指向后继的指针等数据域。

    C++ STL之list双向链表容器方式

    list的前向链,由头节点→第1个节点→第2个节点→…第n个节点→头节点构成循环。

    list的反向链,则由第n个节点→第n-1个节点→…→头节点→第n个节点构成循环。n为list的节点个数,整个链表的存储位置由头指针指出,它指向头节点。

    2.应用基础

    list对象的创建,初始化赋值方法与vector相同,jslist的交换与deque相同,这里直接跳过。

    2.1元素的遍历访问

    由于链表中的数据需要一个个元素进行遍历,因此,list元素的遍历只使用迭代器的方式进行。

    上代码:

    #include <QCoreApplication>
    #include <IOStream>
    #include <list>
    using namespace std;
    struct Student{
        char *name;
        int age;
        char *city;
        char *tel;
    };
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
        Student s[] = {
            {"符符",18,"上海市","156624"},
            {"介介",20,"北京市","152534"},
            {"贝贝",25,"深圳市","453545"},
        };
        //将数据插入链表
        list<Student> l;
        l.push_back(s[0]);
        l.push_back(s[1]);
        l.push_back(s[2]);
        //遍历打印链表元素
        list<Student>::iterator i,iend;
        iend=l.end();
        cout << "姓名 年龄 城市 电话" << endl;
        cout << "----------------------------" << endl;
        for(i=l.begin();i!=iend;i++)
        {
            cout << (*i).name << " ";
            cout << (*i).age << " ";
            cout << (*i).city << " ";
            cout << (*i).tel << " " << endl;
        }
        cout << "----------------------------" << endl;
        return a.exec();
    }
    

    运行结果:

    C++ STL之list双向链表容器方式

    2.2元素的插入

    由于list链表元素的插入不需要对其他元素进行移位拷贝,除了push_back函数在尾部添加元素外,list还提供了在链首插入元素的push_front函数和在任意迭代器位置的插入insert()函数。

    #include <QCoreApplication>
    #include <iostream>
    #include <list>
    using namespace std;
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
        list<int> l;
        l.push_back(6);
        l.push_back(8);
        l.push_back(9);
        list<int>::iterator i,iend;
        i=l.begin();
        i++;
        l.insert(i,7);    //在6的后面插入7
        l.push_front(5);     //在链首插入5
        iend=l.end();
        for(i=l.begin();i!=iend;i++)
        {
            cout << *i << ' ';
        }
        return a.exec();
    }
    

    输出结果:

    C++ STL之list双向链表容器方式

    2.3元素的反向遍历和删除

    由于list容器的迭代器具有"–"操作,因此也定义了反向迭代器。用反向迭代器来进行链表的遍历。

    #include <QCoreApplication>
    #include <iostream>
    #include <list>
    using namespace std;
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
        list<int> l;
        l.push_back(5);
        l.push_back(6);
        l.push_back(7);
        l.push_back(8);
        l.push_back(9);
        l.push_back(9);
        l.push_back(9);
        l.push_back(10);
        list<int>::reverse_iterator ri,rend;
        rend=l.rend();
        cout << "反向遍历python:";
        for(ri=l.rbegin();ri!=rend;ri++)
        {
            cout << *ri << " ";
        }
        cout << endl;
        list<int>::iterator i,iend;
        i=l.begin();
        i++;
        l.erase(i);     //删除6
        l.pop_back();   //删除末元素10
        l.pop_front();   //删除首元素5
        l.remove(9);     //删除所有值为9的元素
        iend=l.end();
        for(i=l.begin();i!=iend;i++)
        {
            cout << *i << " ";
        }
        cout << endl;
        return a.exec();
    }
    

    运行结果:

    C++ STL之list双向链表容器方式

    2.4list的排序与归并

    list 提供的void sort函数,将链表中的元素按"<"关系进行排序,较小的排在前面。

    list链表元素的排序,是将list链表分割成若干部分进行子排序,然后通过归并处理,实现list的所有元素的排序。为此,list容器提供了splice和merge的归并函数。

    void splice(iterator posit编程客栈ion,list& x) //将x的链表归并到当前list链表的position之前,list对象x将被清空
    void splice(iterator position,list&,iterator i)//将一个list的迭代器i值所指的元素,归并到当前list链表中,并将被归并的元素从原链表中删除
    void merge(list& x)//将list对象x的链表归并到当前list链表中,并清空x的链表。从merge函数的源码可知,只有当前的list链表和x均预先按元素的"<“关系排好序,merge函数才有意义,归并后的链表也是按”<"关系排列。

    上代码:

    #include <QCoreApplication>
    #include <iostream>
    #include <list>
    using namespace std;
    void print(list<int>& l)
    {
        list<int>::iterator i,iend;
        iend=l.end();
        for(i=l.begin();i!=iend;i++)
        {
            cout << *i << " ";
        }
        cout<< endl;
    }
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
        list<int> l;
        l.push_back(13);
        l.push_www.devze.comback(6);
        l.push_back(7);
        l.push_back(15);
        l.push_back(9);
        l.push_back(8);
        l.push_back(9);
        l.push_back(10);
        cout << "未排序前:";
        print(l);
        l.sort();   //从小到大排序
        cout << "排序后:";
        print(l);
        list<int> carry;
        carry.splice(carry.begin(),l,l.begin());   //将l的第一个元素归并到carry的首元素,并将l的首元素删除
        cout << "carry的链表元素为:";
        print(carry);
        cout << "l的链表元素为:";
        print(l);
        list<int> x;
        x.push_back(30);
        x.push_back(31);
        x.push_back(32);
        l.merge(x);                      //将x链表里的元素归并到l,并清空x
        cout << "x的链表元素为:";
        print(x);
        cout &lhttp://www.devze.comt;< "l的元素为:";
        print(l);
        return a.exec();
    }
    

    运行结果:

    C++ STL之list双向链表容器方式

    总结

    list双向链表容器采用双向链表的数据结构来存储数据,可高效查找、插入和删除容器元素。

    list提供的splice和merge归并函数,可用于链表的元素排序。

    以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程客栈(www.devze.com)。

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜