列表

2023-08-18 19:18| 来源: 网络整理| 查看: 265

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

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

列表节点模板类

typedef int Rank; //秩 #define ListNodePosi ListNode* //列表节点位置 template 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 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&, 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 const& L }; //整体复制列表L List() { List 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 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& 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 //操作器 void traverse (VST& ); //遍历，依次实施visit操作(函数对象) }; //List

默认构造方法

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

由秩到位置的转换

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

查找

//无序列表查找接口 template //在无序列表内节点p的n个前驱中，找到等于e的最后者 ListNodePosi(T) List::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 ListNodePosi(T) List::insertAsFirst (T const& e) { _size++; return header->insertAsSucc(e); } //e当作首节点插入 template ListNodePosi(T) List::insertAsLast (T const& e) { _size++; return trailer->insertAsPred(e); } //e当作末节点插入 template ListNodePosi(T) List::insertA (ListNodePosi(T) p, T const& e) { _size++; return p->insertAsSucc(e); } //e当作p的后继插入(After) template ListNodePosi(T) List::insertB (ListNodePosi(T) p, T const& e) { _size++; return p->insertAsPred(e); } //........前驱....(Before) //前插入 template //将e紧靠当前节点之前插入于当前节点所属列表 ListNodePosi(T) ListNode::insertAsPred (T const& e) { ListNodePosi(T) x = new ListNode(e,pred,this); //创建新节点 pred->succ = x; pred = x; //设置正向链接 return x; //返回新节点位置 } //后插入 template //...............后....................... ListNodePosi(T) ListNode::insertAsSucc (T const& e) { ListNodePosi(T) x = new ListNode(e,this,succ); succ->pred = x; succ = x; //设置逆向链接 return x; }

基于复制的构造

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

删除

//删除 template T List::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 List::~List() //列表析构器 { clear(); delete header; delete trailer; } //清空列表,释放头尾哨兵 template int List::clear() {//清空列表 int oldSize = _size; while ( 0 < _size ) remove(header->succ); //反复删除首节点 return oldSize; //返回删除规模 }

唯一化

无序列表：

//无序列表唯一化 template int List::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 int List::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 //在有序列表内节点p的n个前驱中,找到不大于e的最后者 ListNodePosi(T) List::search(T const& e, int n, ListNodePosi(T) p) const { while (0 pred)->data) < e) break; //直至命中 return p; //返回查找终止的位置 }

排序器

//统一入口 template void List::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 void List::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 void List::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 ListNodePosi(T) List::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; //返回最大节点的位置 }

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

【本文地址】

列表

列表

今日新闻

推荐新闻