列表—List 底层实现

Myth丶恋晨 2022-05-21 11:10 245阅读 0赞

列表的元素构成一个线性逻辑次序，元素的物理地址可以任意。

链表(linked list)是一种典型的动态存储结构，其中的数据分散为一系列节点单位。节点之间通过指针相互索引和访问。为了引进新节点或删除原有节点，只需在局部，调整少量相关节点之间的指针。这意味着，采用动态存储策略，可以大大降低动态操作的成本。

列表节点模板类

typedef int Rank;		//秩
    #define ListNodePosi<T>	ListNode<T>*	//列表节点位置
    
    template <typename T> struct ListNode {	//列表节点模板类:以双向链表形式实现
    //成员
    	T data;	ListNodePosi(T) pred;	ListNodePosi(T)	succ;	//数值、前驱、后继
    //构造函数
    	ListNode() {}	//针对header和trailer的构造
    	ListNode( T e, ListNodePosi(T) p = NULL, ListNodePosi s = NULL )
    		: data(e), pred(p), succ(s) {}			//默认构造器
    //操作接口
    	ListNodePosi(T) insertAsPred ( T const& e);	//紧靠当前节点之前插入新节点
    	ListNodePosi(T) insertAsSucc ( T const& e);	//紧靠当前节点之后插入新节点
    };

列表(List)模板类

#include "listNode.h"
    
    template <typename T> class List {	//列表模板类
    	private:
    		int _size; ListNodePosi(T)	header; ListNodePosi(T) trailer;	//规模、头哨兵、尾哨兵
    		
    	protected:
    		void init();	//列表创建时的初始化
    		int clear();	//清除所有节点
    		void copyNodes ( ListNodePosi(T), int );	//复制列表中自位置p起的n项
    		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() { List<T> const& L };	//整体复制列表L
    	List() { List<T> const& L, Rank r, int n };	//复制列表L中自第r项起的n项
    	List( ListNodePosi(T) p, int n );			//复制列表中自位置p起的n项
    
    	//析构函数
    	~List();			//释放所有节点
    
    	//只读访问接口
    	Rank size() const { return _size; }	//规模
    	bool empty() const { return _size <= 0; }	//判空
    	T& operator[] ( Rank r ) const;		//重载，支持循秩访问
    	ListNodePosi(T) first() const { return header->succ; }	//首节点位置
    	ListNodePosi(T) last() const { return trailer->pred; }  //末节点位置
    	bool valid ( ListNodePosi(T) p )	//判断位置p是否对外合法
    	{	return p && (trailer != p) && (header != p ); }		//将头、尾节点等同于NULL
    	int disordered() const;				//判断列表是否已排序
    	ListNodePosi(T) find( T const& e) const	//无序列表查找
    	{	return find(e, _size, trailer);}
    	ListNodePosi(T) find( T const& e, int n, ListNodePosi(T) p) const;	//无序区间查找
    	ListNodePosi(T) search(T const& e) const	//有序列表查找
    	{	return search(e, _size, trailer); }
    	ListNodePosi(T) search(T const& e, int n , ListNodePosi(T) p) const;//有序区间查找
    	ListNodePosi(T) selectMax( ListNodePosi(T) p, int n);	//在p及其n-1个后继中选出最大者
    	ListNodePosi(T) selectMax() { return selectMax(header->succ, _size); }	//整体最大值
    
    	//可写访问接口
    	ListNodePosi(T) insertAsFirst( T const& e);	//将e当作首节点插入
    	ListNodePosi(T) insertAsLast ( T const& e);	//将e当作末节点插入
    	ListNodePosi(T) insetyA ( ListNodePosi(T) p, T const& e);	//将e当作p的后继插入
    	ListNodePosi(T) insertB ( ListNodePosi(T) p, T const& e);	//..........前驱...
    	T remove( ListNodePosi(T) p);				//删除合法位置p处的节点，返回被删除节点
    	void merge( List<T>& L ) { merge(first(), size, L, L.first(), L._size); }	//全列表归并
    	void sort ( ListNodePosi(T) p, int n );		//列表区间排序
    	void sort() { sort( first(), _size); }		//列表整体排序
    	int deduplicate();	//无序去重
    	int uniquify();		//有序去重
    	void reverse();		//前后倒置
    
    	//遍历
    	void traverse ( void(* ) ( T& ) );		//遍历，依次实施visit操作(函数指针)
    	template <typename VST>		//操作器
    	void traverse (VST& );		//遍历，依次实施visit操作(函数对象)
    };	//List

默认构造方法

template <typename T> void List<T>::init() {	//列表初始化
    	header = new ListNodePosi<T>;	//创建头哨兵节点
    	trailer = new ListNodePosi<T>;	//创建尾哨兵节点
    	header->succ = trailer;	header->pred = NULL;
    	trailer->pred = header;	trailer->succ = NULL;
    	_size = 0;		//记录规模
    }

由秩到位置的转换

//重载下标操作符[]
    template <typename T>	
    T& List<T>::operator[] (Rank r ) const {
    	ListNodePosi(T)	p = first();		//从首节点出发
    	while( 0 < r-- )	p = p->succ;	//顺数第r个节点
    	return p->data;		//返回目标节点数据
    }

查找

//无序列表查找接口
    template <typename T>	//在无序列表内节点p的n个前驱中，找到等于e的最后者
    ListNodePosi(T) List<T>::find (T const& e, int n, ListNodePosi(T) p) const {
    	while( 0 < n-- )	//对于p的最近的n个前驱，从由向左
    		if (e == (p = p->pred)->data) return p;	
    	return NULL;
    }	//失败返回NULL

