以下是我结合网上实例 修改的 双链表 增删改操作, 但是总感觉 还是属于单链表的行为 , 希望高人指点一下, 感激不尽class Book {
public $next = null;
public $pre = null;
public $id;
public $name;
public function __construct($id = '', $name = '') {
$this->id = $id;
$this->name = $name;
}
/**
* 添加 book , 构建一个双向链表
* @param Book $head
* @param Book $book
*/
public static function addBook($head, $book) {
//cur 作为辅助节点
$cur = $head;
$isExist = false;
while ($cur->next != null) {//判断是否到队尾
if ($cur->next->id > $book->id) {
break;
} else if ($cur->next->id == $book->id) {
$isExist = true;
echo "存在相同编号";
}
$cur = $cur->next;
}
if (!$isExist) {//如果不存在 则添加
if ($cur->next != null) {
$book->next = $cur->next;
}
$book->pre = $cur;
if ($cur->next != null) {
$cur->next->pre = $book;
}
$cur->next = $book;
}
}
/**
* 修改节点
* @param Book $head
* @param Book $book
*/
public static function editBook(Book $head, Book $book) {
$cur = $head->next;
$isFind = false;
while ($cur != null) {
if ($cur->id == $book->id) {
//找到对应的ID
$cur->name = $book->name;
$isFind = true;
break;
}
$cur = $cur->next;
}
}
/**
* 删除指定节点
* @param Book $head
* @param type $id
*/
public static function delBook($head, $id) {
$cur = $head->next;
$isFind = false;
while ($cur != null) {
if ($cur->id == $id) {
//找到对应的ID
$isFind = true;
break;
}
$cur = $cur->next;
}
if ($isFind) {
//执行删除
if ($cur->next != null) {
$cur->next->pre = $cur->pre;
}
$cur->pre->next = $cur->next;
return $cur->id;
} else {
return false;
}
}
/**
* 遍历显示双链表
* @param Book $head
*/
public static function showBook($head) {
$cur = $head->next;
while ($cur->next != null) {
echo $cur->id . "=>" . $cur->name, "<br>";
$cur = $cur->next;
}
echo $cur->id . "=>" . $cur->name, "<br>";
}
}
header("Content-type: text/html; charset=utf-8");
//创建一个头节点
$head = new Book();
//添加书籍
$book = new Book(1, "PHP");
Book::addBook($head, $book);
//添加书籍
$book = new Book(2, "Mysql");
Book::addBook($head, $book);
//添加书籍
$book = new Book(3, "Linux");
Book::addBook($head, $book);
echo "添加的书籍:<BR/>";
Book::showBook($head);
//修改书籍
echo "修改ID=3的书籍为Java:<BR/>";
$book = new Book(3,"Java");
Book::editBook($head, $book);
Book::showBook($head);
//删除书籍
echo "删除 ID=3的书籍:<br/>";
Book::delBook($head, 3);
Book::showBook($head);
public $next = null;
public $pre = null;
public $id;
public $name;
public function __construct($id = '', $name = '') {
$this->id = $id;
$this->name = $name;
}
/**
* 添加 book , 构建一个双向链表
* @param Book $head
* @param Book $book
*/
public static function addBook($head, $book) {
//cur 作为辅助节点
$cur = $head;
$isExist = false;
while ($cur->next != null) {//判断是否到队尾
if ($cur->next->id > $book->id) {
break;
} else if ($cur->next->id == $book->id) {
$isExist = true;
echo "存在相同编号";
}
$cur = $cur->next;
}
if (!$isExist) {//如果不存在 则添加
if ($cur->next != null) {
$book->next = $cur->next;
}
$book->pre = $cur;
if ($cur->next != null) {
$cur->next->pre = $book;
}
$cur->next = $book;
}
}
/**
* 修改节点
* @param Book $head
* @param Book $book
*/
public static function editBook(Book $head, Book $book) {
$cur = $head->next;
$isFind = false;
while ($cur != null) {
if ($cur->id == $book->id) {
//找到对应的ID
$cur->name = $book->name;
$isFind = true;
break;
}
$cur = $cur->next;
}
}
/**
* 删除指定节点
* @param Book $head
* @param type $id
*/
public static function delBook($head, $id) {
$cur = $head->next;
$isFind = false;
while ($cur != null) {
if ($cur->id == $id) {
//找到对应的ID
$isFind = true;
break;
}
$cur = $cur->next;
}
if ($isFind) {
//执行删除
if ($cur->next != null) {
$cur->next->pre = $cur->pre;
}
$cur->pre->next = $cur->next;
return $cur->id;
} else {
return false;
}
}
/**
* 遍历显示双链表
* @param Book $head
*/
public static function showBook($head) {
$cur = $head->next;
while ($cur->next != null) {
echo $cur->id . "=>" . $cur->name, "<br>";
$cur = $cur->next;
}
echo $cur->id . "=>" . $cur->name, "<br>";
}
}
header("Content-type: text/html; charset=utf-8");
//创建一个头节点
$head = new Book();
//添加书籍
$book = new Book(1, "PHP");
Book::addBook($head, $book);
//添加书籍
$book = new Book(2, "Mysql");
Book::addBook($head, $book);
//添加书籍
$book = new Book(3, "Linux");
Book::addBook($head, $book);
echo "添加的书籍:<BR/>";
Book::showBook($head);
//修改书籍
echo "修改ID=3的书籍为Java:<BR/>";
$book = new Book(3,"Java");
Book::editBook($head, $book);
Book::showBook($head);
//删除书籍
echo "删除 ID=3的书籍:<br/>";
Book::delBook($head, 3);
Book::showBook($head);
不过你似乎也没有提供单项查找的功能你那几个静态方法都是从根开始处理的
如果你提供方法,能从 任何一个 $book 出发,去查找指定 id,就算是了
所谓的双向 是指头尾并行吗 , 是的话又是如何实现呢 能做个简例给我参考下吗 thanks
你现在都是沿 next 属性向下到结尾
还缺少沿 pre(一般写作 prev)向上到开始,如果有了,就不需要传递 $head 了$head = new Book();
$head->addbook(new Book()); //这是你现在有的
$book = $head->addbook(new Book()); //这是你没有的,$book 应该是新建的节点
$book = $book->addbook(new Book()); //然后应可以这样写
$book = $book->find($id); //这样就指向了指定的
假定现在的 $book 是 id 等于 3 的节点
你应可以 $book->delbook($d=1);