线性表（1）：线性表顺序存储结构的php实现

线性表的顺序存储结构 (sequential list)，也叫顺序表中，存和读数据时间复杂度为 O(1)，插入和删除数据时间复杂度为 O(n)。

线性表优点：

1.无需为表中元素之间的逻辑关系而额外增加存储空间

2.可以快速存取表中任一位置的元素

线性表缺点：

1.插入和删除操作需要移动大量元素

2.当线性表长度变化较大时，难以确定存储空间的容量 （这个对 php 不是问题，而且貌似php只能申请动态数组。。。）

3.造成存储空间的碎片

下面是 php 的实现

<?php  /**  * @author Dongjie LIU  * @version chinese  *   *顺序表 (sequential list)：线性表的顺序存储结构  *需要3个属性，数组，最大存储容量，线性表长度，  *但由于php 特性，无法在初始化时定义数组长度，  *故只定义数组一个属性  *   * 线性表基本操作包括  * 1.线性表表初始化操作 __contruct()  * 2.清空线性表 __destruct()  * 3.判断线性表是否为空 listEmpty()  * 4.返回线性表元素个数 listLength()  * 5.根据下标返回线性表中的某个元素 getElem()  * 6.返回线性表中某个元素的位置 locateElem()  * 7.根据给定位置在线性表中插入元素 listInsert()  * 8.根据给定位置在线性表中删除元素 listDelete()  */ class seqList{     private $seq_list; //顺序表     /**      * 顺序表初始化      *       * @param mixed $seq_list      * @return void      */     public function __construct($seq_list=array()){     	$this->seq_list = $seq_list;     }     /**      * 清空顺序表      *       * @return void      */     public function __destruct(){         unset($this->seq_list);     }     /**      * 判断顺序表是否为空      *      * @return bool 为空返回true，否则返回false      */     public function listEmpty(){         return empty($this->seq_list);     }     /**      * 返回顺序表元素个数      *      * @return int      */     public function listLength(){     	return count($this->seq_list);     }          /**      * 返回顺序表中下标为i的元素值      *       * @param int i       * @return mixed 如找到返回元素值，否则返回false      */     public function getElem($i){         if ($i > 0 && $i <= $this->listLength()) {         	return $this->seq_list[$i-1];         }else{         	return false;         }     }     /**      * 在顺序表中查找与给定值 $value 相等的元素,      * 这里没有考虑 $value 为数组的情况      *      * @param mixed $value      * @return mixed 如查找成功，返回该元素在表中序号，否则返回 0      */     public function locateElem($value){     	if (in_array($value, $this->seq_list)) {     	$i = 0;             foreach ($this->seq_list as $key=>$val) {             	if (strcmp($value, $val) === 0){             	//若存在多个元素与匹配值相等             	if ($i == 0) {             	$i = $key + 1;             	}else{                         $i .= ",".($key + 1);             	}             	}                }             return $i;     	}else{     	return false;     	}     }     /**      * 在指定位置 i 插入一个新元素 $value      *      * @param int $i      * @param mixed $value      * @return bool 插入成功返回 true, 否则返回 false      */     public function listInsert($i, $value){     	//三种情况：插入位置不合理，元素加在末尾和其他         if ($i > $this->listLength()+1 || $i < 1) {         	return false;         }elseif ($i == $this->listLength()+1) {         	$this->seq_list[$i-1] = $value;         }else{         	//从 $i-1 到最后的元素位置向后移动一位             for ($k = $this->listLength()-1; $k >= $i-1; $k--) {                 $this->seq_list[$k+1] = $this->seq_list[$k];             }             $this->seq_list[$i-1] = $value;         }         return true;     }     /**      * 删除顺序表中 i 位置的元素， 并用 $value 返回其值      *       * @param int $i       * @return mixed 删除成功返回 $value，否则返回 false      */     public function listDelete($i){     	//两种情况：插入位置不合理和其他         if ($i <= 0 || $i > $this->listLength()) {         	return false;         }else{         	$value = $this->seq_list[$i-1];         	for ($k=$i-1; $k < $this->listLength()-1; $k++) {          	$this->seq_list[$k] = $this->seq_list[$k+1];         	}         	unset($this->seq_list[$this->listLength()-1]);         	return $value;                 }     } } ?>