当前位置:Gxlcms > PHP教程 > 数据结构---线性表学习(php模拟)数据结构与算法数据结构严蔚敏c#树形数据结

数据结构---线性表学习(php模拟)数据结构与算法数据结构严蔚敏c#树形数据结

时间:2021-07-01 10:21:17 帮助过:6人阅读

线性表:零个或多个数据元素的有限序列(注:以下都是用的整型数据模拟)

一 顺序存储结构(用一段地址连续的存储单元一次存储线性表的数据元素)
  1.1 三个属性:存储空间的起始位置;最大存储容量;当前长度
  注:数组长度是存放线性表的存储空间的长度(一般是不变的),不过语言可以动态增加容量,会带来性能损耗;
    线性表长度是数据元素的个数;
    线性表是从1开始数的,对应数组0的位置
  1.2 获取元素、插入元素、删除元素(代码中展示)

  1.3 顺序结构优缺点:
    优点:无须为表示表中元素之间的逻辑关系而增加额外的存储空间;可以快速地存取表中任一位置元素
    缺点:插入和删除操作需要移动大量的元素;当线性表长度裱花较大时,难以确定存储空间容量;造成存储空间'碎片'

    //用一维数组模拟线性表class Sequential_Structure
    {
        //线性表的长度private$num = 0;
        //数组长度private$len = 0;
        //数组模拟private$arr = array();

        /**
          * 初始化结构
          * @param Int $len 最大数组长度
          * @param Array $arr 数组
          * @return 
          */publicfunction __construct($len, Array$arr)
        {
            $this->len = $len;
            $length = count($arr);
            if($length > 0 && $length <= $len)
            {
                $this->arr = $arr;
                $this->num = $length;
            }
        }

        /**
          * 获取线性表元素
          * @param Int $i 需要获取的第几个元素
          * @return 
          */publicfunction get_elem($i)
        {
            if($this->num == 0 || $i < 1 || $i > $this->num) //判断查找是否合理returnfalse;
            return$this->arr[$i-1];    //返回数据,时间复杂度O(1)        }

        /**
          * 插入元素(顺序结构中,插入元素后,后面所有的数据都要后移,平均时间复杂度O(1)):
          * 如果插入位置不合理,失败
          * 如果线性长度大于数组长度,则返回错误或者动态增加容量
          * 从最后一个元素开始向前遍历到第i个位置,分别将它们向后移动一个位置
          * 将元素插入i位置
          * @param Int $i 需要插入到第几个元素
          * @param Int $elem 插入的节点
          * @return bool
          */publicfunction insert_elem($i,  $elem)
        {
            if($this->num == $this->len) //顺序线性表已满returnfalse;
            if($i < 1 || $i > ($this->num+1)) //i不在范围之内returnfalse;
            if ($i <= $this->num)  //若数据插入位置不在表尾            {
                for($k = $this->num-1; $k >= $i-1; --$k) //后面所有元素往后移动一位$this->arr[$k+1] = $this->arr[$k];
            }
            $this->arr[$i-1] = $elem; //插入元素            ++$this->num;
            returntrue;
        }

        /**
          * 删除元素(顺序结构中,插入元素后,后面所有的数据都要前移,平均时间复杂度O(1)):
          * 如果删除位置不合理,失败
          * 将元素删除
          * 从最后删除元素开始向后遍历到最后,分别将它们向前移动一个位置
          * @param Int $i 需要仓储的第几个元素
          * @return bool
          */publicfunction delete_elem($i)
        {
            if($this->num == 0) //线性表为空returnfalse;
            if($i < 1 || $i > $this->num) //删除位置不正确returnfalse;
            if($i < $this->num) //删除位置不是表尾            {
                for($k = $i; $k < $this->num; ++$k) //前移$this->arr[$k-1] = $this->arr[$k];
            }    
            unset($this->arr[$this->num-1]);
            --$this->num;
            returntrue;
        }

        /**
          * 获取顺序表
          * @return 
          */publicfunction get_arr()
        {
            return$this->arr;
        }

        /**
          * 获取长度
          * @return 
          */publicfunction get_len()
        {
           returnarray('num' => $this->num , 'len' => $this->len);
        }
    }
    
    $link = new Sequential_Structure(10,[1,4,8,7]);
    echo$link->get_elem(2);
    var_dump($link->insert_elem(5,5));
    var_dump($link->get_arr());
    var_dump($link->get_len());
    var_dump($link->delete_elem(1));
    var_dump($link->get_arr());
    var_dump($link->get_len());

输出:
booleantruearray (size=5) 0 => int 1 1 => int 4 2 => int 8 3 => int 7 4 => int 5 array (size=2) 'num' => int 5 'len' => int 10 booleantruearray (size=4) 0 => int 4 1 => int 8 2 => int 7 3 => int 5 array (size=2) 'num' => int 4 'len' => int 10

二 链表存储结构(n个节点链结成一个链表)
  2.1 单链表(用数组模拟)
    2.1.1 链表中第一个结点的存储位置为头指针(通常为了方便对链表进行操作,会在单链表的第一个结点前附设一个头结点)
      注 头指针:指向链表第一个结点的指针,若链表有头结点,这是指向头结点的指针;无论链表是否为空,头指针不为空
        头结点:放在第一元素的结点之前

