跳至
[1]
[全屏预览]
/**
* The class LinkedList allows an application to store strings in
* alphabetical order by calling orderInsert().
* 此处定义的 LinkedList 类,可以调用它的 方法 orderInsert(),来以字母
* 大小的顺序储存 英文字符串。
* The frequency for each word is also provided.
* 同时记录 英文单词出现的次数
* 作者: 许同春 author Tongchun Xu
* @开源中国 Open Source, China communiity
* 完成日期:2016年6月11日 completion date: 11 June, 2016
*/
class Node{
public $data;
public $frequency;
public $next;
function __construct($data, $next = null, $frequency = 1){
$this->data = $data; //英文字符串
$this->next = $next; //指向后继结点的指针
$this->frequency=$frequency; //英文字符串出现的次数
}
}
class LinkedList{
private $head; //单链表的头结点,不存储数据
function __construct(){//单链表的构造方法
//头结点的数据为"傀儡", 不代表 任何数据
$this->head = new Node("dummy 傀儡");
$this->first = null;
}
function isEmpty(){
return ($this->head->next == null);
}
/* orderInsert($data) 方法,
* 按给定字符串 $data 的大小, 将其安插到适当的位置,
* 以保证单链表中字符串的存储,始终是有序的。
*/
function orderInsert($data){
$p = new Node($data);
if($this->isEmpty()){
$this->head->next = $p;
}
else {
$node= $this->find($data);
if(!$node){
$q = $this->head;
while($q->next != NULL && strcmp($data, $q->next->data)> 0 ){
$q = $q->next;
}
$p->next = $q->next;
$q->next = $p;
}else
$node->frequency++;
}
}
function find($value){//查询是否有给定的字符串
$q = $this->head->next;
while($q->next != null){
if(strcmp($q->data,$value)==0){
break;
}
$q = $q->next;
}
if ($q->data == $value)
return $q;
else
return null;
}
function traversal(){//遍历单链表
if(!$this->isEmpty()){
$p=$this->head->next;
echo $p->data."(".$p->frequency.") ";
while($p->next != null){
$p=$p->next;
echo $p->data."(".$p->frequency.") ";
}
}else
echo "链表为空!";
}
}
$ll = new LinkedList();
$city =array("Wuhan", "Beijing", "Shanghai","Thunder Bay",
"Tianjin", "Changsha", "Kunming", "Edmonton", "Glasgow",
"Gongyi","Tokyo","New York","Ottawa","Moskow","Edmonton",
"Glasgow","Edinburgh","Thunder Bay","New Delhi","Edinburgh",
"Edmonton", "Glasgow", "Edmonton","Glasgow");
for ($i=0;$iorderInsert($city[$i]);
$ll->traversal();
?>