[数据结构与算法]数据结构之有序符号表

有序符号表

在符号表的基础上，对键的值进行排序，实现有序符号表

添加元素分析

1.首先，使key继承comparable接口

2.通过链表的遍历，比较键的大小，知道该节点的键大于待插入键，则停止

3.关键在于记录大于待插入键的上一个结点，来便于元素的插入

4.当键相同时实现替换

public void put(Key key,Value value){
    Node curr = head.next;
    Node pre = null;
    while (curr != null && key.compareTo(curr.key) > 0) {
        //变换当前节点 和前一个节点
        pre = curr;
        curr = curr.next;
    }
    //如果当前节点，curr的key和要插入的key一样则替换
    if (curr != null && key.compareTo(curr.key) == 0) {
        curr.value = value;
        return;
    }

    //如果当前节点和要插入的节点不一样
    Node newNode = new Node(key, value, null);
    pre.next = newNode;

    N++;

}

测试

public class orderSymbolTest {
    public static void main(String[] args) {
        
        //创建有序符号表对象
        OrderSymbolTable<Integer, String> orderSymbolTable = new OrderSymbolTable<>();
        orderSymbolTable.put(1,"1");
        orderSymbolTable.put(2,"2");
        orderSymbolTable.put(4,"4");
        orderSymbolTable.put(3,"3");
        
        
    }
}