当前位置:   article > 正文

数据结构学习总结 ——3.线性表一顺序存储结构_顺序存储结构线性表的长度是其所占用存储空间的个数

顺序存储结构线性表的长度是其所占用存储空间的个数

数据结构学习总结 ——3.线性表一顺序存储结构

启示:零个或多个数据元素的有限序列。


3.1线性表的定义

	首先它是一个序列。元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。线性表强调是有限的。
	所以线性表的元素的个数 n (n >= 0)的定义为线性表的长度,当 n = 0 时,称为空表。
  • 1
  • 2

3.2 线性表的顺序存储结构

	线性表的顺序存储结构,指的是用一段地址连续的存储单元一次存储线性表的数据元素。
  • 1
3.2.1 顺序存储方式
	线性表的顺序存储结构就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。可以用数组来实现顺序存储结构,即把第一个数据元素存到数组下标为 0 的位置中,接着把线性表相邻的元素存储在数组相邻的位置。
  • 1

描述顺序存储结构需要的三个属性:

  • 存储空间的起始位置 : 数组 data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量 : 数组长度 size
  • 线性表的当前长度:length
3.2.2 数据长度与线性表长度区别
	数组的长度是存放线性表的存储空间长度,存储分配后这个量一般是不变的。
	
	线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。

	在任意时刻,线性表的长度应该小于等于数组的长度。
  • 1
  • 2
  • 3
  • 4
  • 5
3.2.3 顺序存储结构的插入与删除
插入操作

插入算法的思路:

  • 如果插入位置不合理,抛出异常;
  • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
  • 从最后一个元素开始向前遍历到第 i 个位置,分别将它们都向后移动一个位置;
  • 将要插入元素填入位置 i 处;
  • 表长加 1;

实现代码如下(PHP):

//线性表
class List
{
	protected $len;			//线性表的长度
	protected $list;		//线性表的数据
	protected $maxSize;		//线性表最大长度

	/**
	 *	初始化线性表
	 *	@params int $size 最大长度
	 */
	public function initList($size)
	{
		$this->list = [];
		$this->len = 0;
		$this->maxSize = $size;
	}

	public function listInsert($i, $elem)
	{
		//线性表已满
		if ($this->len == $this->maxSize) {
			return false;
		}
		//插入位置不正确
		if ($i < 1 || $i > $this->len + 1) {
			return false;
		}
		
		//插入位置不在尾部
		if($i <= $this->len) {
			for ($k = $this->len - 1; $k >= $i - 1; $k--) {
				$this->list[$k + 1] = $this->list[$k];
			}
		}
		
		$this->list[$i - 1] = $elem;
		$this->len++;
		return true;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
删除操作

删除算法的思路:

  • 如果删除位置不合理,抛出异常;
  • 取出删除元素;
  • 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
  • 表长减 1;

实现代码如下(PHP):

//线性表
class List
{
	protected $len;			//线性表的长度
	protected $list;		//线性表的数据
	protected $maxSize;		//线性表最大长度

	/**
	 *	初始化线性表
	 *	@params int $size 最大长度
	 */
	public function initList($size)
	{
		$this->list = [];
		$this->len = 0;
		$this->maxSize = $size;
	}

	public function listDelete($i)
	{
		//线性表为空
		if ($this->len == 0) {
			return false;
		}
		//删除位置不正确
		if ($i < 1 || $i > $this->len) {
			return false;
		}
		
		//删除的不是最后一个元素,其后元素都向前移动一位
		if($i < $this->len) {
			for ($k = $i; $k < $this->len; $k++) {
				$this->list[$k - 1] = $this->list[$k];
			}
		}
		
		unset($this->list[$i - 1]);
		$this->len--;
		return true;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
3.2.4 线性表顺序存储结构的优缺点

优点:

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任意位置的元素

缺点:

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时,难以确定存储空间的容量
  • 造成存储空间的 “碎片
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/700716
推荐阅读
相关标签
  

闽ICP备14008679号