快捷導(dǎo)航

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

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

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

1.list技術(shù)原理

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

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

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

2.應(yīng)用基礎(chǔ)

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

2.1元素的遍歷訪問

由于鏈表中的數(shù)據(jù)需要一個(gè)個(gè)元素進(jìn)行遍歷，因此，list元素的遍歷只使用迭代器的方式進(jìn)行。

上代碼：

#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ù)據(jù)插入鏈表
    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();
}

運(yùn)行結(jié)果：

list遍歷結(jié)果

2.2元素的插入

由于list鏈表元素的插入不需要對(duì)其他元素進(jìn)行移位拷貝，除了push_back函數(shù)在尾部添加元素外，list還提供了在鏈?zhǔn)撞迦朐氐膒ush_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);     //在鏈?zhǔn)撞迦?
    iend=l.end();
    for(i=l.begin();i!=iend;i++)
    {
        cout << *i << ' ';
    }
    return a.exec();
}

輸出結(jié)果：

2.3元素的反向遍歷和刪除

由于list容器的迭代器具有"–"操作，因此也定義了反向迭代器。用反向迭代器來進(jìn)行鏈表的遍歷。

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

運(yùn)行結(jié)果：

2.4list的排序與歸并

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

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

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

上代碼：

#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的第一個(gè)元素歸并到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();
}

運(yùn)行結(jié)果：