最近想起来两件事1.大话数据结构和大话设计模式
这两本书很有意思,C语言有指针,所以实现起来容易理解,所以突然想到用PHP写一下来熟悉一下数据结构的线性表,不过看的比较慢。一般两三天才看完一部分,毕竟还要工作,老板还安装摄像头看着每天干了啥。。。。。老板事业兴隆,嘻嘻。
线性表的概念不赘述,直接去看大话数据结构,代码也是在参考众多实现方案,比较符合大话数据结构的原本思想,就是基本上还原C语言的实现过程。
直接上代码
-
线性表
-
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
<?php
/*
*文件名:linearList.php
* 功能:数据结构线性表的顺序存储实现
* author:jack
* @copyright:www.gifttodj.com
*/
class
linearList{
private
$length
;
//当前长度
private
$arr
;
//当前存储位置
const
MAXSIZE=100;
//最大长度
/*
*构造函数,判断空表还是非空表,并且进行实例化,定义一个数组
* @param array $arr 输入的数组
* @param int $n 输入数组的长度
* @ruturn void;
*/
function
__construct(
$arr
,
$n
){
if
(
$n
>self::MAXSIZE){
echo
"对不起,数组的长度超过了最大允许值"
.self::MAXSIZE;
}
elseif
(
$n
<0){
echo
'异常,数组长度不能为负数'
;
}
elseif
(
$n
==0){
echo
'<br/>... 你创建了一张空表,数组长度为0'
;
$this
->arr=
$arr
;
$this
->length=
$n
;
}
else
{
echo
'<br/>... 你成功创建了一张表<br/>'
;
$this
->arr=
$arr
;
$this
->length=
$n
;
}
}
/*
*按位查找,返回查找到的值
*@param int $n 查找的位置
* @ruturn string;
*/
function
findValue(
$n
){
if
(
$n
<1||
$n
>
$this
->length){
echo
'输入的位置有误,请在1到'
.
$this
->length.
'范围内选择'
;
}
return
'你要找的第'
.
$n
.
'位的值为'
.
$this
->arr[
$n
-1];
}
/*
*按值查找,返回查找到的位置
* @ruturn string;
* @param int $n 查找的值
*/
function
findLocation(
$n
){
$v
=true;
foreach
(
$this
->arr
as
$key
=>
$value
){
if
(
$value
==
$n
){
$b
=
$key
+1;
return
'你要找的'
.
$n
.
'的位置是'
.
$b
;;
}
else
{
$v
=false;
}
}
if
(!
$v
){
return
'你要找的值'
.
$n
.
'不存在'
;
}
}
/*
*在选定的位置处插入某个值
* @param int $i 插入位置
* @param int $v 插入的值
* @ruturn array;
*/
function
insertValue(
$i
,
$v
){
if
(
$i
<1||
$i
>self::MAXSIZE){
echo
'输入的位置有误,请在1到'
.self::MAXSIZE.
'范围内选择'
;
return
;
}
//现将所有i之后的值往后移动一位
for
(
$h
=
$this
->length;
$h
>=
$i
;
$h
--){
$this
->arr[
$h
]=
$this
->arr[
$h
-1];
}
if
(
$i
>
$this
->length){
$this
->arr[
$this
->length]=
$v
;
}
else
{
$this
->arr[
$i
-1]=
$v
;
}
$this
->length++;
return
$this
->arr;
}
/*
*在选定的位置删除某个值
* @param int $i 位置
* @ruturn array;
*/
function
deleteValue(
$i
){
if
(
$i
<1||
$i
>self::MAXSIZE){
echo
'输入的位置有误,请在1到'
.self::MAXSIZE.
'范围内选择'
;
return
;
}
//现将所有i之后的值往前移动一位
for
(
$j
=
$i
;
$j
<
$this
->length;
$j
++){
$this
->arr[
$j
-1]=
$this
->arr[
$j
];
}
unset(
$this
->arr[
$this
->length-1]);
$this
->length--;
return
$this
->arr;
}
function
__destruct(){
if
(
$this
->length==0){
echo
'<br/>...销毁一张空表...<br/>'
;
}
else
{
echo
'<br/>...成功销毁一张表..<br/>'
;
}
}
}
?>
-
12345678910111213141516
线性表测试
require_once
(
'linearList.php'
);
$arr
=
array
(10,125,123,1,4);
$n
=5;
$list
=
new
linearList(
$arr
,
$n
);
echo
$list
->findValue(5).
'<br/>'
;
echo
$list
->findLocation(4).
'<br/>'
;
echo
'<pre>'
;
print_r(
$list
->insertValue(20,300));
echo
'</pre>'
;
echo
'<pre>'
;
print_r(
$list
->deleteValue(1));
echo
'</pre>'
;
-
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
单链表<?php
class
LNode{
public
$data
;
public
$next
;
public
function
__construct(
$data
=
''
){
$this
->data=
$data
;
$this
->next=null;
}
}
class
SingleLinkList{
public
$data
;
public
$next
;
//单链表的创建都是从空表逐渐增加上去的
//这相当于头结点
public
function
__construct(){
$this
->data=null;
//公用信息
$this
->next=null;
}
//每个节点的数据这么传进来呢
//头插法,每个新数据都是第一个位置
public
function
CreateListHead(
$num
){
for
(
$i
=0;
$i
<
$num
;
$i
++){
$node
=
new
LNode();
$node
->data = mt_rand(100,200);
$node
->next=
$this
->next;
var_dump(
$node
);
$this
->next=
$node
;
}
}
//尾插法
public
function
CreateListTail(
$num
){
$tail
=
$this
;
//把新节点当成当前节点的下一节点
for
(
$i
=0;
$i
<
$num
;
$i
++){
$node
=
new
LNode();
$node
->data = mt_rand(100,200);
$tail
->next=
$node
;
$tail
=
$node
;
var_dump(
$node
);
}
$node
->next=null;
}
//销毁单链表
public
function
DestroyList(){
//
$that
=
$this
;
while
(
$that
){
$temp
=
$that
->next;
unset(
$that
);
$that
=
$temp
;
}
}
//清空单链表
//只留下头结点
public
function
ClearList(){
$temp
=
$this
->next;
while
(
$temp
){
$tmp
=
$temp
->next;
unset(
$temp
);
$temp
=
$tmp
;
}
$this
->next=null;
}
//判断单链表是否为空
public
function
ListEmpty(){
if
(
$this
->next){
return
false;
}
else
{
return
true;
}
}
//单链表的长度
public
function
ListLength(){
$temp
=
$this
->next;
$count
=0;
while
(
$temp
){
$count
++;
$temp
=
$temp
->next;
}
return
$count
;
}
//查找特定位置的数据
public
function
FindValue(
$pos
){
$count
=1;
$temp
=
$this
->next;
//也可以吧count与pos判断放在循环里
while
(
$temp
&&
$count
<
$pos
){
$count
++;
$temp
=
$temp
->next;
}
if
(!
$temp
||
$count
>
$pos
){
return
'该位置没有数据'
;
}
//这里可以利用该节点找出下一个值,也就能找出上一个节点
return
$p
->data;
}
//查找数据所在的位置
public
function
LocateElem(
$value
){
$count
=1;
$temp
=
$this
->next;
//也可以吧count与pos判断放在循环里
while
(
$temp
){
$count
++;
if
(
$value
==
$temp
->data){
return
$count
;
}
}
if
(!
$temp
){
return
'没有该数据:'
.
$value
;
}
}
//特定值的前一个值
public
function
PriorElem(
$value
){
$temp
=
$this
->next;
if
(
$temp
&&
$temp
->data==
$value
){
return
$p
->data.
'已经是第一个元素,已无前驱元素'
;
}
while
(
$temp
&&
$temp
->next){
$tmp
=
$temp
->next;
if
(
$tmp
->data==
$value
){
return
$temp
->data;
}
$temp
=
$tmp
;
}
return
'该单链表没有该数值'
.
$value
;
}
//特定值的下一个值
public
function
NextElem(
$value
){
$temp
=
$this
->next;
if
(
$temp
&&
$temp
->next==null){
return
$temp
->data.
'已经是尾节点数据,已无后续'
;
}
while
(
$temp
){
if
(
$this
->data==
$value
){
return
$temp
->data;
}
}
return
'该单链表没有该数值'
.
$value
;
}
//在指定位置之前插入数据
/**
*@param class LNode $node
*
**/
public
function
ListInsert(
$pos
,
$node
){
$count
=1;
$temp
=
$this
;
//也可以吧count与pos判断放在循环里
while
(
$temp
&&
$count
<
$pos
){
$count
++;
$temp
=
$temp
->next;
}
if
(!
$temp
||
$count
>
$pos
){
return
'该位置没有数据'
;
}
//这里可以利用该节点找出下一个值,也就能找出上一个节点
$node
->next=
$temp
->next;
$temp
->next=
$node
;
return
'ok'
;
}
//删除单链表指定位置的数据元素
public
function
ListDelete(
$pos
){
$count
=0;
$temp
=
$this
;
while
(
$temp
->next){
$count
++;
if
(
$count
==
$pos
){
$tmp
=
$temp
->next;
$temp
->next=
$tmp
->next;
unset(
$tmp
);
return
'OK'
;
}
$temp
=
$temp
->next;
}
return
'该位置没有数据'
;
}
public
function
ListTraverse(){
$arr
=
array
();
$temp
=
$this
;
while
(
$temp
->next){
$arr
[]=
$temp
->data;
$temp
=
$temp
->next;
}
return
$arr
;
}
}
?>
-
123456
单链表测试
require_once
(
'LinkList.php'
);
$list
=
new
SingleLinkList();
$listt
=
$list
->CreateListHead(5);
$list
=
$list
->ListTraverse();
var_dump(
$listt
);
-
1
注意:应该没有注意的了,这个还是很有用武之地,只不过理论偏多,不喜欢的就跳过吧。本来也没有多大问题
本文转自 jackdongting 51CTO博客,原文链接:http://blog.51cto.com/10725691/1947480