我是靠谱客的博主 开放鸵鸟,这篇文章主要介绍顺序查找(基于无序链表),现在分享给大家,希望可以做个参考。

      • 1、基本思想
      • 2、算法实现
      • 3、性能分析

1、基本思想

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

2、算法实现

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/** 算法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 N 次比较
特别地,向一个空表中插入 N 个不同的键需要 ~ N2/2 N 2 / 2 次比较。∑Ni = ∑(i) = 1+2+…+N = N(N+1)/2 ~ N2/2 N 2 / 2

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


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


最后

以上就是开放鸵鸟最近收集整理的关于顺序查找(基于无序链表)的全部内容,更多相关顺序查找(基于无序链表)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(74)

评论列表共有 0 条评论

立即
投稿
返回
顶部