In letzter Zeit ist die Datenstruktur ein wenig interessant, daher werde ich eine Software erstellen, die die Datenstruktur nach und nach visualisiert, auch als Übung von OOP.
Als ersten Schritt haben wir den Haufen visualisiert. Ich hoffe du kannst es sehen wenn du willst. Wenn ich eine Chance habe, werde ich einen Artikel über das Sortieren von Heaps schreiben. Ich werde es wieder aktualisieren.
Ich laufe übrigens auf einem Mac, daher weiß ich nicht, wie es unter Windows funktioniert.
from tkinter import *
import time
class EntryAndButton(Frame):
def __init__(self, master, **kwargs):
super().__init__(master)
self.grid(column=0, row=0, sticky=NSEW)
self.entry = Entry(self)
self.entry.grid(column=0, row=1, sticky=NSEW)
self.button = Button(self, **kwargs)
self.button.grid(column=0, row=2)
self.columnconfigure(0, weight=1)
self.rowconfigure(0, weight=1)
self.rowconfigure(1, weight=1)
self.rowconfigure(2, weight=1)
self.rowconfigure(3, weight=1)
def getVal(self):
val = self.entry.get()
self.entry.delete(0, END)
return val
class MakeToolbar(Frame):
def __init__(self, master):
super().__init__(master)
self.master = master
self.grid(row=0, column=0, sticky=NSEW)
def makeToolbar(self, toolbar):
for i, (ui, kwds) in enumerate(toolbar):
name = 'widget'+str(i)
setattr(self, name, ui(self, **kwds))
wid = getattr(self, name)
wid.grid(row=i, column=0, sticky=NSEW)
self.rowconfigure(i, weight=1)
class PicAndOpes(Frame):
def __init__(self, master=None):
super().__init__(master)
self.master = master
self.grid(column=0, row=0, sticky=NSEW)
self.master.columnconfigure(0, weight=1)
self.master.rowconfigure(0, weight=1)
self.canvas = Canvas(self, background='white')
self.canvas.grid(row=0, column=0, sticky=NSEW)
self.master.update()
self.canvas.config(width=self.canvas.winfo_width(), height=self.canvas.winfo_height())
self.operations = MakeToolbar(self)
self.operations.grid(row=0, column=1, sticky=NSEW)
self.operations.columnconfigure(0, weight=1)
self.columnconfigure(0, weight=1)
self.columnconfigure(1, weight=1)
self.rowconfigure(0, weight=1)
class Stack():
def __init__(self, master):
self.frame = PicAndOpes(master)
self.master = master
self.master.title('stack')
self.num = 0
self.size = 16
self.cor_x = self.frame.canvas.winfo_width()/2
self.cor_y = self.frame.canvas.winfo_height() - self.size
self.frame.canvas.bind('<Configure>', self.resize)
self.frame.operations.makeToolbar(((Button, {'text':'add', 'command':self.add}),(Button, {'text':'pop', 'command':self.pop}),))
def add(self):
self.num = self.num + 1
self.frame.canvas.create_rectangle(self.cor_x-self.size, self.cor_y-self.num*self.size/2, self.cor_x+self.size, self.cor_y-(self.num+1)*self.size/2, tag=('stack'+str(self.num)))
def pop(self):
self.frame.canvas.delete('stack'+str(self.num))
self.num = self.num-1
def resize(self, event):
self.frame.canvas.move('all', event.width/2-self.cor_x, event.height-self.cor_y - self.size)
self.cor_x, self.cor_y = event.width/2, event.height - self.size
class Heap():
def __init__(self, master=None):
#Der Heap-Knoten wird ab 1 zugewiesen
#Die Höhe des Heaps wird von 0 zugewiesen
self.frame = PicAndOpes(master)
self.master = master
self.master.title('heap')
self.nodeNum = 0
self.rad = 10
self.gap = 15
self.edge_length = 20
self.heapHeight = 0
self.heapCurrentHeight = 0
self.top_cor_x = self.frame.canvas.winfo_width() / 2
self.top_cor_y = (self.frame.canvas.winfo_height() - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x = self.frame.canvas.winfo_width()/2
self.next_cor_y = self.frame.canvas.winfo_height()/2
self.frame.canvas.bind('<Configure>', self.resize)
self.frame.operations.makeToolbar(((EntryAndButton, {'text':'append', 'command':self.append}),
(Button, {'text':'getMin', 'command':self.getMin}),
(Button, {'text':'heapify', 'command':self.heapify}))
)
def append(self):
val = self.frame.operations.widget0.getVal()
if val == "":
print('write something')
else:
self.nodeNum = self.nodeNum + 1
if 2**(self.heapHeight + 1) == (self.nodeNum):
self.heapHeight = self.heapHeight + 1
self.heapCurrentHeight = 0
self.redraw(val)
else:
self.heapCurrentHeight = self.heapHeight
self.frame.canvas.create_oval(self.next_cor_x-self.rad,
self.next_cor_y-self.rad,
self.next_cor_x+self.rad,
self.next_cor_y+self.rad,
fill='white',
tag=('shape'+str(self.nodeNum)))
self.frame.canvas.create_text(self.next_cor_x,
self.next_cor_y,
text=val, tag=('text'+str(self.nodeNum)))
self.set_next_cor(self.nodeNum)
def redraw(self, val):
self.top_cor_x = self.frame.canvas.winfo_width() / 2
self.top_cor_y = (self.frame.canvas.winfo_height() - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x = self.top_cor_x
self.next_cor_y = self.top_cor_y
for i in range(1, self.nodeNum):
x0, y0, x1, y1 = self.frame.canvas.coords('shape'+str(i))
x, y = (x0+x1)/2, (y0+y1)/2
self.frame.canvas.move('shape'+str(i), self.next_cor_x-x, self.next_cor_y-y)
self.frame.canvas.move('text'+str(i), self.next_cor_x-x, self.next_cor_y-y)
self.set_next_cor(i)
self.frame.canvas.create_oval(self.next_cor_x-self.rad, self.next_cor_y-self.rad, self.next_cor_x+self.rad, self.next_cor_y+self.rad, fill='white',tag=('shape'+str(self.nodeNum)))
self.frame.canvas.create_text(self.next_cor_x, self.next_cor_y, text=val, tag=('text'+str(self.nodeNum)))
self.set_next_cor(self.nodeNum)
#set_next_i as cor ist bis zum i-ten Knoten fertig+Geben Sie als nächstes die Koordinaten des ersten Knotens ein
def set_next_cor(self, i):
if (2**(self.heapCurrentHeight + 1) - 1 ) == i:
self.heapCurrentHeight = self.heapCurrentHeight + 1
sum = 0
for j in range(self.heapCurrentHeight):
sum = sum + 2**(self.heapHeight - j - 1)
self.next_cor_x = self.top_cor_x - self.gap * sum
self.next_cor_y = self.next_cor_y + 2 * self.gap
else:
self.next_cor_x = self.next_cor_x + 2 * self.gap * 2**(self.heapHeight - self.heapCurrentHeight)
def resize(self, event):
diffx = event.width / 2 - self.top_cor_x
diffy = (event.height - 2 * self.rad * self.heapHeight) / 2 - self.top_cor_y
self.frame.canvas.move('all', diffx, diffy)
self.top_cor_x, self.top_cor_y = event.width/2, (event.height - 2 * self.rad * self.heapHeight) / 2
self.next_cor_x, self.next_cor_y = self.next_cor_x + diffx, self.next_cor_y + diffy
def getMin(self):
if self.nodeNum == 0:
pass
elif self.nodeNum == 1:
pass
else:
parentid = self.frame.canvas.find_withtag('text' + str(1))
lastid = self.frame.canvas.find_withtag('text' + str(self.nodeNum))
last = self.frame.canvas.itemcget(lastid, 'text')
self.frame.canvas.itemconfig(parentid, text='')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(parentid, text=last)
self.frame.canvas.delete('shape'+str(self.nodeNum))
self.frame.canvas.delete('text'+str(self.nodeNum))
time.sleep(1)
self.master.update()
self.nodeNum = self.nodeNum - 1
self.subheapify(1)
def heapify(self):
ran = 2**self.heapHeight - 1
for i in reversed(range(1, ran + 1)):
self.subheapify(i)
def subheapify(self, i):
flag = True
max = self.nodeNum
while flag:
n = i
if max < 2*i:
flag = False
elif 2*i <= max < (2*i + 1):
parentid = self.frame.canvas.find_withtag('text' + str(n))[0]
leftchildid = self.frame.canvas.find_withtag('text' + str(2*n))[0]
parent = self.frame.canvas.itemcget(parentid, 'text')
leftchild = self.frame.canvas.itemcget(leftchildid, 'text')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='red')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='white')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='white')
time.sleep(1)
self.master.update()
if leftchild < parent:
self.frame.canvas.itemconfig(parentid, text=leftchild)
self.frame.canvas.itemconfig(leftchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i
elif parent <= leftchild:
flag = False
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='black')
time.sleep(1)
self.master.update()
elif (2*i+1) <= max:
parentid = self.frame.canvas.find_withtag('text' + str(n))[0]
leftchildid = self.frame.canvas.find_withtag('text' + str(2*n))[0]
rightchildid = self.frame.canvas.find_withtag('text' + str(2*n+1))[0]
parent = self.frame.canvas.itemcget(parentid, 'text')
leftchild = self.frame.canvas.itemcget(leftchildid, 'text')
rightchild = self.frame.canvas.itemcget(rightchildid, 'text')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='red')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='white')
time.sleep(1)
self.master.update()
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n+1))[0], fill='blue')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n+1))[0], fill='white')
time.sleep(1)
self.master.update()
if leftchild <= rightchild:
if leftchild < parent:
self.frame.canvas.itemconfig(parentid, text=leftchild)
self.frame.canvas.itemconfig(leftchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i
elif parent <= leftchild:
flag = False
elif rightchild < leftchild:
if rightchild < parent:
self.frame.canvas.itemconfig(parentid, text=rightchild)
self.frame.canvas.itemconfig(rightchildid, text=parent)
time.sleep(1)
self.master.update()
i = 2 * i + 1
elif parent <= rightchild:
flag = False
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('shape' + str(2*n+1))[0], fill='white')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n))[0], fill='black')
self.frame.canvas.itemconfig(self.frame.canvas.find_withtag('text' + str(2*n+1))[0], fill='black')
time.sleep(1)
self.master.update()
def main():
root = Tk()
app = Heap(root)
root.mainloop()
if __name__ == '__main__':
main()