slist為單向鏈表的泛化容器，與list雙向鏈表容器一樣，實(shí)現(xiàn)了線性表數(shù)據(jù)的鏈表存儲(chǔ)，數(shù)據(jù)元素不必在物理內(nèi)存中連續(xù)分布。

slist鏈表的節(jié)點(diǎn)，只有后繼的指針，不含前驅(qū)的指針。因此，在節(jié)省前驅(qū)指針的存儲(chǔ)空間的同時(shí)，也就不再支持迭代器的反向移動(dòng)。

1.slist技術(shù)原理

slist內(nèi)部的鏈表由頭指針、頭節(jié)點(diǎn)和元素節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)含有指向后繼節(jié)點(diǎn)的指針，最后一個(gè)節(jié)點(diǎn)的指針為null，可見slist沒有形成一個(gè)環(huán)形回路。

頭節(jié)點(diǎn)一般不存儲(chǔ)數(shù)據(jù)，為了使各個(gè)元素節(jié)點(diǎn)都有前驅(qū)節(jié)點(diǎn)的指針指向它以便能夠不加區(qū)別的對(duì)第一個(gè)元素節(jié)點(diǎn)和其他元素節(jié)點(diǎn)進(jìn)行統(tǒng)一處理，所以構(gòu)造頭節(jié)點(diǎn)。

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

list對(duì)象的創(chuàng)建和vector一樣，不多解釋。元素的刪除、歸并、排序與list相同。

2.1初始化賦值和遍歷

通常使用push_front函數(shù)進(jìn)行初始化，由于slist的頭節(jié)點(diǎn)僅有一個(gè)指針域保存首元素地址，而沒有存放最后一個(gè)元素的地址，因此slist沒有提供類似的push_back函數(shù)能夠在容器尾部添加元素。

push_front函數(shù)在鏈表首元素前面，插入一個(gè)新元素，使之成為首元素。

遍歷slist和list一樣，只能使用迭代器進(jìn)行遍歷，而不能使用數(shù)組下標(biāo)的形式。

#include <QList>                 //在qt中QList就是單向鏈表，用法和slist相同
#include <QCoreApplication>
#include<QString>
using namespace std;
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
    QList<int> s;
    s.push_front(11);           //在首元素插入11
    s.push_front(23);           //在11前面插入23，即現(xiàn)在23為首元素
    s.push_front(39);          // 在首元素23之前插入39，即39,23,11
    QList<int>::iterator i,iend;
    iend=s.end();
    for(i=s.begin();i!=iend;i++)
    {
        cout << *i << " ";
    }
    cout << endl;
    return a.exec();
}

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

2.2元素的插入

對(duì)于任意位置上的slist鏈表元素的插入，可使用insert_after和insert函數(shù)，insert_after函數(shù)直接在指定的pos位置后插入新元素。

insert則從單向鏈表的頭節(jié)點(diǎn)開始，找到pos的前驅(qū)位置，然后調(diào)用insert_after函數(shù)進(jìn)行插入，因此執(zhí)行效率比較低。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論