场景

• 插入排序算法的描述
  • 适用于序列 (列表/向量)
• 实现
  • 将序列分成前后两个序列, 前缀序列是有序的, 后继序列是无序的，每次循环都将后继序列的首个节点插入到前缀序列的合适位置

列表插入排序算法实现

// 插入排序: 对于起始于节点p的n个节点进行排序（包含N）    将序列分成有序的前缀和无序的后缀， 反复的将无序后缀的首元素插入到前缀合适的位置
template <typename T> void List<T>::insertionSort(ListNodePosi (T) p, int n) {
    // p必需是合法的节点 && rank(p) + n <+ _size
    if (!valid(p)) {
        cout << "不合法的节点p" << endl;
        throw STATUS_ERROR;
    }
    ListNodePosi (T) node_small;
    for(int i = 0; i< n; i ++) {
        // 有序前缀中不大于无序后继首元素的最后一个节点
         node_small = search(p->data, i, p);

        // 首元素插入前缀有序列表
        insertA(node_small, p->data);

        // 更新循环依据
        p = p->succ;

        // 元素后继的首元素
       remove(p->pred);
    }
}

// 有序列表内节点p的个前驱元素中找到不大于e的最后一个元素
template <typename T> ListNodePosi(T) List<T>::search(T const &e, int n , ListNodePosi(T) p){
    // p可能是trailer
    // 0 <= n <= rank(p) < _size;
    if (n < 0 || n > _size) {
        throw STATUS_ERROR;
    }

    while(n-- >= 0) {
        p = p->pred;
        if (p->data <= e) {
            break;
        }
    }
    return p;
}


// 删除特定的节点，返回特定的元素
template <typename T> T List<T>::remove(ListNodePosi(T) p) {
    // 备份待删除节点
    T data = p->data;

    // 当前页面的上一个节点的后继节点改成p的后继节点
    p->pred->succ = p->succ;

    // p的后继节点改成p的前驱节点
    p->succ->pred = p->pred;

    delete p;

    // 规模减1
    _size --;
    return data;
}

完整代码

• ListNode.h 列表节点

using namespace std;
#define ListNodePosi(T) ListNode<T>*

typedef int T;
typedef int Rank;
typedef int RANK;

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

template<typename T> ListNodePosi(T)   ListNode<T>::insertAsPred(T const& e){
// 插入新增的节点
    ListNodePosi(T) new_node = new ListNode(e, pred, this);
// 新节点进入连接
    pred->succ = new_node;
    pred = new_node;
    return new_node;
};

// 插入当前节点后面
template<typename T> ListNodePosi(T)  ListNode<T>::insertAsSucc(T const& e){
// 新节点
    ListNodePosi(T) new_node = new ListNode(e, this, succ);

// 当前节点的原后缀节点的前缀节点改成新节点
    succ->pred = new_node;

// 当前节点的后缀节点改成
    succ = new_node;
    return new_node;
};

• List.h 列表模板类

using namespace std;

#define STATUS_ERROR -1

template<typename T>
class List {
private:
    // 规模
    int _size;

    // 头节点
    ListNodePosi(T) header;

    // 尾指针
    ListNodePosi(T) trailer;

protected:
    // 列表创建时初始化
    void init();

    // 清除所有节点
    int clear();

    // 复制列表中自位置p起的n项
    void copyNodes(ListNodePosi(T) p,int n);

public:
    // 构造方法
    List() { init(); };

    // 析构方法
    ~List(){
        clear();
        delete trailer;
        delete header;
    };//释放所有节点

    // 获取规模
    Rank size() { return _size; };

    // 列表是否为空
    bool empty() { return _size < 1; }

    // 重载[]
    T& operator[](Rank r);

    // 获取首节点
    ListNodePosi(T) const first() {
        return header->succ;
    }

    // 获取末节点
    ListNodePosi(T) const last() {
        return trailer->pred;
    }

    // 某个节点是否合法
    bool valid(ListNodePosi(T) p) {
        // 节点不为空并且不是头尾节点
        return p && p != trailer && p != header;
    }

    // 插入首节点
    ListNodePosi(T) insertAsFirst(T const& e){
      _size ++;
      return header->insertAsSucc(e);
    };

    // 插入尾节点
    ListNodePosi(T) insertAsLast(T const& e);

    // 将e当作节点p的后继插入
    ListNodePosi(T) insertA(ListNodePosi(T) p, T const& e);

    // 将e当作节点p的前驱插入
    ListNodePosi(T) insertB(ListNodePosi(T) p, T const& e);

    // 删除特定的节点，返回特定的元素
    T remove(ListNodePosi(T) p);

    // 遍历 函数指针机制遍历
    void traverse(void (*)(T&));

    // 无序去重
    int deduplicate();

    // 无序列表中查找  没有找到返回NULL
    ListNodePosi(T) find(T const &e, int n , ListNodePosi(T) p);

    // 有序列表内节点p的个前驱元素中找到不大于e的最后一个元素
    ListNodePosi(T) search(T const &e, int n , ListNodePosi(T) p);

    // 插入排序
    void insertionSort(ListNodePosi(T) p,int n);
};

// 有序列表内节点p的个前驱元素中找到不大于e的最后一个元素
template <typename T> ListNodePosi(T) List<T>::search(T const &e, int n , ListNodePosi(T) p){
    // p可能是trailer
    // 0 <= n <= rank(p) < _size;
    if (n < 0 || n > _size) {
        throw STATUS_ERROR;
    }

    while(n-- >= 0) {
        p = p->pred;
        if (p->data <= e) {
            break;
        }
    }
    return p;
}

