<meta charset=
"utf-8"
/>
<?
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);
}
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;
$i
<
count
(
$city
);
$i
++)
$ll
->orderInsert(
$city
[
$i
]);
$ll
->traversal();
?>