在 PHP 中實現連結串列

參考文件         The SplDoublyLinkedList class

(PHP 5 >= 5.3.0, PHP 7, PHP 8)

連結串列是在許多程式語言中實現的常見資料結構。它是線性的,包含相互連結的節點。
每個節點都包含資料和到相鄰節點的連結。因此,連結串列形成了一個節點鏈。連結串列有不同的變體。
1.單連結串列:單向。它只在向前的方向上移動。
2.雙連結串列:是雙向的。它向前和向後兩個方向遍歷。
3.迴圈連結串列:單向迴圈。
4.迴圈雙向連結串列:雙向迴圈。

我們可以在連結串列中進行各種操作。基本操作如下:
1.遍歷
2.插入
3.刪除
4.更新
5.搜尋
PHP 提供了一個類 SplDoublyLinkedList 用於實現連結串列。它是一個雙向連結串列。

$list = new SplDoublyLinkedList();
$list->push(10);
$list->push(15);
$list->push(20);
displayList($list);
function displayList($list) {
for ($list->rewind(); $list->valid(); $list->next()){
echo $list->current()."<br>";
}
}

push() 方法接受要推送的引數並允許在列表中附加值。該元素將被推到連結串列的末尾。
rewind() 方法從連結串列的開頭回退迭代器。例如,迭代器將移動到列表的第一個元素。
valid() 方法檢查連結串列是否包含更多節點,next() 方法移動到連結串列的下一項。因此,我們可以在 for 迴圈中使用上述示例中的這些方法來遍歷連結串列的元素。
在迴圈內部,current( )方法表示當前元素。因此,將列印當前元素。使用 pop() 方法刪除連結串列中的元素

使用 pop() 方法刪除連結串列中的元素
我們可以使用 pop() 方法從連結串列中刪除最後一個元素。該方法不接受任何引數。

從連結列表中查詢頂部和底部值
我們可以使用 top() 方法找到連結串列的頂部值,對於底部值,我們可以使用 bottom() 方法

echo "top_element=".$list->top()."<br>";
echo "bottom_element=".$list->bottom();

使用 add() 方法在連結串列中插入值
我們可以使用 add() 方法通過指定位置在連結串列中插入元素。該方法有兩個引數。
第一個引數是要插入專案的索引,第二個引數是要插入的專案。例如,以 2 和 50 為引數呼叫 add() 方法並呼叫 displayList() 方法。

$list->add(2,50);
displayList($list);

PHP          link.php

注意插入點會從第n個參數下插入

圖說演算法使用JavaScript(十一)

        堆疊結構在電腦中的應用相當廣泛,時常被用來解決電腦的問題,例如前面所談到的遞迴呼叫、副程式的呼叫,至於在日常生活中的應用也隨處可以看到,例如大樓電梯、貨架上的貨品等等,都是類似堆疊的資料結構原理。
        佇列在電腦領域的應用也相當廣泛,例如計算機的模擬simulation、CPU的工作排程Job Scheduling、線上同時周邊作業系統的應用與圖形走訪得先廣後深搜尋法BFS。由於堆疊與佇列都是抽象資料型態Abstract Data Type,ADT,本章終將為各位介紹相關演算法。
         堆疊在程式設計領域中,包含以下兩種設計方式,分別為陣列結構與鏈結串列結構。

6-1陣列實作堆疊輕鬆學

         以陣列結構來製作堆疊的好處是製作與設計的演算法都相當簡單,但因為如果堆疊本身是變動的話,大小並無法事先規劃宣告,太大時浪費空間,太小則不夠使用。

相關演算法如下
//判斷是否空堆疊
var isEmpy=()=>{
if (top==-1)
return true;
else
return false;
}
//將指定的資料存入堆疊
var push=(data)=>{
if (top>=MAXSTACK-1)
process.stdout.write('堆疊已滿,無法再加入');
else {
top +=1;
stack[top]=data; //將資料存入堆疊
}
}
//從堆疊取出資料
var pop=()=>{
if (isEmpty())
process.stdout.write('堆疊是空');
else {
process.stdout.write('彈出的元素為: '+stack[top]+'\n');
top=top-1;
}
}

JS            array_stack.js

