当前位置:   article > 正文

数据结构——线性表:顺序表、单向链表、循环链表、双向链表_画出顺序表、单链表、双向链表、循环链表数据结构的图示

画出顺序表、单链表、双向链表、循环链表数据结构的图示

 

线性表  

 

是一种数据结构:n个数据元素的有限序列

表示形式: L = (a1,a2...an)

a1是线性表的元素,小写。

n=0时候为空表

数据元素具有相同特性

相邻元素之间存在序偶关系:即有唯一的第一和最后一个元素,除了第一个元素外,每个元素有且只有一个前驱,除最后一个元素外,有且只有一个后继。

定义数据类型构成list:

怎么具体实现

存储结构:顺序、链式

线性表的顺序存储结构:顺序表 (逻辑结构和物理结构相同)

线性表的链式存储结构:链表

 

 

顺序表

顺序:用一组地址连续的存储空间依次存储线性表的数据元素。

顺序表的特点:逻辑结构与存储结构一致。访问每个数据元素花费时间相等。这种方法称为随机存储结构。

表示方法:用一维数组

线性表的基本操作:

初始化、销毁、清空、判断是否为空、求长度、取第i个元素、检索L中的元素e、插入、返回、删除、遍历、...

例如:

 

顺序表的应用:

最大前缀子集:就是相同

解题思路:

 

 

线性表的 链式表示和实现

顺序表的局限:插入和删除都要移动大量元素,耗费时间。

好的地方:随机存储

 

链式存储:用一组任意存储单元存放线性表

存储单元不要求连续:物理结构不反映逻辑结构

不可以随机存取,但插入和删除方便

需要两个域:一个表示数据本身,一个表示数据元素的先后关联。

结点中表示关联的部分为指针。

取元素的话,顺序表更快。 单链表慢一点,要一个个往下找。

 

 单链表取第i个元素: 时间更多

 

顺序表取第i个元素:时间更快

 

单链表的插入操作:

 

循环链表:

 

双向链表:

双向循环链表:

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/765981
推荐阅读
相关标签
  

闽ICP备14008679号