数据结构与算法——列表的实现、排序与遍历（C++）

文章目录

1 列表实现
2 列表三大排序方法
3 列表遍历
4 总结

1 列表实现

1.1 ListNode节点结构体

构建列表的前提是建造一个列表节点的结构体，这个结构体表示了列表的最小单元。ListNode结构体一般包括的成员有数据，前驱与后继。

typedef int Rank; // 秩
#define ListNodePosi(T) ListNode<T>* //列表节点位置

template <typename T> struct ListNode{
    //成员
    T data; ListNodePosi(T) pred; ListNodePosi(T) succ;
    //构造函数
    ListNode() {};
    ListNode( T e, ListNodePosi(T) p = NULL, ListNodePosi(T) s =NULL)
    :data( e ), pred( p ), succ ( s ){}
    //操作接口 
    ListNodePosi(T) insertAsPred ( T const& e);
    ListNodePosi(T) insertAsSucc ( T const& e);
};

1.2 List类

List类是列表的主体部分，是列表得以在ListNode结构体基础上完成各项操作的地基。

#include "listnode.h"

template  <typename T> class List{

private:
    int _size; ListNodePosi(T) header; ListNodePosi(T) trailer;

protected:
    void init();
    int clear();
    void merge( ListNodePosi(T)&, int, List<T>&, ListNodePosi(T), int );
    void mergeSort (ListNodePosi(T)&, int);//从对p开始的连续n个节点归并排序
    void selectionSort ( ListNodePosi(T), int);//从对p开始的连续n个节点选择排序
    void insertionSort ( ListNodePosi(T) , int );//从对p开始的连续n个节点插入排序

public:
    //构造与析构
    List() {init();}
    ~List();

    bool empty() const{ return _size <= 0;}
    ListNodePosi(T) last() const { return trailer->pred;}
    ListNodePosi(T) first() const { return header->succ;}
    T& operator[] (Rank r) const;//重载，支持循秩访问（效率低）
    //排序相关
    ListNodePosi(T) search( T const& e, int n, ListNodePosi(T) p) const;
    ListNodePosi(T) selectMax( ListNodePosi(T) p, int n);
    void sort( ListNodePosi(T) p, int n);
    //插入与删除
    ListNodePosi(T) insertAsFirst(T const& e);
    ListNodePosi(T) insertAsLast(T const& e);
    ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e);//将e当做p的后继插入
    ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e);//将e当做p的前驱插入
    T remove(ListNodePosi(T) p);//删除合法位置p处的节点，返回被删除节点


    //遍历
    void traverse (void (*)(T&) );
    template <typename VST> //操作器
    void traverse(VST&);
};//List

//默认构造方法
template <typename T> void List<T>::init(){
    header = new ListNode<T>;
    trailer = new ListNode<T>;
    header->succ = trailer;
    header->pred = nullptr;
    trailer->pred = header;
    trailer->succ = nullptr;
    _size = 0;
}

template <typename T> T& List<T>::operator[] (Rank r) const{
    ListNodePosi(T) p = first();
    while ( 0 < r--) p = p->succ;
    return p->data;
}

//插入
template <typename T> ListNodePosi(T) List<T>::insertAsFirst(T const& e)
{ _size++; return header->insertAsSucc(e);}
template <typename T> ListNodePosi(T) List<T>::insertAsLast(T const& e)
{ _size++; return trailer->insertAsPred(e);}
template <typename T> ListNodePosi(T) List<T>::insertA(ListNodePosi(T) p, T const& e)
{ _size++; return p->insertAsSucc(e);}
template <typename T> ListNodePosi(T) List<T>::insertB(ListNodePosi(T) p, T const& e)
{ _size++; return p->insertAsPred(e);}

template <typename T> ListNodePosi(T) ListNode<T>::insertAsPred(T const& e){
    ListNodePosi(T) x = new ListNode(e, pred, this);
    pred->succ = x; pred = x;
    return x;
}
template <typename T> ListNodePosi(T) ListNode<T>::insertAsSucc(T const& e){
    ListNodePosi(T) x = new ListNode(e, this, succ);
    succ->pred  = x; succ = x;
    return x;
}

//删除
template <typename T> T List<T>::remove( ListNodePosi(T) p){
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p; _size--;
    return e;
}

//析构
template <typename T> List<T>::~List()
{ clear(); delete header; delete trailer;}