const MAXSTACK=100; //定義最大堆疊容量
stack=[]; //堆疊的陣列宣告
top=-1; //堆疊的頂端

//判斷是是否為空堆疊
var isEmpty=()=>{
	if(top==-1)
		return true;
	else
		return false;
}

//將指定的資料存入堆疊
var push=(data)=> {
	if (top>=MAXSTACK-1)
		process.stdout.write('堆疊已滿,無法再加入');
	else {
		top +=1;
		stack[top]=data;//將資料存入堆疊
	}
}

//從堆疊取出資料
var pop=()=> {
	if (isEmpty())
		process.stdout.write('堆疊是空');
	else {
		process.stdout.write('彈出的元素為:'+stack[top]+'\n');
		top=top-1;
	}
}

//主程式
i=2;
count=0;
const prompt = require('prompt-sync')();
while(true) {
	const i = parseInt(prompt('要推入堆疊,請輸入1,彈出則輸入0,停止操作則輸入-1:'));
	if (i==-1)
		break;
	else if (i==1) {
		const value = parseInt(prompt('請輸入元素值:'));
		push(value);
	}
	else if (i==0)
		pop();
}

process.stdout.write('========================\n');

if (top<0)
	process.stdout.write('\n 堆疊是空的\n');
else {
	i=top;
	while (i>=0) {
		process.stdout.write('堆疊彈出的順序為:'+stack[i]+'\n');
		count +=1;
		i =i-1;
	}
}
process.stdout.write('=====================================\n');

PHP          array_stack.php

6-2鏈結串列實作堆疊

        使用鏈結串列來製作堆疊的優點是隨時可以動態改變串列長度,能有效利用記憶體資源,不過缺點是設計時,演算法較為複雜。

相關演算法如下:

class Node {    //堆疊鏈結點的宣告
constructor() {
this.data=0; //堆疊資料的宣告
this.next=null; //堆疊中用來指向下一個節點
}
}
top=null;
var isEmpty=()=> {
if(top===null)
return true;
else
return false;
}
//將指定的資料存入堆疊
var push=(data)=> {
new_add_node=new Node();
new_add_node.data=data; //將傳入的值指定為節點的內容
new_add_node.next=top; //將新節點指向堆疊的頂端
top=new_add_node; //新節點成為堆疊的頂端
}
//從堆疊取出資料
var pop=()=> {
if (isEmpty()) {
process.studout.write('===目前為空堆疊====\n');
return -1;
}
else {
ptr=top; //指向堆疊的頂端
top=top.next; //將堆疊頂端的指標指向下一個節點
temp=ptr.data; //取出堆疊的資料
return temp; //將從堆疊取出的資料回傳給主程式
}
}
class Node {    //堆疊鏈結節點的宣告
constructor() {
this.data=0; //堆疊資料的宣告
this.next=null; //堆疊中用來指向下一個節點
}
}
top=null;
var isEmpty=()=> {
if(top==null)
return true;
else
return false;
}
//將指定的資料存入堆疊
var push=(data)=> {
new_add_node=new Node();
new_add_node.data=data; //將傳入的值指定為節點的內容
new_add_node.next=top; //將新節點指向性堆疊的頂端
top=new_add_node; //新節點成為堆疊的頂端
}
//從堆疊取出資料
var pop=()=> {
if (isEmpty()) {
process.stdout.write('===目前為空堆疊===\n');
return -1;
}
else {
ptr=top; //指向堆疊的頂端
top=top.next; //將堆疊頂端的指標指向下一個節點
temp=ptr.data; //取出堆疊資料
return temp; //將從堆疊取出的資料回傳給主程式
}
}
// 主程式
const prompt = require('prompt-sync') ();
while (true) {
const i = parseInt(prompt('要推入堆疊,請輸入1,彈出則輸入0,停止操作則輸入-1: '));
if (i==-1)
break;
else if (i==1) {
const value = parseInt(prompt('請輸入元素值:'));
push(value);
}
else if (i==0)
process.stdout.write('彈出的元素為'+pop()+'\n');
}
process.stdout.write('===========================\n');
while (!isEmpty()) //將資料陸續從頂端彈出
process.stdout.write('堆疊彈出的順序為:'+pop()+'\n');
process.stdout.write('===========================\n');

 JS           list_strack.js