線性表：零個或多個數據元素的有限序列（注：以下都是用的整型數據模擬）
一 順序存儲結構（用一段地址連續的存儲單元一次存儲線性表的數據元素）
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 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為下個數組元素下標
*/
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
