定义类
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* ) ) ) ) ) )