Récemment, la structure des données est un peu intéressante, donc je vais faire un logiciel qui visualise la structure des données petit à petit, également comme une pratique de la POO.
Dans un premier temps, nous avons visualisé le tas. J'espère que vous pourrez le voir si vous le souhaitez. Si j'ai une chance, j'écrirai un article sur le tri en tas. Je vais le mettre à jour à nouveau.
Au fait, j'exécute sur mac donc je ne sais pas comment cela fonctionne sous Windows.
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):
#Le nœud de tas sera alloué à partir de 1
#La hauteur du tas sera allouée à partir de 0
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 fini jusqu'au i-ième nœud+Mettez les coordonnées du premier nœud dans next
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()