数据结构 --- 线性表学习（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 < 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 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
PHP与MySQL程序设计3
下载
本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。 本书内容全面深入，适合各层次PHP和MySQL开发人员阅读，既是优秀的学习教程，也可用作参考手册。
立即学习“PHP免费学习笔记（深入）”；
立即学习“PHP免费学习笔记（深入）”；
二 链表存储结构（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<$i，遍历链表 * @param Int $i 需要获取的第几个元素 * @return */ 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<$i，遍历链表 * 将元素插入i位置 * @param Int $i 需要插入到第几个元素 * @param Int $elem 插入的节点 * @return bool */ 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<$i，遍历链表 * 将i位置删除 * @param Int $i 需要删除第几个元素 * @return bool */ 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 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
立即学习“PHP免费学习笔记（深入）”；
