java实现数据结构07.01（映射详解代码之自定义链表映射）

「爱情、让人受尽委屈。」 2023-06-23 05:00 2阅读 0赞

## 因为main测试时使用了自定义数组，所有可以先阅读[java实现数据结构01(数组详解代码之自定义数组)][java_01] ##

## 自定义链表映射 ##

/**
     * @description: 基于链表创建映射
     * @author: liangrui
     * @create: 2019-12-17 15:06
     **/
    public class LinkedListMap<K,V> implements Map<K,V> {
    
        private class Node{
            //键
            public K key;
            //值
            public V value;
            //下一节点
            public Node next;
    
            /**
             * 有参构造函数
             * @param key 键
             * @param value 值
             * @param 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+":"+value;
            }
        }
    
        //虚拟头节点
        private Node dummyHead;
        //元素个数
        private int size;
    
    
        public LinkedListMap(){
            dummyHead=new Node();
            size=0;
        }
    
        /**
         * 根据键获取节点
         * @param k
         * @return
         */
        private Node getNode(K k){
            Node cur=dummyHead.next;
            while (cur!=null){
                if (k.equals(cur.key)){
                    return cur;
                }
                cur=cur.next;
            }
            return null;
        }
    
        @Override
        public void add(K k, V v) {
            Node node=getNode(k);
            if (node==null){
                dummyHead.next=new Node(k,v,dummyHead.next);
                size++;
            }else {
                node.value=v;
            }
        }
    
        @Override
        public V remove(K k) {
            Node prev=dummyHead;
            //循环遍历得到要删除节点的前一个节点
            while (prev.next!=null){
                if (prev.next.key.equals(k)){
                    break;
                }
                prev=prev.next;
            }
    
            //删除节点
            Node delNode=prev.next;
            prev.next=delNode.next;
            delNode.next=null;
            size--;
            return delNode.value;
    
        }
    
        @Override
        public void set(K k, V v) {
            Node setNode=getNode(k);
            if (setNode==null){
                throw new IllegalArgumentException(k+"doesn't exist.");
            }
            setNode.value=v;
        }
    
        @Override
        public V get(K k) {
            Node getNode=getNode(k);
            return getNode==null?null:getNode.value;
        }
    
        @Override
        public boolean contains(K k) {
            return getNode(k)!=null;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size==0;
        }
    }

## 文件操作类 ##

import java.io.FileInputStream;
    import java.util.Scanner;
    import java.util.Locale;
    import java.io.File;
    import java.io.BufferedInputStream;
    import java.io.IOException;
    
    // 文件相关操作
    public class FileOperation { 
    
        // 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
        public static boolean readFile(String filename, Array<String> words){ 
    
            if (filename == null || words == null){ 
                System.out.println("filename is null or words is null");
                return false;
            }
    
            // 文件读取
            Scanner scanner;
    
            try { 
                File file = new File(filename);
                if(file.exists()){ 
                    FileInputStream fis = new FileInputStream(file);
                    scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                    scanner.useLocale(Locale.ENGLISH);
                }else{ 
                    return false;
                }
            }catch(IOException ioe){ 
                System.out.println("Cannot open " + filename);
                return false;
            }
    
            // 简单分词
            // 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
            // 在这里只做demo展示用
            if (scanner.hasNextLine()) { 
    
                String contents = scanner.useDelimiter("\\A").next();
    
                int start = firstCharacterIndex(contents, 0);
                for (int i = start + 1; i <= contents.length(); )
                    if (i == contents.length() || !Character.isLetter(contents.charAt(i))) { 
                        String word = contents.substring(start, i).toLowerCase();
                        words.addLast(word);
                        start = firstCharacterIndex(contents, i);
                        i = start + 1;
                    } else { 
                        i++;
                    }
            }
            return true;
        }
    
        // 寻找字符串s中，从start的位置开始的第一个字母字符的位置
        private static int firstCharacterIndex(String s, int start){ 
            for( int i = start ; i < s.length() ; i ++ ){ 
                //Character.isLetter()判断字符是否为字母
                if(Character.isLetter(s.charAt(i))){ 
                    return i;
                }
            }
            return s.length();
        }
    }

## main测试 ##

public class Main { 
    
        public static void main(String[] args) { 
            Array<String> array=new Array<>();
            //将所有单词添加到array中
            FileOperation.readFile("pride-and-prejudice.txt",array);
            System.out.println("Total words:"+array.getSize());
    
            LinkedListMap<String,Integer> linkedListMap=new LinkedListMap<>();
            for (int i = 0; i < array.getSize(); i++) { 
                String word=array.get(i);
                //如果映射中存在该元素，则将其值+1
                if (linkedListMap.contains(word)){ 
                    linkedListMap.set(word,linkedListMap.get(word)+1);
                }else { 
                    //如果映射中不存在该元素，则添加该元素到映射
                    linkedListMap.add(word,1);
                }
            }
    
            //不同单词个数
            System.out.println("Different words:"+linkedListMap.getSize());
            //'pride'出现的频率
            System.out.println("Frequency of 'pride':"+linkedListMap.get("pride"));
            //'prejudice'出现的频率
            System.out.println("Frequency of 'prejudice':"+linkedListMap.get("prejudice"));
        }
    }

## 测试结果 ##

> Total words:125901  
> Different words:6530  
> Frequency of ‘pride’:53  
> Frequency of ‘prejudice’:11

[java_01]: https://blog.csdn.net/liangruilz/article/details/103430382