顺序查找（基于无序链表）

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 对键值的基于（无序）链表的符号表中，
未命中的查找和插入操作都需要 NN 次比较； 命中的查找在最坏情况下需要 N N 次比较
特别地，向一个空表中插入 NN 个不同的键需要 ~ N2/2 N 2 / 2 次比较。∑Ni = ∑(i) = 1+2+…+N = N(N+1)/2 ~ N2/2 N 2 / 2

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


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

最后

以上就是开放鸵鸟为你收集整理的顺序查找（基于无序链表）的全部内容，希望文章能够帮你解决顺序查找（基于无序链表）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。