數(shù)據(jù)結(jié)構(gòu)(八)兩種方式實(shí)現(xiàn)map

數(shù)據(jù)結(jié)構(gòu)(一)數(shù)組實(shí)現(xiàn)一個(gè)簡(jiǎn)單的ArrayList
數(shù)據(jù)結(jié)構(gòu)(二)鏈表實(shí)現(xiàn)LinkedList
數(shù)據(jù)結(jié)構(gòu)(三)用兩種方式簡(jiǎn)單實(shí)現(xiàn)棧
數(shù)據(jù)結(jié)構(gòu)(四)棧和隊(duì)列的簡(jiǎn)單應(yīng)用
數(shù)據(jù)結(jié)構(gòu)(五)用兩種方式簡(jiǎn)單實(shí)現(xiàn)隊(duì)列
數(shù)據(jù)結(jié)構(gòu)(六)二分搜索樹(Binary Search Tree)(上)
數(shù)據(jù)結(jié)構(gòu)(六)二分搜索樹(Binary Search Tree)(下)
數(shù)據(jù)結(jié)構(gòu)(七)兩種方式實(shí)現(xiàn)set
數(shù)據(jù)結(jié)構(gòu)(八)兩種方式實(shí)現(xiàn)map
數(shù)據(jù)結(jié)構(gòu)(九)set解決LeetCode349號(hào)問題

今天我們來實(shí)現(xiàn)一下map评雌,總共有兩種方式酝静,第一種是二分搜索樹實(shí)現(xiàn)map首妖,第二種方式鏈表實(shí)現(xiàn)map。
話不多說直接上源碼。

