数据结构与算法Day2

2707-小吴同学

发表文章数:43

热门标签

, ,
首页 » 数据结构 » 正文

顺序表的基本形式

1.顺序表结构
包含顺序表表头信息以及数据区两个部分组成 

2.顺序表两种实现形式

顺序表组成部分:表头信息以及数据区

表头信息包括容量以及元素个数

数据区既包含数据

一体式结构:表头信息+数据区 两个区域连接在一起

分离式结构:表头信息一个顺序表 数据区一个顺序表 其中表头信息有一个存储数据区第一个元素的物理地址

两种结构相比之下,分离式结构更适合修改数据,进行操作时时间复杂度比一体式结构要少

3.元素存储区替换

一体式结构在元素要修改时,需要改变整个顺序表的信息,即创建一个新的物理地址来存储新的信息。而分离式结构修改元素信息时,只需要修改好新的数据区信息再将表头信息中数据区地址的信息修改成新的数据区地址。

4.元素扩充策略

两种扩充策略:

①以等差数列的方式扩充容量

这样较为节省存储空间,但操作次数多

②以倍增的方式扩充容量 (1,2,4,8,16…,类似于等比数列)

这样浪费存储空间,但操作次数较少,以空间换时间

5.顺序表操作

顺序表操作有三种形式:

①对尾部数据进行操作 时间复杂度O(1) ②非保序元素操作 时间复杂度O(1) ③保序元素操作 时间复杂度O(n)

5.Python中的顺序表

列表和元组采用了顺序表的实现技术 但tuple是不可变类型 即不变的顺序表 因此不支持改变其内部状态的任何操作 而其他方面 则与list的性质类似

在Python中 列表是采用分离式技术的动态顺序表

在扩充数据方面的策略 列表采用在前50000个数据采用4倍倍增的方式扩充,在50000之后的数据采用扩增一倍的形式。

拜师教育学员文章:作者:2707-小吴同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《数据结构与算法Day2》 发布于2022-01-27

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录