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