PHP实现的静态链表
- WBOY原創
- 2016-06-21 08:53:131462瀏覽
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>
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn