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


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


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


直接上代码

  1. 线性表


  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    <?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/>' ;
                        }
             }
             
         }
    ?>
  3. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    线性表测试
    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>' ;
  4. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    单链表<?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 ;
         }
         
    }
    ?>
  5. 1
    2
    3
    4
    5
    6
    单链表测试 require_once ( 'LinkList.php' );
     
    $list  =  new  SingleLinkList();
    $listt  =  $list ->CreateListHead(5);
    $list  =  $list ->ListTraverse();
    var_dump( $listt );
  6. 1
    注意：应该没有注意的了，这个还是很有用武之地，只不过理论偏多，不喜欢的就跳过吧。本来也没有多大问题