2017年09月23日 星期六

数据结构(二)线性表的顺序存储(顺序表)

data struct 耗子睡着了 47阅读 0评论

顺序表就是顺序存储的线性表。

顺序存储是用一组地址连续的存储空间依次存放线性表中的各个元素的存储结构。

特点

  • 逻辑上相邻的数据元素,在物理存储上也相邻
  • 存储密度高,需要预先分配空间,容易造成空间浪费
  • 便于随机存取
  • 不便于插入和删除,会引起大量数据元素的移动、

描述

定义类,实现IList接口。(参见:https://chenzhihao.cc/archives/394#title-1

类定义

置空

置空链表,只需要将标示长度设为0即可。

叛空

求长度

某位置插入元素

  • 第一步:判满。判断当前顺序表是否已满,若满则抛出异常。
  • 第二步:临界点。判断插入点是否超出临界点,若超出则抛出异常。
  • 第三步:窜位置。将插入点之后的所有元素向后窜一位。
  • 第四步:插入。将元素放入插入点位置。
  • 第五步:重置长度。长度加一。

某位置删除元素

  • 第一步:判空。判断线性表是否为空。
  • 第二步:临界点。判断删除位置是否超出临界点。若是则抛出异常。
  • 第三步:删除。将删除元素后的所有元素前移。
  • 第四步:重置长度。长度减一。

根据位置获取元素内容

根据元素内容获取位置

遍历

总结

  1. 顺序表是线性表的顺序存储结构的实现,底层实现常用数组
  2. 对于顺序表,便于随机存取,不便于插入和删除,因插入和删除会造成大量数据元素的移动。
  3. 对于有n个元素的顺序表来说:插入“叛满”,删除“叛空”。
  4. 顺序表的合法操作区域:0 ≤ i ≤ length-1
  5. 对于有n个元素的顺序表来说,在第i位置插入元素,会引起n-i个元素移动,所以时间复杂度为O(n)
  6. 对于有n个元素的顺序表来说,删除第i位置的元素,会引起n-i-1个元素移动,所以时间复杂度是O(n)
  7. 对于查找指定位置上的元素的值,使用随机存取的方式,时间复杂度为O(1)
  8. 对于查找指定内容的元素在顺序表上的位置,使用遍历操作。若要查找顺序表中第i个位置上的数据元素值为x的元素,需要比较i+1次;若顺序表中不存在值为x的元素,此时为最坏情况,需要比较n次。因此对于该操作的平均时间复杂度为O(n)

经过线性表的顺序存储结构的学习,我对线性表的实现和关键操作的逻辑有了更深入的理解。顺序表在Java类库中也有出现,就是ArrayList类。该类有多个构造方法,其中默认构造方法会初始化一个容量为为10的数组,超出该容量后会自动构建一个新的数组,并将就数组内的元素全部克隆到新数组中。新数组的大小是动态分配的,根据调试可知,ArrayList内部数组容量超出10之后,会以以下顺序增长10->16->25->38->58->88->..,然而在这个示例中我并没有这样的设计,只为清晰的描述顺序表的存储结构和存取逻辑。

数据结构系列的下一篇会记录线性表的链式存储结构的实现过程。

本示例源码地址:点击查看

与本文相关的文章

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址