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網頁設計已成為網頁設計推薦首選
想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計
廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益