《数据结构

一:什么是线性表?

  - 线性表定义: 0个 或 多个 数据元素 有限 序列

    - 序列:这个必须有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后驱。一个元素只能有一个前驱/后驱

    - 有限:线性表必须是有限的,无限的只存在于数学中。

  - 线性表元素个数必须是 大于 0, 当 n = 0 时,称为空表

二:线性表抽象模型(线性表通用模型)?

  • 线性表创建/初始化 - 对数据排队
  • 不符合规则,重置为空表
  • 根据位序得到数据
  • 线性表存在
  • 线性表长度
  • 移入/删除 
 
三:什么是 顺序存储结构 ?

  - 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素

  - 存储器中的每个存储元都有自己的编号,这个编号称为地址.

  - 线性表长度应该小于数组长度

  - 在PHP语言中,也可用一维数据来实现.

四:顺序存储结构的优点/缺点?

  - 优点

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

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

  - 缺点

    -  删除/移动需要改变大量的元素

    -  当线性表长度较大,难以确定容量

    -  存储空间的 碎片

五:实现 顺序结构线性表

<?php

class ArrayList 
{
    public $Arr;
    public $Length;

    /**
     * 构建线性表
     */
    public function __construct($Arr)
    {
        $this->Arr    = $Arr;
        $this->Length = count($SqArr);
    }
    
    /**
     * 销毁顺序线性表
     */
    public function Destroy()
    {
        $this->Arr    = NULL;
        $this->Length = 0;
    }

    /**
     * 将线性表重置为空
     */
    public function Init()
    {
        $this->Arr    = [];
        $this->Length = 0;
    }
    
    /**
     * 判断线性表是否为空
     */
    public function Empty()
    {
        if($this->Length == 0) {
            return TRUE;
        }

        return FALSE;
    }

    /**
     * 返回线性表的长度
     */
    public function ListLength(){
        return $this->Length;
    }

    /**
     * 返回线性表中第$index个数据元素
     */
    public function GetIndex($index)
    {
        if($this->Length == 0 || $index < 1 || $index > $this->Length) {
            return 'ERROR';
        }
        return $this->Arr[$index-1];
    }

    /**
     * 在第index的位置插入元素elem
     * 添加之后,其他位置元素也需要随之改变
     */
    public function Insert($index, $elem)
    {
        if($index < 1 || $index > ($this->Length + 1)) {
            return 'ERROR';
        }

        if($index <= $this->Length) {
            for ($i = $this->Length - 1; $i >= $index - 1; $i--) {
                $this->Arr[$i + 1] = $this->Arr[$i];
            }
        }
        $this->Arr[$index - 1] = $elem;
        $this->Length++;
        return 'ok';
    }

    /**
     * 删除第index位置的元素elem
     * 删除之后,其他位置元素也需要随之改变
     */
    public function Delete($index){
        if ($index < 1 || $index > $this->Length + 1) {
            return 'ERROR';
        }
        if ($index < $this->Length) {
            for($i = $index; $i < $this->Length; $i++) {
                $this->Arr[$i - 1] = $this->Arr[$i];
            }
        }
        $this->Length--;
        return $this->Arr[$index - 1];
    }
}
原文地址:https://www.cnblogs.com/25-lH/p/10413340.html