赞
踩
启示:零个或多个数据元素的有限序列。
首先它是一个序列。元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。线性表强调是有限的。
所以线性表的元素的个数 n (n >= 0)的定义为线性表的长度,当 n = 0 时,称为空表。
线性表的顺序存储结构,指的是用一段地址连续的存储单元一次存储线性表的数据元素。
线性表的顺序存储结构就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。可以用数组来实现顺序存储结构,即把第一个数据元素存到数组下标为 0 的位置中,接着把线性表相邻的元素存储在数组相邻的位置。
描述顺序存储结构需要的三个属性:
数组的长度是存放线性表的存储空间长度,存储分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。
在任意时刻,线性表的长度应该小于等于数组的长度。
插入算法的思路:
实现代码如下(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; } }
删除算法的思路:
实现代码如下(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; } }
优点:
缺点:
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。