DIV CSS 佈局教程網

JavaScript 引用與指標:從一道鏈表填空題看清賦值本質
編輯:關於JavaScript     

很多時候,我們以為自己懂 JavaScript 的「引用」,直到寫到鏈表這類指標操作密集的結構,才發現理解有偏差。本文用一道鏈表完形填空,把變量、引用與對象三者之間的關係徹底攤開來看。

先看題目

下面是一段用 JavaScript 實作的整数鏈表,其中 dcatenate(串接)與 sublist(截取)兩個函式留空,請自行補完,且不允許使用 new 關鍵字以外的取巧手法。

/* 建立一個鏈表節點,head 為頭,tail 為尾 */
function IntList(head0, tail0){
    this.head = head0 || 0;
    this.tail = tail0 || null;
}

/* 由陣列產生鏈表 */
IntList.list = function(__args){
    var sentinel = new IntList(),
        len = __args.length,
        p = sentinel;
    for (var i = 0; i < len; i++){
        p.tail = new IntList(__args[i]);
        p = p.tail;
    }
    return sentinel.tail;
};

/* 轉成字串 */
IntList.prototype.toString = function(){
    var temp = "[";
    for (var L = this; L !== null; L = L.tail){
        temp = temp + " " + L.head;
    }
    return temp + " ]";
};

/* 把 B 接在 A 之後 */
function dcatenate(A, B){ /* 待補完 */ }

/* 取出長度 len、起始位置為 start 的子鏈表,且不修改 L */
function sublist(L, start, len){ /* 待補完 */ }

配套測試碼如下:

function test(){
    var A = IntList.list([4,6,7,3,8]),
        B = IntList.list([3,2,5,9]);
    dcatenate(A, B);
    if (A.toString() === "[ 4 6 7 3 8 3 2 5 9 ]") alert("dcatenate 正確");

    var L = IntList.list([3,4,5,2,6,8,1,9]),
        result = sublist(L, 3, 3);
    if (result.toString() === "[ 2 6 8 ]") alert("sublist 正確");
}

所謂「引用」到底存了什麼

當我們把一個引用類型(物件)的實例指派給變數時,變數裡保存的並不是實例本身,而是指向該實例的引用:

var temp = new Object();

這個行為非常符合「引用類型」這個名字——實例是拿來被引用的。而當我們把這個變數再指派給另一個變數時,複製的其實只是「引用」這份地址資料:

var temp2 = temp;

也就是說,寫成 temp2 = temp 之後,兩者並沒有變成同一個綁定關係。若把 temp 重新指向另一個物件:

var temp = { name: "temp" };
var temp2 = temp;
temp = { name: "not temp2" };
temp === temp2;   // false

但如果只是改動「引用所指向的那個實例」內部,兩者依然相等:

var temp = { name: "temp" };
var temp2 = temp;
temp.name = "also temp2";
temp === temp2;   // true

一句話總結:變數之間傳遞的是地址的副本,改地址互不相干,改地址上的內容則彼此可見。

IntList 是什麼東西

  1. 先建立兩個空變數,此時 L 與 Q 都沒有指向任何節點。
  2. 建立一個 head 為 3、tail 為空的 IntList,並把 L 的引用值指派給 Q,於是 L 與 Q 指向同一個節點。
  3. 再讓 Q 指向一個 head 為 42 的新節點,並把 Q 的引用寫進 L.tail,兩個節點就串了起來。

由此可見,IntList 是一個靠引用(指標)層層嵌套的資料結構,也就是我們熟悉的鏈表(Linked List)。

解題一:鏈表串接

思路很單純——把 A 的最後一個節點的 tail 指向 B 即可:

function dcatenate(A, B){
    var p;
    for (p = A; p != null; p = p.tail){
        if (p.tail === null){
            p.tail = B;
            break;
        }
    }
    return A;
}

解題二:鏈表截取

題目要求不得改動原鏈表,因此只能遍歷取值、重新建立一條新鏈表:

function sublist(L, start, len){
    var K, P, J;
    var i = 0, end = start + len;
    for (P = L; i <= end; P = P.tail, i++){
        if (i < start) continue;
        else if (i === start){ K = new IntList(P.head); J = K; }
        else if (i > start && i < end){ J.tail = new IntList(P.head); J = J.tail; }
        else break;
    }
    return K;
}

留給讀者的思考題

函式在傳參時,究竟是按值傳遞還是按引用傳遞?觀察下面這段碼,變數 obj 進入函式之後經歷了怎樣的引用過程?

var obj = { name: "anything" };
function getName(__obj){
    return __obj.name;
}
var name = getName(obj);

答案是:物件本身從未被複製,被複製的只有那份指向物件的引用。理解這一點,鏈表、樹、圖這類指標結構才會真正變得順手。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved