PHP 实战 : 静态单链表

Jonny 自創文章 PHP 2018-01-08 1,497 0 0

在《数据结构 : 静态单链表 (C++ 描述)》中讲过, 静态单链表主要是面向没有指针的语言, PHP 就是一个很好的例子. 不过, PHP 中是存在引用 "&" 的, 所以改造代码变得非常简单

实战中将会用到的 PHP 语法 :

面向对象编程 (接口、继承、修饰符、属性与方法、父类调用)

数组

引用

条件判断

循环

命名空间

初次之外, 还有文件的包含和系统自带的函数

其中, 接口和命名空间是之前没有讲过的, 这个在之后会有

这里就不再累赘具体思路, 因为之前的文章已经详细讲过了, 直接给出代码 :

StaticLinkedListInterface.php :

<?php
   namespace Jonny\StaticLinkedList;
   interface NodeInterface {
      public function getData();
      public function getCursor();
      public function insertData($data);
      public function insertCursor($cursor);
   }
   interface LinkListInterface extends NodeInterface {
      public function __construct($maxSize);
      public function __destruct();
      public function getElement($position);
      public function getLength();
      public function insert($data, $position);
      public function insertFromHead($data);
      public function insertFromTail($data);
      public function locate($data);
      public function locateAllData($data);
      public function deleteByPosition($position);
      public function deleteByElement($data);
      public function cleanList();
      public function getStaticList();
   }
?>

StaticLinkedList.php