public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {

    private class Node{
        public K key;
        public V value;
        public Node left, right;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap(){
        root = null;
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    // 向二分搜索樹中添加新的元素(key, value)
    @Override
    public void add(K key, V value){
        root = add(root, key, value);
    }

    // 向以node為根的二分搜索樹中插入元素(key, value),遞歸算法
    // 返回插入新節(jié)點(diǎn)后二分搜索樹的根
    private Node add(Node node, K key, V value){

        if(node == null){
            size ++;
            return new Node(key, value);
        }

        if(key.compareTo(node.key) < 0)
            node.left = add(node.left, key, value);
        else if(key.compareTo(node.key) > 0)
            node.right = add(node.right, key, value);
        else // key.compareTo(node.key) == 0
            node.value = value;

        return node;
    }

    // 返回以node為根節(jié)點(diǎn)的二分搜索樹中,key所在的節(jié)點(diǎn)
    private Node getNode(Node node, K key){

        if(node == null)
            return null;

        if(key.equals(node.key))
            return node;
        else if(key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else // if(key.compareTo(node.key) > 0)
            return getNode(node.right, key);
    }

    @Override
    public boolean contains(K key){
        return getNode(root, key) != null;
    }

    @Override
    public V get(K key){

        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue){
        Node node = getNode(root, key);
        if(node == null)
            throw new IllegalArgumentException(key + " doesn't exist!");

        node.value = newValue;
    }

    // 返回以node為根的二分搜索樹的最小值所在的節(jié)點(diǎn)
    private Node minimum(Node node){
        if(node.left == null)
            return node;
        return minimum(node.left);
    }

    // 刪除掉以node為根的二分搜索樹中的最小節(jié)點(diǎn)
    // 返回刪除節(jié)點(diǎn)后新的二分搜索樹的根
    private Node removeMin(Node node){

        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }

    // 從二分搜索樹中刪除鍵為key的節(jié)點(diǎn)
    @Override
    public V remove(K key){

        Node node = getNode(root, key);
        if(node != null){
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) < 0 ){
            node.left = remove(node.left , key);
            return node;
        }
        else if(key.compareTo(node.key) > 0 ){
            node.right = remove(node.right, key);
            return node;
        }
        else{   // key.compareTo(node.key) == 0

            // 待刪除節(jié)點(diǎn)左子樹為空的情況
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            // 待刪除節(jié)點(diǎn)右子樹為空的情況
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            // 待刪除節(jié)點(diǎn)左右子樹均不為空的情況

            // 找到比待刪除節(jié)點(diǎn)大的最小節(jié)點(diǎn), 即待刪除節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn)
            // 用這個(gè)節(jié)點(diǎn)頂替待刪除節(jié)點(diǎn)的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }

    public static void main(String[] args){

        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
            System.out.println("Total words: " + words.size());

            BSTMap<String, Integer> map = new BSTMap<>();
            for (String word : words) {
                if (map.contains(word))
                    map.set(word, map.get(word) + 1);
                else
                    map.add(word, 1);
            }

            System.out.println("Total different words: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
        }

        System.out.println();
    }
}
  • add方法
    這個(gè)node與之前鏈表的node有點(diǎn)不太一樣,這里多了一個(gè)value株扛,指針變成了left和right尤筐。這個(gè)add方法我們用遞歸的方式實(shí)現(xiàn)的,當(dāng)這個(gè)節(jié)點(diǎn)是空的時(shí)候我們就創(chuàng)建一個(gè)節(jié)點(diǎn)洞就,如果這個(gè)節(jié)點(diǎn)不是空的:先比較可以與當(dāng)前節(jié)點(diǎn)的元素盆繁,如果比當(dāng)前節(jié)點(diǎn)的元素小則去這個(gè)節(jié)點(diǎn)的左子樹去處理;如果比當(dāng)前節(jié)點(diǎn)的元素大旬蟋,那么就去這個(gè)節(jié)點(diǎn)的右子樹去遍歷油昂,如果相等那么就把值賦給這個(gè)節(jié)點(diǎn)。
  • getNode
    獲取方法倾贰,獲取值為key的節(jié)點(diǎn)元素的value冕碟。這里也是遞歸的方式實(shí)現(xiàn)的,首先如果這個(gè)節(jié)點(diǎn)是空的匆浙,就返回null安寺,然后比較這個(gè)節(jié)點(diǎn)的值與傳入的key,如果相等首尼,就返回當(dāng)前的節(jié)點(diǎn)挑庶,如果比這個(gè)節(jié)點(diǎn)小那么就去這個(gè)節(jié)點(diǎn)的左子樹去遍歷,如果比這個(gè)節(jié)點(diǎn)的值大就去這個(gè)節(jié)點(diǎn)的右子樹去遍歷软能。
public class LinkedListMap<K, V> implements Map<K, V> {

    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key, V value, Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key, V value){
            this(key, value, null);
        }

        public Node(){
            this(null, null, null);
        }

        @Override
        public String toString(){
            return key.toString() + " : " + value.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap(){
        dummyHead = new Node();
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    private Node getNode(K key){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.key.equals(key))
                return cur;
            cur = cur.next;
        }
        return null;
    }

    @Override
    public boolean contains(K key){
        return getNode(key) != null;
    }

    @Override
    public V get(K key){
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void add(K key, V value){
        Node node = getNode(key);
        if(node == null){
            dummyHead.next = new Node(key, value, dummyHead.next);
            size ++;
        }
        else
            node.value = value;
    }

    @Override
    public void set(K key, V newValue){
        Node node = getNode(key);
        if(node == null)
            throw new IllegalArgumentException(key + " doesn't exist!");

        node.value = newValue;
    }

    @Override
    public V remove(K key){

        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.key.equals(key))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
            return delNode.value;
        }

        return null;
    }

    public static void main(String[] args){

        System.out.println("Pride and Prejudice");

        ArrayList<String> words = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
            System.out.println("Total words: " + words.size());

            LinkedListMap<String, Integer> map = new LinkedListMap<>();
            for (String word : words) {
                if (map.contains(word))
                    map.set(word, map.get(word) + 1);
                else
                    map.add(word, 1);
            }

            System.out.println("Total different words: " + map.getSize());
            System.out.println("Frequency of PRIDE: " + map.get("pride"));
            System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
        }

        System.out.println();
    }
}

更多精彩請(qǐng)關(guān)注公眾號(hào)及時(shí)接收

公眾號(hào)
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末迎捺,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子埋嵌,更是在濱河造成了極大的恐慌破加,老刑警劉巖俱恶,帶你破解...
    沈念sama閱讀 211,561評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件雹嗦,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡合是,警方通過查閱死者的電腦和手機(jī)了罪,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,218評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來聪全,“玉大人泊藕,你說我怎么就攤上這事∧牙瘢” “怎么了娃圆?”我有些...
    開封第一講書人閱讀 157,162評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)蛾茉。 經(jīng)常有香客問我讼呢,道長(zhǎng),這世上最難降的妖魔是什么谦炬? 我笑而不...
    開封第一講書人閱讀 56,470評(píng)論 1 283
  • 正文 為了忘掉前任悦屏,我火速辦了婚禮节沦,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘础爬。我一直安慰自己甫贯,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,550評(píng)論 6 385
  • 文/花漫 我一把揭開白布看蚜。 她就那樣靜靜地躺著叫搁,像睡著了一般。 火紅的嫁衣襯著肌膚如雪供炎。 梳的紋絲不亂的頭發(fā)上常熙,一...
    開封第一講書人閱讀 49,806評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音碱茁,去河邊找鬼裸卫。 笑死,一個(gè)胖子當(dāng)著我的面吹牛纽竣,可吹牛的內(nèi)容都是我干的墓贿。 我是一名探鬼主播,決...
    沈念sama閱讀 38,951評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開眼蜓氨,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼聋袋!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起穴吹,我...
    開封第一講書人閱讀 37,712評(píng)論 0 266
  • 序言:老撾萬榮一對(duì)情侶失蹤幽勒,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后港令,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體啥容,經(jīng)...
    沈念sama閱讀 44,166評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,510評(píng)論 2 327
  • 正文 我和宋清朗相戀三年顷霹,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了咪惠。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,643評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡淋淀,死狀恐怖遥昧,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情朵纷,我是刑警寧澤炭臭,帶...
    沈念sama閱讀 34,306評(píng)論 4 330
  • 正文 年R本政府宣布,位于F島的核電站袍辞,受9級(jí)特大地震影響鞋仍,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜革屠,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,930評(píng)論 3 313
  • 文/蒙蒙 一凿试、第九天 我趴在偏房一處隱蔽的房頂上張望排宰。 院中可真熱鬧,春花似錦那婉、人聲如沸板甘。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,745評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)盐类。三九已至,卻和暖如春呛谜,著一層夾襖步出監(jiān)牢的瞬間在跳,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,983評(píng)論 1 266
  • 我被黑心中介騙來泰國(guó)打工隐岛, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留猫妙,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,351評(píng)論 2 360
  • 正文 我出身青樓聚凹,卻偏偏與公主長(zhǎng)得像割坠,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子妒牙,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,509評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容