Création d'un logiciel qui visualise la structure des données ~ Heap ~

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()

Recommended Posts

Création d'un logiciel qui visualise la structure des données ~ Heap ~
Créer des données d'entraînement
Création d'un logiciel qui reflète l'écran Android sur un PC 2 Édition tactile en temps réel