// 插入排序: 对于起始于节点p的n个节点进行排序（包含N）    将序列分成有序的前缀和无序的后缀， 反复的将无序后缀的首元素插入到前缀合适的位置
template <typename T> void List<T>::insertionSort(ListNodePosi (T) p, int n) {
    // p必需是合法的节点 && rank(p) + n <+ _size
    if (!valid(p)) {
        cout << "不合法的节点p" << endl;
        throw STATUS_ERROR;
    }
    ListNodePosi (T) node_small;
    for(int i = 0; i< n; i ++) {
        // 有序前缀中不大于无序后继首元素的最后一个节点
         node_small = search(p->data, i, p);

        // 首元素插入前缀有序列表
        insertA(node_small, p->data);

        // 更新循环依据
        p = p->succ;

        // 元素后继的首元素
       remove(p->pred);
    }
}

// 无序列表中查找, 在节点p的n个前驱元素中查数据e, 并返回逻辑次序最大的节点
template <typename T>
ListNodePosi(T) List<T>::find(T const &e, int n , ListNodePosi(T) p){
    // 如果n 异常
    if (n < 0  || n >= _size) {
        throw STATUS_ERROR;
    }

    // 另外rank(p) >= n
    while(n-- > 0) {

        // 循环直到n个结束
        p = p->pred;

        // 如果p节点之前没有n个节点， 则抛出异常
        if (p == header) {
            throw STATUS_ERROR;
        }

        if (p->data == e) {
            return p;
        }
    }

    return NULL;
}

// 无序列表去重
template <typename T> int List<T>::deduplicate()
{
    // 平凡列表自然无重复
    if (_size < 2) {
        return 0;
    }

    int old_size = _size;

     // 从第二个元素开始每个元素都要和逻辑次序在它之前的节点进行比较
     // 循环节点
    ListNodePosi(T) p = first();
    RANK r = 1;
    while((p = p->succ) != trailer) {

        // p节点之前是否存在这个数据
        ListNodePosi(T) exist_node = find(p->data, r, p);
        exist_node ? remove(exist_node) : r ++;
    }

    return old_size - _size;
}


// 借助函数指针
template <typename T> void List<T>::traverse(void (*visit)(T &)) {
    for (ListNodePosi(T) p = header->succ; p != trailer ; p = p->succ) {
        visit(p->data);
    }
}

// 删除特定的节点，返回特定的元素
template <typename T> T List<T>::remove(ListNodePosi(T) p) {
    // 备份待删除节点
    T data = p->data;

    // 当前页面的上一个节点的后继节点改成p的后继节点
    p->pred->succ = p->succ;

    // p的后继节点改成p的前驱节点
    p->succ->pred = p->pred;

    delete p;

    // 规模减1
    _size --;
    return data;
}

// 清理掉所有的数据节点,并返回原有节点的数量
template <typename T> int List<T>::clear(){
    int old_size = _size;

    // 反复删除首节点，直到列表数据为空
    while (_size > 0) {
        remove(first());
    }

    return old_size;
}

// 插入尾节点
template <typename T>
ListNodePosi(T) List<T>::insertAsLast(T const& e){
    _size ++;
    return trailer->insertAsPred(e);
}

// 将e当作节点p的后继插入
template <typename T>
ListNodePosi(T) List<T>::insertA(ListNodePosi(T) p, T const& e){
    _size ++;
    return p->insertAsSucc(e);
}

// 将e当作节点p的前驱插入
template <typename T>
ListNodePosi(T) List<T>::insertB(ListNodePosi(T) p, T const& e){
    // 生成一个新的节点
    _size ++;
    return p->insertAsPred(e);
}


// 重载[]
template<typename T>
T& List<T>::operator[](Rank r) {
    if (r < 0 || r > _size) {
        return -1;
    }

    // 首节点
    ListNodePosi(T) p = first();

    for (int i = 1; i < r; ++i) {
        p = p->succ;
    }
    return p->data;
}

// 初始化列表函数
template<typename T>
void List<T>::init() {
    // 生成头节点
    header = new ListNode<T>;

    // 生成尾节点
    trailer =new  ListNode<T>;

    // 生成头尾节点的联系
    header->succ = trailer;
    trailer->pred = header;

    header->pred = NULL;
    trailer->succ = NULL;

    // 规模初始化0
    _size = 0;
}

• main.cpp 主运行程序

#include <iostream>
#include <string>
#include "listNode.h"
#include "list.h"

using namespace std;

#define MAX_AGE 20
#define MIN_AGE 15
#define SIZE 10

int getRandAge()
{
    return MIN_AGE + rand()%(MAX_AGE - MIN_AGE);
};


// 打印列表
template <typename T> void print(T data)
{
    cout << data << " " ;
}

// 给列表赋值
template <typename T> void initAges(List<T> *ages)
{
    int age;
    for (int i = 0; i <SIZE ; ++i) {
        age = getRandAge();
        cout << "age=" << age << endl;
        ages->insertAsFirst(age);
    }
}

// 打印列表
void printAges(List<int> ages){
    // 打印列表的数据
    cout << " 11" << endl;
    ages.traverse(print);
    cout << " 22 "<< endl;
}

int main() {
    List<T> ages;

    // 赋值
    initAges(&ages);

    // 无序列表去重
    ages.deduplicate();

    cout << " " << endl;
    ages.traverse(print);
    cout << " "<< endl;

    // 插入排序
    ages.insertionSort(ages.first(), ages.size());

    // 打印年龄
//    printAges(ages);

    cout << " " << endl;
    ages.traverse(print);
    cout << " "<< endl;

    return 0;
}