C++ STL之list雙向鏈表容器方式

更新時間：2024年04月23日 10:03:07 作者：csdn_HZW

這篇文章主要介紹了C++ STL之list雙向鏈表容器方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

1.list技術原理

為了支持前向和反向訪問list容器的元素，list采用雙向循環(huán)的鏈表結構組織數(shù)據元素，鏈表的每個節(jié)點包括指向前驅的指針、實際數(shù)據和指向后繼的指針等數(shù)據域。

list的前向鏈，由頭節(jié)點→第1個節(jié)點→第2個節(jié)點→…第n個節(jié)點→頭節(jié)點構成循環(huán)。

list的反向鏈，則由第n個節(jié)點→第n-1個節(jié)點→…→頭節(jié)點→第n個節(jié)點構成循環(huán)。n為list的節(jié)點個數(shù)，整個鏈表的存儲位置由頭指針指出，它指向頭節(jié)點。

2.應用基礎

list對象的創(chuàng)建，初始化賦值方法與vector相同，list的交換與deque相同，這里直接跳過。

2.1元素的遍歷訪問

由于鏈表中的數(shù)據需要一個個元素進行遍歷，因此，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"},
    };
    //將數(shù)據插入鏈表
    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();
}

運行結果：

list遍歷結果

2.2元素的插入

由于list鏈表元素的插入不需要對其他元素進行移位拷貝，除了push_back函數(shù)在尾部添加元素外，list還提供了在鏈首插入元素的push_front函數(shù)和在任意迭代器位置的插入insert()函數(shù)。

#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();
}

輸出結果：

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 << "反向遍歷：";
    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();
}

運行結果：

2.4list的排序與歸并

list 提供的void sort函數(shù)，將鏈表中的元素按"<"關系進行排序，較小的排在前面。

list鏈表元素的排序，是將list鏈表分割成若干部分進行子排序，然后通過歸并處理，實現(xiàn)list的所有元素的排序。為此，list容器提供了splice和merge的歸并函數(shù)。

void splice(iterator position,list& x) //將x的鏈表歸并到當前l(fā)ist鏈表的position之前，list對象x將被清空
void splice(iterator position,list&,iterator i)//將一個list的迭代器i值所指的元素，歸并到當前l(fā)ist鏈表中，并將被歸并的元素從原鏈表中刪除
void merge(list& x)//將list對象x的鏈表歸并到當前l(fā)ist鏈表中，并清空x的鏈表。從merge函數(shù)的源碼可知，只有當前的list鏈表和x均預先按元素的"<“關系排好序，merge函數(shù)才有意義，歸并后的鏈表也是按”<"關系排列。

上代碼：

#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_back(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 << "l的元素為：";
    print(l);
    return a.exec();
}

運行結果：