1.基本思想符号表中使用的数据结构的一个简单选择是链表,每个结点存储一个键值对,如算法中的代码所示。get()的实现即为遍历链表,用equals()方法比较需被查找的键和每个结点中的键。如果匹配成功我们就返回相应的值,否则我们返回null。put()的实现也是遍历链表,用equa ...
1.基本思想
符号表中使用的数据结构的一个简单选择是链表,每个结点存储一个键值对,如算法中的代码所示。get()的实现即为遍历链表,用equals()方法比较需被查找的键和每个结点中的键。如果匹配成功我们就返回相应的值,否则我们返回null。put()的实现也是遍历链表,用equals()方法比较需被查找的键和每个结点中的键。如果匹配成功我们就用第二个参数指定的值更新和该键相关联的值,否则我们就用给定的键值对创建一个新的结点并将其插入到链表的开头。这种方法也被称为顺序查找:在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的键。
2.具体算法
/** * 算法3.1 顺序查找(基于无序链表) * Created by huazhou on 2015/11/11. */public class SequentialSearchST<Key, Value> { private Node first; //链表首结点 //链表结点的定义 private class Node{ Key key; Value val; Node next; public Node(Key key, Value val, Node next){ this.key = key; this.val = val; this.next = next; } } //查找给定的键,返回相关联的值 public Value get(Key key){ for(Node x = first; x != null; x = x.next){ if(key.equals(x.key)){ return x.val; //命中 } } return null; //未命中 } //查找给定的键,找到则更新其值,否则在表中新建结点 public void put(Key key, Value val){ for (Node x = first; x != null; x = x.next){ if(key.equals(x.key)){ //命中,更新 x.val = val; return; } } first = new Node(key, val, first); //未命中,新建结点 }}
原标题:算法—7.无序链表中的顺序查找
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。