在《数据结构 : 静态单链表 (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/
AliPay QR Code
WeChat QR Code
Leave a Reply