資訊專欄INFORMATION COLUMN
開始對數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)
今天寫代碼換了一個字體，以前一直用console很好看，今天發(fā)現(xiàn)一個更喜歡的風(fēng)格Source Code Pro
上兩張圖，還是挺好看的?。?！
步入正題，講講鏈表的操作節(jié)點
首先得有一個節(jié)點類，用于存儲數(shù)據(jù)
data = X; 賦值
$this->data = $data;
}
}
鏈表管理類（用于操作節(jié)點數(shù)據(jù)）
操作類的代碼由于太長，我們分部分解析
頭插入（因為比較簡單，所以先講這個）聽名字，就知道是從頭部插入一個節(jié)點
當(dāng)鏈表為空，則初始化當(dāng)前節(jié)點
當(dāng)鏈表不為空，把新節(jié)點作為頭結(jié)點
public function insertHead(int $data) : bool
{
///////////////////////////////////////////////////////////////////////////
// +-----------+ +--------+ +--------+
// | | | | | |
// | head node | +> | node | +> | node | +>
// | | | | | | | | |
// | | | | | | | | |
// | next | | | next | | | next | |
// +------+----+ | +----+---+ | +----+---+ |
// | | | | | |
// +------+ +-----+ +-----+
///////////////////////////////////////////////////////////////
// +-----------+ +--------+ +--------+
// | | | | | |
// +---> | head node | +> | node | +> | node | +>
// | | | | | | | | | |
// | | | | | | | | | |
// | | next | | | next | | | next | |
// | +------+----+ | +----+---+ | +----+---+ |
// | | | | | | |
// +--------+ | +------+ +-----+ +-----+
// | | |
// |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
//
// 1. 實例化一個數(shù)據(jù)節(jié)點
// 2. 使當(dāng)前節(jié)點的下一個等于現(xiàn)在的頭結(jié)點
// 即使當(dāng)前頭結(jié)點是 null，也可成立
// 3. 使當(dāng)前節(jié)點成為頭結(jié)點
// 即可完成頭結(jié)點的插入
$newNode = new Node($data);
$newNode->next = $this->head;
$this->head = $newNode;
return true;
}
插入節(jié)點（index=0 是頭結(jié)點，依次下去，超出位置返回 false）
public function insert(int $index = 0, int $data) : bool
{
// 頭結(jié)點的插入, 當(dāng)頭部不存在，或者索引為0
if (is_null($this->head) || $index === 0) {
return $this->insertHead($data);
}
// 正常節(jié)點的插入, 索引從 0 開始計算
// 跳過了頭結(jié)點，從 1 開始計算
$currNode = $this->head;
$startIndex = 1;
// 遍歷整個鏈表，如果當(dāng)前節(jié)點是 null，則代表到了尾部的下一個，退出循環(huán)
for ($currIndex = $startIndex; ! is_null($currNode); ++ $currIndex) {
////////////////////////////////////////////////////////////////////////////
///
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +----+---+ | +------+------+ | +----+---+ |
// | | | | | | | |
// +-----+ +-----+ +--------+ +-----+
////////////////////////////////////////////////////////////////////////////
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +--------+ | +------+------+ | +----+---+ |
// | | +--------+ | | | | |
// +-----+ | | | +--------+ +-----+
// |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
////////////////////////////////////////////////////////////////////////////
//
// +--------+ +--------+ +-------------+ +--------+
// | | | | | | | |
// | node | +> |currNode| +> |currNode next| +> | node | +>
// | | | | | | | | | | | |
// | | | | | | | | | | | |
// | next | | | next | | | next | | | next | |
// +----+---+ | +----+---+ | +------+------+ | +----+---+ |
// | | | +--------+ | | | | |
// +-----+ | | | | +--------+ +-----+
// +----> |new node| |
// | | |
// | | |
// | next | |
// +----+---+ |
// | |
// +-----+
//
// 1. 當(dāng)前索引等于傳入?yún)?shù)的索引
// 2. 實例化新數(shù)據(jù)節(jié)點
// 3. 新節(jié)點的下一個指向當(dāng)前節(jié)點的下一個節(jié)點
// 4. 當(dāng)前節(jié)點的下一個節(jié)點指向新節(jié)點
if ($currIndex === $index) {
$newNode = new Node($data);
$newNode->next = $currNode->next;
$currNode->next = $newNode;
return true;
}
// 移動到下一個節(jié)點
$currNode = $currNode->next;
}
return false;
}
以上兩個這是插入的基本操作。看一下實例的代碼。
insertHead(8); // 5 8 $manager->insertHead(5); // 1 5 8 $manager->insertHead(1); // 1 2 5 8 $manager->insert(1, 2); // false 節(jié)點元素不足 6 個 $manager->insert(5, 4); // 1 2 5 8 9 $manager->insertEnd(9); // 3 $manager->find(8); // 1 2 8 9 $manager->delete(2);查找
查找鏈表的值也是很簡單的，只要遍歷即可
/**
* 查找鏈表的值中的索引
* 成功返回索引值，找不到返回 -1
*
* @param int $data
* @return int
*/
public function find(int $data) : int
{
$currNode = $this->head;
// 查找還是很簡單的，只要遍歷一次鏈表，然后再判斷值是否相等就可以了
for ($i = 0; ! is_null($currNode); ++ $i) {
if ($currNode->data === $data) {
return $i;
}
$currNode = $currNode->next;
}
return -1;
}
只需要遍歷一次鏈表，找到相等的值，找到返回索引值，找不到返回 -1
刪除/**
* 刪除鏈表的節(jié)點
*
* @param int $index
* @return bool
*/
public function delete(int $index) : bool
{
// 沒有任何節(jié)點，直接跳過
if (is_null($this->head)) {
return false;
} elseif ($index === 0) {
// 頭結(jié)點的刪除
$this->head = $this->head->next;
}
// 這里的開始的索引是 1
// 但當(dāng)前節(jié)點指向的確實 頭結(jié)點
// 因為刪除的時候必須標(biāo)記刪除的前一個節(jié)點
// for 的判斷是判斷下一個節(jié)點是否為 null
// $currNode 是操作的節(jié)點
// $currNode->next 是要刪除的節(jié)點
$startIndex = 1;
$currNode = $this->head;
for ($i = $startIndex; ! is_null($currNode->next); ++ $i) {
if ($index === $i) {
// 使當(dāng)前節(jié)點等于要刪除節(jié)點的下一個
// 即可完成刪除
$currNode->next = $currNode->next->next;
break;
}
$currNode = $currNode->next;
}
return true;
}
End
代碼已托管在github
后續(xù)有時間繼續(xù)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，雙鏈表，樹之類的?。?！
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/28654.html
摘要：一鏈表鏈表是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針。指向整個列表的指針可以被稱作訪問指針。 你好，是我琉憶，PHP程序員面試筆試系列圖書的作者。 本周（2019.3.18至3.22）的一三五更新的文章如下： 周一：PHP面試?？贾?dāng)?shù)據(jù)結(jié)構(gòu)——鏈表的概念周三：PHP面試常考之?dāng)?shù)據(jù)結(jié)構(gòu)——棧和隊列周五：PHP面試?？贾?..
摘要：數(shù)組是最常用的數(shù)據(jù)類型，同時容易上手也得益于其強大的數(shù)組，但是數(shù)組在中是如何實現(xiàn)的呢首先，我們還是先了解下相關(guān)的數(shù)據(jù)結(jié)構(gòu)，為下面的內(nèi)容打好基礎(chǔ)哈希表哈希表，顧名思義，即將不同的關(guān)鍵字映射到不同單元的一種數(shù)據(jù)結(jié)構(gòu)。 數(shù)組是PHPer最常用的數(shù)據(jù)類型，同時php容易上手也得益于其強大的數(shù)組，但是數(shù)組在php中是如何實現(xiàn)的呢？ 首先，我們還是先了解下相關(guān)的數(shù)據(jù)結(jié)構(gòu)，為下面的內(nèi)容打好基礎(chǔ) 哈希...
摘要：本文首發(fā)于我的博客引用數(shù)據(jù)結(jié)構(gòu)與算法鏈表該文章提供的版的鏈表的實現(xiàn)。 本文首發(fā)于我的博客引用：Java數(shù)據(jù)結(jié)構(gòu)與算法——鏈表 該文章提供的JAVA版的鏈表的實現(xiàn)。 現(xiàn)在我也貼一下PHP版的鏈表的實現(xiàn)： class Node { private $data; private $next; public function getData() { ...
php中的哈希表 php中的變量是以符號表的方式進(jìn)行存儲的，實際上也是個HashTable，哈希表是通過特定的哈希算法將索引轉(zhuǎn)換成特定的index然后映射到對應(yīng)的槽中，然后采用拉鏈法，在一個槽中使用鏈表將數(shù)據(jù)進(jìn)行存儲，鏈表的時間復(fù)雜度為O(n)。 php中的hashtable的結(jié)構(gòu)定義在Zend/zend_hash.h文件中： //保存數(shù)據(jù)的單鏈表結(jié)構(gòu) typedef struct bucket ...
閱讀 3615·2021-11-15 11:38
閱讀 2812·2021-11-11 16:55
閱讀 2565·2021-11-08 13:22
閱讀 2640·2021-11-02 14:45
閱讀 1325·2021-09-28 09:35
閱讀 2606·2021-09-10 10:50
閱讀 475·2019-08-30 15:44
閱讀 2788·2019-08-29 17:06
