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