溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)(3)——鏈表

發(fā)布時間:2020-07-13 07:23:05 來源:網(wǎng)絡(luò) 閱讀:404 作者:大史不說話 欄目:開發(fā)技術(shù)

野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)(3)——鏈表

網(wǎng)上的相關(guān)教程非常多,基礎(chǔ)知識自行搜索即可。

習(xí)題主要選自O(shè)relly出版的《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》一書。

參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/List

鏈表的基本知識

  • 特點:

    鏈表由節(jié)點組成,每個節(jié)點增加一個對象的引用指向它的后繼節(jié)點。鏈表也就是將一個線性表轉(zhuǎn)換為一個存儲空間上不連續(xù),而在抽象層面可連續(xù)訪問的表。

  • 用途:

    更快的插入和刪除,因為只需要操作插入刪除位置相鄰元素即可,如果在線性表中,操作中間位置的元素后,后續(xù)的元素位置都需要調(diào)整。javascript中的應(yīng)用例如原型鏈。

  • 基本屬性

    • element當前節(jié)點的值
    • next下一個節(jié)點
  • 基本方法

    • insert(item, newitem)在item后面插入一個新元素newitem

    插入一個元素,需要將item元素節(jié)點的next指向新元素,新元素的next指向item元素的后繼元素。

    • remove(pos)從隊頭刪除一個元素

    刪除一個節(jié)點時,需要將其前驅(qū)節(jié)點的next指向其后繼節(jié)點即可。

    • find(element)查詢值為element的節(jié)點位置

    • findpre(element)查詢值為element的節(jié)點的前一個節(jié)點

    • display()顯示整個鏈表

基本練習(xí)

  1. 根據(jù)鏈表的基本特性實現(xiàn)一個LinkedList類,并在后續(xù)題目中需要用鏈表時使用它。

    【注意點】:刪除指定元素時,由于需要修改指定元素前一個節(jié)點的next指針,所以當所查找的節(jié)點存在時,搜索方法應(yīng)當返回其前一個節(jié)點以供后續(xù)步驟使用。

  2. 實現(xiàn)一個雙向鏈表TwoWayLinkedList類。

    【注意點】:每一個實例會記錄前驅(qū)節(jié)點和后繼節(jié)點,雙向鏈表比單鏈表增加了反向遍歷的能力,并且由于所查找節(jié)點的屬性中包含了前驅(qū)和后繼節(jié)點的信息,故插入節(jié)點和刪除節(jié)點時使用同一個搜索方法即可。

  3. LinkedList類為參考基準,實現(xiàn)一個循環(huán)鏈表CircularLinkedList類。

    【注意點】:循環(huán)鏈表的特點是尾節(jié)點的next指針指向了頭節(jié)點。

課后習(xí)題(書中第六節(jié)習(xí)題)

  1. 實現(xiàn)Advance(n)方法,使節(jié)點向前移動n個節(jié)點。
  2. 實現(xiàn)back(n)方法,使節(jié)點向后移動n個節(jié)點。
  3. 實現(xiàn)show()方法,只顯示當前節(jié)點上的數(shù)據(jù)。
  4. (略)
  5. (略)
  6. 傳說在公元1世紀猶太戰(zhàn)爭中,猶太歷史學(xué)家弗拉維奧·約瑟夫斯和他的40個同胞被羅馬士兵包圍,猶太士兵決定寧可自殺也不做俘虜,于是商量出一個自殺方案。他們圍成一個圈,從一個人開始,數(shù)到第三個人事將第三個人殺死,然后再數(shù),直到殺光所有人,約瑟夫和另一個人決定不參加這個瘋狂的游戲,他們快速地計算出兩個位置,站在那里得以幸存。寫一段將n個人圍成一圈,并且第m個人會被殺掉,計算一圈中哪兩個人最后會存貨,使用循環(huán)鏈表解決該問題。

習(xí)題思路

  1. 向前移動n個位置,在位置驗證合法時相當于,從原位置刪除一個節(jié)點,在新位置插入一個節(jié)點,為操作方便直接使用雙向鏈表來實現(xiàn)即可。【注意點】:示例代碼中直接以放入鏈表的值為依據(jù)進行節(jié)點查找,故不支持重復(fù)數(shù)據(jù),可為節(jié)點增加index屬性來區(qū)分相同數(shù)據(jù)。
    野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)(3)——鏈表

  2. 與上一題同理。

  3. 很好實現(xiàn)。

  4. 使用一個單鏈表來存儲輸入的成績即可,當最后一個成績節(jié)點的指針指向null即可。

  5. 用值為1-40的元素循環(huán)鏈表來刪除節(jié)點直到總節(jié)點數(shù)目只剩2個為止。為了方便統(tǒng)計剩余元素的數(shù)量,為鏈表增加一個count屬性來記錄元素個數(shù)。
    野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)(3)——鏈表
向AI問一下細節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI