• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-19  評論-21  文章-0  trackbacks-0
             要找工作了,終于覺得是時候總結一下數據結構了(ps: 對于數組,鏈表這樣簡單常用的結構就不總結了,此文會持續更新),總結有助于更好地思考。

            1. 位圖
                位圖的威力可以在<編程珠璣>的開頭就體會到。另外在Find an integer not among four billion given ones中的運用也很精彩。

            2. 堆
               在<編程珠璣>里重點運用了該結構,直接導致我以后經常想到并使用該結構。
               不得不說,它真的很有用,如:找N個數中最大/最小的k個數。
               實現優先級隊列時也有用。

            3. 樹
                 二叉搜索樹:是一個很容易就能想到的結構,只要讓一棵二叉樹滿足以下一個特性就可以了:對于任一結點N,其左子樹結點left滿足key(x) <= key(N),其右子樹結點right滿足key(y) >= key(N),其優點是操作簡單,缺點是插入,刪除結點的復雜度高,為O(N)
                 二叉搜索樹復雜度高的原因為:樹的高度不確定/不穩定,有可能為n,所以問題的關鍵是:如何控制樹的高度
                 很多人靈機一動:產生了一系列平衡二叉樹,如:AVL樹,Red-Black樹,Treap
                 也產生了很多平衡二叉樹的變種,如:Weight balanced tree,k-neighbor tree等
                 Skip List 也是平衡二叉樹之外的另一種選擇
                 Trie樹 用來存儲一個字典,然后用來查找某個字符串還是很方便的(A trie can be seen as a deterministic finite automaton.) 另外可以看看Suffix_tree后綴樹。

            4. hash
                hash的兩個關鍵點在于:a. hash桶大小的設定(一般為一個素數) b. 沖突處理機制,如可以用一個鏈表處理hash值相同的元素。
                我很少考慮hash,覺得復雜度不好把握。以后倒是可以考慮用用,如:在問題“判斷兩個鏈表是否相交”有可以使用hash;“判斷鏈表有沒有環”用hash也很給力。
            posted on 2011-08-24 20:15 hex108 閱讀(590) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            国产精品久久久久乳精品爆| 久久精品免费全国观看国产| 精品久久久久久亚洲精品| 天天爽天天狠久久久综合麻豆| 久久久久亚洲AV成人片| 国产成人无码精品久久久免费| 午夜福利91久久福利| 精品久久久久久亚洲精品 | 国产成人久久久精品二区三区| 日韩欧美亚洲综合久久影院Ds| 久久久久无码精品国产不卡| 理论片午午伦夜理片久久| 色综合久久无码五十路人妻| 国产精品成人99久久久久 | 久久强奷乱码老熟女网站| 一级做a爰片久久毛片人呢| 久久免费看黄a级毛片| 久久本道久久综合伊人| www.久久热.com| 伊人久久综合成人网| 久久久久国产精品麻豆AR影院| 国产精品美女久久久久久2018| 香蕉久久永久视频| 久久91这里精品国产2020| 国产精品久久免费| 久久国产精品成人影院| 麻豆精品久久久久久久99蜜桃| 国内精品久久久久久久久| 国产精品久久波多野结衣| 精品蜜臀久久久久99网站| 欧美喷潮久久久XXXXx| 国产精品久久久久久久久软件 | 色综合久久无码中文字幕| 亚洲愉拍99热成人精品热久久 | 亚洲国产成人精品久久久国产成人一区二区三区综 | 久久精品国产网红主播| 无码人妻久久一区二区三区蜜桃| 久久久久这里只有精品 | 色综合久久88色综合天天| 99久久精品国产高清一区二区| 97热久久免费频精品99|