JS數據結構第三篇—雙向鏈表和循環鏈表之約瑟夫問題

一、雙向鏈表

在上文《JS數據結構第二篇—鏈表》中描述的是單向鏈表。單向鏈表是指每個節點都存有指向下一個節點的地址,雙向鏈表則是在單向鏈表的基礎上,給每個節點增加一個指向上一個節點的地址。然後頭結點的上一個節點,和尾結點的下一個節點都指向null。同時LinkedList類中再增加一個last內部屬性,一直指向鏈表中最後一個節點。結構模擬如圖:

同樣對外暴露的方法和單向鏈表一樣,只是內部實現稍有變化

雙向鏈表完整設計代碼:

/**
 * 自定義雙向鏈表:對外公開的方法有
 * append(element) 在鏈表最後追加節點
 * insert(index, element) 根據索引index, 在索引位置插入節點
 * remove(element)  刪除節點
 * removeAt(index)  刪除指定索引節點
 * removeAll(element) 刪除所有匹配的節點
 * set(index, element) 根據索引,修改對應索引的節點值
 * get(index)  根據索引獲取節點信息
 * indexOf(element) 獲取某個節點的索引位置
 * clear()  清空所有節點
 * length()   返回節點長度
 * print() 打印所有節點信息
 * toString() 打印所有節點信息,同print
 * */
