6. 数据结构(PHP实现) -- 图 (用链表来实现)
码农天地 -1. 特征每个结点都是以key-value的形式存储2. 时间复杂度操作时间复杂度添加O(1)更新O(n)删除O(n)查询O(n)3. 代码结点代码
<?php
/**
* content: 图的节点元素
* create: 2020-11-03
*/
namespace MapBundle;
class Node
{
/**
* 尾指针
* @var Node|null
*/
protected $tail;
/**
* 该节点存储的key
* @var string|int
*/
protected $key;
/**
* 该节点存储的value
* @var mixed
*/
protected $value;
public function __construct($key = null, $value = null, ?Node $tail = null)
{
$this->setTail($tail)->setKey($key)->setValue($value);
}
/**
* 设置尾结点
* @param Node|null $tail
* @return $this
*/
public function setTail(?Node $tail): self
{
$this->tail = $tail;
return $this;
}
/**
* 获取尾结点
* @return Node|null
*/
public function getTail(): ?Node
{
return $this->tail;
}
/**
* 设置key
* @param string|int $key
* @return $this
*/
public function setKey($key): self
{
$this->key = $key;
return $this;
}
/**
* 获取结点里的key
* @return mixed
*/
public function getKey()
{
return $this->key;
}
/**
* 设置值
* @param mixed $value
* @return $this
*/
public function setValue($value): self
{
$this->value = $value;
return $this;
}
/**
* 获取结点里的值
* @return mixed
*/
public function getValue()
{
return $this->value;
}
}
图的代码<?php
/**
* content: 图(链表实现)
* auth: 俞佳明
* create: 2020-11-03
*/
namespace MapBundle;
class LinkMap
{
/**
* @var Node|null
*/
protected $node;
/**
* 集合大小
* @var int
*/
protected $size;
public function __construct()
{
$this->node = null;
$this->size = 0;
}
/**
* 获取集合中的元素
* @return int
*/
public function getSize(): int
{
return $this->size;
}
/**
* 查询是否存在该值的结点
* @param $key
* @return Node|null
*/
public function contains($key): ?Node
{
$node = $this->node;
while (!is_null($node)) {
if ($node->getKey() === $key) {
return $node;
}
$node = $node->getTail();
}
return null;
}
/**
* 插入
* @param string|int $key
* @return Node
* @throws \Exception
*/
public function add($key): ?Node
{
if (is_null($this->contains($key))) {
// 添加新的
$newNode = new Node($key, 1, null);
$newNode->setTail($this->node);
$this->node = $newNode;
$this->size++;
return $newNode;
} else {
// 在原基础上自增
$node = $this->node;
while (!is_null($node)) {
if ($node->getKey() == $key) {
$node->setValue($node->getValue() + 1);
return $node;
}
}
}
return null;
}
/**
* 删除
* @param $key
*/
public function remove($key)
{
// 如果图中不存在元素就返回
if (is_null($this->node)) return;
// 如果删除的是第一个结点
if ($this->node->getKey() == $key) {
$this->node = $this->node->getTail();
$this->size--;
return;
}
// 删除第二个结点及以后
$node = $this->node;
while (!is_null($node->getTail())) {
if ($node->getTail()->getKey() === $key) {
$node->setTail($node->getTail()->getTail());
$this->size--;
return;
}
$node = $node->getTail();
}
return;
}
public function varDump()
{
$node = $this->node;
while (!is_null($node)) {
echo $node->getKey(). " >> ". $node->getValue(). PHP_EOL;
$node = $node->getTail();
}
}
}
4. 示例<?php
require_once __DIR__ . '/../../vendor/autoload.php';
$map = new MapBundleLinkMap();
// 插入结点
$map->add('a');
$map->add('a');
$map->add('c');
$map->add('c');
$map->add('d');
$map->add('d');
$map->add('b');
$map->add('b');
// 移除结点
$map->remove('b');
// 打印
$map->varDump();
d >> 2
c >> 2
a >> 2
特别申明:本文内容来源网络,版权归原作者所有,如有侵权请立即与我们联系(cy198701067573@163.com),我们将及时处理。
php介绍
PHP即“超文本预处理器”,是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言,与C语言类似,是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习,使用广泛,主要适用于Web开发领域。
上一篇: php如何实现禁止ip访问