欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

顺序查找(基于无序链表)

程序员文章站 2022-05-11 09:12:21
...

1、基本思想

采用链表数据结构,每个节点存储一个键值对
get():顺序遍历链表,用equals()方法比较键,如果匹配成功就返回相应的值,否则返回null
put():顺序遍历链表,用equals()方法比较键,如果匹配成功就用第二个参数更新该键相关联的值,否则就创建一个新的节点并将该键值对插入到链表的开头。
顺序查找(基于无序链表)
顺序查找(基于无序链表)

2、算法实现

/** 算法3.1 顺序查找(基于无序链表)
 * 符号表的实现使用了一个私有内部Node类来在链表中保存键和值。
*/
public class SequentialSearchST<Key,Value>
{
    private Node first;           //链表首节点
    //private int N;              //结点数量
    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; }
    }

    // get()的实现会顺序地搜索链表查找给定的键(找到则返回相关联的值)
    public Value get(Key key)
    {              
        for(Node x=first; x!=null; x=x.next)
            if(key.equals(x.key))
                return x.val;                /*命中*/
        return null;                         /*未命中*/
    }

    //put()的实现也会顺序地搜索链表查找给定的键,如果找到则更新相关联的值,否则它会用给定的键值对创建一个新的结点并将其插到链表的开头。
    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);       /*未命中,新建结点*/
    }

    //表中的键值对数量
    public int size()                         
    {
        int N=0;
        for(Node x=first; x!=null; x=x.next)
            N++;
        return N;
    }

    //从表中删去键key及其对应的值
    public void delete (Key key)              
    {
        for(Node x=first; x!=null; x=x.next)
        {
            if(key.equals(x.next.key))
                x.next = x.next.next;
        }
    }

    //键key在表中是否有对应的值
    public boolean contains(Key key)            
    {
        for(Node x=first; x!=null; x=x.next)          
            if(key.equals(x.key))               
                return true;
        return false;
    }

    //表中所有键的集合
    public Iterable<Key> Keys()           
    {
        Queue<Key> q=new Queue<Key>();
        for(Node x=first; x!=null; x=x.next)
            q.enqueue(x.key);
        return q;
    }
}

附:可参考例子-记频器

3、性能分析

在含有 N 对键值的基于(无序)链表的符号表中,
未命中的查找和插入操作都需要 N 次比较; 命中的查找在最坏情况下需要 N 次比较
特别地,向一个空表中插入 N 个不同的键需要 ~N2/2 次比较。∑Ni = ∑(i) = 1+2+…+N = N(N+1)/2 ~N2/2

这些分析完全证明了基于链表的实现以及顺序查找是非常低效的,无法满足处理庞大输入问题的需求。


附:数据结构中含节点数量N参考


相关标签: 顺序查找