class LinkList():
class Node():
def __init__(self
,item
=None):
self
.item
=item
self
.next=None
class LinkListIterator():
def __init__(self
,node
):
self
.node
=node
def next(self
):
if self
.node
:
cur_node
=self
.node
self
.node
=cur_node
.next
return cur_node
.item
else:
raise StopIteration
def __iter__(self
):
return self
def __init__(self
):
self
.head
=None
def append(self
,item
):
node
=self
.Node
(item
)
if not self
.head
:
self
.head
=node
else:
node
.next=self
.head
self
.head
=node
def delete(self
,obj
):
CurNode
=self
.head
while CurNode
:
if CurNode
.next.item
==obj
:
CurNode
.next=CurNode
.next.next
return True
CurNode
=CurNode
.next
else:
raise IndexError
('linklist have no num %d'%obj
)
def find(self
,obj
):
for n
in self
:
if n
==obj
:
return True
else:
return False
def __iter__(self
):
return self
.LinkListIterator
(self
.head
)
def __repr__(self
):
return '<<'+','.join
(map(str,self
))+'>>'
class HashTable():
def __init__(self
,size
):
self
.size
=size
self
.hashtable
=[LinkList
() for i
in range(size
)]
def append(self
,item
):
self
.hashtable
[self
.hash_func
(item
)].append
(item
)
def hash_func(self
,item
):
return item
%self
.size
def __repr__(self
):
return ','.join
(map(str,self
.hashtable
))
def delete(self
,obj
):
k
=self
.hash_func
(obj
)
if self
.hashtable
[k
].find
(obj
):
self
.hashtable
[k
].delete
(obj
)
return True
else:
raise IndexError
('hashtable have no num %d'%obj
)
def find(self
,obj
):
k
=self
.hash_func
(obj
)
for n
in self
.hashtable
[k
]:
if n
==obj
:
return True
else:
return False
ll
=LinkList
()
ll
.append
(1)
ll
.append
(2)
ll
.append
(3)
ll
.append
(4)
ll
.append
(5)
print ll
print ll
.find
(3)
ll
.delete
(3)
print ll
h
=HashTable
(10)
for i
in range(100):
h
.append
(i
)
print h
print h
.find
(44)
h
.delete
(44)
print h
print h
.find
(44)
h
.delete
(111)
头插链表，长度为size的哈希表。（这个代码对齐方式我真的搞不定。。） 输出结果： <<5,4,3,2,1>> True <<5,4,2,1>> <<90,80,70,60,50,40,30,20,10,0>>,<<91,81,71,61,51,41,31,21,11,1>>,<<92,82,72,62,52,42,32,22,12,2>>,<<93,83,73,63,53,43,33,23,13,3>>,<<94,84,74,64,54,44,34,24,14,4>>,<<95,85,75,65,55,45,35,25,15,5>>,<<96,86,76,66,56,46,36,26,16,6>>,<<97,87,77,67,57,47,37,27,17,7>>,<<98,88,78,68,58,48,38,28,18,8>>,<<99,89,79,69,59,49,39,29,19,9>> True <<90,80,70,60,50,40,30,20,10,0>>,<<91,81,71,61,51,41,31,21,11,1>>,<<92,82,72,62,52,42,32,22,12,2>>,<<93,83,73,63,53,43,33,23,13,3>>,<<94,84,74,64,54,34,24,14,4>>,<<95,85,75,65,55,45,35,25,15,5>>,<<96,86,76,66,56,46,36,26,16,6>>,<<97,87,77,67,57,47,37,27,17,7>>,<<98,88,78,68,58,48,38,28,18,8>>,<<99,89,79,69,59,49,39,29,19,9>> False Traceback (most recent call last): File “1.py”, line 418, in h.delete(111) File “1.py”, line 390, in delete raise IndexError(‘hashtable have no num %d’%obj) IndexError: hashtable have no num 111