const LinkedListDouble = function(){
    let head = null; //鏈表中第一個LinkNode
    let last = null;  //鏈表中最後一個LinkNode
    let size = 0;   //記錄鏈表元素個數

    //Node模型
    function LinkNode(prev, element, next){
        this.prev = prev; //當前節點的上一個node
        this.element = element;  //當前節點的元素
        this.next = next; //當前節點的下一個node
    }

    //元素越界檢查, 越界拋出異常
    function outOfBounds(index){
        if (index < 0 || index >= size){
            throw("抱歉,目標位置不存在!");
        }
    }

    //根據索引,獲取目標對象
    function node(index){
        outOfBounds(index);

        //判斷index是靠近前半部分,還是後半部分,以求最少次數找到目標節點
        if (index <= size>>1){
            //說明從頭往後找,次數少一點
            let obj = head;
            for (let i = 0;i < index; i++){
                obj = obj.next;
            }
            return obj;
        }
        else{
            //說明從后往前找,次數少一點
            let obj = last;
            for (let i = size-1; i > index; i--){
                obj = obj.prev;
            }
            return obj;
        }
    }

    //新增一個元素
    function append(element){
        if (size == 0){
            head = new LinkNode(null, element, null);
            last = head;
        }
        else{
            let obj = node(size-1);
            obj.next = new LinkNode(obj, element, null);
            last = obj.next;
        }
        size++;
    }

    //插入一個元素
    function insert(index, element){
        if (index == 0){
            head = new LinkNode(null, element, head);

            if (size == 0){
                last = head;
            }
        }
        else{
            let obj = node(index-1);
            obj.next = new LinkNode(obj, element, obj.next);

            if (index == size){
                last = obj.next;
            }
        }
        size++;
    }

    //修改元素
    function set(index, element){
        let obj = node(index);
        obj.element = element;
    }

    //移除節點(內部使用,不對外暴露)
    function removeNode(node){
        let prev = node.prev, next = node.next; //當前節點的前一個,和后一個

        //判斷head臨界點
        if (prev == head){
            head = next;
        }
        else{
            prev.next = next;
        }

        //判斷last臨界點
        if (next == last){
            last = prev;
        }
        else{
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    //根據值移除節點元素
    function remove(element){
        let temp = head;
        while(temp){
            if (temp.element == element){
                return removeNode(temp);
            }
            else{
                temp = temp.next;
            }
        }
        return null;
    }

    //根據索引移除節點
    function removeAt(index){
        return removeNode(node(index));
    }

    //移除鏈表裡面的所有匹配值element的元素
    function removeAll(element){
        let newFirst = new LinkNode(null, 0, head), ele = null;
        let virHead = newFirst;

        while(virHead.next){
            if (virHead.next.element == element){

                ele = element;

                if (virHead.next.next){
                    virHead.next.next.prev = virHead.next.prev;
                }
                else{ //刪除了最後一個節點
                    last = virHead.next.prev;
                }
                virHead.next = virHead.next.next;
                size--;
            }
            else{
                virHead = virHead.next;
            }
        }

        //重新賦值
        head = newFirst.next;

        return ele;
    }

    //獲取某個元素
    function get(index){
        return node(index).element;
    }

    //獲取元素索引
    function indexOf(element){
        let obj = head, index = -1;

        for (let i = 0; i < size; i++){
            if (obj.element == element){
                index = i;
                break;
            }
            obj = obj.next;
        }
        return index;
    }

    //清除所有元素
    function clear(){
        head = null;
        last = null;
        size = 0;
    }

    //屬性轉字符串
    function getObjString(obj){

        let str = "";

        if (obj instanceof Array){
            str += "[";
            for (let i = 0; i < obj.length; i++){
                str += getObjString(obj[i]);
            }
            str = str.substring(0, str.length - 2);
            str += "], "
        }
        else if (obj instanceof Object){
            str += "{";
            for (var key in obj){
                let item = obj[key];
                str += "\"" + key + "\": " + getObjString(item);
            }
            str = str.substring(0, str.length-2);
            str += "}, "
        }
        else if (typeof obj == "string"){
            str += "\"" + obj + "\"" + ", ";
        }
        else{
            str += obj + ", ";
        }

        return str;
    }
    function toString(){
        let str = "", obj = head;
        for (let i = 0; i < size; i++){
            str += getObjString(obj.element);
            obj = obj.next;
        }
        if (str.length > 0) str = str.substring(0, str.length -2);
        return str;
    }
    //打印所有元素
    function print(){
        console.log(this.toString())
    }

    //對外公開方法
    this.append = append;
    this.insert = insert;
    this.remove = remove;
    this.removeAt = removeAt;
    this.removeAll = removeAll;
    this.set = set;
    this.get = get;
    this.indexOf = indexOf;
    this.length = function(){
        return size;
    }
    this.clear = clear;
    this.print = print;
    this.toString = toString;
}


////測試
// let obj = new LinkedListDouble();
// let obj1 = { title: "全明星比賽", stores: [{name: "張飛vs岳飛", store: "2:3"}, { name: "關羽vs秦瓊", store: "5:5"}]};
// obj.append(99);
// obj.append("hello")
// obj.append(true)
// obj.insert(3, obj1);
// obj.insert(0, [12, false, "Good", 81]);
// obj.print();
// console.log("obj1.index: ", obj.indexOf(obj1));
// obj.remove(0);
// obj.removeAll(obj1);
// obj.print();

////測試2
console.log("\n\n......test2.....")
var obj2 = new LinkedListDouble();
obj2.append(8); obj2.insert(1, 99); obj2.append('abc'); obj2.append(8); obj2.append(false);
obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);
obj2.print();
obj2.removeAll(8); //刪除所有8
obj2.print();

View Code

 

二、循環鏈表

在鏈表的基礎上,再稍稍修改一下,讓鏈表中的尾結點和頭節點鏈接起來,形成一個循環生生不息。單向循環鏈表是尾結點的下一個地址指向頭結點,而不是null;雙向循環鏈表則是last節點的next指向head節點,head節點的prev指向last節點。結構模擬如下兩個圖:

 

 對於單個節點的循環鏈表,頭結點和尾節點為同一個節點,則自己指向自己。結構模擬如圖:

 循環鏈表的代碼這裏就不貼出來了,代碼放在Github那裡,有興趣可以點進去看看。

 

三、循環鏈表的應用—約瑟夫問題模擬

據說著名猶太歷史學家 Josephus有過以下的故事:在羅馬人佔領喬塔帕特后,39 個猶太人與Josephus及他的朋友躲到一個洞中,39個猶太人決定寧願死也不要被敵人抓到,於是決定了一個自殺方式,41個人排成一個圓圈,由第1個人開始報數,每報數到第3人該人就必須自殺,然後再由下一個重新報數,直到所有人都自殺身亡為止。然而Josephus 和他的朋友並不想遵從。首先從一個人開始,越過k-2個人(因為第一個人已經被越過),並殺掉第k個人。接着,再越過k-1個人,並殺掉第k個人。這個過程沿着圓圈一直進行,直到最終只剩下一個人留下,這個人就可以繼續活着。問題是,給定了和,一開始要站在什麼地方才能避免被處決?Josephus要他的朋友先假裝遵從,他將朋友與自己安排在第16個與第31個位置,於是逃過了這場死亡遊戲。

這裏我做了一個效果圖,模擬下約瑟夫問題:

接下來我們如何用鏈表來模擬約瑟夫問題。

在上面循環鏈表的基礎上,我們給LinkedList再添加一個內部屬性current,指向當前節點,默認指向頭結點;再增加三個對外方法next()、removeCurrent()、reset(),分別表示當前節點指向下一個節點,移除當前節點,重置當前節點為頭結點。修改后,新的LinkedList對外方法有:

 新的循環雙向鏈表完整設計代碼:

/**
 * 在循環雙向鏈表的基礎上,增加1個屬性,3個方法(屬性內部使用,方法對外開放),讓循環鏈表發揮更大的效果:
 * current: 指向當前節點,默認指向首節點head
 * next():讓current每次移動一次,移上下一個節點, 返回元素
 * removeCurrent(): 每次刪除當前current指向的節點,刪除后,current指向下一個節點
 * reset(): 重置current指向首節點head
 *
 * 自定義雙向循環鏈表:對外公開的方法有
 * append(element) 在鏈表最後追加節點
 * insert(index, element) 根據索引index, 在索引位置插入節點
 * remove(element)  刪除節點
 * removeAt(index)  刪除指定索引節點
 * removeAll(element) 刪除所有匹配的節點
 * set(index, element) 根據索引,修改對應索引的節點值
 * get(index)  根據索引獲取節點信息
 * indexOf(element) 獲取某個節點的索引位置
 * clear()  清空所有節點
 * length()   返回節點長度
 * print() 打印所有節點信息
 * toString() 打印所有節點信息,同print
 * */
const CircleLinkedListDouble = function(){
    let head = null; //鏈表中第一個LinkNode
    let last = null;  //鏈表中最後一個LinkNode
    let size = 0;   //記錄鏈表元素個數
    let current = null; //當前指向的節點

    //Node模型
    function LinkNode(prev, element, next){
        this.prev = prev; //當前節點的上一個node
        this.element = element;  //當前節點的元素
        this.next = next; //當前節點的下一個node
    }

    //元素越界檢查, 越界拋出異常
    function outOfBounds(index){
        if (index < 0 || index >= size){
            throw("抱歉,目標位置不存在!");
        }
    }

    //根據索引,獲取目標對象
    function node(index){
        outOfBounds(index);

        //判斷index是靠近前半部分,還是後半部分,以求最少次數找到目標節點
        if (index <= size>>1){
            //說明從頭往後找,次數少一點
            let obj = head;
            for (let i = 0;i < index; i++){
                obj = obj.next;
            }
            return obj;
        }
        else{
            //說明從后往前找,次數少一點
            let obj = last;
            for (let i = size-1; i > index; i--){
                obj = obj.prev;
            }
            return obj;
        }
    }

    //新增一個元素
    function append(element){
        if (size == 0){
            head = new LinkNode(null, element, null);
            head.next = head;
            head.prev = head;
            last = head;
            current = head;
        }
        else{
            let obj = node(size-1);
            obj.next = new LinkNode(obj, element, head);
            last = obj.next;
            head.prev = last;
        }
        size++;
    }

    //插入一個元素
    function insert(index, element){
        //表示插入到第一個
        if (index == 0){

            let last = null;
            if (size > 0) last = node(size-1);

            head = new LinkNode(last, element, head);

            if (size < 1){
                head.next = head;
                head.prev = head;
                last = head;
                current = head;
            }
            else{
                last.prev = head;
            }
        }
        else{
            let prev = node(index-1);
            prev.next = new LinkNode(prev, element, prev.next);

            //表示插入到最後一個
            if (index == size){
                last = prev.next;
                head.prev = last;
            }
        }
        size++;
    }

    //修改元素
    function set(index, element){
        let obj = node(index);
        obj.element = element;
    }

    //移除節點(內部使用,不對外暴露)
    function removeNode(node){

        if (size == 1){
            current = head = last = null;
        }
        else{
            let prev = node.prev, next = node.next; //當前節點的前一個,和后一個

            //判斷head臨界點
            if (prev == last){
                head = next;
                head.prev = last;
                last.next = head;
            }
            else{
                prev.next = next;
            }

            //判斷last臨界點
            if (next == head){
                last = prev;
                last.next = head;
                head.prev = last;
            }
            else{
                next.prev = prev;
            }

            if (current == node){
                current = next;
            }
        }

        size--;
        return node.element;
    }

    //根據值移除節點元素
    function remove(element){
        let temp = head;
        while(temp){
            if (temp.element == element){
                return removeNode(temp);
            }
            else{
                temp = temp.next;
            }
        }
        return null;
    }

    //根據索引移除節點
    function removeAt(index){
        return removeNode(node(index));
    }

    //移除鏈表裡面的所有匹配值element的元素
    function removeAll(element){
        let newFirst = new LinkNode(null, 0, head), delNode = null;
        let virHead = newFirst;

        //為了避免無限循環,先把循環鏈表斷開
        head.prev = null, last.next = null;

        while(virHead.next){
            if (virHead.next.element == element){

                delNode = virHead.next;

                if (virHead.next.next){
                    virHead.next.next.prev = virHead.next.prev;
                }
                else{
                    last = virHead.next.prev;
                }

                if (virHead.next == current){
                    current = current.next;
                    virHead.next = current;
                }
                else{
                    virHead.next = virHead.next.next;
                }

                size--;
            }
            else{
                virHead = virHead.next;
            }
        }

        //重新賦值
        head = newFirst.next;
        last = size > 0 ? node(size-1) : null;
        if (size > 0){
            last.next = head;
            head.prev = last;
        }
        else{
            current = head = last = null;
        }

        return delNode.element;
    }

    //獲取某個元素
    function get(index){
        return node(index).element;
    }

    //獲取元素索引
    function indexOf(element){
        let obj = head, index = -1;

        for (let i = 0; i < size; i++){
            if (obj.element == element){
                index = i;
                break;
            }
            obj = obj.next;
        }
        return index;
    }

    //清除所有元素
    function clear(){
        current = head = last = null;
        size = 0;
    }

    //這次新增加的三個方法next, removeCurrent, reset
    //調用重置current指向head節點
    function reset(){
        current = head;
    }
    function next(){
        if (!current) return null;

        current = current.next;
        return current.element;
    }

    //每調用一次,刪除current指向的節點
    function removeCurrent(){
        if (size < 1) return null;
        return removeNode(current);
    }

    //屬性轉字符串
    function getObjString(obj){

        let str = "";

        if (obj instanceof Array){
            str += "[";
            for (let i = 0; i < obj.length; i++){
                str += getObjString(obj[i]);
            }
            str = str.substring(0, str.length - 2);
            str += "], "
        }
        else if (obj instanceof Object){
            str += "{";
            for (var key in obj){
                let item = obj[key];
                str += "\"" + key + "\": " + getObjString(item);
            }
            str = str.substring(0, str.length-2);
            str += "}, "
        }
        else if (typeof obj == "string"){
            str += "\"" + obj + "\"" + ", ";
        }
        else{
            str += obj + ", ";
        }

        return str;
    }
    function toString(){
        let str = "", obj = head;
        for (let i = 0; i < size; i++){
            str += getObjString(obj.element);
            obj = obj.next;
        }
        if (str.length > 0) str = str.substring(0, str.length -2);
        return str;
    }
    //打印所有元素
    function print(){
        console.log(this.toString())
    }

    //對外公開方法
    this.append = append;
    this.insert = insert;
    this.remove = remove;
    this.removeAt = removeAt;
    this.removeAll = removeAll;
    this.set = set;
    this.get = get;
    this.indexOf = indexOf;
    this.length = function(){
        return size;
    }
    this.clear = clear;
    this.print = print;
    this.toString = toString;

    //新增加的方法
    this.next = next;
    this.removeCurrent = removeCurrent;
    this.reset = reset;
}


////測試
// let obj = new CircleLinkedListDouble();
// let obj1 = { title: "全明星比賽", stores: [{name: "張飛vs岳飛", store: "2:3"}, { name: "關羽vs秦瓊", store: "5:5"}]};
//
// obj.append(99);
// obj.append("hello")
// obj.append(true)
// obj.insert(3, obj1);
// obj.insert(0, [12, false, "Good", 81]);
// obj.print();
// console.log("obj1.index: ", obj.indexOf(obj1));
// obj.remove(0);
// obj.removeAll(obj1);
// obj.print();

////測試2
// console.log("\n\n......test2.....")
// var obj2 = new CircleLinkedListDouble();
// obj2.append(8); obj2.append(99); obj2.append('abc'); obj2.append(8); obj2.append(false);
// obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8);
// obj2.print();
// obj2.removeAll(8); //刪除所有8
// obj2.print();


/**
 * 測試3,來做一個有意思的題目:約瑟夫題目
 據說著名猶太歷史學家 Josephus有過以下的故事:在羅馬人佔領喬塔帕特后,39 個猶太人與Josephus及他的朋友躲到一個洞中,
 39個猶太人決定寧願死也不要被敵人抓到,於是決定了一個自殺方式,41個人排成一個圓圈,
 由第1個人開始報數,每報數到第3人該人就必須自殺,然後再由下一個重新報數,直到所有人都自殺身亡為止。
 然而Josephus 和他的朋友並不想遵從。
 首先從一個人開始,越過k-2個人(因為第一個人已經被越過),並殺掉第k個人。
 接着,再越過k-1個人,並殺掉第k個人。這個過程沿着圓圈一直進行,直到最終只剩下一個人留下,這個人就可以繼續活着。
 問題是,給定了和,一開始要站在什麼地方才能避免被處決?
 Josephus要他的朋友先假裝遵從,他將朋友與自己安排在第16個與第31個位置,於是逃過了這場死亡遊戲。

 用循環鏈表來模擬這個遊戲
 */
console.log("\n\n........test3約瑟夫題目。。。....");
var obj3 = new CircleLinkedListDouble();
for (let i = 0; i < 41; i++){
    obj3.append(i+1);
}
obj3.print();
console.log("*************約瑟夫遊戲開始**********")
for (let i = 0; i < 39; i++){
    obj3.next(); obj3.next(); //移動兩次
    obj3.removeCurrent(); //刪除當前節點
    console.log("第", (i+1), "次,剩餘的為:", obj3.toString())
}
console.log("***************game over***************")
console.log("最後生存下來的是:", obj3.toString());

View Code

看下用鏈表模擬約瑟夫問題過程的效果:

 

其餘單向循環鏈表、單向循環鏈表增強、雙向循環鏈表等代碼Demo見github地址:https://github.com/xiaotanit/Tan_DataStruct

【精選推薦文章】

智慧手機時代的來臨,RWD網頁設計已成為網頁設計推薦首選

想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

帶您來看台北網站建置台北網頁設計,各種案例分享

廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益