数据结构之映射

朴灿烈づ我的快乐病毒、 2022-02-23 02:58 284阅读 0赞

### 数据结构之映射 ###

*  映射
 *   *  Map接口定义
     *  基于链表的映射实现
     *  基于二分搜索树的映射实现
     *  映射的复杂度分析
     *  有序映射和无序映射
     *  多重映射

# 映射 #

映射概念的实现：

<table> 
 <thead> 
  <tr> 
   <th>dict</th> 
   <th>key</th> 
   <th>value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>字典</td> 
   <td>单词</td> 
   <td>释义</td> 
  </tr> 
  <tr> 
   <td>名册</td> 
   <td>身份证号</td> 
   <td>人</td> 
  </tr> 
  <tr> 
   <td>车辆管理</td> 
   <td>车牌号</td> 
   <td>车</td> 
  </tr> 
  <tr> 
   <td>数据库</td> 
   <td>id</td> 
   <td>信息</td> 
  </tr> 
  <tr> 
   <td>词频统计</td> 
   <td>单词</td> 
   <td>频率</td> 
  </tr> 
 </tbody> 
</table>

*  存储（键，值）数据对的数据结构（Key，Value）
 *  根据键（Key），寻找值（Value）
 *  非常容易使用链表或者二分搜索树实现

## Map接口定义 ##

/** * Created by binzhang on 2019/4/5. */
    public interface Map<K, V> { 
    
        void add(K key, V value);
        V remove(K key);
        boolean contains(K key);
        V get(K key);
        void set(K key, V newValue);
        int getSize();
        boolean isEmpty();
    }

## 基于链表的映射实现 ##

/** * Created by binzhang on 2019/4/5. */
    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){ 
                this(key, null, 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;
        }
    
        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 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 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;
        }
    
        @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 set(K key, V newValue) { 
            Node node = getNode(key);
            if (node == null)
                throw new IllegalArgumentException(key + "doesn't exist");
            node.value = newValue;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    }

## 基于二分搜索树的映射实现 ##

import java.util.ArrayList;
    
    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)，递归算法
        // 返回插入新节点后二分搜索树的根
        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为根节点的二分搜索树中，key所在的节点
        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为根的二分搜索树的最小值所在的节点
        private Node minimum(Node node){ 
            if(node.left == null)
                return node;
            return minimum(node.left);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点
        // 返回删除节点后新的二分搜索树的根
        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的节点
        @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
    
                // 待删除节点左子树为空的情况
                if(node.left == null){ 
                    Node rightNode = node.right;
                    node.right = null;
                    size --;
                    return rightNode;
                }
    
                // 待删除节点右子树为空的情况
                if(node.right == null){ 
                    Node leftNode = node.left;
                    node.left = null;
                    size --;
                    return leftNode;
                }
    
                // 待删除节点左右子树均不为空的情况
    
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                // 用这个节点顶替待删除节点的位置
                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();
        }
    }

## 映射的复杂度分析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

## 有序映射和无序映射 ##

*  有序映射中的键具有顺序性 基于搜索树的实现
 *  无序映射中的键没有顺序性 基于哈希表的实现

## 多重映射 ##

*  多重映射中的键可以重复

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220223/db6a4534d3eb4f5990d1078b41e19819.png