您現在的位置是:電腦技術吧?>? 編程技術 ??>??數據結構 鏈表,單鏈表數據結構??>??正文詳情

數據結構 鏈表,單鏈表數據結構

岳芮欣2019-12-05 14:11:58 人圍觀
簡介鏈表本文主要介紹JavaScript中的數據結構和算法(3):鏈表。本文分別介紹了單鏈表和雙鏈表的代碼示例,以及添加節和刪除節的代碼示例。我們可以看到JavaScr什么是鏈表

這篇文章主要介紹了JavaScript中數據結構與算法(三):鏈表,本文分別講解了單鏈表與雙鏈表以及增加節和刪除節的代碼實例,需要的朋友可以參考下  我們可以看到在javascript概念中的隊列與棧都是一種特殊的線性表的結構,也是一種比較簡單的基于數組的順序存儲結構。

由于javascript的解釋器針對數組都做了直接的優化,不會存在在很多編程語言中數組固定長度的問題(當數組填滿后再添加就比較困難了,包括添加刪除,都是需要把數組中所有的元素全部都變換位置的,javascript的的數組確實直接給優化好了,如push,pop,shift,unshift,split方法等等)  線性表的順序存儲結構,最大的缺點就是改變其中一個元素的排列時都會引起整個合集的變化,其原因就是在內存中的存儲本來就是連貫沒有間隙的,刪除一個自然就要補上。

針對這種結構的優化之后就出現了鏈式存儲結構,換個思路,我們完全不關心數據的排列,我們只需要在每一個元素的內部把下一個的數據的位置給記錄就可以了,所以用鏈接方式存儲的線性表簡稱為鏈表,在鏈式結構中,數據=(信息 地址)  鏈式結構中,我們把地址也可以稱為鏈,一個數據單元就是一個節點,那么可以說鏈表就是一組節點組成的合集。

每一個節點都有一個數據塊引用指向它的下一個節點

  數組元素是靠位置關系做邏輯引用,鏈表則是靠每一個數據元保存引用指針關系進行引用  這種結構上的優勢就非常明顯的,插入一個數據完全不需要關心其排列情況,只要把鏈的指向銜接上  這樣做鏈表的思路就不會局限在數組上了,我們可以用對象了,只要對象之間存在引用關系即可  鏈表一般有,單鏈表、靜態鏈表、循環鏈表、雙向鏈表  單鏈表:就是很單一的向下傳遞,每一個節點只記錄下一個節點的信息,就跟無間道中的梁朝偉一樣做臥底都是通過中間人上線與下線聯系,一旦中間人斷了,那么就無法證明自己的身份了,所以片尾有一句話:我是好人,誰知道呢?  靜態鏈表:就是用數組描述的鏈表。

