清华大学韩顺平讲师讲算法之三（下），环链表创建与删除

webcode

浏览: 5940511 次
性别:
来自: 上海

最近访客更多访客>>

ap950

u012363178

wangyy

ybfjavaeye

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (7533)

社区版块

存档分类

2013-02 ( 78)
2013-01 ( 83)
2012-12 ( 121)
更多存档...

<html>
<head>
<meta http-equiv='content-type' content='text/html;charset=utf-8'>
<title>/高性能的计算器/</title>
</head>
<body>
<?php
class Hero{
	public $pre=null;//指向前一个节点的引用
	public $no;
	public $name;
	public $nickname;
	public $next=null;
	public function __construct($no='',$name='',$nickname=''){
		$this->no=$no;
		$this->name=$name;
		$this->nickname=$nickname;
	}
	public static function addHero($head,$hero){
		$cur=$head;//一个辅助点，不能动头
		$isExist=false;
		if($cur->next==null){
			$cur->next=$hero;
			$hero->pre=$cur;
		}else{
			///如果不是空节点，则按排名来添加
			
			while($cur->next!=null){
				if($cur->next->no>$hero->no){
					//说明$hero要加入在$cur的后面

				}else if($cur->next->no==$hero->no){
					$isExist=true;
					echo '<br>不能有相同编号';
				}
				$cur=$cur->next;
			}//while
			// 退出while时，我们只要把$hero添加到$cure后面即可
			if(!$isExist){
				//比如加的就是末
				if($cur->next !=null){//处理空表
					$hero->next=$cur->next;
				}
				$hero->pre=$cur;
				if($cur->next !=null){//处理空表
					$cur->next->pre=$hero;
				}
				$cur->next=$hero;
			}
		}//if



	}//addHero

		public static function showHero($head){
			$cur=$head;
			while($cur->next !=null){
				echo '<br>编号：'.$cur->no.'名字：'.$cur->name;
			$cur=$cur->next;
			}
			//当退出while
			echo '<br>编号是：'.$cur->no.'名字：'.$cur->name;
		}//showHero
		public static function delHero($head,$herono){
			//不用辅助结点
			$cur=$head->next;
			if($cur==null){
				echo '一个空表，删除了没意义';
			}
			$isFind=false;
			while ($cur !=null) {
				if($cur->no == $herono){
					//找到了
					$isFind=true;
					break;

				}//if
				$cur=$cur->next;//向下找
			}//while
			if($isFind){
				//找到了可以删除
				//自我删除,不使用辅助结点
				if($cur->next !=null){
					$cur->next->pre=$cur->pre;
				}
				$cur->pre->next=$cur->next;

			}else{
				echo "找不到了，你输入的不对，没法子删除啊.";
			}//if
		}//delHero
}//class
	$head=new Hero();
	$hero=new Hero(1,'宋江','及时狗');
	Hero::addHero($head,$hero);

	$hero=new Hero(2,'吴用','一个老师');
	Hero::addHero($head,$hero);	

	$hero=new Hero(3,'林冲','教头');
	Hero::addHero($head,$hero);	
	Hero::showHero($head);

	//试试删除
	Hero::delHero($head,2);
	//
	echo '<br>'."删除的后的".'<br>';
	Hero::showHero($head);

	echo '<br><br>'.'其好处是自好删除，以后学习二叉树及其他，打下良好的基础';
?>
</body>
</html>

分享到：