圖說演算法使用JavaScript(十)

5-3-3單向鏈結串列刪除節點

在單向鏈結型態的資料結構中,如果要在串列中刪除一個節點,如同一列火車拿掉原有的車廂,依據所刪除節點的位置有三種不同的情形:

演算法如下

top=head;
head=head.next;

演算法如下

ptr.next=tail;
ptr.next=null;

演算法如下

Y=ptr.next;
ptr.next=Y.next;

class employee{
        constructor() {
               this.num=0;
               this.salary=0;
               this.name=”;
               this.next=null;
        }
}

JS          del_node.js

class employee{
	constructor(){
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

var del_ptr=(head,ptr)=>{   //刪除節點副程式
	top=head;
	if (ptr.num==head.num) {  //[情形1]:刪除點在串列首
		head=head.next;
		process.stdout.write('已刪除第' +ptr.num+' 號員工 姓名:'+ptr.
			name+' 薪資:'+ptr.salary);
	}
	else {
		while (top.next!=ptr)  //找到刪除點的前一個位置
			top=top.next;
		if(ptr.next==null) {   //刪除在串列尾的節點
			top.next=null;
			process.stdout.write('已刪除第'+ptr.num+' 號員工 姓名:'+ptr.
				name+' 薪資:'+ptr.salary+'\n');
		}
		else{
			top.next=ptr.next;
			process.stdout.write('已刪除第 '+ptr.num+' 號員工 姓名:'+ptr.
				name+' 薪資:' +ptr.salary+'\n');
		}		
	}
	return head;
}

findword=0;
namedata=['Allen','Scott','Mary','John','Mark','Ricky',
		  'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
		[1012,42660],[1014,25676],[1018,44145],[1043,52182],
		[1031,32769],[1037,21100],[1041,32196],[1046,25776]];
process.stdout.write('員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n');
process.stdout.write('--------------------------------------------------\n');

for(i=0; i<3; i++) {
	for (j=0; j<4; j++)
		process.stdout.write(data[j*3+i][0]+ '\t'+data[j*3+i][1]+'\t');
	console.log();
}

head=new employee(); //建立串列首
if(!head) {
	console.log('Error!! 記憶體配置失敗!!');
	return;
}
head.num=data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;

ptr=head;
for (i=1; i<12; i++) { //建立串列
	newnode=new employee();
	newnode.next=null;
	newnode.num=data[i][0];
	newnode.name=namedata[i];
	newnode.salary=data[i][1];
	newnode.next=null;
	ptr.next=newnode;
	ptr=ptr.next;
}
const prompt = require('prompt-sync')();
while(true)  {
	const findword = parseInt(prompt('請輸入要刪除的員工編號,要結束刪除過程,請輸入-1:'));
	if (findword==-1)  //迴圈中斷條件
		break;
	else {
		ptr=head;
		find=0;
		while (ptr!=null) {
			if (ptr.num==findword){
				ptr=del_ptr(head,ptr);
				find=find+1;
				head=ptr;
			}
			ptr=ptr.next;
		}
		if (find==0)
			process.stdout.write('//////////沒有找到///////////\n');
	}
}
ptr=head;
process.stdout.write('\t座號\t  姓名\t成績\n');  //列印剩餘串列資料
process.stdout.write('\t======================\n');  
while (ptr!=null)  {
	process.stdout.write('\t['+ptr.num+' ]\t[ '+ptr.name+' ]\t[ '
		+ptr.salary+']\n');
	ptr=ptr.next;
}

5-3-4單向鏈結串列的反轉

看完了節點的刪除及插入後,各位可以發現在這種具有方向性的鏈結串列結構中增刪節點是相當容易的一件事。而要從頭到尾印整個串列似乎也不難,不過如果要反轉過來列印就真的需要某些技巧了。我們知道在鏈結串列中的節點特性是知道下一個節點的位置,可是卻無從得知它的上一個節點位置,不過如果要將串列反轉,則必須使用三個指標變數。請看下圖說明:

演算法如下:

class employee{
constructor() {
this.num=0;
this.salary=0;
this.name='';
this.next=null;
}
}
var invert=(x)=> { //x為串列的開始指標
p=x; //將p指向串列的開頭
q=null; //q是p的前一個節點
while (p!=null) {
r=q; //將r接到q之後
q=p; //將q接到p之後
p=p.next //p移到下一個節點
q.next=r; //q連結到之前的節點
}
return q;
}

JS          rev_node.js

class employee {
	constructor() {
		this.num=0;
		this.salary=0;
		this.name='';
		this.next=null;
	}
}

findword=0;
namedata=['Allen','Scott','Marry','John','Mark','Ricky',
			'Lisa','Jasica','Hanson','Daniel','Axel','Jack'];
data=[[1001,32367],[1002,24388],[1003,27556],[1007,31299],
		[1012,42660],[1014,25676],[1018,44145],[1043,52182],
		[1031,32769],[1037,21100],[1041,32196],[1046,25776]];

head = new employee();//建立串列首
if(!head) {
	console.log('Error!! 記憶體配置失敗!!');
	return;
}
head.num =data[0][0];
head.name=namedata[0];
head.salary=data[0][1];
head.next=null;

ptr=head;

for(i=1; i<12; i++){  //建立串列
	newnode=new employee();
	newnode.next=null;
	newnode.num=data[i][0];
	newnode.name=namedata[i];
	newnode.salary=data[i][1];
	newnode.next=null;
	ptr.next=newnode;
	ptr=ptr.next;
}

ptr=head;
i=0;
process.stdout.write('原始員工串列節點資料:\n');
while (ptr !=null) { //列印串列資料
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] -> ');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

ptr=head;
before=null;
process.stdout.write('\n反轉後串列節點資料:\n');
while (ptr!=null) { //串列反轉,利用三指標
	last=before;
	before=ptr;
	ptr=ptr.next;
	before.next=last;
}
ptr=before;
while (ptr!=null) {
	process.stdout.write('['+ptr.num+'\t'+ptr.name+'\t'
							+ptr.salary+'] ->');
	i=i+1;
	if (i>=3) { //三個元素為一列
		console.log();
		i=0;
	}
	ptr=ptr.next;
}

PHP  陣列 函數

array_pop() 刪除陣列最後一個元素。
array_push() 將一個或多個元素加入末端。
array_reverse() 以相反的順序返回陣列。
array_shift() 刪除首個元素。
array_slice() 刪除指定位置的元素,返回陣列。

JavaScript 概念三明治(六)

Event Table

Event Table 是與Event Queue 互相搭配的資料集合,它負責記錄在非同步目的達成後,有哪些函式或者事件要被執行,這裡指的非同步目的指的是像計時完畢、API資料獲取完畢、事件被觸發。當我們執行setTimeout這個函式時,JavaScript會把給定的函式與像是倒數的秒數之類的附帶資訊(meta data)推送到Event Table裡面,等到一秒過後(目的達成)該函式教會被正式推送到事件除列等待執行,而在這之前JavaScript就是透過Event Table知道有那些事件要被送到事件儲列中。

Event Loop

那麼,什麼又是事件迴圈Event Loop呢?可以把Event Loop想成是另外一個幾乎無時無刻、每一毫秒都在執行的程式,它負責檢查現在主執行環境堆疊是否是空的。如果是空的,再去檢查Event Queue,若Event Queue有函式等待執行,則將這些函式從Event Queue依序到主執行環境並執行。
也因為有事件迴圈與事件儲列的機制,像是事件監聽與透過Ajax拉取資料這類行為才有辦法被達成。例如在監聽網頁點時,一旦使用者做了點擊的動作,對應的邏輯就會被推送到事件儲列內,而事件迴圈看到儲列內有待執行的任務,就會負責去執行。
那麼,現在了解了整個事件儲列的概念,讓我們再度回到setTimeout的例子,來看看一道經典的面試問題。
for (var i=0; i<3; i++){
setTimeout(function(){
console.log(i)
}, 1000)
}
各位可以先想一下,在一秒之後,setTiomeout函式內console.log的輸出的結果是甚麼。這邊用到的概念跟前面講閉包的時候類似,都與先後順序有關。若沒有非同步概念的話,通常會下意識的認為結果會是0、1、2,不過這段程式碼最後其實是會印出3、3、3,不知道有沒有猜對。
搭配識見儲列的概念,現在我們知道setTimeout對應的函式會在主執行環境結束之後才被執行,而等到該函式被執行時,for迴圈裡面的i早就已經因為迴圈而被修改為3了。
要改變三個3的結果,想要看到0、1、2的話該怎麼辦呢?這邊要結合一點前面說到的範疇與閉包的觀念,可以看到for迴圈裡面的i是利用var所宣告,而既然var具有的範疇是根據函式來界定,那麼我只要利用函式,是不是就是夠透過產生閉包,把每個迴圈的i值保留下來呢?當然可以,我們可以利用立即執行函式(IIFE),並把i導入這個立即執行函式,就能夠產生閉包了。

for (var i=0; i<3; i++)
(function(x) {
setTimeout(function(){
console.log(x)
})(i)
}

或者是把var宣告改成let來做宣告
for (let i=0; i<3; i++){
setTimeout(function(){
console.log(i)
}, 1000)
}

Promise

我們在前一個段落提到,為了防止網頁的主程式因為等待某些邏輯運算的回應而停擺,有時候JavaScript的行為需要透過非同步的方式來執行,包括一些瀏覽器的API和對外部伺服器拉取資料的動作,而這些動作是利用瀏覽器的Event Queue來達成非同步的行為。
這的確減少不必要的等待,進而增加了使用流程上的順暢度。不過就程式碼的撰寫方式來看,由於在做這些非同步行為的時候,若不做任何的處理,一般都是以回呼函式的方式來進行,才能確保某一段邏輯在非同步行為完成之後才被執行,若這類邏輯開始複雜的時候,可能會變得難以閱讀。
舉前例講到的例子來說,若以setTimeout來模擬一個非同步的行為,想要確保這件事情的話,我們就必須把一個非同步行為放到另外一個非同步的行為的回呼函式裡面。當這樣子的需求越來越多時,你可能就會看到這樣的程式碼。
const asynActionA = (fn)=>setTimeout(fn, 10000);
const asynActionB = (fn)=>setTimeout(fn, 10000);
const asynActionC = (fn)=>setTimeout(fn, 10000);
const asynActionD = (fn)=>setTimeout(fn, 10000);

asyncActionA(()=>{
console.log("asynActionA");
asynActionB(()=>{
console.log("asynActionB");
asynActionC(()=>{
console.log("asynActionC");
asynActionD(()=>{
console.log("asynActionD");
});
});
});
});
這種巢狀的回呼函式一旦多了起來,就容易造成維護上的困難。一般在正式的專案中都非常不樂見這樣子的程式碼。為了解決這樣的問題,我們就必須認識這個Promise
>Promise簡介
Promise是什麼呢?Promise是JavaScript版本E86以後出現的新語法,這個詞以字面上的意義來看,用比較白話的方式解釋的話有一種:我承諾幫你做某件事情,能不能成功還不一定,但是我做完之後會把結果告訴你的意思。官方的文件描述則是:
Promise是一個代表非同步運作的最終狀態的物件(成功或失敗)
A Promise is an object repressnting the eventual completion
or failure of an asynchronous operation.(MDN)

從技術文件的角度來解釋就顯得比較抽象,不過你應該大致能夠看出一點頭緒,只要抓住幾個關鍵字--也就是「成功」與「失敗」兩種狀態。
>Promise的狀態
進一步總結以上的論點,一個Promise以時間順序來看是有狀態之分的。除了前面講的成功與失敗兩種結果,一般以Pending來描述在執行中,懸而未決的Promise,一個Promise總共會有三種可能的狀態,分別代表進行中、成功與失敗。而相對於Pending這個代表處理中的狀態,不管是進入成功或失敗狀態的Promise,我們都能夠用Settled來表示這個Promise已經被解決了。

*Pending:還在執行中的狀態,表示還沒有特定結果。
*Fulfilled:成功的狀態,代表Promise被實現,對應的回呼函式為resolve。
*Rejected:失敗的狀態,代表Promise被拒絕,對應的回呼函式為reject。
*Settled:表示Promise已經被解決,結果已經確定。

>Promise基本使用方式
從前面文件的描述應該也可以看得出來Promise在JavaScript裡面是以物件的方式存在。這個物件又是怎麼產生呢?接下來我們就來看看要怎麼使用Promise吧!基本的Promise宣告方式如下:
我們進一步仔細看一下這個傳進Promise建構函式,它接收了兩個參數:resolvereject來命名。

resolvereject 其實分別是兩個具有不同目的的函式。resolve(解析)被用於在認為Promise內的行為成功時呼叫reject(拒絕)則用於被認為失敗的邏輯發生時呼叫。使用這兩個詞最為函式的名稱只因為這是一種約定俗成,許多人都用這些詞來稱呼它們。

JavaScript 概念三明治(五)

同步/非同步

「同步」聽起來就是指一次做好幾件事情,其實並不是,同步指的是:
同一時間只做一件事
套用到JavaScript裡面就是指一次只跑一段程式碼,就像JavaScript語法解析器做的,從上到下一行一行執行那樣。當JavaScript載入全域執行環境,也許呼叫了某個函式創造出一個函式執行環境,然後回到全域環境後結束,這一切都是同步來做處裡的,也就是說,在JavaScript裡面不可能同時執行兩個函式、執行多段程式碼邏輯。
而「非同步」呢?就很好理解了,相較於同步,它的概念則相反:
同一時間內處理不只一件事
必須透過非同步的處理方式,才能讓JavaScript在進入全域執行環境到結束的這中間,能夠額外處理一些需要時間進行的邏輯,而又不影響原來的主程式。在非同步的處理方式下,主程式的運行還是會繼續,而非同步進行的工作也還是會進行,只是不是馬上,而是等到主程式執行完畢,JavaScript引擎有空檔後才會被執行。
非同步的行為在瀏覽器前端很常見,像是部落格網站,當網站一打開,JavaScript必須處理畫面上的一些行為,卻又必須跟後端取文章資料。若以同步的方式來進行這個拉取文章的動作,那麼在拉取道完整文章之前,JavaScript就會無法執行任何其他任務。
也就是說,即便JavaScript是一門同步的語言,但為了符合瀏覽器的使用情境,某些時候它必須具有非同步執行邏輯的能力,至於它怎麼處理這些互動的非同步動作呢?就是透過瀏覽器內的事件迴圈的幫助,關於事件迴圈在後面馬上就會看到。
瀏覽器內可不是只有JavaScript引擎而已,還有其他許多部份在JavaScript引擎之外執行的其他程式,像是渲染引擎負責畫面的構築、以及負責處理網路溝通如Http請求以獲得資料的部分。而JavaScript可能在某些時候必須要要求瀏覽器變更畫面的內容,或是觸發網路溝通的流程,以與其他伺服器溝通,但是這些工作可能會是非同步的,只有在JavaScript引擎裡面事同步的運行。

Event Queue 與 Event Loop

Event Queue、Event Loop這兩個部分並不存在於JavaScript內,而是瀏覽器的其中一部份。它們雖然不屬於JavaScript,卻是前端產品開發裡面最重要的概念之一。因此,需要了解它們為前端互動方面帶來什麼樣的幫助和影響。
>JavaScript引擎的組成

讓我們回想一下前面提到的基礎。之前提到過「執行環境堆疊」,函式呼叫時會產生執行環境,若在這個函式執行環境內含有其他函式被呼叫,就會在之上產生另一個執行環境,形成堆疊。而在上層的執行環境結束之前,下層部分的其他程式碼事無法被執行的,包含全域執行環境。                                                                                                

因此,只要在這之中某個堆疊過久,就算只有一個函式執行環境的堆疊,都有可能影響整個主程式(全域執行環境)的運行。不過應用程式裡面總是會有某些功能需要時間來提取/運算,這時候為了不讓整個主程式停下來等待太久,我們可以,而且其實我們很常把這些比較耗時的工作放在主程式以外的某一個部分去執行。
要討論下一段之前,必須先複習一下,前面我們提到的,JavaScript引擎底下根據功能大致上可以分為三個部分:

#全域執行環境
#執行環境堆疊
#記憶體堆疊

然而瀏覽器內可不只有JavaScript引擎,接下來我們要提到一個很重要的概念--Queue(又稱Message/Event/Callback Queue)。
整個瀏覽器的運行並非只有JavaScript引擎組成。前面說到過,因為JavaSript屬於同步執行的語言,同時又為了讓網頁具有像「監聽事件」、「計時」、「拉第三方API」這些類似「背景作業」的功能,瀏覽器提供了另外一些部份來達成,分別是:
#

#Event Queue
#Web API
#Event Table
#Event Loop

整個由上述部分,包含JavaScript引擎所組成的整體,稱為JavaScript Runtime Environment(JRE),瀏覽器內並不只有JavaScript語言本身而已,我們先來看一下瀏覽器內的事件處理。
>Event Queue
Queue(儲列)是什麼樣的概念呢?我們先來看一下,在寫網頁程式的時候,有一些所謂的「內建的」API如setTimeout、setInterval,這些API不存在於JavaScript原始碼內,但你仍然可以在開發時直接使用。因為這些API是屬於瀏覽器所提供的WebAPI。WebAPI並非JavaScript引擎的一部份,但它屬於瀏覽器運行流程的一環。
關於Web API,舉一些例子:
*操作DOM節點的API:document.getElementeById
*AJAX相關API,像是:XMLttpRequest
*計時類型的API,就像剛剛提到的setTimeout
這類Web API在與JavaScript原始碼一起執行的時候,通常不會直接影響JavaScript主執行環境的運行。否則的話若網頁需要與後端伺服器溝通,拉取外部資料時,就只有乾等,無法執行任何其他事情了!
>Event Queue 運行流程
要了解Event Queue的運行,我們必須先找到一件會放到Event Queue執行的事情。所以這邊要先介紹其中幾個瀏覽器的API:setTimeout與setInterval。setTimeout是一個全域的函式,用於將想做的事情延後幾秒進行。將想要執行的邏輯以函式的方式傳入第一個參數,並在第二個參數傳入想要等待的時間,JavaScript就會為你在若干秒之後,呼叫你傳入的函式。
而setInterval呢?與setTimeout相似,只不過setTimeout只會在你給定的秒數之後執行一次,而setInterval則是根據你給定的時間,固定幾秒執行一次。
function executeAfterDelay(){
console.log("一秒之後才會執行");
}
setTimeout(executerAfterDelay, 1000);
console.log("我會先被被執行");
如果了解了這兩個方法的用途,來觀察上圖的程式碼應該不會太難理解,函式內的程式碼會在一秒之後才被呼叫。不過意外的事情總是會發生,這段程式碼裡面,setTimeout可不像一般的函式那樣運行起來那麼單純。
我們可以試試看把setTimeout的時間調整為0,那是不是就會馬上執行對應的函式內容了呢?
function executeAfterDalay() {
console.log("應該要馬上執行");
}
setTimeout(excuteAfterDalay,0);
console.log("應該要最後執行");

整個流程看起來像這樣:
1.JavaScript 引擎執行到瀏覽器提供的setTimeout函式。
2.JavaScript 引擎繼續運行,同時瀏覽器開始根據給定的秒數計時。
3.等待計時完成後,把剛才接收到的函式推送到Event Queue內。
4.等待JavaScript引擎運行完畢,主執行環境結束後,將Event Queue內的函式推送到JavaScript主執行環境,產生堆疊(執行該函式)。