Python数据结构与算法(二)–顺序表

587-王同学

发表文章数:79

热门标签

,
首页 » 数据结构 » 正文

顺序表

基本形式

lo + (n – 1)* c

元素外置

用于存储不同类型的数据,数据类型所占字节大小不统一

顺序表中存的是地址

结构

  • 还需要有表头

    存储顺序表的信息,容量,元素个数

    需要先定义好顺序表的大小

  • 数据区

实现方式

  • 直接顺序
  • 分离式

    三个元素,前两个做表头

    最后一个作为地址指向数据

  • 分离式优点

    保留原有表头地址不变

扩充与替换

  • 扩充

    扩充固定多个数目

    倍增的方式:

    用空间换时间

  • 支持扩充的顺序表叫做动态顺序表

顺序表操作

  • 增加元素

表尾插入

O(1)

 

保序元素插入

O(n)

 

非保序的元素插入:

与要插入的位置元素置换

O(1)

 

  • 删除元素

删除队尾

O(1)

 

保序删除

O(n)

 

非保序:

队尾元素换到删除元素位置

O(1)

 

Python中顺序表

list、tuple都是用顺序表实现的

  • list:

    分离式存储

    元素外置存储

    动态顺序表

    初始化:8个元素存储区

    倍增方式:

    4倍

    50000阀值时一倍一倍增加

拜师教育学员文章:作者:587-王同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法(二)–顺序表》 发布于2020-02-06

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录