Python数据结构(顺序表)

Python数据结构(顺序表)

时间复杂度排序

O(1)< O(logn)< O(n)< O(nlogn)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)
顺序表的形式

image-20231016183002835

图a表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素

的下标是其逻辑地址,而元素存储的物理地址 (实际内存地址)可以通过存储区的起始地址Loc(e0)加上逻

辑地址(第i个元素)与存储单元大小©的乘积计算而得,即:

Loc(ei) = Loc(e0)+ ci

故,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。

如果元素的大小不统一,则须采用图b的元素外置的形式,将实际数据元素另行存储,而顺序表中各单元

位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元

素链接的存储位置,而后顺着链接找到实际存储的数据元素。注意,图b中的c不再是数据元素的大小,

而是存储一个链接地址所需的存储量,这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构

顺序表的结构与实现

顺序表的结构

image-20231016183222890

一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需记录的

信息,即有关表的整体情况的信息,这部分信息主要包括元素存储区的容量和当前表中已有的元素个数

两项.

顺序表的两种基本实现

image-20231016184644039

图a为一体式结构,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整

体形成一个完整的顺序表对象。

一体式结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素

存储区就固定了。

图b为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一

个独立的元素存储区里,通过链接与基本表对象关联

元素存储区替换

一体式结构由于顺序表信息区与数据区连续存储在一起,所以若想更换数据区,则只能整体搬迁,即整

个顺序表对象(指存储顺序表的结构信息的区域)改变了。

分离式结构若想更换数据区,只需将表信息区中的数据区链接地址更新即可,而该顺序表对象不变

元素存储区扩充

采用分离式结构的顺序表,若将数据区更换为存储空间更大的区域,则可以在不改变表对象的前提下对

其数据存储区进行了扩充,所有使用这个表的地方都不必修改。只要程序的运行环境(计算机系统)还有空

闲存储,这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态

顺序表,因为其容量可以在使用中动态变化。

扩充的两种策略

​ 每次扩充增加固定数目的存储位置,如每次扩充增加10个元素位置,这种策略可称为线性增长。

​ 特点:节省空间,但是扩充操作频繁,操作次数多

​ 每次扩充容量加倍,如每次扩充增加一倍存储空间

​ 特点:减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐的方式。

顺序表的操作

增加元素

如图所示,为顺序表增加新元素111的三种方式

image-20231016185558068

a.尾端加入元素,时间复杂度为O(1)

b.非保序的加入元素 (不常见) ,时间复杂度为O(1)

c.保序的元素加入,时间复杂度为O(n)

删除元素

image-20231016185650398

a.删除表尾元素,时间复杂度为O(1)

b.非保序的元素删除(不常见),时间复杂度为O(1)

c.保序的元素删除,时间复杂度为O(n)

Python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术,具有前面讨论的顺序表的所有性质tuple是不

可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类

似。

list的基本实现技术

Python标准类型list就是一种元素个数可变的线性表,可以加入和删除元素,并在各种操作中维持已有元

素的顺序(即保序),而且还具有以下行为特征:

​ 基于下标(位置)的高效元素访问和更新,时间复杂度应该是O(1);

​ 为满足该特征,应该采用顺序表技术,表中元素保存在一块连续的存储区中。

​ 充许任意加入元素,而且在不断加入元素的过程中,表对象的标识(函数id得到的值)不变

​ 为满足该特征,就必须能更换元素存储区,并且为保证更换存储区时list对象的标识id不变,只能采用

​ 分离式实现技术

在Python的官方实现中,list就是一种采用分离式技术实现的动态顺序表。这就是为什么list.append(x)

(或list.insert(len(list),x),即尾部插入) 比在指定位置插入元素效率高的原因。

在Python的官方实现中,list实现采用了如下的策略: 在建立空表(或者很小的表)时,系统分配一块能容纳

8个元素的存储区;在执行插入操作 (insert或append)时,如果元素存储区满就换一块4倍大的存储区。但

如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方

ist实现采用了如下的策略: 在建立空表(或者很小的表)时,系统分配一块能容纳

8个元素的存储区;在执行插入操作 (insert或append)时,如果元素存储区满就换一块4倍大的存储区。但

如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。引入这种改变策略的方

式,是为了避免出现过多空闲的存储位置。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/160362.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

GitHub验证的2FA

一、 起因&#xff1a; GitHub需要双重身份验证 (2FA) 是登录网站或应用时使用的额外保护层。启用 2FA 时&#xff0c;必须使用您的用户名和密码登录&#xff0c;并提供另一种只有您知道或可以访问的身份验证形式。 二、解决&#xff1a; 2.1 这里使用chrome的身份验证插件进…

前端之【数据可视化】

目录 &#x1f31f;前言&#x1f31f;为什么要数据可视化(优点)&#x1f31f;前端数据可视化框架&#x1f31f;Echarts&#x1f31f;Highcharts&#x1f31f;D3 &#x1f31f;数据可视化框架的选择&#x1f31f;写在最后 &#x1f31f;前言 数据可视化主要旨在借助于图形化手段…

浅谈智能照明控制系统应用在城市轨道交通

叶根胜 江苏安科瑞电器制造有限公司 江苏江阴 214405 摘要&#xff1a;在传统的城市轨道交通设计方面&#xff0c;照明设计方案具有一定的弊端。随着计算机技术的发展&#xff0c;智能化技术渐渐步入人们的生活并成为主流&#xff0c;故在城市轨道交通中应用新型的照明控制设…

论文阅读:CenterFormer: Center-based Transformer for 3D Object Detection

目录 概要 Motivation 整体架构流程 技术细节 Multi-scale Center Proposal Network Multi-scale Center Transformer Decoder Multi-frame CenterFormer 小结 论文地址&#xff1a;[2209.05588] CenterFormer: Center-based Transformer for 3D Object Detection (arx…

