1.词典 Dictionary
定义
词典，也称映射（map），表（table）或关联胡祖（associatearray），词典中每个元素都由两部分组成：一个关键字，通常称为查找键（search key）；一个与该键值相关联的值。
词典根据查找键来组织与区分它的元素，因此只要指定元素的查找键，就能从词典中检索或删除一个元素。词典中每个元素都具有一个查找键，虽然也可以将具有查找键的元素放入线性表，但线性表的数据是按位置而不是按查找键来组织的。
Java接口
|
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
|
public
interface
DictionaryInterface<K, V> {
/**
* 将一个新元素插入词典。如果给定的查找键一再词典中，则替换相应的值
* @param key 新元素的查找键对象
* @param value 与查找键相关联的对象
* @return 如果新元素被插入到词典中则返回null，如果与key相关联的值被替换，则返回原来的值 */
public
V add(K key, V value);
/**
* 从词典中删除一个指定的元素
* @param key 欲删除的元素的查找键对象
* @return 与查找键相关联的值，如果不存在这样的对象则返回null */
public
V remove(K key);
/**
* 检索与给定的查找键相关联的对值
* @param key 欲检索的元素的查找键对象
* @return 与查找键相关联的值，如果不存在这样的对象则返回null */
public
V getValue(K key);
/**
* 确定一个指定的元素在不在词典中
* @param key 欲检索的元素的查找键对象
* @return 如果key与词典中的一个元素相关联则返回true */
public
boolean
contains(K key);
/**
* 创建一个迭代器遍历词典中所有的查找键
* @return 返回一个迭代器，提供对词典中查找键的顺序访问 */
public
Iterator<K> getKeyIterator();
/**
* 创建一个迭代器遍历词典中所有的值
* @return 返回一个迭代器，提供对词典中的值顺序访问 */
public
Iterator<V> getValueIterator();
/**
* 确定词典是否为空
* @return 如果词典为空则返回true */
public
boolean
isEmpty();
/**
* 确定词典是否为满
* @return 如果词典为满则返回true */
public
boolean
isFull();
/**
* 缺德词典的大小
* @return 返回词典中当前的元素(键-值二元组)数目 */
public
int
getSize();
/**
* 删除词典中所有元素 */
public
void
clear();
}
|
Java类库：Map接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public
interface
Map<K, V> {
public
V put(K key, V value);
public
V remove(Object key);
public
V get(Object key);
public
boolean
containsKey(Object key);
public
boolean
containsValue(Object value);
public
Set keySet();
public
Collection<V> values();
public
boolean
isEmpty();
public
int
size();
public
void
clear();
}
|
2.迭代器 Iterator
迭代器总是指向链表中的一些链接点。它同链表相关联，但并不等同于链表或链接点。
迭代器类
迭代器类包含对数据结构中数据项的引用，并用来遍历这些结构的对象。
|
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
|
public
class
Link {
public
long
dData;
public
Link next;
}
public
class
LinkList {
private
Link first;
public
ListIterator getIterator() {
return
new
ListIterator(
this
);
}
}
public
class
ListIterator {
private
Link current;
// reference to current link
private
Link previous;
// reference to previous link
private
LinkList ourList;
// reference to "parent" list
public
ListIterator(LinkList list) {
ourList = list;
reset();
}
// 把迭代器复位并设在表头
public
void
reset() {
current = ourList.getFirst();
previous =
null
;
}
public
boolean
atEnd() {
return
(current.next ==
null
);
}
public
void
nextLink() {
previous = current;
current = current.next;
}
public
Link getCurrent() {
return
current;
}
// 在当前链接点前插入新连接点
public
void
insertAfter() {
Link newLink =
new
Link();
if
(ourList.isEmpty()) {
ourList.setFirst(newLink);
current = newLink;
}
else
{
newLink.next = current.next;
current.next = newLink;
nextLink();
}
}
// 在当前链接点后插入新连接点
public
void
insertBefor() {
Link newLink =
new
Link();
if
(previous ==
null
) {
newLink.next = ourList.getFirst();
ourList.setFirst(newLink);
reset();
}
else
{
newLink.next = previous.next;
previous.next = newLink;
current = newLink;
}
}
// 删除当前链接点
public
long
deleteCurrent() {
long
value = current.dData;
if
(previous ==
null
) {
ourList.setFirst(current.next);
reset();
}
else
{
previous.next = current.next;
if
(atEnd())
reset();
else
current = current.next;
}
return
value;
}
}
|
3.基于数组实现词典
词典中的每个元素必须是Entry类的一个实例。
基于数组的无序词典
|
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
76
77
78
79
80
|
public
class
ArrayDictionary<K, V>
implements
DictionaryInterface<K, V>,
Serializable {
private
Entry<K, V>[] dictionary;
// 无需元素的数组
private
int
currentSize;
// 元素的数量
private
final
static
int
DEFAULT_CAPACITY =
25
;
public
ArrayDictionary() {
this
(DEFAULT_CAPACITY);
}
public
ArrayDictionary(
int
initialCapacity) {
// 编译器发现，含有Entry类型的元素的数组赋给了含有Entry<K,V>类型的元素的数组。因此，它警告有一个未检验的转换。
// 试图把新数值转换为Entry<K,V>也将导致一个类似的警告。
// 这两种情况都不用编译器的警告。
dictionary =
new
Entry[initialCapacity];
currentSize =
0
;
}
private
class
Entry<S, T>
implements
Serializable {
private
S key;
private
T value;
private
Entry(S searchKey, T dataValue) {
key = searchKey;
value = dataValue;
}
// 内部Entry不具有用于设置或修改查找键的方法setKey
public
S getKey() {
return
key;
}
public
T getValue() {
return
value;
}
public
void
setValue(T value) {
this
.value = value;
}
}
public
V add(K key, V value) {
// 讲一个新的键-值元素插入词典并返回null。如果key已在词典中，则返回相应的值，并且用value替换它
V result =
null
;
// 在数值中查找含有key的元素
int
keyIndex = locateIndex(key);
// 如果在数组中找到含有key的元素
if
(keyIndex < currentSize) {
// result = 当前与key相关联的值
result = dictionary[keyIndex].getValue();
// 以value替换与key相关联的值
dictionary[keyIndex].setValue(value);
}
else
{
// 数组已满
if
(isArrayFull())
// 将其长度加倍
doubleArray();
// 为由当前的查找确定的索引处的新元素在数组中腾出空间，江汉油田key与value的新元素插入数组中空出的位置
dictionary[currentSize] =
new
Entry<K, V>(key, value);
// 词典长度加1
currentSize++;
}
return
result;
}
// 返回含有查找键的元素的索引，或者如果元素不存在，返回currentSize
private
int
locateIndex(K key) {
int
index =
0
;
while
((index < currentSize) && !key.equals(dictionary[index].getKey()))
index++;
return
index;
}
public
V remove(K key) {
// 给定查找键，从词典中删除一个元素，并返回该元素的值。如果不存在这样一个元素，则返回null
V result =
null
;
// 在数组中查找含有给定查找键的元素
int
keyIndex = locateIndex(key);
// 在词典中找到了含有给定查找键的元素
if
(keyIndex < currentSize) {
// result = 当前与key相关联的值
result = dictionary[keyIndex].getValue();
// 用数组的最后一个元素替换该元素
dictionary[keyIndex] = dictionary[currentSize -
1
];
// 词典长度减1
currentSize --;
}
return
result;
}
}
|
基于数组的有序词典
|
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
|
public
class
SortedArrayDictionary<K
extends
Comparable<?
super
K>, V>
implements
DictionaryInterface<K, V>, Serializable {
private
Entry<K, V>[] dictionary;
// 无需元素的数组
private
int
currentSize;
// 元素的数量
private
final
static
int
DEFAULT_CAPACITY =
25
;
public
SortedArrayDictionary() {
this
(DEFAULT_CAPACITY);
}
public
SortedArrayDictionary(
int
initialCapacity) {
// 编译器发现，含有Entry类型的元素的数组赋给了含有Entry<K,V>类型的元素的数组。因此，它警告有一个未检验的转换。
// 试图把新数值转换为Entry<K,V>也将导致一个类似的警告。
// 这两种情况都不用编译器的警告。
dictionary =
new
Entry[initialCapacity];
currentSize =
0
;
}
public
V add(K key, V value) {
// 讲一个新的键-值元素插入词典并返回null。如果key已在词典中，则返回相应的值，并且用value替换它
V result =
null
;
// 查找数组，直到发现含有key的元素，或者找到这样的元素应处的位置
int
keyIndex = locateIndex(key);
// key已在词典中
if
((keyIndex < currentSize) && key.equals(dictionary[keyIndex].getKey())) {
// result = 当前与key相关联的值
result = dictionary[keyIndex].getValue();
// 以value替换与key相关联的值
dictionary[keyIndex].setValue(value);
}
else
{
// 插入新元素
// 数组已满
if
(isArrayFull())
// 将其长度加倍
doubleArray();
// 移动数组元素，在指定索引处为新元素腾出空间
makeRoom(keyIndex);
// 为由前面的查找确定的索引处的新元素在数组中腾出位置，将含有key与value的新元素插入到数组中空出的位置
dictionary[currentSize] =
new
Entry<K, V>(key, value);
// 词典长度加1
currentSize++;
}
return
result;
}
// 返回含有查找键的元素的索引，或者如果元素不存在，返回currentSize
private
int
locateIndex(K key) {
// 进行查找，知道找到一个含有key的元素，或传递它应在的位置
int
index =
0
;
while
((index < currentSize) && key.compareTo(dictionary[index].getKey())>
0
)
index++;
return
index;
}
}
|
4.基于链表实现词典
使用链表的另一种选择时不使用Entry类。简单的方式是修改节点的定义，使之包含元素的两个部分。
基于链表的无序词典
由于无序词典中的元素没有特定的顺序，所以可用最有效的方法来插入新元素。如果元素是用链表来存放的，则最快的插入方法就是在链表的始端进行插入，插入的效率是O(1)。
基于链表的有序词典
|
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
|
public
class
SortedLinkedDictionary<K
extends
Comparable<?
super
K>, V>
implements
DictionaryInterface<K, V>, Serializable {
private
Node firstNode;
// 指向链表的第一个结点的引用
private
int
currentSize;
// 元素的数量
public
SortedLinkedDictionary() {
firstNode =
null
;
currentSize =
0
;
}
private
class
Node<K
extends
Comparable<?
super
K>, V>
implements
Serializable {
private
K key;
private
V value;
private
Node next;
}
public
V add(K key, V value) {
// 将一个新的键-值元素插入词典并返回null。如果key已在词典中，则返回相应的值，并且用value替换它
V result =
null
;
// 查找链表，直到找到一个含有key的结点，或者传递它应在的位置
Node currentNode = firstNode;
Node nodeBefore =
null
;
while
((currentNode !=
null
) && key.compareTo(currentNode.getKey()) >
0
) {
nodeBefore = currentNode;
currentNode = currentNode.getNext();
}
// 包含key的结点在链表中
if
((currentNode !=
null
) && key.equals(currentNode.getKey())) {
// result = 当前与key相关联的值
result = currentNode.getValue();
// 用value替换与key相关联的值
currentNode.setValue(value);
}
else
{
// 链表为空，或者新元素应位于链表始端
// 为包含key和value的新结点分配存储空间，为该新结点插入到链表始端
Node newNode =
new
Node(key, value);
// 词典长度加1
currentSize++;
if
(nodeBefore ==
null
) {
// 在开头插入
newNode.setNext(firstNode);
firstNode = newNode;
}
else
{
newNode.setNext(currentNode);
nodeBefore.setNext(newNode);
}
}
return
result;
}
}
|
本文转自 LinkedKeeper 51CTO博客，原文链接：http://blog.51cto.com/sauron/1227432，如需转载请自行联系原作者
