這篇文章將為大家詳細(xì)講解有關(guān)php中鏈表的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
創(chuàng)新互聯(lián)建站專注于房縣網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供房縣營銷型網(wǎng)站建設(shè)，房縣網(wǎng)站制作、房縣網(wǎng)頁設(shè)計(jì)、房縣網(wǎng)站官網(wǎng)定制、成都微信小程序服務(wù)，打造房縣網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供房縣網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
鏈表的操作相對順序表來說就復(fù)雜了許多。因?yàn)镻HP確實(shí)已經(jīng)為我們解決了很多數(shù)組操作上的問題，所以我們可以很方便的操作數(shù)組，也就不用為數(shù)組定義很多的邏輯操作。比如在C中，數(shù)組是有長度限制的，而在PHP中我們就不會考慮這個問題。
首先，在之前的關(guān)于線性表的第一篇文章中我們就說過鏈表的定義，在這里，我們再復(fù)習(xí)一下之前的那個關(guān)于鏈表的圖來更清晰的理解鏈表的概念。
我們將圖中的節(jié)點(diǎn) Node 用類來表示：
重慶分公司
重慶分公司
/**
* 鏈表結(jié)構(gòu)
*/
class LinkedList
{
public $data;
public $next;
}一個鏈表類就看可以看做是鏈表中的一個節(jié)點(diǎn)，它包含兩個內(nèi)容，data 表示數(shù)據(jù)，next 表示下一個節(jié)點(diǎn)的指針。就像鏈條一樣一環(huán)套一環(huán)，這就是傳說中的鏈表結(jié)構(gòu)。
/**
* 生成鏈表
*/
function createLinkedList()
{
$list = new LinkedList();
$list->data = null;
$list->next = null;
return $list;
}
/**
* 初始化鏈表
* @param array $data 鏈表中要保存的數(shù)據(jù)，這里以數(shù)組為參考
* @return LinkedList 鏈表數(shù)據(jù)
*/
function Init(array $data)
{
// 初始化
$list = createLinkedList();
$r = $list;
foreach ($data as $key => $value) {
$link = new LinkedList();
$link->data = $value;
$link->next = null;
$r->next = $link;
$r = $link;
}
return $list;
}
$link = Init(range(1, 10));
print_r($link);
// LinkedList Object
// (
// [data] =>
// [next] => LinkedList Object
// (
// [data] => 1
// [next] => LinkedList Object
// (
// [data] => 2
// [next] => LinkedList Object
// (
// [data] => 3
// [next] => LinkedList Object
// (
// [data] => 4
// [next] => LinkedList Object
// (
// [data] => 5
// [next] => LinkedList Object
// (
// [data] => 6
// [next] => LinkedList Object
// (
// [data] => 7
// [next] => LinkedList Object
// (
// [data] => 8
// [next] => LinkedList Object
// (
// [data] => 9
// [next] => LinkedList Object
// (
// [data] => 10
// [next] =>
// )
// )
// )
// )
// )
// )
// )
// )
// )
// )
// )在使用鏈表的時候，我們一般會讓第一個結(jié)點(diǎn)不包含任何數(shù)據(jù)，僅僅是做為一個空的結(jié)點(diǎn)來指向第一個有數(shù)據(jù)的結(jié)點(diǎn)。這種結(jié)點(diǎn)我們可以稱之為頭結(jié)點(diǎn)，如果需要判斷鏈表是否為空的話，只需要判斷第一個結(jié)點(diǎn)的 next 是否為空就可以了。在上面的代碼中，創(chuàng)建鏈表 createLinkedList() 函數(shù)其實(shí)就是生成了這樣一個頭結(jié)點(diǎn)。
然后，我們通過 Init() 初始化函數(shù)來構(gòu)造這個鏈表。構(gòu)造過程還是比較簡單的，這里我們是固定的傳遞進(jìn)來一個數(shù)組，按照這個數(shù)組結(jié)構(gòu)來構(gòu)造這個鏈表，當(dāng)然，在實(shí)際應(yīng)用中，我們可以使用任何數(shù)據(jù)來構(gòu)造鏈表。構(gòu)造過程也并不復(fù)雜，將當(dāng)前結(jié)點(diǎn)賦值給 r 變量，然后創(chuàng)建一個新結(jié)點(diǎn)，讓 r->next 等于這個新創(chuàng)建的節(jié)點(diǎn)就可以了。構(gòu)造好的鏈表直接打印出來的結(jié)構(gòu)就是注釋中的形式。
function IteratorLinkedList(LinkedList $link)
{
while (($link = $link->next) != null) {
echo $link->data, ',';
}
echo PHP_EOL;
}鏈表的遍歷是不是非常像某些數(shù)據(jù)庫的游標(biāo)操作，或者像迭代器模式的操作一樣。沒錯，其實(shí)游標(biāo)和迭代器的結(jié)構(gòu)就是鏈表的一種表現(xiàn)形式。我們不停的尋找 $next 直到?jīng)]有下一個結(jié)點(diǎn)為止，這樣就完成了一次鏈表的遍歷?？梢钥闯觯@個過程的時間復(fù)雜度是 O(n) 。
/**
* 鏈表指定位置插入元素
* @param LinkedList $list 鏈表數(shù)據(jù)
* @param int $i 位置
* @param mixed $data 數(shù)據(jù)
*/
function Insert(LinkedList &$list, int $i, $data)
{
$j = 0;
$item = $list;
// 遍歷鏈表，找指定位置的前一個位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 創(chuàng)建一個新節(jié)點(diǎn)
$s = new LinkedList();
$s->data = $data;
// 新創(chuàng)建節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向原 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)，也就是當(dāng)前的 i 節(jié)點(diǎn)
$s->next = $item->next;
// 將 i-1 節(jié)點(diǎn)的下一跳節(jié)點(diǎn)指向 s ，完成將 s 插入指定的 i 位置，并讓原來的 i 位置元素變成 i+1 位置
$item->next = $s;
return true;
}
/**
* 刪除鏈表指定位置元素
* @param LinkedList $list 鏈表數(shù)據(jù)
* @param int $i 位置
*/
function Delete(LinkedList &$list, int $i)
{
$j = 0;
$item = $list;
// 遍歷鏈表，找指定位置的前一個位置
while ($j < $i - 1) {
$item = $item->next;
$j++;
}
// 如果 item 不存在或者 $i > n+1 或者 $i < 0
if ($item == null || $j > $i - 1) {
return false;
}
// 使用一個臨時節(jié)點(diǎn)保存當(dāng)前節(jié)點(diǎn)信息，$item 是第 i-1 個節(jié)點(diǎn)，所以 $item->next 就是我們要找到的當(dāng)前這個 i 節(jié)點(diǎn)
$temp = $item->next;
// 讓當(dāng)前節(jié)點(diǎn)，也就是目標(biāo)節(jié)點(diǎn)的上一個節(jié)點(diǎn)， i-1 的這個節(jié)點(diǎn)的下一跳（原來的 i 位置的節(jié)點(diǎn)）變成原來 i 位置節(jié)點(diǎn)的下一跳 next 節(jié)點(diǎn)，讓i位置的節(jié)點(diǎn)脫離鏈條
$item->next = $temp->next;
return true;
}
// 插入
Insert($link, 5, 55);
// 遍歷鏈表
IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,
// 刪除
Delete($link, 7);
// 遍歷鏈表
IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,鏈表的插入和刪除其實(shí)很類似，都是需要尋找到插入或刪除位置的前一個元素，也就是第 i-1 這個位置的元素。然后通過對這個元素的 next 指針的操作來實(shí)現(xiàn)鏈表元素的插入刪除操作。
它們在遍歷和位置判斷這兩個功能中的代碼其實(shí)都是一樣的，不同的是創(chuàng)建時要新創(chuàng)建一個結(jié)點(diǎn)，然后讓這個結(jié)點(diǎn)的 next 指向之前 i-1 位置元素的 next ，再將 i-1 位置元素的 next 指向新創(chuàng)建的這個結(jié)點(diǎn)。而刪除操作則是保存要刪除這個位置 i 的結(jié)點(diǎn)到一個臨時變量中，然后將 i-1 位置元素的 next 指向刪除位置 i 的 next 。
上面的解釋需要結(jié)合代碼一步一步來看，當(dāng)然，我們也可以結(jié)合下面的這個圖來學(xué)習(xí)。插入和刪除操作是鏈表操作的核心，也是最復(fù)雜的部分，需要多多理解掌握。
/**
* 根據(jù)位置查找元素位置
* @param LinkedList $list 鏈表數(shù)據(jù)
* @param int $i 位置
*/
function GetElem(LinkedList &$list, int $i)
{
$item = $list;
$j = 1; // 從第一個開始查找，0是頭結(jié)點(diǎn)
while ($item && $j <= $i) {
$item = $item->next;
$j++;
}
if (!$item || $j > $i + 1) {
return false;
}
return $item->data;
}
/**
* 根據(jù)數(shù)據(jù)查找數(shù)據(jù)元素所在位置
* @param LinkedList $list 鏈表數(shù)據(jù)
* @param mixed $data 數(shù)據(jù)
*/
function LocateElem(LinkedList &$list, $data)
{
$item = $list;
$j = 1; // 從第一個開始查找，0是頭結(jié)點(diǎn)
while (($item = $item->next)!=null) {
if($item->data == $data){
return $j;
}
$j++;
}
return false;
}
// 獲取指定位置的元素內(nèi)容
var_dump(GetElem($link, 5)); // int(55)
// 獲取指定元素所在的位置
var_dump(LocateElem($link, 55)); // int(5)鏈表的查找有兩種形式，一種是給一個位置，比如要我要第五個位置的元素內(nèi)容，那么就是根據(jù)指定位置查找元素的值，就像數(shù)組的下標(biāo)一樣。不過需要注意的是，鏈表的下標(biāo)是從 1 開始的，因?yàn)?0 的位置是我們的頭結(jié)點(diǎn)了。當(dāng)然，我們也可以變換代碼忽略掉頭結(jié)點(diǎn)讓它和數(shù)組保持一致，但這樣的話，鏈表的特點(diǎn)就不明顯了，所以這里的測試代碼我們還是以 1 為起始。
另一種查找就是給定一個數(shù)據(jù)內(nèi)容，查找它在鏈表的什么位置。其實(shí)這兩種算法都是在遍歷整個鏈表，本質(zhì)上沒有什么區(qū)別。由于鏈表不像數(shù)組一樣有下標(biāo)的能力，所以它的這些查找操作的時間復(fù)雜度都是 O(n) 。
關(guān)于“php中鏈表的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
