数据结构

1588-刘同学

发表文章数:19

首页 » 数据结构 » 正文

顺序表

顺序表的形式

顺序表基本形式

数据元素本身连续储存,每个元素所占的储存单元大小固定相同,元素的下标是其逻辑地址,而元素储存的物理地址可以通过储存区的起始地址Loc(e0)加上逻辑地址(第i个元素)与储存单元大小©的乘积而得:Loc(ei) = Loc(e0) + c*i
访问指定元素时无需从头遍历,通过计算可获得对应地址,其时间复杂度为O(1)。
数据结构
图为顺序表基本形式

元素外置形式

如果元素大小不统一,则需采用元素外置形式,将实际数据元素另行存储,顺序表中各单元位置保存对应元素的地址信息,图中c不是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。
数据结构
元素外置的顺序表

顺序表的结构与实现

顺序表的结构

顺序表完整信息包括两部分,一是表中的元素集合,二是为实现正确操作而需记录的信息,这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。
数据结构

顺序表的两种基本实现方式

一体式结构

存储表信息的单元与元素储存区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象。整体性强,易于管理,但元素存储区固定。
数据结构

分离式结构

分离式结构表对象里只保存与整个表有关的信息,实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。
数据结构

元素存储区替换

一体式结构替换时,整个顺序表对象都需要搬迁;
分离式结构替换时,只需将表信息区中的数据区链接地址更新即可,顺序表对象不变。

元素存储区扩充

扩充的两种策略:
1.每次扩充增加固定数目的存储位置,也称为线性增长。
特点:节省空间,但操作次数多。
2.每次扩充容量加倍。
特点:减少操作次数,但可能会浪费空间资源。

顺序表的操作

增加元素

数据结构
1.尾端加入元素,时间复杂度为O(1)
2.非保序的加入元素,时间复杂度为O(1)
3.保序的元素加入,时间复杂度为O(n)

删除元素

数据结构
1.删除表尾元素,时间复杂度为O(1)
2.非保序的元素删除,时间复杂度为O(1)
3.保序的元素删除,时间复杂度为O(n)

Python中的顺序表

list的基本实现形式

Python标准类型list是一种元素个数可变的线性表,可以加入和删除元素,并在操作中保序,而且还具有以下特征:
1.基于下标的高效元素访问和更新,表中元素报错在一块连续的存储区中。
2.允许任意加入元素,并且表对象的标识不变。
在Python中,list就是一种采用分离式技术实现的动态顺序表

未经允许不得转载:作者:1588-刘同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构》 发布于2021-02-22

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录