/**
      *    用一维数组模拟线性表
      * array('data'=>data,'cur'=>cur) data为存放数据,cur为下个数组元素下标
      */class Simple_Link
    {
        //数组长度private$len = 0;
        //数组模拟private$arr = array();
        //数组中空闲的下标private$space_arr = array();

        /**
          * 初始化结构
          * @param Int $len 最大数组长度
          * @param Array $arr 数组
          * @return 
          */publicfunction __construct($len, Array$arr)
        {
            $this->len = $len;
            $length = count($arr);
            $this->arr[0]['data'] = $length;
            $this->arr[0]['cur'] = 0;
            for($i = 0; $i < $length; ++$i)
                $this->arr[$i]['cur'] = $i+1;  //模拟链表的指向if($length)
                $this->arr[$length]['cur'] = 0;  //最后一个结点指针空for($i = $length + 1; $i <= $len-$length ; ++$i) //空闲数组array_unshift($this->space_arr,$i);  
        }

        /**
          * 获取线性表元素:
          * 初始化$j从1开始
          * 当$j<$i,遍历链表
          * @param Int $i 需要获取的第几个元素
          * @return 
          */publicfunction get_elem($i)
        {
            if($i < 1 || $i > $this->arr[0]['data']) 
                returnfalse;
            $j = 1;
            $cur = $this->arr[0]['cur'];  //指向第一个结点while($j < $i)
            {
                $cur = $this->arr[$cur]['cur'];
                ++$j;
            }
        
            return$this->arr[$cur]['data'];
        }

        /**
          * 插入元素:
          * 初始化$j从1开始
          * 当$j<$i,遍历链表
          * 将元素插入i位置
          * @param Int $i 需要插入到第几个元素
          * @param Int $elem 插入的节点
          * @return bool
          */publicfunction insert_elem($i, $elem)
        {
            $len = $this->arr[0]['data'] + 1;
            if($i < 1 || $i > $len) 
                returnfalse;
            $j = $this->malloc(); //获取空闲下标if(!$j)
                returnfalse;
            $this->arr[$j]['data'] = $elem;
            
            $k = 1;
            $index = 0;
            $cur = !empty($this->arr[0]['cur']) ? $this->arr[0]['cur'] : 0;  //指向第一个结点while($k < $i)
            {
                //记录当前cur和下一个cur$index = $cur;  
                $cur = $this->arr[$index]['cur'];
                ++$k;
            }
            //改变指针指向$this->arr[$index]['cur'] = $j;
            $this->arr[$j]['cur'] = $cur;

            ++$this->arr[0]['data'];
            returntrue;

        }

        /**
          * 删除元素:
          * 初始化$j从1开始
          * 当$j<$i,遍历链表
          * 将i位置删除
          * @param Int $i 需要删除第几个元素
          * @return bool
          */publicfunction delete_elem($i)
        {
            $len = $this->arr[0]['data'];
            if($i < 1 || $i > $len) 
                returnfalse;
            
            $k = 1;
            $index = 0; 
            $cur = !empty($this->arr[0]['cur']) ? $this->arr[0]['cur'] : 0;  //指向第一个结点while($k < $i)
            {
                //记录当前cur和下一个cur$index = $cur;  
                $cur = $this->arr[$index]['cur'];
                ++$k;
            }
            //改变指针指向$this->arr[$index]['cur'] = $this->arr[$cur]['cur'];
        
            $this->free($cur);
            unset($this->arr[$cur]);
            --$this->arr[0]['data'];
            returntrue;
        }

        /**
          * 获取空闲的结点下标,也就是相当于申请一个空结点
          * @return 
          */privatefunction malloc()
        {
            if(empty($this->space_arr))
                returnfalse;
            returnarray_pop($this->space_arr);
        }

        /**
          * 释放结点
          * @param Int $cur 需要回收的结点下标
          */privatefunction free($cur)
        {
            array_push($this->space_arr, $cur);
        }

        /**
          * 打印
          * @return 
          */publicfunction print_arr()
        {
            $i = 0;
            if(!empty($this->arr[0]['data']))
            {    while($this->arr[$i]['cur'])
                {
                    $i = $this->arr[$i]['cur'];
                    echo$this->arr[$i]['data'].' ';
                }
            }
        }

        /**
          * 获取长度
          * @return 
          */publicfunction get_len()
        {
           returnarray('num' => $this->arr[0]['data'] , 'len' => $this->len);
        }
    }

    $link = new Simple_Link(10,array());
    var_dump($link->insert_elem(1,5));
    var_dump($link->insert_elem(2,4));
    var_dump($link->insert_elem(1,6));
    var_dump($link->delete_elem(3));
    echo$link->print_arr();
    var_dump($link->get_len());
        
        
输出: booleantruebooleantruebooleantruebooleantrue 6 5 array (size=2) 'num' => int 2 'len' => int 10

以上就介绍了数据结构 --- 线性表学习(php模拟),包括了数据结构,---方面的内容,希望对PHP教程有兴趣的朋友有所帮助。

人气教程排行