Bonsoir. Merci pour votre soutien continu. m (_ _) m
Suite de la session précédente. Je l'ai écrit en douceur Supplément sur dump.
test.py
def dump(self):
#je suis table[*]Parce que c'est un pointeur vers une table[i]
for i in range(self.capacity):
# table[i]La clé stockée dans,value,Appeler np
p = self.table[i]
# end=""Est une description qui se connecte à l'impression suivante
print(i,end="")
while p is not None:
#Afficher la description suivante immédiatement après i ci-dessus
# p.key , p.Continuer à afficher la valeur
print(f"=>{p.key}({p.value})",end="")
#Remplacez np par p et la clé suivante,value,Connectez-vous à np
p = p.np
#nouvelle ligne
print()
Si vous avez une image qui stocke des données avec une chaîne de perles que j'ai écrite la dernière fois Je pense que c'est facile à imaginer.
Jusqu'à présent, en utilisant la chaîne Hash, J'ai stocké les données. Maintenant que nous l'avons stocké, remettons en question l'approche de recherche de données. Fondamentalement, il recherche des données en les associant à la clé du nœud déjà stockée.
test.py
def search(self,key):
#Trouvez le pointeur de la table à partir de la clé.
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
#Lorsque la clé stockée et la clé d'entrée correspondent. ..
if p.key == key:
#Afficher les données avec impression
return print(f"searched value is {p.value}")
p = p.np
#S'il n'y a rien même si vous recherchez les données correspondantes jusqu'à la fin avec while, échouez
print("faile to search")
Si vous le recherchez en l'ajoutant au tableau préparé, Vous pouvez également supprimer les éléments inutiles, non? Défions. Identique à la recherche, recherchez essentiellement le nœud correspondant par clé. Après cela, changez le point de connexion de Nœud à Nœud pour terminer la suppression. Oui, nous éditerons le np à l'intérieur du nœud.
test.py
def remove(self,key):
Vhash = key % self.capacity
p = self.table[Vhash]
pp = None #Valeur initiale Aucune
while p is not None:
if p.key == key
#Description lors de la suppression des premières données
if pp is None:
self.table[Vhash] = self.table[Vhash].np
#Modifier les points de connexion np autres que le premier élément
else:
#pp sera décrit plus tard, mais l'image est Node avant que la clé ne corresponde.
#p est le nœud auquel correspond la clé.
# pp.En substituant np du Node dont la clé correspond à np
#Supprimer le nœud correspondant de clé de la connexion de données
pp.np = p.np
#Si p au début.key !=Si c'est la clé, remplacez p par pp et tampon
pp = p
#Réglez la valeur de p sur p pour passer au nœud de pointe avec while.Mis à jour avec np
p = p.np
Je n'ai pas expliqué ce qu'est Hash ?? Je crois comprendre qu'en fournissant une clé, vous pouvez obtenir un pointeur vers le tableau correspondant en une seule fois. Vous pouvez le trouver, puis vous pouvez trouver la valeur correspondante par recherche linéaire. C'était une méthode de recherche intéressante. Bien entendu, pour atteindre ce qui précède, il doit être stocké selon cette règle.
Jusqu'à présent, les articles ont été organisés à partir d'un arrangement donné ou du même arrangement. L'approche d'exploration était basique.
Cette fois, ce n'est pas le cas, examinez la méthode de stockage elle-même C'était un algorithme intéressant qui facilitait l'exploration. (`) Non
Je vais mettre l'image entière. Il existe un plan optimal Si vous rencontrez des problèmes, faites-le moi savoir. M (_ _) m.
Chained_hash.py
class Node:
def __init__(self,key,value,np):
self.key = key
self.value = value
self.np = np
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity
self.table = [None]*self.capacity
def add(self,key,value):
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
if p.key == key:
return False
p = p.np
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
def dump(self):
for i in range(self.capacity):
p = self.table[i]
print(i,end="")
while p is not None:
print(f"=>{p.key}({p.value})",end="")
p = p.np
print()
def search(self,key):
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
if p.key == key:
return print(f"searched value is {p.value}")
p = p.np
print("faile to search")
def remove(self,key):
Vhash = key % self.capacity
p = self.table[Vhash]
pp = None
while p is not None:
if p.key == key:
if pp is None:
self.table[Vhash] = self.table[Vhash].np
else:
pp.np = p.np
pp = p
p = p.np
test = ChainedHash(7)
while True:
num = int(input("select 1.add, 2.dump, 3.search, 4.remove : "))
if num == 1:
key = int(input("key: "))
val = int(input("val: "))
test.add(key,val)
elif num == 2:
test.dump()
elif num == 3:
key = int(input("key: "))
test.search(key)
elif num == 4:
key = int(input("key: "))
test.remove(key)
else:
break
Recommended Posts