最近想起來兩件事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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
