定义类
class Node { public $id; public $name; public $next; public function __construct($id, $name) { $this->id = $id; $this->name = $name; $this->next = NULL; } } /** * 链表中有两个特别重要的方法,插入和删除 * * 插入需要找到插入的位置,把前一个元素的next指针指向被插入的节点,并将被插入极端点的next指针指向后一个节点 * * 而删除则把前一个节点的next指针指向后一个节点,并返回被删除元素的数据内容。 * * */ class SimpleWhile { private $header; public function __construct($node = NULL) { if (is_null($node)) $this->header = NULL; else { $node->next = $node; $this->header = $node; } } /** * 获取链式列表中的数据的个数 * @return int */ public function getLinkLength() { if ($this->is_empty()) return 0; $count = 1; $current = $this->header; while ($current->next != $this->header) { $count++; $current = $current->next; } return $count; } /** * 在循环列表中某一个位置插入代码 * @param $id * @param $node */ public function insert($id, $node) { if ($this->is_empty()) { $node->next = $node; $this->header = $node; } /** * 插入到了第一位 */ if ($id === 1) { $next = $this->header; $node->next = $next; $current = $this->header; while ($current->next != $this->header) { $current = $current->next; } $this->header = $node; $current->next = $this->header; return; } $count = 1; //如果while条件成立,这就是第一个 $current = $this->header; $found = FALSE; while ($current->next != $this->header) { if ($count === $id) { $found = TRUE; break; } $count++; $current = $current->next; } //找到了位置 if ($found) { $node->next = $current->next; $current->next = $node; } else { //$this->addLink($node); 这样的添加是有顺序的不能使用。 $node->next = $this->header; $current->next = $node; } } /** * * 向里面添加一个元素, * 元素添加,是根据id自动进行排序链表的 * * * * * @param $node */ public function addLink($node) { if ($this->is_empty()) { $node->next = $node; $this->header = $node; } else { $current = $this->header; //如果相等,就是一个元素 if ($current->next == $this->header) { if (($current->id > $node->id)) { $current->next = $node; $node->next = $current; $this->header = $node; return; } } $islast = TRUE;//判断是不是最后一个 $isfirst = TRUE; $changeHeader = FALSE; //如果$current->next 是null 就退退出while循环 while ($current->next != $this->header) { if (($current->next->id > $node->id) || ($changeHeader = ($current->id > $node->id) && $isfirst)) { $islast = FALSE; break; } $isfirst && $isfirst = FALSE; //只有第一次循环的时候,才会执行 $current = $current->next; } //如果定义一个有序的列表,这里返回的不是最后一个,因此$node不应该指向最后一个。 if ($changeHeader) { $current->next = $node; $node->next = $current; $this->header = $node; } else { $node->next = $islast ? $this->header : $current->next; $current->next = $node; } } } /** * 删除一个id的链表, * 这里需要着重说一说,怎么删除 * * 删除时,需要知道 删除元素的上一个元素是谁 * * 删除元素的下一个元素是谁, * * 这两个元素需要做一个对接 * * 这样就能保证 链式列表不断链。 * @param $id */ public function delLink($id) { if ($this->is_empty()) return; $current = $this->header; //删除第一个 if ($current->id === $id) { $next = $current->next; while ($current->next != $this->header) { $current = $current->next; } $this->header = $next; $current->next = $this->header; return TRUE; } $islast = TRUE; $find = FALSE; while ($current->next != $this->header) { if ($current->next->id == $id) { $islast = FALSE; $find = TRUE; break; } $current = $current->next; } //$current->next = $current->next->next; if (!$find && $current->id === $id) $find = TRUE; if ($find) { $islast ? $current->next = $this->header : $current->next = $current->next->next; return TRUE; } else return FALSE; } /** * 判断链式列表是否为空 * @return bool */ public function is_empty() { return is_null($this->header) ? TRUE : FALSE; } /** * 根据id获取到对应的name 或者叫 value * @param $id * @return string */ public function getLinkNameById($id) { if ($this->is_empty()) return ''; $current = $this->header; if ($current->id === $id) { return $current->name; } while ($current->next != $this->header) { if ($current->id === $id) { break; } $current = $current->next; } if ($current->id === $id) { return $current->name; } return ''; } /** * 更新指定id中的name * @param $id * @param $name * @return bool */ public function updateLink($id, $name) { $current = $this->header; if ($current->id === $id) { $current->name = $name; return TRUE; } while ($current->next != $this->header) { if ($current->id == $id) { break; } $current = $current->next; } if ($current->id === $id) { $current->name = $name; return TRUE; } return FALSE; } /** * 获取整个链式列表,并以链式的方式返回 * @return array */ public function getLinkList() { if ($this->is_empty()) return []; $current = $this->header; $data = [$current]; while ($current->next != $this->header) { $data[] = $current->next; $current = $current->next; } return $data; } /** * 获取整个链式列表中的数据 * @return array */ public function getData() { if ($this->is_empty()) return []; $current = $obj = $this->header; $data = [['id' => $obj->id, 'name' => $obj->name]]; while ($current->next != $this->header) { $_obj = $current->next; $data[] = ['id' => $_obj->id, 'name' => $_obj->name]; $current = $current->next; } return $data; } }
项目调用:
$linkList = new SimpleWhile(); //$linkList->addLink(new Node(1, 'james')); $linkList->addLink(new Node(4, 'jon')); $linkList->addLink(new Node(3, 'shiree')); $linkList->addLink(new Node(8, 'james')); $linkList->addLink(new Node(2, 'james')); $linkList->addLink(new Node(7, 'jim')); var_dump($linkList->getLinkLength()); print_r($linkList->getData()); print_r($linkList->getLinkList()); // //print_r($linkList->getData()); // //var_dump($linkList->updateLink(3, 'jon123')); // // // // //var_dump($linkList->getLinkNameById(3)); // //var_dump($linkList->getLinkNameById(8)); // // print_r($linkList->getData()); //var_dump($linkList->delLink(1)); //var_dump($linkList->delLink(2)); //print_r($linkList->getLinkList()); var_dump($linkList->getLinkLength()); $linkList->insert(10, new Node(0, 'head')); print_r($linkList->getData()); var_dump($linkList->getLinkLength()); $linkList->updateLink(3, '123123'); echo $linkList->getLinkNameById(3); $data=$linkList->getLinkList(); print_r($data); var_dump($linkList->getLinkLength()); $linkList->delLink(3); var_dump($linkList->getLinkLength()); $data = $linkList->getLinkList(); print_r($data); $data=$linkList->getLinkList();
结果展示:
int(5) Array ( [0] => Array ( [id] => 3 [name] => shiree ) [1] => Array ( [id] => 2 [name] => james ) [2] => Array ( [id] => 4 [name] => jon ) [3] => Array ( [id] => 7 [name] => jim ) [4] => Array ( [id] => 8 [name] => james ) ) D:\phpStudy\WWW\test>php simpleWhile.php D:\phpStudy\WWW\test\simpleWhile.php:371: int(5) Array ( [0] => Array ( [id] => 3 [name] => shiree ) [1] => Array ( [id] => 2 [name] => james ) [2] => Array ( [id] => 4 [name] => jon ) [3] => Array ( [id] => 7 [name] => jim ) [4] => Array ( [id] => 8 [name] => james ) ) Array ( [0] => Node Object ( [id] => 3 [name] => shiree [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) [1] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 3 [name] => shiree [next] => Node Object *RECURSION* ) ) ) ) ) [2] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 3 [name] => shiree [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) [3] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 3 [name] => shiree [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object *RECURSION* ) ) ) ) ) [4] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 3 [name] => shiree [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object *RECURSION* ) ) ) ) ) ) Array ( [0] => Array ( [id] => 3 [name] => shiree ) [1] => Array ( [id] => 2 [name] => james ) [2] => Array ( [id] => 4 [name] => jon ) [3] => Array ( [id] => 7 [name] => jim ) [4] => Array ( [id] => 8 [name] => james ) ) D:\phpStudy\WWW\test\simpleWhile.php:402: int(5) Array ( [0] => Array ( [id] => 3 [name] => shiree ) [1] => Array ( [id] => 2 [name] => james ) [2] => Array ( [id] => 4 [name] => jon ) [3] => Array ( [id] => 7 [name] => jim ) [4] => Array ( [id] => 8 [name] => james ) [5] => Array ( [id] => 0 [name] => head ) ) D:\phpStudy\WWW\test\simpleWhile.php:409: int(6) 123123Array ( [0] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object *RECURSION* ) ) ) ) ) ) [1] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object *RECURSION* ) ) ) ) ) ) [2] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) ) [3] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object *RECURSION* ) ) ) ) ) ) [4] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object *RECURSION* ) ) ) ) ) ) [5] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 3 [name] => 123123 [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) ) ) D:\phpStudy\WWW\test\simpleWhile.php:417: int(6) D:\phpStudy\WWW\test\simpleWhile.php:421: int(5) Array ( [0] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object *RECURSION* ) ) ) ) ) [1] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) [2] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object *RECURSION* ) ) ) ) ) [3] => Node Object ( [id] => 8 [name] => james [next] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object *RECURSION* ) ) ) ) ) [4] => Node Object ( [id] => 0 [name] => head [next] => Node Object ( [id] => 2 [name] => james [next] => Node Object ( [id] => 4 [name] => jon [next] => Node Object ( [id] => 7 [name] => jim [next] => Node Object ( [id] => 8 [name] => james [next] => Node Object *RECURSION* ) ) ) ) ) )