<?php
   use Jonny\StaticLinkedList;
   require_once("StaticLinkedListInterface.php");
   class Node implements StaticLinkedList\NodeInterface{
      protected const cursorLast = -1;
      protected const cursorEmpty = -2;
      protected $data;
      protected $cursor;
      public function getData() {
         return $this->data;
      }
      public function getCursor() {
         return $this->cursor;
      }
      public function insertData($data) {
         $this->data = $data;
      }
      public function insertCursor($cursor) {
         $this->cursor = $cursor;
      }
   }
   class LinkList extends Node implements StaticLinkedList\LinkListInterface {
      private $usedSize;
      private $insertPointer;
      private $first;
      protected $staticList;
      protected $maxSize;
      public function __construct($maxSize) {
         $this->maxSize = $maxSize;
         $this->staticList = array();
         $this->usedSize = 0;
         for($i = 1; $i <= $maxSize; $i++) {
            $this->staticList[$i] = new Node();
                $this->staticList[$i]->insertCursor(Parent::cursorEmpty);
         }
         $this->staticList[0] = new Node();
         $this->first = &$this->staticList[0];
         $this->insertPointer = &$this->staticList[1];
         $this->first->insertCursor(Parent::cursorLast);
      }
      public function __destruct() {
         unset($this->usedSize, $this->insertPointer, $this->first, $this->staticList, $this->maxSize);
      }
        protected function insertPointerFind() {
            $flag = false;
            for($i = 1; $i <= $this->maxSize; $i++) {
                if($this->staticList[$i]->getCursor() == Parent::cursorEmpty) {
                    $this->insertPointer = &$this->staticList[$i];
                    $flag = true;
                    break;
                }
            }
            if(!$flag) {
                $this->insertPointer = false;
            }
        }
        protected function getInsertPointerIndex() {
            for($i = 1; $i <= $this->maxSize; $i++) {
                if($this->insertPointer == $this->staticList[$i]) {
                    return $i;
                }
            }
        }
      public function getElement($position) {
         if($position < 1 or $position > $this->usedSize) {
            return false;
         }
         $linkList = &$this->first;
         $count = 0;
         while($count != $position) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            $count++;
         }
         return $linkList->getData();
      }
      public function getLength() {
         return $this->usedSize;
      }
      public function insert($data, $position) {
         if(!$this->insertPointer) {
            return false;
         }
         $linkList = &$this->first;
         $count = 0;
         while($count != $position - 1) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            $count++;
         }
         $this->insertPointer->insertData($data);
         if($linkList->getCursor() != Parent::cursorLast) {
            $this->insertPointer->insertCursor($linkList->getCursor());
            $linkList->insertCursor($this->getInsertPointerIndex());
         }else {
            $this->insertPointer->insertCursor(Parent::cursorLast);
            $linkList->insertCursor($this->getInsertPointerIndex());
         }
         $this->usedSize++;
         $this->insertPointerFind();
      }
      public function insertFromHead($data) {
         if(!$this->insertPointer) {
            return false;
         }
         $this->insertPointer->insertData($data);
         $linkList = &$this->first;
         if($linkList->getCursor() == Parent::cursorLast) {
            $linkList->insertCursor($this->getInsertPointerIndex());
            $this->insertPointer->insertCursor(Parent::cursorLast);
            $this->usedSize++;
            $this->getInsertPointerIndex();
            return null;
         }
         $this->insertPointer->insertCursor($linkList->getCursor());
         $linkList->insertCursor($this->getInsertPointerIndex());
         $this->usedSize++;
         $this->insertPointerFind();
      }
      public function insertFromTail($data) {
         if(!$this->insertPointer) {
            return false;
         }
         $this->insertPointer->insertData($data);
         $linkList = &$this->first;
         while($linkList->getCursor() != Parent::cursorLast) {
            $linkList = &$this->staticList[$linkList->getCursor()];
         }
         $linkList->insertCursor($this->getInsertPointerIndex());
         $this->insertPointer->insertCUrsor(Parent::cursorLast);
         $this->insertPointerFind();
         $this->usedSize++;
      }
      public function locate($data) {
         $linkList = &$this->first;
         $count = 0;
         while($linkList->getCursor() != Parent::cursorLast) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            $count++;
            if($linkList->getData() == $data) {
               return $count;
            }
         }
         return false;
      }
      public function locateAllData($data) {
         $linkList = &$this->first;
         $count = 0;
         while($linkList->getCursor() != Parent::cursorLast) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            if($linkList->getData() == $data) {
               $count++;
            }
         }
         if(!$count) {
            return false;
         }
         $location = array();
         $linkList = &$this->first;
         $count = 1;
         $loopCount = 0;
         while($linkList->getCursor() != Parent::cursorLast) {
            $loopCount++;
            if($this->staticList[$linkList->getCursor()]->getData() == $data) {
               $location[$count] = $loopCount;
               $count++;
            }
            $linkList = &$this->staticList[$linkList->getCursor()];
         }
         $location[0] = $count - 1;
         return $location;
      }
      public function deleteByPosition($position) {
         if($position < 1 or $position > $this->usedSize) {
            return false;
         }
         $linkList = &$this->first;
         $count = 0;
         while($count != $position - 1) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            $count++;
         }
         $node = &$this->staticList[$linkList->getCursor()];
         if($node->getCursor() != Parent::cursorLast) {
            $linkList->insertCursor($node->getCursor());
            $node->insertCursor(Parent::cursorLast);
         }else {
            $linkList->insertCursor(Parent::cursorLast);
            $node->insertCursor(Parent::cursorEmpty);
         }
         $this->usedSize--;
         $this->insertPointerFind();
      }
      public function deleteByElement($data) {
         if($this->locate($data) === false) {
            return false;
         }
         while($this->locate($data)) {
            $linkList = &$this->first;
            while($linkList->getCursor() != Parent::cursorLast) {
               if($this->staticList[$linkList->getCursor()]->getData() == $data and $this->staticList[$linkList->getCursor()]->getCursor() != Parent::cursorLast) {
                  $node = &$this->staticList[$linkList->getCursor()];
                  $linkList->insertCursor($node->getCursor());
                  $node->insertCursor(Parent::cursorEmpty);
                  $this->usedSize--;
               }else if($this->staticList[$linkList->getCursor()]->getData() == $data and $this->staticList[$linkList->getCursor()]->getCursor() == Parent::cursorLast) {
                  $node = &$this->staticList[$linkList->getCursor()];
                  $linkList->insertCursor(Parent::cursorLast);
                  $node->insertCursor(Parent::cursorEmpty);
                  $this->usedSize--;
               }
               $linkList = &$this->staticList[$linkList->getCursor()];
            }
         }
         $this->insertPointerFind();
      }
      public function cleanList() {
         $linkList = &$this->first;
         $linkList = &$this->staticList[$linkList->getCursor()];
         while($linkList->getCursor() != Parent::cursorLast) {
            $node = &$linkList;
            $linkList = &$this->staticList[$linkList->getCursor()];
            $node->insertCursor(Parent::cursorEmpty);
         }
         $linkList->insertCursor(Parent::cursorEmpty);
         $this->first->insertCursor(Parent::cursorLast);
         $this->usedSize = 0;
         $this->insertPointerFind();
      }
      public function getStaticList() {
         $list = array();
         $linkList = &$this->first;
         while($linkList->getCursor() != Parent::cursorLast) {
            $linkList = &$this->staticList[$linkList->getCursor()];
            $list[count($list)] = $linkList->getData();
         }
         return $list;
      }
   }
?>

以上代码在 PhpStorm 里面是测试通过的

这里主要讲一下遇到的坑

这次是本人第一次使用 PHP 进行面向对象编程, 幸亏有 PhpStorm, 否则很多错误都是莫名其妙

当类别中需要调用自己的属性以及方法, 需要在前面加上 "$this->". 前段时间 C++ 写多了, 没怎么看 PHP, 导致自己花了一段时间去修改这个错误
子类调用父类中属性或者方法可以在前面加上 "Parent::"
PHP 暂时不支持多重继承, 有些时候可以使用性状 (traits), 本篇没有用到

本来想做一个简单的网页, 插在这篇文章里面, 实现网页静态单链表. 但是在 JavaScript 与 AJAX 调用 PHP 的时候出现了错误, 具体错误暂时没有找到. 从 Safari 网路这里看返回了 500 错误, 应该是服务器那边的问题. 这个问题解决还需要一段时间, 因为最近要考试, 没办法太关注这个了

如果之后做出来了, 可能会出个 JavaScript 的教程

自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《PHP 实战 : 静态单链表》https://jonny.vip/2018/01/08/php-%e5%ae%9e%e6%88%98-%e9%9d%99%e6%80%81%e5%8d%95%e9%93%be%e8%a1%a8/

Like (0)