0 课程地址
https://coding.imooc.com/lesson/207.html#mid=13708
1 重点关注
1.1 使用链表实现映射Map
详见3.1用链表实现映射Map
2 课程内容
3 Coding
3.1 使用链表实现映射Map
- 需求
使用链表实现的映射统计 傲慢与偏见 书的英文词汇量
- Map接口
package com.company;
public interface Map<K,V> {
/**
* 是否为空
* @author weidoudou
* @date 2022/12/26 17:50
* @return boolean
**/
boolean isEmpty();
/**
* 获取元素个数
* @author weidoudou
* @date 2022/12/26 17:51
* @return int
**/
int getSize();
/**
* 是否包含
* @author weidoudou
* @date 2022/12/26 17:52
* @param key 请添加参数描述
* @return boolean
**/
boolean contains(K key);
/**
* 获取元素
* @author weidoudou
* @date 2022/12/26 17:59
* @param key 请添加参数描述
* @return V
**/
V get(K key);
/**
* 新增元素
* @author weidoudou
* @date 2022/12/26 17:53
* @param key 请添加参数描述
* @param value 请添加参数描述
* @return void
**/
void add(K key,V value);
/**
* 修改元素
* @author weidoudou
* @date 2022/12/26 17:54
* @param key 请添加参数描述
* @param value 请添加参数描述
* @return void
**/
void set(K key,V value);
/**
* 删除元素
* @author weidoudou
* @date 2022/12/26 17:55
* @param key 请添加参数描述
* @return V
**/
V remove(K key);
}
- LinkedListMap
package com.company;
public class LinkedListMap<K,V> implements Map<K,V>{
class Node{
private K key;
private V value;
private Node next;
public Node(){
this(null,null,null);
}
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);
}
@Override
public String toString() {
final StringBuffer sb = new StringBuffer("Node{");
sb.append("key=").append(key);
sb.append(", value=").append(value);
sb.append('}');
return sb.toString();
}
}
private Node dummyHead;
private int size;
public LinkedListMap(){
dummyHead = new Node();
this.size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int getSize() {
return size;
}
//公用方法判断是否包含
private Node containsKey(K key){
Node curNode = dummyHead.next;
while(curNode!=null){
//想想这里为什么不用 =
if(curNode.key.equals(key)){
return curNode;
}
curNode = curNode.next;
}
return null;
}
@Override
public boolean contains(K key) {
return (null == containsKey(key)) ? false : true;
}
@Override
public V get(K key) {
//这里没有考虑到空指针的情况，每次.方法的时候都需要注意
return (null == containsKey(key)) ? null : (containsKey(key).value);
}
@Override
public void add(K key, V value) {
Node node = containsKey(key);
//设计问题，这里，如果传入已有的key,则更新value,否则，新增（也可以传入已有的key后抛异常）
if(null!=node){
node.value = value;
}else{
dummyHead.next = new Node(key,value,dummyHead.next);
size++;
}
}
@Override
public void set(K key, V value) {
Node node = containsKey(key);
if(null==node){
throw new IllegalArgumentException("键值不存在");
}
node.value = value;
}
@Override
public V remove(K key) {
//1 是否包含
//设计问题，如果key不存在，则不做任何操作
if(!contains(key)){
return null;
}
//2 定位
Node preNode = dummyHead;
while(preNode.next!=null){
if(key.equals(preNode.next.key) ){
break;
}
preNode = preNode.next;
}
//3 删除操作
Node delNode = preNode.next;
preNode.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
}
}
- 文件处理类：
package com.company;
import java.io.FileInputStream;
import java.util.ArrayList;
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, ArrayList<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.add(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 ++ )
if( Character.isLetter(s.charAt(i)) )
return i;
return s.length();
}
}
- 测试类：
package com.company;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt",words)){
System.out.println("total words is "+words.size());
}
Map<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("different words is "+map.getSize());
System.out.println("pride size is"+map.get("pride"));
System.out.println("prejudice size is"+map.get("prejudice"));
// write your code here
}
}
- 测试结果：
total words is 125901 different words is 6530 pride size is53 prejudice size is11 Process finished with exit code 0
标签：Node,null,return,value,链表,玩转,key,数据结构,public From： https://www.cnblogs.com/1446358788-qq/p/17013352.html