插入

//接口
    template <typename T> ListNodePosi(T) List<T>::insertAsFirst (T const& e)
    {	_size++; return header->insertAsSucc(e);	}	//e当作首节点插入
    
    template <typename T> ListNodePosi(T) List<T>::insertAsLast (T const& e)
    {	_size++; return trailer->insertAsPred(e);	}	//e当作末节点插入
    
    template <typename T> ListNodePosi(T) List<T>::insertA (ListNodePosi(T) p, T const& e)
    {	_size++; return p->insertAsSucc(e);	}			//e当作p的后继插入(After)
    
    template <typename T> ListNodePosi(T) List<T>::insertB (ListNodePosi(T) p, T const& e)
    {	_size++; return p->insertAsPred(e);	}			//........前驱....(Before)
    
    //前插入
    template <typename T>	//将e紧靠当前节点之前插入于当前节点所属列表
    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;
    }

基于复制的构造

//copyNodes()
    template <typename T>	//列表内部方法:复制列表中自位置p起的n项 
    void List<T>::copyNodes (ListNodePosi(T) p, int n)	{	//p合法，则至少有n-1个后继节点
    	init();		//创建头尾哨兵并做初始化
    	while(n--)	{ insertAsLast(p->data); p = p->succ; }	//将起自p的n项依次作为末节点插入
    }
    
    //基于复制的构造
    template <typename T>	//复制自p起的n项
    List<T>::List (ListNodePosi(T) p, int n) { copyNodes(p, n); }
    
    template <typename T>	//整体复制列表L
    List<T>::List (List<T> const& L) { copyNodes(L.first(), L._size); }
    
    template <typename T>	//复制L中自第r项起的n项
    List<T>::List (List<T> const& L,int r, int n) { copyNodes(L[r], n); }

删除

//删除
    template <typename T> T List<T>::remove (ListNodePosi(T) p ) {	//删除合法节点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;	//返回删除规模
    }

唯一化

无序列表：

//无序列表唯一化
    template <typename T> int List<T>::deduplicate() {	
    	if (_size < 2) return 0;	//平凡列表自然无重复
    	int oldSize = _size;
    	ListNodePosi(T) p = header; Rank r = 0;
    	while (trailer != ( p = p->succ ) ) {	//依次直至末节点
    		ListNodePosi(T) q = find(p->data,r,p);	//在p的r个前驱元素中查找相同者
    		q ? remove(q) : r++;		//若的确存在，则删除之；否者秩加1;
    	}
    	return oldSize - _size;		//列表规模变化量，即被删除元素总数
    }

有序列表：

//有序列表唯一化
    template <typename T> int List<T>::uniquify() {		//成批删除重复元素，效率更高
    	if (_size < 2) return 0;	//平凡列表自然无重复
    	int oldSize = _size;
    	ListNodePosi(T) p = first(); ListNodePosi(T) q;	//p为各区段起点，q为其后继
    	while (trailer != ( q = p->succ ) ) {	//反复考查紧邻的节点
    		if (p->data != q->data) p = q;		//若互异，则转向下一区段
    		else remove(q);	//雷同则删除后者
    	return oldSize - _size;		//列表规模变化量，即被删除元素总数
    }

有序列表查找

//有序列表查找接口
    template <typename T>	//在有序列表内节点p的n个前驱中,找到不大于e的最后者
    ListNodePosi(T) List<T>::search(T const& e, int n, ListNodePosi(T) p) const {
    	while (0 <= n--)	//对于p的最近的n个前驱，从右向左逐个比较
    		if ( ( ( p = p->pred)->data) < e) break;	//直至命中
    	return p;			//返回查找终止的位置
    }

排序器

//统一入口
    template <typename T> void List<T>::sort(ListNodePosi(T) p, int n) {	//列表区间排序
    	switch(rand() % 3)	{	//随机选取排序算法
    		case 1 : insertionSort(p,n); break;	//插入排序
    		case 2 : selectionSort(p,n); break;	//选择排序
    		default : mergeSort(p,n);	break;	//归并排序
    	}
    }

插入排序：

//插入排序
    template <typename T>
    void List<T>::insertionSort( ListNodePosi(T) , int n ) {
    	for ( int r = 0; r < n; r++_)	{//逐一为各节点
    		insertA( search(p->data,r,p), p->data );	//查找不大于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;		//待排序区间为(head,tail)
    	while (1 < n) {	//在至少还剩两个节点之前，在待排序区间内
    		ListNodePosi(T) max = selectMax(head->succ, n);	//找出最大者
    		insertB(tail,remove(max));		//将其移至无序期间末尾(作为有序区间的新元素)
    		tail = tail->pred;	n--;
    	}
    }
    
    //列表最大值的定位
    template <typename T>
    ListNodePosi(T) List<T>::selectMax(ListNodePosi(T) p, int n) {
    	ListNodePosi(T) max = p;	//最大值暂定为首节点p
    	for (ListNodePosi(T) cur = p; 1 < n; n--)	//从首节点出发,将后续节点逐一与max比较
    		if (!lt( (cur = cur->succ)->data, max->data) )	//若当前元素不小于max,则
    			max = cur;	//更新最大元素位置记录
    	return  max;		//返回最大节点的位置
    }

//归并排序....  
//略