国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

前端的數(shù)據(jù)結(jié)構(gòu)與算法（1）-- dfs

hizengzeng / 2172人閱讀

摘要：前端在開發(fā)過程中接觸到的算法最多的莫過于排序和深度優(yōu)先遍歷。關(guān)于算法的遍歷過程，我簡略的畫了一個示例圖實(shí)例最近在實(shí)際業(yè)務(wù)場景中，跟后端約定頁面中所有組件的消息根據(jù)頁面上的組件聚合到一個對象中，后端返回的是類似如下的一個樹形數(shù)據(jù)結(jié)構(gòu)。

dfs 
前端在開發(fā)過程中接觸到的算法最多的莫過于排序和 dfs(深度優(yōu)先遍歷) 。 dfs 算法廣泛用于圖（樹是圖的一種）的遍歷，如：沒有 querySelectorAll 的時候，根據(jù) classname 或者 tag 查找 element。

關(guān)于 dfs 算法的遍歷過程，我簡略的畫了一個示例圖：

實(shí)例：

最近在實(shí)際業(yè)務(wù)場景中，跟后端約定頁面中所有組件的消息根據(jù)頁面上的組件 id 聚合到一個對象中，后端返回的是類似如下的一個樹形數(shù)據(jù)結(jié)構(gòu)。前端需要把所有的錯誤信息都拿出來，按照頁面上所有組件的順序聚合顯示在一個全局信息面板組件上（至于按照組件順序排序算法本文暫且略過）

let tree = {
    "id1": {
        message: "hello"
    },
    "id2": {
        message: "world",
        children: {
          "id2-1": {
              message: "haha",
              children: {
              }
          },
          "id2-2": {
              message: "heihei"
          }
        }
    }
}

由于某些大組件可能是由多個小組件層層嵌套組合而來，且每個小組件都有相應(yīng)的 message 需要展示，所以就選擇了上述的樹形結(jié)構(gòu)來表達(dá)組件的信息。這個時候就會有人問，為什么不讓后端把所有 message 都聚合到數(shù)組里面？因?yàn)榍岸瞬粌H需要把這些錯誤信息聚合到一起展示，也需要把錯誤定位到具體組件上

遞歸版本實(shí)現(xiàn) 
function dfs(tree = {}, messages = []) {
    let i = 0;
    if(!messages) messages = [];
    if(tree.message) messages.push(tree.message);
    
    const keys = Object.keys(tree.children || {});
    while (i < keys.length) {
        dfs(tree.children[keys[i]], messages);
        i += 1;
    }
    return messages;
}

 tree = {
    message: null,
    children: tree
 };  
 
 dfs(tree);
非遞歸版本實(shí)現(xiàn) 
  function dfs(tree = {}) {
    const array = [tree];
    let messages = [];
    while (array.length) {
      const top = array.pop();
      if (top.message) {
        messages.push(top.message);
      }
      const keys = Object.keys(top.children || {});
      let i = keys.length;
      while (i > 0) {
        i -= 1;
        array.push(top.children[keys[i]]);
      }
    }
    return messages
  }
  
 tree = {
    message: null,
    children: tree
 };  
 
 dfs(tree);

在實(shí)際使用中，考慮到數(shù)據(jù)結(jié)構(gòu)的層數(shù)沒那么多，其實(shí)尾遞歸版本和非遞歸版本所消耗的時間在瀏覽器的優(yōu)化下幾乎可忽略了。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/87261.html

相關(guān)文章

  • 算法（第4版） Chapter 4.2 有向圖

    摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運(yùn)行，將頂點(diǎn)按照逆后序方式壓入棧中顯然，這個過程作用在有向無環(huán)圖上得到的就是一個拓?fù)渑判蜃饔迷诜巧系玫降氖且粋€偽拓?fù)渑判虻诙皆谠瓐D上按第一步的編號順序進(jìn)行。等價(jià)于已知在逆圖中存在有向路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslat...

    曹金海 評論0 收藏0

  • PHP面試：常見查找算法一篇說透

    摘要：我們現(xiàn)在來看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對二分搜索算法的改進(jìn)，插值搜索可以基于搜索的值選擇到達(dá)不同的位置。 預(yù)警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥?，所以篇幅可能較長，大伙可以先Mark下來，每天抽時間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...

    付永剛 評論0 收藏0

  • 隨機(jī)生成指定面積單連通區(qū)域

    摘要：原文鏈接最近在知乎上看到一個問題，隨機(jī)生成指定面積單連通區(qū)域，感覺還挺有意思的，于是整理一下寫一篇新文章。問題闡述如下圖所示，在的區(qū)域中，隨機(jī)生成面積為的單連通區(qū)域，該隨機(jī)包括位置隨機(jī)以及形狀隨機(jī)。 原文鏈接：https://xcoder.in/2018/04/01/random-connected-area/ 最近在知乎上看到一個問題，「隨機(jī)生成指定面積單連通區(qū)域？」，感覺還挺有意...

    zhoutk 評論0 收藏0

  • 算法（第4版） Chapter 4.1 無向圖

    摘要：邊僅由兩個頂點(diǎn)連接，并且沒有方向的圖稱為無向圖。用分隔符當(dāng)前為空格，也可以是分號等分隔。深度優(yōu)先算法最簡搜索起點(diǎn)構(gòu)造函數(shù)找到與起點(diǎn)連通的其他頂點(diǎn)。路徑構(gòu)造函數(shù)接收一個頂點(diǎn)，計(jì)算到與連通的每個頂點(diǎn)之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

    kamushin233 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<