当前位置：首页 > PHP教程 > php应用 > 列表

php数据结构之顺序链表与链式线性表示例

发布:smiling　来源: PHP粉丝网 　添加日期：2021-08-31 11:24:32　浏览: 评论：0　

这篇文章主要介绍了php数据结构之顺序链表与链式线性表,结合实例形式较为详细的分析了php实现顺序链表与链式线性表的各种常用操作技巧,需要的朋友可以参考下。

本文实例讲述了php数据结构之顺序链表与链式线性表，分享给大家供大家参考，具体如下：

链表操作

1、InitList(L)：初始化链表

2、DestroyList(L)：删除连接

3、ClearList(L)：清空链表

4、ListEmpty(L)：判断是否为空

5、     ListLength(L)：链表长度

6、     getElem(L,i)：取出元素

7、LocateElem(L,e)：判断e是否在链表中

8、PriorElem(L,i)：前驱

9、 NextElem(L,i)：后继

10、ListInsert(L,i,e)：插入元素

11、ListDelete(L,i,)：删除元素

顺序链表操作

  1. <?php 
  2. class ArrayList{ 
  3.   private $list; 
  4.   private $size; 
  5.   //构造函数 
  6.   public function __construct(){ 
  7.    $this->list=array(); 
  8.    $this->size=0; 
  9.   } 
  10.   public function initList(){ 
  11.    $this->list=array(); 
  12.    $this->size=0; 
  13.   } 
  14.   //删除链表 
  15.   public function destoryList(){ 
  16.    if(isset($this->list)){ 
  17.      unset($this->list); 
  18.     $this->size=0; 
  19.    } 
  20.   } 
  21.   //清空链表 
  22.   public function clearList(){ 
  23.    if(isset($this->list)){ 
  24.     unset($this->list); 
  25.    } 
  26.    $this->list=array(); 
  27.    $this->size=0; 
  28.   } 
  29.   //判断链表是否为空 
  30.   public function emptyList(){ 
  31.    if(isset($this->list)){ 
  32.      if($this->size=0) 
  33.       return TRUE; 
  34.     else 
  35.      return FALSE; 
  36.    } 
  37.   } 
  38.   //链表长度 
  39.   public function lenghtList(){ 
  40.    if(isset($this->list)){ 
  41.     return $this->size; 
  42.    } 
  43.   } 
  44.   //取元素 
  45.   public function getElem($i){ 
  46.    if($i<1||$i>$this->size){ 
  47.     echo "溢出<br>"; 
  48.     exit(); 
  49.    } 
  50.    if(isset($this->list)&&is_array($this->list)){ 
  51.     return $this->list[$i-1]; 
  52.    } 
  53.   } 
  54.   //是否在链表中 
  55.   public function locateElem($e){ 
  56.    if(isset($this->list)&&is_array($this->list)){ 
  57.     for($i=0;$i<$this->size;$i++){ 
  58.       if($this->list[$i]==$e){ 
  59.        return $i+1; 
  60.       } 
  61.     } 
  62.     return 0; 
  63.    } 
  64.   } 
  65.   //前驱 
  66.   public function priorElem($i){ 
  67.    if($i<1||$i>$this->size){ 
  68.     echo "溢出"; 
  69.     exit(); 
  70.    } 
  71.    if($i==1){ 
  72.     echo "没有前驱"; 
  73.     exit(); 
  74.    } 
  75.    if(isset($this->list)&&is_array($this->list)){ 
  76.     return $this->list[$i-2]; 
  77.    } 
  78.   } 
  79.   //后继 
  80.   public function nextElem($i){ 
  81.    if($i<1||$i>$this->size){ 
  82.     echo "溢出"; 
  83.     exit(); 
  84.    } 
  85.    if($i==$this->size){ 
  86.     echo "没有后继"; 
  87.     exit(); 
  88.    } 
  89.    if(isset($this->list)&&is_array($this->list)){ 
  90.     return $this->list[$i]; 
  91.    } 
  92.   } 
  93.   //插入元素 
  94.   public function insertList($i,$e){ 
  95.    if($i<1||$i>$this->size+1){ 
  96.     echo "插入元素位置有误"; 
  97.     exit(); 
  98.    } 
  99.    if(isset($this->list)&&is_array($this->list)){ 
  100.     if($this->size==0){ 
  101.       $this->list[$this->size]=$e; 
  102.       $this->size++; 
  103.     }else{ 
  104.       $this->size++; 
  105.       for($j=$this->size-1;$j>=$i;$j--){ 
  106.        $this->list[$j]=$this->list[$j-1]; 
  107.       } 
  108.       $this->list[$i-1]=$e; 
  109.     } 
  110.    } 
  111.   } 
  112.   //删除元素 
  113.   public function deleteLlist($i){ 
  114.    if($i<1||$i>$this->size){ 
  115.     echo "删除元素位置有误"; 
  116.     exit(); 
  117.    } 
  118.    if(isset($this->list)&&is_array($this->list)){ 
  119.     if($i==$this->size){ 
  120.       unset($this->list[$this->size-1]); 
  121.     }else{ 
  122.       for($j=$i;$j<$this->size;$j++){ 
  123.        $this->list[$j-1]=$this->list[$j]; 
  124.       } 
  125.       unset($this->list[$this->size-1]); 
  126.      } 
  127.    $this->size--; 
  128.    } 
  129.   } 
  130.   //遍历 
  131.   public function printList(){ 
  132.    if(isset($this->list)&&is_array($this->list)){ 
  133.     foreach ($this->list as $value){ 
  134.       echo $value." "; 
  135.     } 
  136.     echo "<br>"; 
  137.    } 
  138.   } 
  139. } 
  140. ?> 