template <typename T> int List<T>::clear(){
    int oldSize = _size;
    while(0 < _size) remove(header->succ);
    return oldSize;
}

//遍历1——借助函数指针机制遍历
//void traverse (void (*)(T&) );
template <typename T> void List<T>::traverse ( void (*visit )( T& ))
{
    for( ListNodePosi(T) p = header->succ; p != trailer; p = p->succ) visit( p->data);
}
//遍历2——借助函数对象机制遍历
// template <typename VST> //操作器
//     void traverse(VST&);
template <typename T> template <typename VST>
void List<T>::traverse( VST& visit)
{ for ( ListNodePosi(T) p = header->succ; p != trailer; p = p->succ) visit( p->data );}

//查找
template <typename T> ListNodePosi(T) List<T>::search( T const& e, int n, ListNodePosi(T) p) const{
    while( 0 <= n--)
        if( (( p = p->pred)->data) <= e) break;
    return p;//返回查找终止的位置
}


//排序总览
template <typename T> void List<T>::sort( ListNodePosi(T) p, int n){
    switch( 3 ){
        case 1: insertionSort( p, n ); break;//插入排序
        case 2: selectionSort( p, n ); break;//选择排序
        case 3: mergeSort (p, n ); break;//归并排序
    }
}

//插入排序_对于起始位置p的n个元素排序
template <typename T> void List<T>::insertionSort ( ListNodePosi(T) p, int n){
    for( int i = 0; i < n; i ++){
        insertA ( search ( p->data, i, p), p->data );
        p = p->succ; remove ( p-> pred );
    }
}

//选择排序
template <typename T> void List<T>::selectionSort( ListNodePosi(T) p, int n){
    ListNodePosi(T) head = p->pred;ListNodePosi(T) tail = p;
    for ( int i = 0; i < n; i ++) tail = tail->succ;
    while (1 < n){
        ListNodePosi(T) max = selectMax ( head->succ, n);
        insertB( tail, remove( max));
        tail = tail->pred; n--;
    }
}
//selectMax()
template <typename T> ListNodePosi(T) List<T>::selectMax ( ListNodePosi(T) p, int n){
    ListNodePosi(T) max = p;
    for ( ListNodePosi(T) cur = p; 1 < n; n --)
        if ( ( cur = cur->succ )->data >= max->data)
            max = cur;
    return max;
}

//归并排序
template <typename T> void List<T>::mergeSort( ListNodePosi(T) & p, int n){
    if ( n < 2) return;
    int m = n >> 1;
    ListNodePosi(T) q = p;for (int i = 0; i < m; i ++) q = q->succ;
    mergeSort( p, m); mergeSort( q, n-m );
    merge( p, m, *this, q, n-m);
}
//归并
template <typename T> void List<T>::merge( ListNodePosi(T) & p, int n, List<T>& L, ListNodePosi(T) q, int m){
    ListNodePosi(T) pp = p->pred;
    while( 0 < m)
        if( (0 < n ) && ( p->data <= q->data))
            {if ( q == ( p = p->succ)) break; n--;}
        else
            {insertB ( p, L.remove ( ( q = q->succ )->pred)); m--;}
    p = pp->succ;
}

1.3 主程序

对于List类的关键的几个方法进行测试。主要测试的包括构造，插入，遍历与排序等方法。

/*
* The program is about LIST
* author @Ripples
* 2020-07-15
*/
#include <iostream>
#include "list.h"

using namespace std;

void returnValue(int& a)
{
    cout << "return_value: " << a << endl;
}
int main()
{
    //初始化列表
    List<int> list;
    list.insertAsLast(2); 
    list.insertAsLast(1); 
    list.insertAsLast(6); 
    list.insertAsLast(3); 
    list.insertAsLast(5); 
    list.insertAsLast(4); 
    for ( int i = 0; i < 6; i ++)
    { cout << list[i] << endl;}

    //测试遍历
    void (* visit)(int& ) = &returnValue;
    list.traverse(visit);

    //测试排序 
    for ( int i = 0; i < 6; i ++)
    { cout << list[i] << endl;}
    list.sort(list.first(), 6);
    list.traverse(visit) ;

}

测试的输出结果如下：
2
1
6
3
5
4
return_value: 2
return_value: 1
return_value: 6
return_value: 3
return_value: 5
return_value: 4
2
1
6
3
5
4
return_value: 1
return_value: 2
return_value: 3
return_value: 4
return_value: 5
return_value: 6

