数据结构对php,数据结构，数据结构与算法_PHP教程

你的名字 2022-11-12 09:53 139阅读 0赞

数据结构，数据结构与算法

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

一 顺序存储结构(用一段地址连续的存储单元一次存储线性表的数据元素)

1.1 三个属性:存储空间的起始位置；最大存储容量；当前长度

注：数组长度是存放线性表的存储空间的长度(一般是不变的)，不过语言可以动态增加容量，会带来性能损耗；

线性表长度是数据元素的个数；

线性表是从1开始数的，对应数组0的位置

1.2 获取元素、插入元素、删除元素(代码中展示)

1.3 顺序结构优缺点：

优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置元素

缺点：插入和删除操作需要移动大量的元素；当线性表长度裱花较大时，难以确定存储空间容量；造成存储空间'碎片'

//用一维数组模拟线性表

classSequential\_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 < 1 || $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 < 1 || $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 < 1 || $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 functionget\_arr()

\{return $this->arr;

\}/\*\*

\* 获取长度

\* @return\*/

public functionget\_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 true

array (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

boolean true

array (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为下个数组元素下标\*/

classSimple\_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 < 1 || $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 < 1 || $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 < 1 || $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 functionmalloc()

\{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 functionprint\_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 functionget\_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

6 5

array (size=2)'num' => int 2

'len' => int 10

http://www.bkjia.com/PHPjc/1119062.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/1119062.htmlTechArticle数据结构，数据结构与算法 线性表：零个或多个数据元素的有限序列(注：以下都是用的整型数据模拟) 一 顺序存储结构(用一段地址连...