【软考】9.2 串/数组/矩阵/广义表/树

《字符串》 一种特殊的线性表&#xff0c;数据元素都为字符模式匹配&#xff1a;寻找子串第一次在主串出现的位置 模式匹配算法 1. 暴力破解法&#xff08;布鲁特-福斯算法&#xff09; 主串与子串一个个匹配效率低 2. KMP算法 主串后缀和子串前缀能否找到一样的元素&#xf…

[计算机提升] 用户和用户组

1.1 用户和用户组 1.1.1 用户 用户账户是计算机操作系统中用于标识和管理用户身份的概念。 每个用户都拥有一个唯一的用户账户&#xff0c;该账户包含用户的登录名、密码和其他与用户身份相关的信息。 用户账户通常用于验证用户身份&#xff0c;并授权对系统资源的访问权限。…

用PHP爬取视频代码示例详细教程

以下是一个使用Symfony Panther和PHP进行爬虫的示例程序&#xff0c;用于爬虫企鹅上的视频。请注意&#xff0c;这个示例需要使用https://www.duoip.cn/get_proxy这段代码获取爬虫IP。 <?php // 引入所需的库 require vendor/autoload.php;use Symfony\Component\Panther\P…

【已解决】No Python at ‘D:\Python\python.exe‘

起因&#xff0c;我把我的python解释器&#xff0c;重新移了个位置&#xff0c;导致我在Pycharm中的爬虫项目启动&#xff0c;结果出现这个问题。 然后&#xff0c;从网上查到了这篇博客: 【已解决】No Python at ‘D:\Python\python.exe‘-CSDN博客 但是&#xff0c;按照上述…

LeetCode 137. 只出现一次的数字 II【哈希表;位运算;数字逻辑;DFA】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

尚硅谷Docker核心技术

目录 第1课时 docker_前提知识要求和课程简介第2课时 docker_为什么会出现第3课时 docker_理念第4课时 docker_是什么&#xff1f;第5课时 docker_能干什么第6课时 docker_3要素第7课时 centos6安装Dockercentos7安装Docker第9课时 阿里云镜像加速器配置第10课时 helloworld镜像…

pycharm社区版创建Django项目的一种方式

pycharm社区版创建Django项目 pycharm创建New project安装django&#xff0c;如果安装过可略过安装完成后查看安装情况生成Django项目需要的文件这里注意生成语句后面的 . 不可以省略 生成文件后&#xff0c;框架搭建完成&#xff0c;配置启动我这里在配置完后&#xff0c;报了…

JAVAEE初阶相关内容第十四弹--网络初识

写在前&#xff1a; 这一部分开启网络部分的相关知识&#xff0c;这一弹内容初始网络将主要进行网络相关知识的简单介绍&#xff0c;以及着重介绍协议、协议分层、OSI七层模型、TCP/IP五层模型、封装和分用。 需要认识协议&#xff0c;并知道协议的效果是什么&#xff1b;知道…

RN(React Native)的应用程序在雷电模拟器可以运行,安卓真机运行失败问题解决记录

yarn react-native build-android打包的apk在真机安卓运行提示&#xff1a; Unable to load script . Make sure you re either running Metro ( run npx react - native start ) or that your bundle index . android . bundle is packaged correctly for release . jn…

微服务12-分布式服务理论基础+Seata的认识

文章目录 分布式服务理论基础前言微服务和分布式的区别CAP定理BASE理论 Seata流程&#xff1a;seata部署微服务集成seata 分布式服务理论基础 前言 单体架构&#xff1a; 1.项目过于臃肿&#xff0c;所有服务在一起&#xff0c;一个业务挂了&#xff0c;整个项目就不能用了&…

哪个牌子的电容笔好用?ipad触控笔推荐平价

有哪些电容笔适合学生党入手&#xff1f;苹果Pencil虽然与普通的电容笔&#xff0c;不同的是&#xff0c;这款电容笔同时具有重力传感器和倾斜传感器&#xff0c;而平替电容笔&#xff0c;只有一种倾斜传感器&#xff0c;但在书写方面的体验很不错&#xff0c;可以用来写字&…

【算法|前缀和系列No.4】leetcode238. 除自身以外数组的乘积

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【leetcode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…

如何实现前端数据持久化(LocalStorage、IndexedDB等)?

聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 欢迎来到前端入门之旅&#xff01;感兴趣的可以订阅本专栏哦&#xff01;这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…

MySQL InnoDB引擎深入学习的一天(InnoDB架构 + 事务底层原理 + MVCC)

目录 逻辑存储引擎 架构 概述 内存架构 Buffer Pool Change Buffe Adaptive Hash Index Log Buffer 磁盘结构 System Tablespace File-Per-Table Tablespaces General Tablespaces Undo Tablespaces Temporary Tablespaces Doublewrite Buffer Files Redo Log 后台线程 事务原…

Hadoop 配置 Kerberos 认证

1、安装 Kerberos 服务器和客户端 1.1 规划 服务端&#xff1a; bigdata3 客户端&#xff08;Hadoop集群&#xff09;&#xff1a; bigdata0 bigdata1 bigdata2 192.168.50.7 bigdata0.example.com bigdata0 192.168.50.8 bigdata1.example.com bigdata1 192.168.50.9 b…

4.Python-用Python,Ajax实现MySQL数据库的新增数据

题记 用python&#xff0c;ajax实现mysql数据库的新增数据。以下是一个简单的实例和操作过程。 安装flask模块 pip install flask 安装mysql.connector模块 pip install mysql-connector-python 编写app.py文件 app.py文件如下&#xff1a; 块引用可能显示不完整&#x…