线性表(1):线性表顺序存储结构的php实现

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

创新互联-专业网站定制、快速模板网站建设、高性价比大连网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式大连网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖大连地区。费用合理售后完善,十多年实体公司更值得信赖。

线性表优点:

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

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

线性表缺点:

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

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

3.造成存储空间的碎片

下面是 php 的实现

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;        	
        }
    }

}

?>

当前名称:线性表(1):线性表顺序存储结构的php实现
文章位置:http://myzitong.com/article/gecihe.html