数据结构 - 线性表学习（php模拟）

程序员文章站 2022-05-12 18:47:27

...

数据结构 --- 线性表学习（php模拟）

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

一顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
　　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           */        public function __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           */        public function get_elem($i)        {            if($this->num == 0 || $i $i > $this->num) //判断查找是否合理                return false;            return $this->arr[$i-1];    //返回数据，时间复杂度O(1)        }        /**          * 插入元素（顺序结构中，插入元素后，后面所有的数据都要后移，平均时间复杂度O(1)）:          * 如果插入位置不合理，失败          * 如果线性长度大于数组长度，则返回错误或者动态增加容量          * 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置          * 将元素插入i位置          * @param Int $i 需要插入到第几个元素          * @param Int $elem 插入的节点          * @return bool          */        public function insert_elem($i,  $elem)        {            if($this->num == $this->len) //顺序线性表已满                return false;            if($i $i > ($this->num+1)) //i不在范围之内                return false;            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;            return true;        }        /**          * 删除元素（顺序结构中，插入元素后，后面所有的数据都要前移，平均时间复杂度O(1)）:          * 如果删除位置不合理，失败          * 将元素删除          * 从最后删除元素开始向后遍历到最后，分别将它们向前移动一个位置          * @param Int $i 需要仓储的第几个元素          * @return bool          */        public function delete_elem($i)        {            if($this->num == 0) //线性表为空                return false;            if($i $i > $this->num) //删除位置不正确                return false;            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;            return true;        }        /**          * 获取顺序表          * @return           */            public function get_arr()        {            return $this->arr;        }        /**          * 获取长度          * @return           */            public function get_len()        {           return array('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());

输出:
boolean truearray (size=5)  0 => int 1  1 => int 4  2 => int 8  3 => int 7  4 => int 5array (size=2)  'num' => int 5  'len' => int 10boolean truearray (size=4)  0 => int 4  1 => int 8  2 => int 7  3 => int 5array (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           */        public function __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*/        public function get_elem($i)        {            if($i $i > $this->arr[0]['data'])                 return false;            $j = 1;            $cur = $this->arr[0]['cur'];  //指向第一个结点            while($j $i)            {                $cur = $this->arr[$cur]['cur'];                ++$j;            }　　　　　　　　            return $this->arr[$cur]['data'];        }        /**          * 插入元素:          * 初始化$j从1开始          * 当$j*/        public function insert_elem($i, $elem)        {            $len = $this->arr[0]['data'] + 1;            if($i $i > $len)                 return false;            $j = $this->malloc(); //获取空闲下标            if(!$j)                return false;            $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'];            return true;        }        /**          * 删除元素:          * 初始化$j从1开始          * 当$j*/        public function delete_elem($i)        {            $len = $this->arr[0]['data'];            if($i $i > $len)                 return false;                        $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'];            return true;        }        /**          * 获取空闲的结点下标，也就是相当于申请一个空结点          * @return           */        private function malloc()        {            if(empty($this->space_arr))                return false;            return array_pop($this->space_arr);        }        /**          * 释放结点          * @param Int $cur 需要回收的结点下标          */        private function free($cur)        {            array_push($this->space_arr, $cur);        }        /**          * 打印          * @return           */            public function 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           */            public function get_len()        {           return array('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());                输出：        boolean true        boolean true        boolean true        boolean true        6 5        array (size=2)          'num' => int 2          'len' => int 10