50 lines
2.4 KiB
Python
50 lines
2.4 KiB
Python
import sys, os
|
||
_root = os.path.abspath(os.path.join(os.path.dirname(__file__), '..', '..'))
|
||
_l07 = os.path.join(_root, 'vorlesung', 'L07_hashtable')
|
||
_p06 = os.path.dirname(__file__)
|
||
if _l07 not in sys.path: sys.path.insert(0, _l07)
|
||
if _root not in sys.path: sys.path.insert(0, _root)
|
||
if _p06 not in sys.path: sys.path.insert(0, _p06)
|
||
|
||
from utils.algo_context import AlgoContext
|
||
from utils.algo_array import Array
|
||
from utils.algo_int import Int
|
||
from analyze_hashtable import h
|
||
from aufgabe1_chaining import HashTableChaining
|
||
|
||
ctx = AlgoContext()
|
||
values = Array.from_file('data/seq0.txt', ctx)
|
||
|
||
ht = HashTableChaining(20, h, ctx)
|
||
for cell in values:
|
||
ht.insert(cell)
|
||
|
||
# ── a) Belegungsfaktor ───────────────────────────────────────────────────────
|
||
print("=== a) Nach Einfügen von seq0.txt (14 Werte, m=20) ===")
|
||
print(ht)
|
||
print(f"\nBelegungsfaktor α = {ht._n}/{int(ht.m)} = {ht.alpha():.2f}")
|
||
|
||
# ── b) Löschen von 52 ────────────────────────────────────────────────────────
|
||
print("\n=== b) Nach delete(52) ===")
|
||
ht.delete(Int(52, ctx))
|
||
print(ht)
|
||
print(f"Belegungsfaktor α = {ht._n}/{int(ht.m)} = {ht.alpha():.2f}")
|
||
|
||
# ── c) Erneut seq0.txt einfügen ──────────────────────────────────────────────
|
||
print("\n=== c) Erneut seq0.txt einfügen ===")
|
||
for cell in values:
|
||
ht.insert(cell)
|
||
print(f"Belegungsfaktor α = {ht._n}/{int(ht.m)} = {ht.alpha():.2f} (kann > 1 sein!)")
|
||
print("insert kann bei Verkettung nie False zurückgeben –")
|
||
print("die Kette wächst unbegrenzt, es gibt kein 'Tabelle voll'.")
|
||
|
||
# ── d) Erklärung kein DELETED_MARK ───────────────────────────────────────────
|
||
print("\n=== d) Warum kein DELETED_MARK? ===")
|
||
print(
|
||
"Bei offener Adressierung wird DELETED_MARK benötigt, damit die\n"
|
||
"Sondierungssequenz bei search nicht vorzeitig abbricht. Bei Verkettung\n"
|
||
"wird die vollständige Liste eines Slots linear durchsucht – ein gelöschtes\n"
|
||
"Element wird einfach aus der Liste entfernt. Es gibt keine Sequenz, die\n"
|
||
"'unterbrochen' werden könnte, daher ist kein Tombstone notwendig."
|
||
)
|