链式线性表

  1. <?php 
  2. class LinkList { 
  3.   private $head; 
  4.   private $size; 
  5.   private $list; 
  6.   public function __construct(){ 
  7.    $this->head=""; 
  8.    $this->size=0; 
  9.    $this->list=array(); 
  10.   } 
  11.   public function initList(){ 
  12.    $this->head=""; 
  13.    $this->size=0; 
  14.    $this->list=array(); 
  15.   } 
  16.   //删除链表 
  17.   public function destoryList(){ 
  18.    if(isset($this->list)&&isset($this->head)){ 
  19.     unset($this->list); 
  20.     unset($this->head); 
  21.    } 
  22.   } 
  23.   //清空链表 
  24.   public function clearList(){ 
  25.    if(isset($this->list)){ 
  26.     unset($this->list); 
  27.    } 
  28.    $this->list=array(); 
  29.    $this->size=0; 
  30.    $this->head=""; 
  31.   } 
  32.   //判断链表是否为空 
  33.   public function emptyList(){ 
  34.    if(isset($this->list)){ 
  35.     if($this->size==0) 
  36.       returnTRUE; 
  37.     else 
  38.       returnFALSE; 
  39.    } 
  40.   } 
  41.   //链表长度 
  42.   public function lenghtList(){ 
  43.    if(isset($this->list)){ 
  44.     return$this->size; 
  45.    } 
  46.   } 
  47.   //取元素 
  48.   public function getElem($i){ 
  49.    if($i<1||$i>$this->size){ 
  50.     echo "溢出<br>"; 
  51.     exit(); 
  52.    } 
  53.    if(isset($this->list)&&is_array($this->list)){ 
  54.     $j=1; 
  55.     //头指针 
  56.     $tmp=$this->head; 
  57.     while($i>$j){ 
  58.       if($this->list[$tmp]['next']!=null){ 
  59.        $tmp=$this->list[$tmp]['next']; 
  60.        $j++; 
  61.       } 
  62.     } 
  63.     return  $this->list[$tmp]['data']; 
  64.    } 
  65.   } 
  66.   //是否在链表中 
  67.   public function locateElem($e){ 
  68.    if(isset($this->list)&&is_array($this->list)){ 
  69.     $tmp=$this->head; 
  70.     while($this->list[$tmp]['data']!=$e){ 
  71.       if($this->list[$tmp]['next']!=null){ 
  72.        $tmp=$this->list[$tmp]['next']; 
  73.       }else{ 
  74.        returnFALSE; 
  75.       } 
  76.     } 
  77.     return TRUE; 
  78.    } 
  79.   } 
  80.   //前驱 
  81.   public function priorElem($i){ 
  82.    if($i<1||$i>=$this->size){ 
  83.     echo "溢出"; 
  84.     exit(); 
  85.    } 
  86.    if($i==1){ 
  87.     echo "没有前驱"; 
  88.     exit(); 
  89.    } 
  90.    $tmp=$this->head; 
  91.    $j=1; 
  92.    while($i>$j+1){ 
  93.     if($this->list[$tmp]['next']!=null){ 
  94.       $j++; 
  95.       $tmp=$this->list[$tmp]['next']; 
  96.     } 
  97.    } 
  98.    return$this->list[$tmp]['data']; 
  99.   } 
  100.   //后继 
  101.   public function nextElem($i){ 
  102.    if($i<1||$i>$this->size){ 
  103.     echo "溢出"; 
  104.     exit(); 
  105.    } 
  106.    if($i==$this->size){ 
  107.     echo "没有后继"; 
  108.     exit(); 
  109.    } 
  110.    $j=1; 
  111.    $tmp=$this->head; 
  112.    while($i>=$j){ 
  113.     if($this->list[$tmp]['next']!=null){ 
  114.       $j++; 
  115.       $tmp=$this->list[$tmp]['next']; 
  116.     } 
  117.    } 
  118.    return$this->list[$tmp]['data']; 
  119.   } 
  120.   //插入元素:后插法 
  121.   public function insertList($i,$e){ 
  122.    if(isset($this->list)&&is_array($this->list)){ 
  123.     //空表 
  124.     if($this->size==0){ 
  125.       $this->head=$this->uuid(); 
  126.       $this->list[$this->head]['data']=$e; 
  127.       $this->list[$this->head]['next']=NULL; 
  128.       $this->size++; 
  129.     }else{ 
  130.       if($i<1||$i>$this->size){ 
  131.       echo"插入元素位置有误"; 
  132.       exit(); 
  133.       } 
  134.       $j=1; 
  135.       $tmp=$this->head; 
  136.       while($i>$j){ 
  137.        if($this->list[$tmp]['next']!=null){ 
  138.          $j++; 
  139.          $tmp=$this->list[$tmp]['next']; 
  140.        } 
  141.       } 
  142.       $find=$tmp; 
  143.       $id=$this->uuid(); 
  144.       if($this->list[$find]['next']==null){ 
  145.        //尾部 
  146.        $this->list[$find]['next']=$id; 
  147.        $this->list[$id]['data']=$e; 
  148.        $this->list[$id]['next']=null; 
  149.        $this->size++; 
  150.       }else{ 
  151.        //中间 
  152.        $this->list[$id]['next']=$this->list[$find]['next']; 
  153.        $this->list[$find]['next']=$id; 
  154.        $this->list[$id]['data']=$e; 
  155.        $this->size++; 
  156.       } 
  157.     } 
  158.    } 
  159.   } 
  160.   //删除元素 
  161.   public function deleteLlist($i){ 
  162.    if($i<1||$i>$this->size){ 
  163.     echo "删除元素位置有误"; 
  164.     exit(); 
  165.    } 
  166.    if(isset($this->list)&&is_array($this->list)){ 
  167.     if($i==1){ 
  168.       //删除头元素 
  169.       $this->head=$this->list[$this->head]['next']; 
  170.     }else{ 
  171.       $tmp=$this->head; 
  172.       $j=1; 
  173.       while($i>$j+1){ 
  174.        if($this->list[$tmp]['next']!=null){ 
  175.          $j++; 
  176.          $tmp=$this->list[$tmp]['next']; 
  177.        } 
  178.       } 
  179.       //找到删除元素的前驱 
  180.       $find=$tmp; 
  181.       //删除的元素 
  182.       if($this->list[$find]['next']!=null){ 
  183.        //不是最后一个元素 
  184.        $delete=$this->list[$find]['next']; 
  185.        $this->list[$find]['next']=$this->list[$delete]['next']; 
  186.       }else{ 
  187.        $this->list[$tmp]['next']=null; 
  188.       } 
  189.     } 
  190.    } 
  191.   } 
  192.   public function traverstList(){ 
  193.    $tmp=$this->head; 
  194.    while($this->list[$tmp]['next']!=NULL){ 
  195.     $this->printList($this->list[$tmp]['data'],TRUE); 
  196.     $tmp=$this->list[$tmp]['next']; 
  197.    } 
  198.    $this->printList($this->list[$tmp]['data'],FALSE); 
  199.   } 
  200.   public function printList($str,$flag){ 
  201.    if($flag){ 
  202.     echo$str."->"; 
  203.    }else { 
  204.     echo$str."<br>"; 
  205.    } 
  206.   } 
  207.   //uuid 唯一码 
  208.   public  function uuid($prefix = '') { 
  209.   $chars =md5(uniqid(mt_rand(), true)); 
  210.   $uuid = substr($chars,0,8) . '-'; 
  211.   $uuid .=substr($chars,8,4) . '-'; 
  212.   $uuid .=substr($chars,12,4) . '-'; 
  213.   $uuid .=substr($chars,16,4) . '-'; 
  214.   $uuid .= substr($chars,20,12); 
  215.   return $prefix. $uuid; 
  216.   } 
  217. } 
  218. ?>

Tags: php顺序链表 php链式线性表

分享到：

推荐文章

热门文章

最新评论文章