【数据结构(邓俊辉)学习笔记】列表03——有序列表

2024-05-05 23:36

本文主要是介绍【数据结构(邓俊辉)学习笔记】列表03——有序列表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 0. 概述
  • 1. 唯一化
  • 2. 查找
    • 2.1 实现
    • 2.2 顺序查找
    • 2.3 复杂度

0. 概述

介绍下有序列表。
若列表中所有节点的逻辑次序与其大小次序完全一致,则称作有序列表(sorted list)。为保证节点之间可以定义次序,依然假定元素类型T直接支持大小比较,或已重载相关操作符。

1. 唯一化

在这里插入图片描述
算法思想:
有序列表中的雷同节点也必然(在逻辑上)彼此紧邻。利用这一特性。位置指针p和q分别指向每一对相邻的节点,若二者雷同则删除q,否则转向下一对相邻节点。如此反复迭代,直至检查过所有节点。

template <typename T> 
Rank List<T>::uniquify() { //成批剔除重复元素,效率更高if ( _size < 2 ) return 0; //平凡列表自然无重复Rank oldSize = _size; //记录原规模ListNodePosi<T> p = first(); ListNodePosi<T> q; //p为各区段起点,q为其后继while ( trailer != ( q = p->succ ) ) //反复考查紧邻的节点对(p, q)if ( p->data != q->data ) p = q; //若互异,则转向下一区段else remove( q ); //否则(雷同)直接删除后者,不必如向量那样间接地完成删除return oldSize - _size; //列表规模变化量,即被删除元素总数
}

整个过程的运行时间为O(_size) = O(n),线性正比于列表原先的规模。

2. 查找

在这里插入图片描述

2.1 实现

template <typename T> //在有序列表内节点p(可能是trailer)的n个真前驱中,找到不大于e的最后者
ListNodePosi<T> List<T>::search( T const& e, Rank n, ListNodePosi<T> p ) const {do { //初始有:0 <= n <= rank(p) < _size;此后,n总是等于p在查找区间内的秩p = p->pred; n--;  //从右向左  } while ( ( -1 != n ) && ( e < p->data ) ); //逐个比较,直至越界或命中  return p;  //返回最终停止的位置
} //失败时返回区间左边界的前驱(可能是header)——调用者可据此判断查找是否成功

2.2 顺序查找

与无序列表的顺序查找算法几乎一样。

原因:尽管有序列表中的节点已在逻辑上按次序单调排列,但在动态存储策略中,节点的物理地址与逻辑次序毫无关系,故无法像有序向量那样自如地应用减治策略,从而不得不继续沿用无序列表的顺序查找策略。

2.3 复杂度

最好情况下的运行时间为O(1),最坏情况下为O(n)。在等概率的前提下,平均运行时间也是O(n),线性正比于查找区间的宽度。

这篇关于【数据结构(邓俊辉)学习笔记】列表03——有序列表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/962959

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python中DataFrame转列表的最全指南

《Python中DataFrame转列表的最全指南》在Python数据分析中,Pandas的DataFrame是最常用的数据结构之一,本文将为你详解5种主流DataFrame转换为列表的方法,大家可以... 目录引言一、基础转换方法解析1. tolist()直接转换法2. values.tolist()矩阵

Android App安装列表获取方法(实践方案)

《AndroidApp安装列表获取方法(实践方案)》文章介绍了Android11及以上版本获取应用列表的方案调整,包括权限配置、白名单配置和action配置三种方式,并提供了相应的Java和Kotl... 目录前言实现方案         方案概述一、 androidManifest 三种配置方式

python展开嵌套列表的多种方法

《python展开嵌套列表的多种方法》本文主要介绍了python展开嵌套列表的多种方法,包括for循环、列表推导式和sum函数三种方法,具有一定的参考价值,感兴趣的可以了解一下... 目录一、嵌套列表格式二、嵌套列表展开方法(一)for循环(1)for循环+append()(2)for循环+pyPhWiFd

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

python中列表list切分的实现

《python中列表list切分的实现》列表是Python中最常用的数据结构之一,经常需要对列表进行切分操作,本文主要介绍了python中列表list切分的实现,文中通过示例代码介绍的非常详细,对大家... 目录一、列表切片的基本用法1.1 基本切片操作1.2 切片的负索引1.3 切片的省略二、列表切分的高

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操