PHP实现的静态链表

<ol class="dp-c">
<li class="alt"><span><span><?php  </span></span></span></li>
<li><span>    <span class="comment">//结点类</span><span> </span></span></li>
<li class="alt"><span>    <span class="keyword">class</span><span> Node{ </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="vars">$next</span><span> = NULL; </span><span class="comment">//下一个结点指针</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$data</span><span> = NULL; </span><span class="comment">//数据</span><span> </span></span></li>
<li><span>    </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> Node(</span><span class="vars">$data</span><span>, </span><span class="vars">$next</span><span> = NULL){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->data = </span><span class="vars">$data</span><span>; </span></span></li>
<li class="alt"><span>            <span class="vars">$next</span><span> && </span><span class="vars">$this</span><span>->next = </span><span class="vars">$next</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getData(){ </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setData(</span><span class="vars">$data</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->data = </span><span class="vars">$data</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getNext(){ </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->next; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setNext(</span><span class="vars">$next</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->next = </span><span class="vars">$next</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>    } </span></li>
<li><span> </span></li>
<li class="alt"><span>    <span class="comment">//单链表类</span><span> </span></span></li>
<li><span>    <span class="keyword">class</span><span> LinkList{ </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="vars">$data_list</span><span> = NULL; </span><span class="comment">//结点集          </span><span> </span></span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> LinkList(</span><span class="vars">$data</span><span> = false){ </span></span></li>
<li><span>            <span class="vars">$this</span><span>->data_list = </span><span class="keyword">array</span><span>(); </span></span></li>
<li class="alt"><span>            <span class="vars">$title</span><span> = </span><span class="keyword">new</span><span> Node(NULL); </span></span></li>
<li><span>            <span class="vars">$this</span><span>->data_list[] = </span><span class="vars">$title</span><span>; </span></span></li>
<li class="alt"><span>           </span></li>
<li><span>            <span class="keyword">if</span><span>(</span><span class="vars">$data</span><span>){ </span></span></li>
<li class="alt"><span>                <span class="keyword">if</span><span>(</span><span class="func">is_array</span><span>(</span><span class="vars">$data</span><span>)){ </span></span></li>
<li><span>                    <span class="vars">$this</span><span>->addMoreData(</span><span class="vars">$data</span><span>); </span></span></li>
<li class="alt"><span>                }<span class="keyword">else</span><span>{ </span></span></li>
<li><span>                    <span class="vars">$this</span><span>->addData(</span><span class="vars">$data</span><span>); </span></span></li>
<li class="alt"><span>                } </span></li>
<li><span>            } </span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//返回第N个结点的值</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getNodeByNumber(</span><span class="vars">$number</span><span>){ </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data_list[</span><span class="vars">$this</span><span>->findKeyByNumber(</span><span class="vars">$number</span><span>)]->getData(); </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//添加一组结点</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> addMoreData(</span><span class="vars">$datas</span><span>){ </span></span></li>
<li><span>            <span class="keyword">foreach</span><span>(</span><span class="vars">$datas</span><span> </span><span class="keyword">as</span><span> </span><span class="vars">$value</span><span>){ </span></span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->addData(</span><span class="vars">$value</span><span>); </span></span></li>
<li><span>            } </span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//添加结点统一入口,供外面调用</span><span> </span></span></li>
<li class="alt"><span>        <span class="comment">//$number 添加在第几个结点的后面</span><span> </span></span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> addData(</span><span class="vars">$data</span><span>, </span><span class="vars">$number</span><span> = false){ </span></span></li>
<li class="alt"><span>            <span class="vars">$node</span><span> = </span><span class="keyword">new</span><span> Node(</span><span class="vars">$data</span><span>); </span></span></li>
<li><span>            <span class="keyword">if</span><span>(</span><span class="vars">$number</span><span> === FALSE  </span><span class="vars">$number</span><span> == </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->data_list)){ </span></span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->insertLastNode(</span><span class="vars">$node</span><span>); </span></span></li>
<li><span>            }<span class="keyword">elseif</span><span>(</span><span class="vars">$number</span><span> > </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->data_list)){ </span></span></li>
<li class="alt"><span>                <span class="keyword">return</span><span> false; </span></span></li>
<li><span>            }<span class="keyword">else</span><span>{ </span></span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->insertNode(</span><span class="vars">$node</span><span>, </span><span class="vars">$number</span><span>); </span></span></li>
<li><span>            } </span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//插入一个结点到最后</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> insertLastNode(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span>                <span class="vars">$node</span><span>->setNext(NULL);              </span></span></li>
<li class="alt"><span>                <span class="vars">$lastKey</span><span> = </span><span class="vars">$this</span><span>->findLastNode(); </span></span></li>
<li><span>                <span class="vars">$insert_key</span><span> = </span><span class="vars">$this</span><span>->insertNodeIntoArray(</span><span class="vars">$node</span><span>); </span></span></li>
<li class="alt"><span>                <span class="vars">$this</span><span>->data_list[</span><span class="vars">$lastKey</span><span>]->setNext(</span><span class="vars">$insert_key</span><span>); </span></span></li>
<li><span>        }     </span></li>
<li class="alt"><span>        <span class="comment">//插入一个结点</span><span> </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> insertNode(</span><span class="vars">$node</span><span>, </span><span class="vars">$number</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$insert_number</span><span> = </span><span class="vars">$this</span><span>->findKeyByNumber(</span><span class="vars">$number</span><span>);     </span></span></li>
<li><span>            <span class="vars">$node</span><span>->setNext(</span><span class="vars">$this</span><span>->data_list[</span><span class="vars">$insert_number</span><span>]->getNext()); </span></span></li>
<li class="alt"><span>            <span class="vars">$insert_key</span><span> = </span><span class="vars">$this</span><span>->insertNodeIntoArray(</span><span class="vars">$node</span><span>); </span></span></li>
<li><span>            <span class="vars">$this</span><span>->data_list[</span><span class="vars">$insert_number</span><span>]->setNext(</span><span class="vars">$insert_key</span><span>); </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//查找第N个结点对应的数组key</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> findKeyByNumber(</span><span class="vars">$number</span><span>){ </span></span></li>
<li><span>            <span class="vars">$i</span><span> = </span><span class="vars">$key</span><span> = 0; </span></span></li>
<li class="alt"><span> </span></li>
<li><span>            <span class="keyword">while</span><span>(</span><span class="vars">$i</span><span> <span class="vars">$number</span><span>){ </span></span></span></li>
<li class="alt"><span>                <span class="vars">$key</span><span> = </span><span class="vars">$this</span><span>->data_list[</span><span class="vars">$key</span><span>]->getNext(); </span></span></li>
<li><span>                <span class="vars">$i</span><span> ++; </span></span></li>
<li class="alt"><span>            } </span></li>
<li><span>          </span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$key</span><span>; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>        <span class="comment">//将结点加入数组</span><span> </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> insertNodeIntoArray(</span><span class="vars">$node</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="vars">$this</span><span>->data_list[] = </span><span class="vars">$node</span><span>;      </span></span></li>
<li><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->getLastKey(); </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span>        <span class="comment">//删除结点</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> deleteNode(</span><span class="vars">$number</span><span>){ </span></span></li>
<li><span>            <span class="keyword">if</span><span>(</span><span class="vars">$number</span><span> == 0  </span><span class="vars">$number</span><span> > </span><span class="func">count</span><span>(</span><span class="vars">$this</span><span>->data_list)){ </span></span></li>
<li class="alt"><span>                <span class="keyword">return</span><span> false; </span></span></li>
<li><span>            } </span></li>
<li class="alt"><span> </span></li>
<li><span>            <span class="vars">$pre_key</span><span> = </span><span class="vars">$this</span><span>->findKeyByNumber(</span><span class="vars">$number</span><span> - 1); </span></span></li>
<li class="alt"><span>            <span class="vars">$key</span><span> = </span><span class="vars">$this</span><span>->data_list[</span><span class="vars">$pre_key</span><span>]->getNext(); </span></span></li>
<li><span> </span></li>
<li class="alt"><span>          <span class="vars">$this</span><span>->data_list[</span><span class="vars">$pre_key</span><span>]->setNext(</span><span class="vars">$this</span><span>->data_list[</span><span class="vars">$key</span><span>]->getNext()); </span></span></li>
<li><span>            unset(<span class="vars">$this</span><span>->data_list[</span><span class="vars">$key</span><span>]); </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="comment">//查找某结点的前一个结点</span><span> </span></span></li>
<li><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> getPreNodeKey(</span><span class="vars">$key</span><span>){ </span></span></li>
<li class="alt"><span>            <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->data_list </span><span class="keyword">as</span><span> </span><span class="vars">$k</span><span>=></span><span class="vars">$v</span><span>){ </span></span></li>
<li><span>                <span class="keyword">if</span><span>(</span><span class="vars">$v</span><span>->getNext() == </span><span class="vars">$key</span><span>){ </span></span></li>
<li class="alt"><span>                    <span class="keyword">return</span><span> </span><span class="vars">$k</span><span>;   </span></span></li>
<li><span>                } </span></li>
<li class="alt"><span>            } </span></li>
<li><span>            <span class="keyword">return</span><span> false; </span></span></li>
<li class="alt"><span>        } </span></li>
<li><span> </span></li>
<li class="alt"><span>        <span class="comment">//打印链表</span><span> </span></span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getData_list(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data_list; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="comment">//返回数组的最后一个键</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> getLastKey(){ </span></span></li>
<li><span>            <span class="func">end</span><span>(</span><span class="vars">$this</span><span>->data_list); </span></span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> key(</span><span class="vars">$this</span><span>->data_list); </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span> </span></li>
<li><span>        <span class="comment">//判断某个键值是否存在</span><span> </span></span></li>
<li class="alt"><span>        <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> ifExistKey(</span><span class="vars">$key</span><span>){ </span></span></li>
<li><span>            <span class="keyword">if</span><span>(</span><span class="func">array_key_exists</span><span>(</span><span class="vars">$key</span><span>, </span><span class="vars">$this</span><span>->data_list)){ </span></span></li>
<li class="alt"><span>                <span class="keyword">return</span><span> true; </span></span></li>
<li><span>            }           </span></li>
<li class="alt"><span>            <span class="keyword">return</span><span> false; </span></span></li>
<li><span>        } </span></li>
<li class="alt"><span>        <span class="comment">//查找尾结点</span><span> </span></span></li>
<li><span>        <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> findLastNode(){ </span></span></li>
<li class="alt"><span>            <span class="keyword">foreach</span><span>(</span><span class="vars">$this</span><span>->data_list </span><span class="keyword">as</span><span> </span><span class="vars">$key</span><span>=></span><span class="vars">$value</span><span>){ </span></span></li>
<li><span>                <span class="keyword">if</span><span>(</span><span class="vars">$value</span><span>->getNext() === NULL){ </span></span></li>
<li class="alt"><span>                    <span class="keyword">return</span><span> </span><span class="vars">$key</span><span>; </span></span></li>
<li><span>                } </span></li>
<li class="alt"><span>            } </span></li>
<li><span>        } </span></li>
<li class="alt"><span>    } </span></li>
<li><span>?> </span></li>
</ol>