最近想起来两件事1.大话数据结构和大话设计模式


这两本书很有意思，C语言有指针，所以实现起来容易理解，所以突然想到用PHP写一下来熟悉一下数据结构的线性表，不过看的比较慢。一般两三天才看完一部分，毕竟还要工作，老板还安装摄像头看着每天干了啥。。。。。老板事业兴隆，嘻嘻。


线性表的概念不赘述，直接去看大话数据结构，代码也是在参考众多实现方案，比较符合大话数据结构的原本思想，就是基本上还原C语言的实现过程。


直接上代码

线性表


<?php/**文件名：linearList.php*功能：数据结构线性表的顺序存储实现*author:jack*@copyright:www.gifttodj.com*/classlinearList{private$length;//当前长度private$arr;//当前存储位置constMAXSIZE=100;//最大长度/**构造函数，判断空表还是非空表，并且进行实例化,定义一个数组*@paramarray$arr输入的数组*@paramint$n输入数组的长度*@ruturnvoid;*/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;}}/**按位查找，返回查找到的值*@paramint$n查找的位置*@ruturnstring;*/functionfindValue($n){if($n<1||$n>$this->length){echo'输入的位置有误，请在1到'.$this->length.'范围内选择';}return'你要找的第'.$n.'位的值为'.$this->arr[$n-1];}/**按值查找，返回查找到的位置*@ruturnstring;*@paramint$n查找的值*/functionfindLocation($n){$v=true;foreach($this->arras$key=>$value){if($value==$n){$b=$key+1;return'你要找的'.$n.'的位置是'.$b;;}else{$v=false;}}if(!$v){return'你要找的值'.$n.'不存在';}}/**在选定的位置处插入某个值*@paramint$i插入位置*@paramint$v插入的值*@ruturnarray;*/functioninsertValue($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;}/**在选定的位置删除某个值*@paramint$i位置*@ruturnarray;*/functiondeleteValue($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=newlinearList($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>';

单链表<?phpclassLNode{public$data;public$next;publicfunction__construct($data=''){$this->data=$data;$this->next=null;}}classSingleLinkList{public$data;public$next;//单链表的创建都是从空表逐渐增加上去的//这相当于头结点publicfunction__construct(){$this->data=null;//公用信息$this->next=null;}//每个节点的数据这么传进来呢//头插法，每个新数据都是第一个位置publicfunctionCreateListHead($num){for($i=0;$i<$num;$i++){$node=newLNode();$node->data=mt_rand(100,200);$node->next=$this->next;var_dump($node);$this->next=$node;}}//尾插法publicfunctionCreateListTail($num){$tail=$this;//把新节点当成当前节点的下一节点for($i=0;$i<$num;$i++){$node=newLNode();$node->data=mt_rand(100,200);$tail->next=$node;$tail=$node;var_dump($node);}$node->next=null;}//销毁单链表publicfunctionDestroyList(){//$that=$this;while($that){$temp=$that->next;unset($that);$that=$temp;}}//清空单链表//只留下头结点publicfunctionClearList(){$temp=$this->next;while($temp){$tmp=$temp->next;unset($temp);$temp=$tmp;}$this->next=null;}//判断单链表是否为空publicfunctionListEmpty(){if($this->next){returnfalse;}else{returntrue;}}//单链表的长度publicfunctionListLength(){$temp=$this->next;$count=0;while($temp){$count++;$temp=$temp->next;}return$count;}//查找特定位置的数据publicfunctionFindValue($pos){$count=1;$temp=$this->next;//也可以吧count与pos判断放在循环里while($temp&&$count<$pos){$count++;$temp=$temp->next;}if(!$temp||$count>$pos){return'该位置没有数据';}//这里可以利用该节点找出下一个值，也就能找出上一个节点return$p->data;}//查找数据所在的位置publicfunctionLocateElem($value){$count=1;$temp=$this->next;//也可以吧count与pos判断放在循环里while($temp){$count++;if($value==$temp->data){return$count;}}if(!$temp){return'没有该数据:'.$value;}}//特定值的前一个值publicfunctionPriorElem($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;}//特定值的下一个值publicfunctionNextElem($value){$temp=$this->next;if($temp&&$temp->next==null){return$temp->data.'已经是尾节点数据，已无后续';}while($temp){if($this->data==$value){return$temp->data;}}return'该单链表没有该数值'.$value;}//在指定位置之前插入数据/***@paramclassLNode$node***/publicfunctionListInsert($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';}//删除单链表指定位置的数据元素publicfunctionListDelete($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'该位置没有数据';}publicfunctionListTraverse(){$arr=array();$temp=$this;while($temp->next){$arr[]=$temp->data;$temp=$temp->next;}return$arr;}}?>

单链表测试require_once('LinkList.php');$list=newSingleLinkList();$listt=$list->CreateListHead(5);$list=$list->ListTraverse();var_dump($listt);

注意：应该没有注意的了，这个还是很有用武之地，只不过理论偏多，不喜欢的就跳过吧。本来也没有多大问题