最近想起来两件事1.大话数据结构和大话设计模式
这两本书很有意思，C语言有指针，所以实现起来容易理解，所以突然想到用PHP写一下来熟悉一下数据结构的线性表，不过看的比较慢。一般两三天才看完一部分，毕竟还要工作，老板还安装摄像头看着每天干了啥。。。。。老板事业兴隆，嘻嘻。
线性表的概念不赘述，直接去看大话数据结构，代码也是在参考众多实现方案，比较符合大话数据结构的原本思想，就是基本上还原C语言的实现过程。
直接上代码
线性表
<?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/>';
}
}
}
?>线性表测试
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>';单链表<?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;
}
}
?>单链表测试require_once('LinkList.php');
$list = new SingleLinkList();
$listt = $list->CreateListHead(5);
$list = $list->ListTraverse();
var_dump($listt);注意：应该没有注意的了，这个还是很有用武之地，只不过理论偏多，不喜欢的就跳过吧。本来也没有多大问题
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
