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

作者: 白云飞 分类: php 发布时间: 2017-06-11 14:18 阅读:

线性表是最基本、最简单、也是最常用的一种数据结构。线性表有 0 个或多个数据元素的有限序列。线性表是有长度限制的。且是从 1 开始的。在这里,我们用php 的一维数组来模拟线性表的一些操作。当然,php的数组是从 0 开始的,数组和线性表的对应关系是 线性表的第一个元素 是 数组的第 0 个元素,以此类推。废话不多说,看看代码:

SqList.php

<?php

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

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

    /**
     * 判断线性表是否为空
     * @return bool
     */
	public function listEmpty()
	{
		return empty($this->list);
	}

    /**
     * 清空线性表
     */
	public function clearList()
	{
		$this->list = [];
                $this->len = 0;
	}

    /**
     * 获取线性表指定位置元素
     * @param $i
     * @return null
     */
	public function getElem($i)
	{
		return isset($this->list[$i - 1]) ? $this->list[$i - 1] : null;
	}

    /**
     * 定位线性表中的元素
     * @param $elem
     * @return bool
     */
	public function locateElem($elem)
	{
		foreach($this->list as $v){
		    if($v == $elem){
		        return true;
                    }
               }

              return false;
	}

    /**
     * 向线性表指定的位置插入元素
     * @param $i
     * @param $elem
     */
	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;
	}

    /**
     * 删除线性表指定位置的元素
     * @param $i
     */
	public function listDelete($i)
	{
	    // 线性表为空
	   if(0 == $this->len){
		    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;
	}

    /**
     * 获取线性表的长度
     * @return mixed
     */
	public function listLength()
	{
		return $this->len;
	}

    /**
     * 获取整个线性表
     * @return mixed
     */
    public function getList()
    {
        return $this->list;
    }
}

注释的比较详尽,我也就不过多的说了。线性表的几种常见操作都有实现。看一下,如何测试吧:

demo.php

<?php
require 'SqlList.php';

$list = new SqList();

// 初始化长度为6的线性表
$list->initList(6);

// 插入 3 个元素
$list->listInsert(1, 2);
$list->listInsert(2, 4);
$list->listInsert(3, 6);

// 显示线性表
echo "初始化后的线性表:<br/>";
print_r($list->getList());
echo "<hr/>";

// 获取第 2 个元素
echo "线性表第2个元素是:" . $list->getElem(2);
echo "<hr/>";

// 查询 3 和 6 是否在线性表中
echo "3是否在线性表中" . var_dump($list->locateElem(3));
echo "<br/>";
echo "6是否在线性表中" . var_dump($list->locateElem(6));
echo "<hr/>";

// 向第 2 位插入一个元素
echo "向第 2 位插入元素 3:<br/>";
$list->listInsert(2, 3);
print_r($list->getList());
echo "<hr/>";

// 获取线性表长度
echo "线性表的长度是:" . $list->listLength();
echo "<hr/>";

// 删除第 3 位元素
echo "删除第 3 位元素:<br/>";
$list->listDelete(3);
print_r($list->getList());
echo "<hr/>";

// 清空线性表
$list->clearList();
echo "线性表长度: " . $list->listLength() . "<br/>";
print_r($list->getList());

 

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。