首页 > 代码库 > 第三章 线性表---链式存储结构(双向链表)
第三章 线性表---链式存储结构(双向链表)
双向链表(double linked list)是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。结点都有两个指针域,一个指向直接后继,另一个指向直接前驱。
现在分析添加的情况
已经有1号英雄和5号英雄,现在要添加3号英雄
此时cur指向了1号英雄,hero指向3号英雄
cur指向1号英雄,发现cur的下一个是5号英雄,大于要添加的3号英雄
分析图
过程
(1)让3号英雄指向5号英雄,即把这个①号线搭起来
$hero->next=$cur->next;
//$cur指向1号英雄,$cur->next指向5号英雄
(2)然后再搭pre这根线,让3号英雄的pre指向1号英雄,即把这个②号线搭起来
$hero->per=$cur;
(3)然后让5号英雄的pre指向3号英雄,即把这个③号线搭起来
$cur->next->pre=$hero;
//$cur->next指向5号英雄,$cur->next->pre为5号英雄指向1号英雄,即图中⑥号线
//此时⑥号线就断掉了,原来的5号英雄的pre是指向1号英雄的,现在指向了3号英雄
(4)让1号英雄指向3号英雄,即把这个④号线搭起来
$cur->next=$hero;
//此时⑤号线就断掉了,原来的$cur->next是指向5号英雄的,现在指向了3号英雄
改进:不严密的地方,可以和前面的进行合并的
添加英雄,把添加时是空链表和不是空链表的情况,合并到一起了
现在考虑:要添加的人就在末尾
有一个head和1号人物,要添加的是6号人物
此时cur指向1号人物,
当按照原先的代码执行,既下面这段代码,会有一些小问题的
$hero->next=$cur->next;
$hero->pre=$cur;
$cur->next->pre=$hero;
$cur->next=$hero;
执行
(1)$hero->next=$cur->next;
此时cur指向1号人物,1号人物此时是最后的一个节点,$cur->next就是空了,那么$hero->next=$cur->next; 此时这句话就没有意义了,因为$hero->next本身就是空啊,你再赋给它空,没有意义,干脆这句话此时就不执行了。所以要加一个一个判断条件,即$cur->next不等于空,执行$hero->next=$cur->next; 才有价值
if($cur->next!=null){
$hero->next=$cur->next;
}
(2)$hero->pre=$cur;
这句话还是很有价值的,如下图所示,把①号线搭起来了
(3)$cur->next->pre=$hero;
此时cur指向1号人物,$cur->next就是空了,空的pre就没意义了,所有也要和上面的(1)一样,加判断
if($cur->next!=null){
$cur->next->pre=$hero;
}
(4)$cur->next=$hero;
这句是有意义的,如下图所示,把②号线搭起来了
如果前面的代码修改成了如下的代码:
if($cur->next!=null){
$hero->next=$cur->next;
}
$hero->pre=$cur;
if($cur->next!=null){
$cur->next->pre=$hero;
}
$cur->next=$hero;
就和前面的一个if判断语句不谋而合了
即在doubleLink.php中的这段代码
if($cur->next==null){ //如果是,就说明是空链表,添加第一个英雄
$cur->next=$hero;
//这样就首尾相连了
$hero->pre=$cur;
}else{...
都是在说当$cur->next为空的时候,就执行
$cur->next=$hero;
$hero->pre=$cur;
代码不是一步到位的,优化前进
======
此时删除英雄就不需要辅助节点了
分析图
当要删除的节点在最后的时候,还需要判断下
此时$cur->next本身就是空了,所有要加判断了
$cur->pre->next=$cur->next; //这个就相当于把1号节点的next置空了,这个没错
所以要这样:
if($cur->next!=null){
$cur->next->pre=$cur->pre;
}
$cur->pre->next=$cur->next;
这样执行的话,把上图中的蓝线就去掉了,这样6号英雄就访问不到了,6号英雄出列了,因为我们是从表头开始找的,$cur-next就访问不到6号英雄节点了,6号英雄指向别人是没有用的,★关键★是没有人指向它。
第三章 线性表---链式存储结构(双向链表)