list双向链表容器_采用list 容器实现归并排序。提示:采用list 容器创建两个链表,并对其调用sort 函

list是双向链表的泛化容器，提供了splice和merge归并函数，sort函数利用list的数据结构特点对元素进行了归并排序。

创建list对象

创建list对象的方式主要有以下几种。
(1) list()

list<int> l;
1

(2) list(size_type n)

list<int> l(10);
1

(3) list(size_type n,const T&value)

list<int> l(10,2.5);
1

(4) list(const list&)

list<char> l1(5,’k’);
list<char> l2(l1);
1
2

(5) list(InputIterator first, InputIterator last)

int array[]={1,2,3,4,5};
list<int> l(array,array+5);
1
2

初始化

利用push_back函数进行初始化，其原型为：

void push_back(const T&);
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
1
2
3
4
5

遍历

list元素的遍历只能使用迭代器来实现。

#include<iostream>
#include<list>
using namespace std;
struct student
{
    char *name;
    int age;
};
int main()
{
    student s[]={{"li",18},{"shi",16},{"wang",17}};
    list<student> l;
    l.push_back(s[0]);
    l.push_back(s[1]);
    l.push_back(s[2]);
    //迭代器遍历
    list<student>::iterator begin,end;
    end=l.end();
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<(*begin).name<<" "<<(*begin).age<<endl;
    } 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

插入

利用push_back函数在尾部插入，push_front函数在链首插入，insert在任意位置插入，插入操作不需要对其他元素进行移位拷贝，时间复杂度为O(1)

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    //插入
    list<int>::iterator begin,end;
    begin=l.begin();begin++;
    l.insert(begin,4);
    l.push_front(5);
    end=l.end();
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<*begin<<" ";
    } 

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

删除

利用pop_front函数删除首元素，pop_back函数删除尾元素，erase函数删除任意指定迭代器位置处的元素，clear删除所有链表元素，remove删除指定值的所有元素。

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(3);
    l.push_back(3);
    l.push_back(4);
    l.push_back(5);
    list<int>::iterator begin,end;
    begin=l.begin();
    begin++;
    l.erase(begin);
    l.pop_front();
    l.pop_back();
    l.remove(3);
    end=l.end();
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<*begin<<" ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

反向遍历

反向迭代器reverse_iterator和const_reverse_iterator

list<int>::reverse_iterator rbegin,rend;
rend=l.rend();
for(rbegin=l.rbegin();rbegin!=rend;rbegin++)
{
    cout<<*rbegin<<" ";
}
1
2
3
4
5
6
7

交换

利用swap函数进行交换，其原型为

void swap(list&)
//list<int> l1,l2;
l1.swap(l2);
1
2
3

归并

利用splice函数和merge函数进行归并。
(1) splice(iterator pos,list&x)
将x的链表归并到当前链表的pos位置前，list对象x将被清空。
(2) splice(iterator pos,list&,iterator i)
将一个list的迭代器i值所指的元素归并到当前的list链表中，被归并的元素将从原链表中删除。
(3) merge(list&x)
将list对象x的链表归并到当前list链表中，并清空x的链表。

#include<iostream>
#include<list>
using namespace std;
void print(list<int> &l)
{
    list<int>::iterator begin,end;
    end=l.end(); 
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<*begin<<" ";
    } 
}
int main()
{
    list<int> l;
    for(int i=1;i<=10;i++)
        l.push_back(i);

    //splice归并 
    list<int> c;
    c.splice(c.begin(),l,l.begin());
    cout<<"-------c:";
    print(c);
    cout<<endl;
    cout<<"-------l:";
    print(l);
    cout<<endl;

    //merge归并
    list<int> x;
    x.push_back(10); 
    x.push_back(20);
    x.push_back(30);
    x.push_back(40);
    l.merge(x);
    cout<<"-------x:";
    print(x);
    cout<<endl;
    cout<<"-------l:";
    print(l);
    cout<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

排序

利用list容器提供的sort函数进行排序，默认递增排序。

#include<iostream>
#include<list>
using namespace std;
void print(list<int> &l)
{
    list<int>::iterator begin,end;
    end=l.end();
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<*begin<<" ";
    } 
    cout<<endl;
}
int main()
{
    list<int> l;
    for(int i=10;i>=0;i--)
    {
        l.push_back(i);
    }
    cout<<"排序前：";print(l);

    l.sort();

    cout<<"排序后：";print(l);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

删除连续重复的元素

利用list容器提供的unique函数可以将连续重复的元素删除。

#include<iostream>
#include<list>
using namespace std;
int main()
{

    list<int> l;
    l.push_back(1); 
    l.push_back(1); 
    l.push_back(1); 
    l.push_back(2); 
    l.push_back(3); 
    l.push_back(4); 
    l.push_back(1); 
    l.push_back(1); 
    l.push_back(1); 

    //去除连续重复的元素
    l.unique();

    list<int>::iterator begin,end;
    end=l.end();
    for(begin=l.begin();begin!=end;begin++)
    {
        cout<<*begin<<" ";
    } 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29