也就是數組中每一個下表都是一個節包含了數據與指向  循環鏈表:由于單鏈表的只會往后方傳遞,所以到達尾部的時候,要回溯到首部會非常麻煩,所以把尾部節的鏈與頭連接起來形成循環  雙向鏈表:針對單鏈表的優化,讓每一個節都能知道前后是誰,所以除了后指針域還會存在一個前指針域,這樣提高了查找的效率,不過帶來了一些在設計上的復雜度,總體來說就是空間換時間了  綜合下,其實鏈表就是線性表中針對順序存儲結構的一種優化手段,但是在javascript語言中由于數組的特殊性(自動更新引用位置),所以我們可以采用對象的方式做鏈表存儲的結構  單鏈表  我們實現一個最簡單的鏈表關系  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 function createLinkList() { var _this = {}, prev = null; return { add: function(val) { //保存當前的引用 prev = { data: val, next: prev || null } } } } var linksList = createLinkList(); linksList.add(arron1); linksList.add(arron2); linksList.add(arron3); //node節的next鏈就是 -arron3-arron2-arron1   通過node對象的next去直引用下一個node對象,初步是實現了通過鏈表的引用,這種鏈式思路jQuery的異步deferred中的then方法,還有日本的cho45的jsderferre中都有用到。

這個實現上還有一個最關鍵的問題,我們怎么動態插入數據到執行的節之后?  所以我們必須 要設計一個遍歷的方法,用來搜索這個node鏈上的數據,然后找出這個對應的數據把新的節插入到當前的鏈中,并改寫位置記錄  ? 1 2 3 4 5 6 7 8 9 10 //在鏈表中找到對應的節 var findNode = function createFindNode(currNode) { return function(key){ //循環找到執行的節,如果沒有返回本身 while (currNode.data != key) { currNode = currNode.next; } return currNode; } }(headNode);   這就是一個查找當前節的一個方法,通過傳遞原始的頭部headNode節去一直往下查找next,直到找到對應的節信息  這里是用curry方法實現的  那么插入節的的時候,針對鏈表地址的換算關系這是這樣  a-b-c-d的鏈表中,如果要在c(c.next-d)后面插入一個f  a-b-c-f-d ,那么c,next-f , f.next-d  通過insert方法增加節  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 //創建節 function createNode(data) { this.data = data; this.next = null; } //初始化頭部節 //從headNode開始形成一條鏈條 //通過next銜接 var headNode = new createNode(head); //在鏈表中找到對應的節 var findNode = function createFindNode(currNode) { return function(key){ //循環找到執行的節,如果沒有返回本身 while (currNode.data != key) { currNode = currNode.next; } return currNode; } }(headNode); //插入一個新節 this.insert = function(data, key) { //創建一個新節 var newNode = new createNode(data); //在鏈條中找到對應的數據節 //然后把新加入的掛進去 var current = findNode(key); //插入新的接,更改引用關系 //1:a-b-c-d //2:a-b-n-c-d newNode.next = current.next; current.next = newNode; };   首先分離出createNode節的構建,在初始化的時候先創建一個頭部節對象用來做節開頭的初始化對象  在insert增加節方法中,通過對headNode鏈的一個查找,找到對應的節,把新的節給加后之后,最后就是修改一下鏈的關系  如何從鏈表中刪除一個節點?  由于鏈表的特殊性,我們a-b-c-d ,如果要刪除c那么就必須修改b.next-c為 b.next-d,所以找到前一個節修改其鏈表next地址,這個有點像dom操作中removeChild找到其父節點調用移除子節點  同樣的我們也在remove方法的設計中,需要設計一個遍歷往上回溯一個父節點即可  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 //找到前一個節 var findPrevious = function(currNode) { return function(key){ while (!(currNode.next == null) (currNode.next.data != key)) { currNode = currNode.next; } return currNode; } }(headNode); //插入方法 this.remove = function(key) { var prevNode = findPrevious(key); if (!(prevNode.next == null)) { //修改鏈表關系 prevNode.next = prevNode.next.next; } };   測試代碼:  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 !doctype htmlbutton id=test1插入多條數據/button button id=test2刪除Russellville數據/buttondiv id=listshowbr //divscript type=text/javascript ////////// //創建鏈表 // ////////// function createLinkList() { //創建節 function createNode(data) { this.data = data; this.next = null; } //初始化頭部節 //從headNode開始形成一條鏈條 //通過next銜接 var headNode = new createNode(head); //在鏈表中找到對應的節 var findNode = function createFindNode(currNode) { return function(key) { //循環找到執行的節,如果沒有返回本身 while (currNode.data != key) { currNode = currNode.next; } return currNode; } }(headNode); //找到前一個節 var findPrevious = function(currNode) { return function(key) { while (!(currNode.next == null) (currNode.next.data != key)) { currNode = currNode.next; } return currNode; } }(headNode); //插入一個新節 this.insert = function(data, key) { //創建一個新節 var newNode = new createNode(data); //在鏈條中找到對應的數據節 //然后把新加入的掛進去 var current = findNode(key); //插入新的接,更改引用關系 //1:a-b-c-d //2:a-b-n-c-d newNode.next = current.next; current.next = newNode; }; //插入方法 this.remove = function(key) { var prevNode = findPrevious(key); if (!(prevNode.next == null)) { //修改鏈表關系 prevNode.next = prevNode.next.next; } }; this.display = function(fn) { var currNode = headNode; while (!(currNode.next == null)) { currNode = currNode.next; fn(currNode.data) } }; } var cities = new createLinkList(); function create() { var text = ''; cities.display(function(data) { text = '-' data; }); var div = document.createElement('div') div.innerHTML = text; document.getElementById(listshow).appendChild(div) } document.getElementById(test1).onclick = function() { cities.insert(Conway, head); cities.insert(Russellville, Conway); cities.insert(Carlisle, Russellville); cities.insert(Alma, Carlisle); create(); } document.getElementById(test2).onclick = function() { cities.remove(Russellville); create() } /script   雙鏈表  原理跟單鏈表是一樣的,無非就是給每一個節增加一個前鏈表的指針

  增加節  ? 1 2 3 4 5 6 7 8 9 10 11 12 //插入一個新節 this.insert = function(data, key) { //創建一個新節 var newNode = new createNode(data); //在鏈條中找到對應的數據節 //然后把新加入的掛進去 var current = findNode(headNode,key); //插入新的接,更改引用關系 newNode.next = current.next; newNode.previous = current current.next = newNode; };   刪除節  ? 1 2 3 4 5 6 7 8 9 this.remove = function(key) { var currNode = findNode(headNode,key); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } };   在刪除操作中有一個明顯的優化:不需要找到父節了,因為雙鏈表的雙向引用所以效率比單鏈要高  測試代碼:  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 !doctype htmlbutton id=test1插入多條數據/button button id=test2刪除Russellville數據/buttondiv id=listshowbr //divscript type=text/javascript ////////// //創建鏈表 // ////////// function createLinkList() { //創建節 function createNode(data) { this.data = data; this.next = null; this.previous = null } //初始化頭部節 //從headNode開始形成一條鏈條 //通過next銜接 var headNode = new createNode(head); //在鏈表中找到對應的數據 var findNode = function(currNode, key) { //循環找到執行的節,如果沒有返回本身 while (currNode.data != key) { currNode = currNode.next; } return currNode; } //插入一個新節 this.insert = function(data, key) { //創建一個新節 var newNode = new createNode(data); //在鏈條中找到對應的數據節 //然后把新加入的掛進去 var current = findNode(headNode,key); //插入新的接,更改引用關系 newNode.next = current.next; newNode.previous = current current.next = newNode; }; this.remove = function(key) { var currNode = findNode(headNode,key); if (!(currNode.next == null)) { currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } }; this.display = function(fn) { var currNode = headNode; while (!(currNode.next == null)) { currNode = currNode.next; fn(currNode.data) } }; } var cities = new createLinkList(); function create() { var text = ''; cities.display(function(data) { text = '-' data; }); var div = document.createElement('div') div.innerHTML = text; document.getElementById(listshow).appendChild(div) } document.getElementById(test1).onclick = function() { cities.insert(Conway, head); cities.insert(Russellville, Conway); cities.insert(Carlisle, Russellville); cities.insert(Alma, Carlisle); create(); } document.getElementById(test2).onclick = function() { cities.remove(Russellville); create() } /script

版權聲明:本文由 岳芮欣 整理編輯。

原標題:數據結構單鏈表的實現,數據結構

轉載注明出處:http://www.dn9ww09s.icu/program/15170.html

文章評論

    共有條評論來說兩句吧...

    用戶名:

    驗證碼:

作者推薦

  • iptables 端口轉發,iptables本地端口轉發

    iptables 端口轉發,iptables本地端口轉發 相關圖片centos6端口轉發本地接口IP 61.144.14.72的轉發端口3389到116.6.73.229的端口3389(主要是61.144.14.72的接入端口3389,跳到116.iptables端口轉發不起作用...

  • 鎖和事務,事務一定鎖表嗎

    鎖和事務,事務一定鎖表嗎 相關圖片事務和數據庫鎖的聯系SQL server中的事務和鎖事務都是關于原子性的。原子性的概念意味著某物可以被視為一個單元。從數據庫的角度來看,它是指一個或多個應該執行或不執行的語句的...

  • ajax,ajax如何處理跨域問題

    ajax,ajax如何處理跨域問題 相關圖片java處理ajax請求本文主要介紹jQuery中模擬圖像的ajaxprefilter和ajaxtransport處理。本文直接給出了仿真實現代碼,其中包含了詳細的注釋。朋友請參考“1ajax json...

  • sysdba,expdp sysdba

    sysdba,expdp sysdba 相關圖片dba和sysdba一。Oracle可以通過兩種方式對SYSDBA/sysoper用戶進行身份驗證:1)操作系統級身份驗證:登錄Oracle數據庫主機,使用以下用戶登錄,然后直接使oracle賦予sysdba權限...

  • 什么是位圖索引,創建位圖索引

    什么是位圖索引,創建位圖索引 相關圖片位圖索引的主要優缺點什么是位圖索引位圖索引的一些特性?位圖索引的優缺點?讓我們看看低比特圖像掃描的例子。查詢計劃----------------------------------索引...

  • 實例卡,實例

    實例卡,實例 相關圖片實例文本Example off: V $diag_infosphere name = sqltname.sqlselect value in 'default trac什么是示例圖...

  • gaming mouse鼠標宏,scream鼠標

    gaming mouse鼠標宏,scream鼠標 相關圖片mouse0是哪個鍵本文主要介紹了JavaScript和jQuery的鼠標-鼠標事件冒泡處理,總結了鼠標事件的一些結論,并分別給出了JavaScript和jQuery的測試代碼。您mouse3是哪個鍵...

  • 控制文件損壞,oracle控制文件

    控制文件損壞,oracle控制文件 相關圖片增加控制文件出現的現象是系統無法登錄,沒有用戶可以,懷疑數據庫有問題,輸入服務器,運行sqlplususername/password,無法輸入數據庫,提示輸入用戶名。重新重建控制文件...

  • decode函數的用法,decode函數實例

    decode函數的用法,decode函數實例 相關圖片oracle decode 用模糊decode函數相當于條件語句(if)。它將輸入值與函數中的參數列表進行比較,并根據輸入值返回相應的值。函數的參數列表由多個值及其相應的結果值組成。當然,如果...

  • lvds接口詳解,eDP接口

    lvds接口詳解,eDP接口 相關圖片lvds接口圖解類型檢查是typescript的核心設計原則之一。通過使用接口,可以進行類型檢查,滿足傳統的面向對象思想,有利于有效開發,有效避免類型轉換問題。在typescr主板接口詳細圖...

熱評文章

  • 編程創建一個Rect,編程創建listview

    編程創建一個Rect,編程創建listview 相關圖片uG編程順序本文主要介紹使用angularjs創建單頁應用程序的編程指南。Angularjs是一個流行的JavaScript庫。對于越來越多的朋友,您可以參考單頁應用程序概ug編程創建幾何體怎么設置...

  • 如何進行sql優化,sql查詢優化

    如何進行sql優化,sql查詢優化 相關圖片sql or 優化昨天,我半夜收到一條SQL消息。反應很慢。我很生氣。經過查詢,我只需要三個月運行一次這個SQL。你必須在法定假日經營嗎?SQL如下(非常長)?123456789復雜sql優化...

  • oracle索引怎么用,oracle索引的使用

    oracle索引怎么用,oracle索引的使用 相關圖片oracle視圖索引刪除大量表后,可能會有大量可用空間可回收。請參考以下計算方法:更新統計分析表計算統計;計算碎片空間選擇表名,(塊*8)oracle如何查看索引...

  • curl header,curl打印返回header

    curl header,curl打印返回header 相關圖片curl telnet本文主要介紹了phpcurl偽造IP地址和頭信息代碼的實例。本文給出了服務器端和客戶端的實現代碼,提供了偽造功能和服務器端檢測代碼。你可以給你的朋友們指卷發。雖curl coo...

  • asp 代碼,asp開源代碼

    asp 代碼,asp開源代碼 相關圖片怎樣將asp源代碼這是一個簡單的ASP教程,添加數據代碼程序,接受用戶提交的數據,然后保存到數據庫教程非常方便,哦,讓我們看一個詳細的例子。例如,在“名稱”字段中輸入用戶...

  • jsp遍歷,jsp遍歷for

    jsp遍歷,jsp遍歷for 相關圖片jsp中迭代器遍歷數據如果foreach中的items類型是map或collection,如何使用增強for循環?首先,創建一個label處理器類并定義兩個屬性,string VaRjQuery遍歷li...

  • shutdown用不了,shutdown

    shutdown用不了,shutdown 相關圖片運行shutdown本文主要介紹了語域的使用?關閉?函數在PHP中攔截致命錯誤示例。當我們在做這個項目的時候,你可以向我們的朋友請教,有時由于粗心大意會發生致命的錯誤。如果顯示錯...

  • 程序員成長之路,一個程序員的成長之路

    程序員成長之路,一個程序員的成長之路 相關圖片程序員上升之路一個常見的錯誤是將JSP視為簡化的Java,這是不可能的。(實際上,JSP是一個簡化的servlet)。程序員通常嘗試直接學習jsp而不學習所需的支持技能。JSJava工程師工資成長之...

  • 你能干大事,人能干啥

    你能干大事,人能干啥 相關圖片能干的人都是怎樣的PHP還能夠在PHP中做一些偉大的事情。本文主要介紹了在PHP中進行編譯碼的一些細節,這些細節在PHP中也能起到很大的作用。介紹了ASCII編解碼、URL編解碼太能干的人會...

  • asp與html,asp比html多了哪些

    asp與html,asp比html多了哪些 相關圖片html運行asp代碼如下:函數gethttpxml()set HTTP=server.createobject(msxml2)。服務器xmlhttp)dim lresolve、html改成asp...

關注微信

变脸官网查询