PHP实现线性表的顺序存储结构

<span><span>class</span><span>SqList</span>
{</span><span>public</span><span>$elem</span>;
    <span>public</span><span>$length</span>;
    <span>public</span><span>$size</span>;
}

<span><span>class</span><span>Linear</span>
{</span><span>const</span> LIST_INIT_SIZE = <span>10</span>;
    <span>const</span> LIST_INCREMENT = <span>5</span>;
    <span>private</span><span>$list</span> = <span>null</span>;

    <span>/**
     * 构造一个空的线性表
     */</span><span>public</span><span><span>function</span><span>initList</span><span>()</span>
    {</span><span>$this</span>-><span>list</span> = <span>new</span> SqList();
        <span>$this</span>-><span>list</span>->elem = <span>array</span>();
        <span>$this</span>-><span>list</span>->length = <span>0</span>;
        <span>$this</span>-><span>list</span>->size = <span>self</span>::LIST_INIT_SIZE;
        <span>return</span><span>true</span>;
    }

    <span>/**
     * 销毁线性表
     */</span><span>public</span><span><span>function</span><span>destoryList</span><span>()</span>
    {</span><span>if</span> (is_object(<span>$this</span>-><span>list</span>)) {
            <span>$this</span>-><span>list</span> = <span>null</span>;
        }
    }

    <span>/**
     * 是否为空表
     */</span><span>public</span><span><span>function</span><span>listEmpty</span><span>()</span>
    {</span><span>if</span> (is_object(<span>$this</span>-><span>list</span>)) {
            <span>return</span><span>$this</span>-><span>list</span>->length == <span>0</span> ? <span>true</span> : <span>false</span>;
        }
    }

    <span>/**
     * 返回元素个数
     */</span><span>public</span><span><span>function</span><span>listLength</span><span>()</span>
    {</span><span>if</span> (is_object(<span>$this</span>-><span>list</span>)) {
            <span>return</span><span>$this</span>-><span>list</span>->length;
        }
    }

    <span>/**
     * 获取指定位置的元素
     */</span><span>public</span><span><span>function</span><span>getElem</span><span>(<span>$i</span>)</span>
    {</span><span>if</span> (<span>$i</span> < <span>1</span> || <span>$i</span> > <span>$this</span>-><span>list</span>->length + <span>1</span>) {
            <span>return</span><span>false</span>;
        }
        <span>return</span><span>$this</span>-><span>list</span>->elem[<span>$i</span>-<span>1</span>];
    }

    <span>/**
     * 在指定位置插入元素
     */</span><span>public</span><span><span>function</span><span>listInsert</span><span>(<span>$i</span>, <span>$e</span>)</span>
    {</span><span>if</span> (<span>$i</span> < <span>1</span> || <span>$i</span> > <span>$this</span>-><span>list</span>->length + <span>1</span>) {
            <span>return</span><span>false</span>;
        }
        <span>if</span> (<span>$this</span>-><span>list</span>->length >= <span>$this</span>-><span>list</span>->size) {
            <span>$this</span>-><span>list</span>->size += <span>self</span>::LIST_INCREMENT;
        }
        <span>for</span> (<span>$j</span> = <span>$this</span>-><span>list</span>->length; <span>$j</span> >= <span>$i</span>; <span>$j</span>--) {
            <span>$this</span>-><span>list</span>->elem[<span>$j</span>] = <span>$this</span>-><span>list</span>->elem[<span>$j</span>-<span>1</span>];
        }
        <span>$this</span>-><span>list</span>->elem[<span>$i</span>-<span>1</span>] = <span>$e</span>;
        <span>$this</span>-><span>list</span>->length++;
    }

    <span>/**
     * 删除指定位置数据元素
     */</span><span>public</span><span><span>function</span><span>listDelete</span><span>(<span>$i</span>)</span>
    {</span><span>if</span> (<span>$i</span> < <span>1</span> || <span>$i</span> > <span>$this</span>-><span>list</span>->length) {
            <span>return</span><span>false</span>;
        }
        <span>$data</span> = <span>$this</span>-><span>list</span>->elem[<span>$i</span>-<span>1</span>];
        <span>for</span> (<span>$j</span> = <span>$i</span> -<span>1</span>; <span>$j</span> < <span>$this</span>-><span>list</span>->length -<span>1</span>; <span>$j</span>++) {
            <span>$this</span>-><span>list</span>->elem[<span>$j</span>] = <span>$this</span>-><span>list</span>->elem[<span>$j</span>+<span>1</span>];
        }
        <span>unset</span>(<span>$this</span>-><span>list</span>->elem[<span>$this</span>-><span>list</span>->length-<span>1</span>]);
        <span>$this</span>-><span>list</span>->length--;
        <span>return</span><span>$data</span>;
    }
}