2 列表三大排序方法

2.1 插入排序

插入排序的不变性在于保证当前节点之前的列表段是有序的。其方法的核心是在当前节点之前的节点段自后往前寻找第一个不大于当前节点值的节点，在这个节点后面插入当前节点。之后删除当前节点并转移操作当前节点的后继，直到所有节点都被处理。其复杂度为 $O(n^{2})$ 。

//插入排序_对于起始位置p的n个元素排序
template <typename T> void List<T>::insertionSort ( ListNodePosi(T) p, int n){
    for( int i = 0; i < n; i ++){
        insertA ( search ( p->data, i, p), p->data );
        p = p->succ; remove ( p-> pred );
    }
}

插入排序得以成功实现的一个重要因素是确保查找函数的语义明确，保证返回的是不大于p->data的最后面的一个节点位置。除此之外，需要关注一下前列表段为空的情况。

//查找
template <typename T> ListNodePosi(T) List<T>::search( T const& e, int n, ListNodePosi(T) p) const{
    while( 0 <= n--)
        if( (( p = p->pred)->data) <= e) break;
    return p;//返回查找终止的位置
}

2.2 选择排序

选择排序的不变性在于保证后面的列表段是有序的。其实现的方法是在（head，tail）中寻找最大的那个节点，将其作为前驱插入到tail之前，删除之前的节点并更新tail。其复杂度由selectMax限制为 $O(n^{2})$ 。

//选择排序
template <typename T> void List<T>::selectionSort( ListNodePosi(T) p, int n){
    ListNodePosi(T) head = p->pred;ListNodePosi(T) tail = p;
    for ( int i = 0; i < n; i ++) tail = tail->succ;
    while (1 < n){
        ListNodePosi(T) max = selectMax ( head->succ, n);
        insertB( tail, remove( max));
        tail = tail->pred; n--;
    }
}
//selectMax()
template <typename T> ListNodePosi(T) List<T>::selectMax ( ListNodePosi(T) p, int n){
    ListNodePosi(T) max = p;
    for ( ListNodePosi(T) cur = p; 1 < n; n --)
        if ( ( cur = cur->succ )->data >= max->data)
            max = cur;
    return max;
}

2.3 归并排序

由于列表与数组在插入、删除与查找上的特性不同，基于列表的归并排序的实现方法与数组有所差异。基于列表的归并排序在归并过程中，只需将一个依次插入到另一个列表段中合适的位置。其复杂度为O(nlogn)。

//归并排序
template <typename T> void List<T>::mergeSort( ListNodePosi(T) & p, int n){
    if ( n < 2) return;
    int m = n >> 1;
    ListNodePosi(T) q = p;for (int i = 0; i < m; i ++) q = q->succ;
    mergeSort( p, m); mergeSort( q, n-m );
    merge( p, m, *this, q, n-m);
}
//归并
template <typename T> void List<T>::merge( ListNodePosi(T) & p, int n, List<T>& L, ListNodePosi(T) q, int m){
    ListNodePosi(T) pp = p->pred;
    while( 0 < m)
        if( (0 < n ) && ( p->data <= q->data))
            {if ( q == ( p = p->succ)) break; n--;}
        else
            {insertB ( p, L.remove ( ( q = q->succ )->pred)); m--;}
    p = pp->succ;
}

3 列表遍历

列表的遍历方法包括借助函数指针机制的遍历与借助函数对象机制的遍历。遍历引用的函数需要自己编写，通过遍历可以对访问到的单元做检查或更新的操作。

//遍历1——借助函数指针机制遍历
//void traverse (void (*)(T&) );
template <typename T> void List<T>::traverse ( void (*visit )( T& ))
{
    for( ListNodePosi(T) p = header->succ; p != trailer; p = p->succ) visit( p->data);
}
//遍历2——借助函数对象机制遍历
// template <typename VST> //操作器
//     void traverse(VST&);
template <typename T> template <typename VST>
void List<T>::traverse( VST& visit)
{ for ( ListNodePosi(T) p = header->succ; p != trailer; p = p->succ) visit( p->data );}

4 总结

以上是关于列表类的学习，主要参考了清华大学邓俊辉教授编写的《数据结构（C++语言版）》。由于本人水平有限，存在纰漏的地方敬请指正。