本文主要是介绍【数据结构(邓俊辉)学习笔记】列表01——从向量到列表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 0.概述
- 1. 从向量到列表
- 1.1 从静态到动态
- 1.2 从向量到列表
- 1.3 从秩到位置
- 1.4 列表
- 2. 接口
- 2.1 列表节点
- 2.1.1 ADT接口
- 2.1.2 ListNode模板类
- 2.2 列表
- 2.2.1 ADT接口
- 2.2.2 List模板类
0.概述
学习了向量,再介绍下列表。先介绍下列表里的概念和语义,这个对理解列表接口还是比较重要的。
1. 从向量到列表
1.1 从静态到动态
1.2 从向量到列表
注意:首末节点描述。
1.3 从秩到位置
对数据结构的访问方式,应与其存储策略相一致。此时,既然继续延用循秩访问的方式已非上策,就应更多地习惯于通过位置,来指代并访问动态存储结构中的数据元素。
1.4 列表
与向量一样,列表也是由具有线性逻辑次序的一组元素构成的集合:
~~~~~~~~~~~~~~~~~~~~~~~~ L = { a0, a1, …, an-1 }
列表是链表结构的一般化推广,其中的元素称作节点(node),分别由特定的位置或链接指代。与向量一样,在元素之间,也可定义前驱、直接前驱,以及后继、直接后继等关系;相对于任意元素,也有定义对应的前缀、后缀等子集。
2. 接口
2.1 列表节点
2.1.1 ADT接口
###
2.1.2 ListNode模板类
using Rank = unsigned int; //秩template <typename T> struct ListNode;
template <typename T> using ListNodePosi = ListNode<T>*; //列表节点位置template <typename T>
struct ListNode { //列表节点模板类(以双向链表形式实现)
// 成员T data; ListNodePosi<T> pred, succ; //数值、前驱、后继
// 构造函数ListNode() {} //针对header和trailer的构造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 ); //紧随当前节点之后插入新节点
};
2.2 列表
2.2.1 ADT接口
领会下宏观接口,具体接口后面会做介绍。
分别针对有序和无序列表,提供了去重操作的两个版本(deduplicate()和uniquify()),以及查找操作的两
个版本(find()和search())。与向量一样,有序列表的唯一化,比无序列表效率更高。
由于只能通过位置指针以局部移动的方式访问节点,尽管有序列表中节点在逻辑上始终按照大小次序排列,其查找操作的效率并没有实质改进。
二者的效率完全一致:在最好情况下,均只需O(1)时间;在最坏情况下,均需要O(n)时间;平均而言,二者均需O(n)时间。
2.2.2 List模板类
头尾接口对外不可见,非常重要。
#pragma once#include "listNode.h" //引入列表节点类template <typename T> class List { //列表模板类private:Rank _size; ListNodePosi<T> header, trailer; //规模、头哨兵、尾哨兵protected:void init(); //列表创建时的初始化Rank clear(); //清除所有节点void copyNodes( ListNodePosi<T>, Rank ); //复制列表中自位置p起的n项ListNodePosi<T> merge( ListNodePosi<T>, Rank, List<T>&, ListNodePosi<T>, Rank ); //归并void mergeSort( ListNodePosi<T>&, Rank ); //对从p开始连续的n个节点归并排序void selectionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点选择排序void insertionSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点插入排序void radixSort( ListNodePosi<T>, Rank ); //对从p开始连续的n个节点基数排序public:
// 构造函数List() { init(); } //默认List( List<T> const& L ); //整体复制列表LList( List<T> const& L, Rank r, Rank n ); //复制列表L中自第r项起的n项List( ListNodePosi<T> p, Rank n ); //复制列表中自位置p起的n项// 析构函数~List(); //释放(包含头、尾哨兵在内的)所有节点
// 只读访问接口Rank size() const { return _size; } //规模bool empty() const { return _size <= 0; } //判空ListNodePosi<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 ); } //将头、尾节点等同于NULLListNodePosi<T> find( T const& e ) const //无序列表查找{ return find( e, _size, trailer ); }ListNodePosi<T> find( T const& e, Rank n, ListNodePosi<T> p ) const; //无序区间查找ListNodePosi<T> search( T const& e ) const //有序列表查找{ return search( e, _size, trailer ); }ListNodePosi<T> search( T const& e, Rank n, ListNodePosi<T> p ) const; //有序区间查找ListNodePosi<T> selectMax( ListNodePosi<T> p, Rank 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> insert( ListNodePosi<T> p, T const& e ); //将e当作p的后继插入ListNodePosi<T> insert( T const& e, ListNodePosi<T> p ); //将e当作p的前驱插入T remove( ListNodePosi<T> p ); //删除合法位置p处的节点,返回被删除节点void merge( List<T>& L ) { merge( header->succ, _size, L, L.header->succ, L._size ); } //全列表归并void sort( ListNodePosi<T>, Rank ); //列表区间排序void sort() { sort( first(), _size ); } //列表整体排序Rank dedup(); //无序去重Rank uniquify(); //有序去重void reverse(); //前后倒置(习题)
// 遍历void traverse( void ( * )( T& ) ); //依次实施visit操作(函数指针)template <typename VST> void traverse( VST& ); //依次实施visit操作(函数对象)
}; //List#include "List_implementation.h"
template <typename T>
void List<T>::init() { //列表初始化,在创建列表对象时统一调用header = new ListNode<T>; trailer = new ListNode<T>; //创建头、尾哨兵节点header->succ = trailer; header->pred = NULL; //向前链接trailer->pred = header; trailer->succ = NULL; //向后链接_size = 0; //记录规模
}
这篇关于【数据结构(邓俊辉)学习笔记】列表01——从向量到列表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!