วิชาโครงสร้างข้อมูลและอัลกอริทึม
Data Structures and Algorithms with Python Programming by Aj.NesT the Series
>>> Click Lecture for Full Course Data Structures and Algorithms <<<
เอกสารประกอบการเรียน Data Structures and Algorithms with Python in Google Colab
EP.1 Aj. NesT Recursion in Python #1-6 https://colab.research.google.com/drive/1eoq2Aif1Q4OLi6eewTbdDMPI5l2Y81y7
EP.2 Aj. NesT Stacks in Python #1-5
https://colab.research.google.com/drive/1ufsEvPZovKdUcW-_-4-VkbfBjAFRGzJv
EP.3 Aj. NesT Queues in Python #1-4
https://colab.research.google.com/drive/1bTn_U4vx6wPlUKKz5Ygde2FijklbKNBu
EP.4 Aj. NesT Deque in Python
https://colab.research.google.com/drive/1snWf0P7IWzBKti3z5rLozOiq47wPDn3-
EP.5-EP.6 Aj. NesT Linked Lists in Python #1-4
https://colab.research.google.com/drive/1jnQZQ7Byk1TzBpzMawk40MGoJHabLXs2
EP.7 Aj. NesT Trees in Python #1-4
https://colab.research.google.com/drive/1WS2xQyjOjL-62iEYKdIblCMAlgVnjU6s
EP.8 Aj. NesT Graph in Python #1-5
https://colab.research.google.com/drive/1CVTANIe8dWsF0WQmF_dNmLPubbowUg0U
Lab 1 Recursion in Python
“Of all ideas I have introduced to children, recursion stands out as the one idea that is particularly able to evoke an excited response.”
“จากความคิดทั้งหมดที่ฉันจะแนะนำให้เด็ก ๆ รู้จัก การเรียกซ้ำมีความโดดเด่นคือเป็นแนวคิดเดียวที่สามารถทำให้เกิดการตอบสนองที่น่าตื่นเต้น”
— Seymour Papert, Mindstorms
Lab 1.1 The Factorial Function
#Recursion
#Lab1.1 The Factorial Function
def factorial(n):
if n == 0:
return 1
else:
return n*factorial(n-1)
#int(input("...")) รับค่าข้อมูลแบบตัวเลข integer
number = int(input("Enter factorial number: "))
print(factorial(number))
Lab 1.2 Drawing an English Ruler
#Lab1.2 Drawing an English Ruler
def draw_line(tick_length, tick_label=''):
"""Draw one line with given tick length (followed by optional label)."""
line = '-' * tick_length
if tick_label:
line += ' ' + tick_label
print(line)
def draw_interval(center_length):
"""Draw tick interval based upon a central tick length."""
if center_length > 0: # stop when length drops to 0
draw_interval(center_length - 1) # recursively draw top ticks
draw_line(center_length) # draw center tick
draw_interval(center_length - 1) # recursively draw bottom ticks
def draw_ruler(num_inches, major_length):
"""Draw English ruler with given number of inches and major tick length."""
draw_line(major_length, '0') # draw inch 0 line
for j in range(1, 1 + num_inches):
draw_interval(major_length - 1) # draw interior ticks for inch
draw_line(major_length, str(j)) # draw inch j line and label
if __name__ == '__main__':
draw_ruler(3, 6)
print('=' * 30)
Lab 1.3 The Sum of a List of Numbers
#Lab1.3 The sum of a list of numbers
def list_sum(num_List):
if len(num_List) == 1:
return num_List[0]
else:
return num_List[0] + list_sum(num_List[1:])
print(list_sum([3, 6, 9, 12, 16]))
Lab 1.4 Recursion List Sum
#Lab1.4 Recursion List Sum def recursive_list_sum(data_list): total = 0 for element in data_list: if type(element) == type([]): total = total + recursive_list_sum(element) else: total = total + element return total print( recursive_list_sum([2, 4, [6,8],[10,12]]))
Lab 1.5 Sum of a Non-Negative Integer Digit
#Lab1.5 Sum of a Non-Negative Integer
def sumDigits(n):
if n == 0:
return 0
else:
return n % 10 + sumDigits(int(n / 10))
print(sumDigits(678))
print(sumDigits(79))
Lab 2 Array in Python
Lab 2.1 Dynamic Arrays
#Array
#Lab2.1 Dynamic Arrays
#Array Set 1
data_list = [2, 4, [6, 8], [10, 12]]
for element in data_list:
print("index[", data_list.index(element),"] is", element)
a = len(data_list)
print("data_list's Length =", a)
print("data_list[3] =", data_list[3], "\n")
#Array Set 2
data_car = ["Toyota", "Honda", "Ford"]
for element in data_car:
print("index[", data_car.index(element),"] is", element)
print("data_car's Length = ", len(data_car))
data_car.append("Benz")
data_car.append("BMW")
for element in data_car:
print("index[", data_car.index(element),"] is", element)
print("Last data_car's Length = ", len(data_car))
print("data_car[4] =", data_car[4], "\n")
#Array Set 3
real_number = [1, 2.8, 3.149]
real_number.append(89)
real_number.append(368.659)
real_number.remove(3.149)
for element in real_number:
print("index[", real_number.index(element),"] is", element)
print("Last real_number's Length = ", len(real_number))
print("real_number[3] =", real_number[3], "\n")
Lab 2.2 Implementing a Dynamic Array
#Lab2.2 Implemenring a Dynamic Array p.195
import ctypes
class DynamicArray(object):
"""DYNAMIC ARRAY CLASS (Similar to Python List)"""
#initilize ir
def __init__(self):
#We will have 3 atributes
self.n = 0 # Count actual elements (Default is 0)
self.capacity = 1 # Default Capacity
self.A = self.make_array(self.capacity) #make_array will be defined later
#special len method
def __len__(self):
"""Return number of elements sorted in array"""
return self.n
def __getitem__(self, k):
"""Return element at index k"""
if not 0 <= k <self.n:
# Check it k index is in bounds of array
return IndexError('K is out of bounds !')
return self.A[k] # Retrieve from the array at index k
def append(self, ele):
"""Add element to end of the array"""
#Checking the capacity
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity) #_resize is the method that is defined later
#Set the n indexs of array A to element
self.A[self.n] = ele
self.n += 1
def _resize(self, new_cap): #new_cap is for new capacity
"""Resize internal array to capacity new_cap"""
#Decalare array B
B = self.make_array(new_cap)
for k in range(self.n): # Reference all existing values
B[k] = self.A[k]
self.A = B # Call A the new bigger array
self.capacity = new_cap # Reset the capacity
#making the make-array method using ctypes
def make_array(self, new_cap):
"""Returns a new array with new_cap capacity"""
return (new_cap * ctypes.py_object)()
arr = DynamicArray()
arr.append(1)
print(len(arr))
arr.append(2)
arr.append(6)
arr.append(89)
print(len(arr))
print(arr[2])
print(arr[3])
Lab 2.3 Storing High Scores for a Game
#Lab 2.3 Storing High Scores for a Game
class GameEntry:
"""Represents one entry of a list of high scores."""
def __init__(self, name, score):
"""Create an entry with given name and score."""
self._name = name
self._score = score
def get_name(self):
"""Return the name of the person for this entry."""
return self._name
def get_score(self):
"""Return the score of this entry."""
return self._score
def __str__(self):
"""Return string representation of the entry."""
return '({0}, {1})'.format(self._name, self._score) # e.g., '(Bob, 98)'
class Scoreboard:
"""Fixed-length sequence of high scores in nondecreasing order."""
def __init__(self, capacity=10):
"""Initialize scoreboard with given maximum capacity.
All entries are initially None.
"""
self._board = [None] * capacity # reserve space for future scores
self._n = 0 # number of actual entries
def __getitem__(self, k):
"""Return entry at index k."""
return self._board[k]
def __str__(self):
"""Return string representation of the high score list."""
return '\n'.join(str(self._board[j]) for j in range(self._n))
def add(self, entry):
"""Consider adding entry to high scores."""
score = entry.get_score()
# Does new entry qualify as a high score?
# answer is yes if board not full or score is higher than last entry
good = self._n < len(self._board) or score > self._board[-1].get_score()
if good:
if self._n < len(self._board): # no score drops from list
self._n += 1 # so overall number increases
# shift lower scores rightward to make room for new entry
j = self._n - 1
while j > 0 and self._board[j-1].get_score() < score:
self._board[j] = self._board[j-1] # shift entry from j-1 to j
j -= 1 # and decrement j
self._board[j] = entry # when done, add new entry
if __name__ == '__main__':
board = Scoreboard(5)
for e in (
('Somchai', 750), ('Somsri',1105), ('Somying', 590), ('Sompong', 740),
('Somrak', 510), ('Somhwang', 660), ('Somporn', 720), ('Sompon', 400),
):
ge = GameEntry(e[0], e[1])
board.add(ge)
print('After considering {0}, scoreboard is:'.format(ge))
print(board)
print()
Lab 2.4 Caesar Cipher – Using Array-Based Sequences
Caesar Cipher เป็นการเข้ารหัสแบบซีเคร็ทคีย์ (Secret Key) หรือ Symmetric Key Cryptography คิดค้นโดยกษัตริย์ Julius Caesar เพื่อสื่อสารกับทหารในกองทัพ และป้องกันไม่ให้ข่าวสารรั่วไหลไปถึงศัตรู
Python Type conversions
ฟังก์ชันแปลงข้อมูลในภาษา Python
| Function | Description |
|---|---|
| int(x [,base]) | แปลงออบเจ็ค x จากฐานที่กำหนด base ให้เป็น Integer |
| long(x [,base] ) | แปลงออบเจ็ค x จากฐานที่กำหนด base ให้เป็น Long |
| float(x) | แปลงออบเจ็ค x ให้เป็น Floating point number |
| complex(real [,im]) | สร้างตัวเลขจำนวนเชิงซ้อนจากค่า real และค่า imagine |
| str(x) | แปลงออบเจ็ค x ให้เป็น String |
| repr(x) | แปลงออบเจ็ค x ให้เป็น String expression |
| eval(str) | ประเมินค่าของ String |
| tuple(s) | แปลง Sequence ให้เป็น Tuple |
| list(s) | แปลง Sequence ให้เป็น List |
| set(s) | แปลง Sequence ให้เป็น Tuple |
| dict(d) | แปลงออบเจ็คให้เป็น Dictionary |
| frozenset(s) | แปลงออบเจ็คให้เป็น Frozen set |
| chr(x) | แปลงค่าของ Integer ให้เป็น Unicode Char |
| ord(x) | แปลง Charterer ให้เป็นค่า Integer |
| hex(x) | แปลง Integer ให้เป็น Hex string |
| oct(x) | แปลง Integer ให้เป็น Oct string |
#Lab 2.4 Caesar Cipher - Using Array-Based Sequences
class CaesarCipher:
"""Class for doing encryption and decryption using a Caesar Cipher."""
def __init__(self, shift):
"""Construct Caesar Cipher using given intefer shift for rotation."""
encoder = [None]*26 #temp array for encryption
decoder = [None]*26 #temp array for decryption
for k in range(26):
encoder[k] = chr((k + shift)%26 + ord('A'))
decoder[k] = chr((k - shift)%26 + ord('A'))
self._forward = ''.join(encoder) #will store as string
self._backward = ''.join(decoder) #since fixed
def encrypt(self, message):
"""Return string representing encripted message."""
return self._transform(message,self._forward)
def decrypt(self, secret):
"""Return decrypted message given encrypted secret."""
return self._transform(secret, self._backward)
def _transform(self, original, code):
"""Utility to perform transformation based on given code string."""
msg = list(original)
for k in range(len(msg)):
if msg[k].isupper():
j = ord(msg[k])-ord('A') #index from 0 to 25
msg[k] = code[j] #replace this character
return ''.join(msg)
if __name__ == '__main__':
cipher = CaesarCipher(3)
message = "HELLO PYTHON PROGRAMMING; I LOVE YOU."
coded = cipher.encrypt(message)
print('Secret: ', coded)
answer = cipher.decrypt(coded)
print('Message: ',answer)
Lab 2.5 Tic Tac Toe 1
#Lab 2.5 Tic Tac Toe 1
class TicTacToe:
"""Management of a Tic-Tac-Toe Game (does not do strategy)."""
def __init__(self):
"""Start a new game."""
self._board = [[' ']*3 for j in range(3)]
self._player = 'X'
def mark(self, i, j):
"""Put an X or O mark at position(i,j) for next player's trun."""
if not(0 <= i <= 2 and 0 <= i <= 2):
raise ValueError('Invalid board position')
if self._board[i][j] != ' ':
raise ValueError('Board position occupied')
if self.winner() is not None:
raise ValueError('Game is already complete')
self._board[i][j] = self._player
if self._player == 'X':
self._player = 'O'
else:
self._player = 'X'
def _is_win(self, mark):
"""Check whether the board configuration is a win for the given player."""
board = self._board
return(mark == board[0][0] == board[0][1] == board[0][2] or #row 0
mark == board[1][0] == board[1][1] == board[1][2] or #row 1
mark == board[2][0] == board[2][1] == board[2][2] or #row 2
mark == board[0][0] == board[1][0] == board[2][0] or #column 0
mark == board[0][1] == board[1][1] == board[2][1] or #column 1
mark == board[0][2] == board[1][2] == board[2][2] or #column 2
mark == board[0][0] == board[1][1] == board[2][2] or #diagonal
mark == board[0][2] == board[1][1] == board[2][0]) #rev diag
def winner(self):
"""Return mark of winning player, or None to indicate a tie."""
for mark in 'XO':
if self._is_win(mark):
return mark
return None
def __str__(self):
"""Return string representation of current game board."""
rows = ['|'.join(self._board[r]) for r in range(3)]
return '\n-----\n'.join(rows)
game = TicTacToe()
#X moves: #O moves:
game.mark(1,1); game.mark(0,2)
game.mark(2,2); game.mark(0,0)
game.mark(0,1); game.mark(2,1)
game.mark(1,2); game.mark(1,0)
game.mark(2,0)
print(game)
winner = game.winner()
if winner is None:
print('Tie')
else:
print(winner, 'wins')
Assignment Lab 2 จงเขียนเกม O-X หรือเกมที่ใช้ Array ประยุกต์จากตัวอย่าง โดยมีการรับค่าจากผู้เล่น
Lab 3 Stack, Queue, and Deque in Python
Stack
Lab 3.1 Stack
#Stack
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = [] #nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e) #new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty excpetion if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1] #the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empy')
return self._data.pop() #remove last item from list
S = ArrayStack() #contents: []
S.push(5) #contents: [5]
S.push(3) #contents: [5, 3]
print(len(S)) #contents: [5, 3]; outputs 2
print(S.pop()) #contents: [5]; outputs 3
print(S.is_empty()) #contents: [5]; outputs False
print(S.pop()) #contents: []; outputs 5
print(S.is_empty()) #contents: []; outputs True
S.push(7) #contents: [7]
S.push(9) #contents: [7, 9]
print(S.top()) #contents: [7, 9]; outputs 9
S.push(4) #contents: [7, 9, 4]
print(len(S)) #contents: [7, 9, 4]; outputs 3
print(S.pop()) #contents: [7, 9]; outputs 4
S.push(6) #contents: [7, 9, 6]
Lab 3.2 Reversing Data Using a Stack
Input File: Data.txt
Upload Data.txt –> Write Source Code –> Directory Path: “/content/Data.txt”
#Stack
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = [] #nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e) #new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty excpetion if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1] #the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty."""
if self.is_empty():
raise Empty('Stack is empy')
return self._data.pop() #remove last item from list
def reverse_file(filename):
"""Overwrite given file with its contents line-by-line reversed."""
S = ArrayStack()
original = open(filename)
for line in original:
S.push(line.rstrip('\n')) #we will re-insert newlines when writing
original.close()
#now we overwrite with contents in LIFO order
output = open(filename, 'w') #reopening file overwrites original
while not S.is_empty():
output.write(S.pop() + '\n') #re-insert newline characters
output.close()
Output = reverse_file("/content/Data.txt")
Queue
Lab 3.3 Queue
#Queues
class ArrayQueue:
"""FIFO queue implementation using a Python list as underlying storage."""
DEFAULT_CAPACITY = 10 #moderate capacity for all new queues
def __init__(self):
"""Create an empty queue."""
self._data = [None]*ArrayQueue.DEFAULT_CAPACITY
self._size = 0
self._front = 0
def __len__(self):
"""Return the number of elements in the queue."""
return self._size
def is_empty(self):
"""Return True if the queue is empty."""
return self._size == 0
def first(self):
"""Return (but do not remove) the element at the front of the queue.
Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise Empty('Queue is empty')
return self._data[self._front]
def dequeue(self):
"""Remove and return the first element of the queue (i.e.,FIFO).
Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise Empty('Queue is empty')
answer = self._data[self._front]
self._data[self._front] = None #help garbage collection
self._front = (self._front + 1)%len(self._data)
self._size -= 1
return answer
def enqueue(self, e):
"""Add an element to the back of queue."""
if self._size == len(self._data):
self._resize(2*len(self.data)) #double the array size
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1
def _resize(self, cap): #we assume cap >= len(self)
"""Resize to a new list of capacity >= len(self)."""
old = self._data #keep track of existing list
self._data = [None]*cap #allocate list with new capacity
walk = self._front
for k in range(self._size): #only consider existing elements
self._data[k] = old[walk] #intentionally shift indices
walk = (1+walk) % len(old) #use old size as modulus
self._front = 0 #front has been realigned
Q = ArrayQueue()
Q.enqueue(5) #[5]
Q.enqueue(3) #[5, 3]
print(len(Q)) #[5, 3]
print(Q.dequeue()) #[3]
print(Q.is_empty()) #[3]
print(Q.dequeue()) #[]
print(Q.is_empty()) #[]
#print(Q.dequeue()) #Error
Q.enqueue(7) #[7]
Q.enqueue(9) #[7, 9]
print(Q.first()) #[7, 9]
Q.enqueue(4) #[7, 9, 4]
print(len(Q)) #[7, 9, 4]
print(Q.dequeue()) #[9, 4]
Lab 3.4 Priority Queue
#PriorityQueue
class PriorityQueue(object):
def __init__(self):
self.queue = []
def __str__(self):
return ' '.join([str(i) for i in self.queue])
# for checking if the queue is empty
def isEmpty(self):
return len(self.queue) == []
# for inserting an element in the queue
def insert(self, data):
self.queue.append(data)
# for popping an element based on Priority
def delete(self):
try:
max = 0
for i in range(len(self.queue)):
if self.queue[i] > self.queue[max]:
max = i
item = self.queue[max]
del self.queue[max]
return item
except IndexError:
print()
exit()
if __name__ == '__main__':
myQueue = PriorityQueue()
myQueue.insert(12)
print(myQueue)
myQueue.insert(1)
print(myQueue)
myQueue.insert(16)
print(myQueue)
myQueue.insert(9)
print(myQueue) # 12 1 16 9
# 2 บรรทัดนี้รันไม่ได้ใน Colab
# ให้รันด้วยโปรแกรม VSCode หรือ Python IDE หรือ onlinegdb.com แทนจะทำงานได้
# Priority Queue จะทำการจัดเรียงคิวตามค่าตัวเลข Priority จากค่ามากไปค่าน้อยตามความสำคัญ
while not myQueue.isEmpty():
print(myQueue.delete(), end = ' ') # 16 12 9 1
Deques (Double-Ended Queues) Abstract Data Type (ADT)
Lab 3.5 Deque
#Deque
class Deque(object):
def __init__(self, limit = 10):
self.queue = []
self.limit = limit
def __str__(self):
return ' '.join([str(i) for i in self.queue])
# check if queue is empty
def isEmpty(self):
return len(self.queue) <= 0
# check if queue is full
def isFull(self):
return len(self.queue) >= self.limit
# for inserting at rear
def insertRear(self, data):
if self.isFull():
return
else:
self.queue.insert(0, data)
# for inserting at front end
def insertFront(self, data):
if self.isFull():
return
else:
self.queue.append(data)
# deleting from rear end
def deleteRear(self):
if self.isEmpty():
return
else:
return self.queue.pop(0)
# deleting from front end
def deleteFront(self):
if self.isFull():
return
else:
return self.queue.pop()
if __name__ == '__main__':
myDeque = Deque()
myDeque.insertFront(6) # 6
myDeque.insertRear(9) # 9 6
myDeque.insertFront(3) # 9 6 3
myDeque.insertRear(12) #12 9 6 3
print(myDeque)
myDeque.deleteRear() # 9 6 3
print(myDeque)
myDeque.deleteFront() # 9 6
print(myDeque)
Lab 4 Linked List
Lab 4.1 Implementing a Stack with a Single Linked List
# Implementation of Singly Linked List
class SinglyLinkedList:
"""Singly linked list implementation using object `Node` for storage."""
# ---------- Nested _Node class ---------- #
class _Node:
"""Lightweight, non-public class for storing a singly linked node."""
__slots__ = '_element', '_next' # streamline memory usage
# initialize node's fields,
# use `next_` to avoid conflic with the built-in function `next`
def __init__(self, element, next_):
self._element = element # reference to user's element
self._next = next_ # reference to next node
# ----------- linked list methods ----------- #
def __init__(self):
"""Create an empty list."""
self._head = None # reference to the head node
self._tail = None # reference to the tail node
self._size = 0 # number of stack elements
def __len__(self):
"""Return the number of elements in the list."""
return self._size
def is_empty(self):
"""Return True if the list is empty."""
return self._size == 0
def add_first(self, e):
"""Insert an element at the beginning of the linked list."""
newest = self._Node(e, self._head) # create new node instance
if self.is_empty(): # if the list is originally empty
self._tail = newest # make `_tail` to point to `newest` as well
self._head = newest # make `_head` to point to `newest`
self._size += 1
def add_last(self, e):
"""Insert an element at the end of the linked list."""
newest = self._Node(e, None)
if self.is_empty(): # if the list is originally empty
self._head = newest # make `_head` point to `newest`
else: # if not originally empty
self._tail._next = newest # make old tail node to link to newset
self._tail = newest # make `newest` the new `_tail` node
self._size += 1
def remove_first(self):
"""Remove the node at the beginning of the linked list."""
if self.is_empty():
raise Empty('Linked list is empty')
self._head = self._head._next # make `_head` point to the next node (or None)
self._size -= 1
def remove_last(self):
"""Remove the node at the end of the linked list."""
if self.is_empty():
raise Empty('Linked list is empty')
new_last = self._traverse(self._size-1) # find the second to last node
self._tail = new_last # make `_tail` point to the new last node
self._tail._next = None # make the new last node point to None
def _traverse(self, n):
"""Traverse the linked n steps from `_head` and reutrn the node."""
current = self._head
for _ in range(1, n):
current = current._next
return current
def __str__(self):
"""Return string representation of the linked list."""
expr = []
if self.is_empty():
return "[]"
current = self._head
expr.append(current._element)
while current._next != None:
current = current._next
expr.append(current._element)
return str(expr)
S = SinglyLinkedList()
print(S)
S.add_first("MSP")
print(S)
S.add_last("ATL")
print(S)
S.add_first("LAX")
print(S)
S.add_last("BOS")
print(S)
S.remove_first()
S.remove_last()
print(S)
Lab 4.2 Circularly Linked Lists
#Circularly Linked Lists
class CircularQueue:
"""Queue implementation using circularly linked list for storage."""
# ------------------------------------ #
class _Node:
"""Lightweight, nonpublic class for storing a singly linked node."""
__slots__ = '_element', '_next'
def __init__(self, e, next_):
self._element = e
self._next = next_
# ------------------------------------ #
def __init__(self):
"""Create an empty queue."""
self._tail = None
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def first(self):
if self.is_empty():
raise Empty('Queue is empty')
head = self._tail._next
return head._element
def dequeue(self):
"""Remove and return the first element of the queue (i.e., FIFO).
Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise Empty('Queue is empty')
oldhead = self._tail._next
self._size -= 1
if self._size == 0: # removing only element
self._tail = None # queue becomes empty
else:
self._tail._next = oldhead._next # bypass the old head
return oldhead._element
def enqueue(self, e):
"""Add an element e to the back of queue."""
newest = self._Node(e, None) # new tail node
# ***
if self.is_empty():
newest._next = newest # initialize circularly
else:
newest._next = self._tail._next # new tail node points to head
self._tail._next = newest # old tail node points to new node
self._tail = newest # new node becomes the tail
self._size += 1
def rotate(self):
"""Rotate front element to the back of the queue."""
if self._size > 0:
self._tail = self._tail._next # old head becomes new tail
def __str__(self):
"""String representation of the stack."""
expr = []
if self.is_empty():
return "[]"
current = self._tail._next # set current to `head` node
expr.append(current._element)
# while not circular back to head
while current._next != self._tail._next:
current = current._next
expr.append(current._element)
return str(expr)
Q = CircularQueue()
print(Q)
Q.enqueue("LAX")
Q.enqueue("MPS")
print(Q)
Q.dequeue()
print(Q)
Q.enqueue("ATL")
print('First: ', Q.first())
Q.enqueue("BOS")
print(Q)
Q.rotate()
print(Q)
Lab 4.3 Doubly Linked Lists
#Doubly Linked Lists
# A base class for managing a doubly linked list
class _DoublyLinkedBase:
"""A base class providing a doubly linked list representation."""
# ------------ nested Node class ---------- #
class _Node:
"""Lightweight, nonpublic class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next_):
self._element = element
self._prev = prev # previous node reference
self._next = next_ # next node reference
# -------------- doubly linked base methods ----------- #
def __init__(self):
"""Create an emtpy list."""
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, self._header, None) # header is before trailer
self._header._next = self._trailer # trailer is after header
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def _insert_between(self, e, predecessor, successor):
"""Add element e between two existing nodes and return new node."""
newest = self._Node(e, predecessor, successor) # linked to neighbors
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node(self, node):
"""Delete nonsentinel node from the list and return its element."""
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element # record deleted element
node._prev = node._next = node._element = None # deprecate node
return element # return deleted element
def __str__(self):
if self.is_empty():
return "[]"
expr = []
current = self._header
while current._next != self._trailer:
current = current._next
expr.append(current._element)
return str(expr)
L = _DoublyLinkedBase()
print(L)
L._insert_between(0, L._header, L._trailer)
print(L)
L._insert_between(1, L._header._next, L._trailer)
print(L)
L._delete_node(L._header._next)
print(L)
Lab 4.4 Implementing a Deque with a Doubly Linked List
#Implementing a Deque with a Doubly Linked List
#--------------------- Inherite Class #DoublyLinkedBase of Lab 4.5
class _DoublyLinkedBase:
"""A base class providing a doubly linked list representation."""
# ------------ nested Node class ---------- #
class _Node:
"""Lightweight, nonpublic class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next_):
self._element = element
self._prev = prev # previous node reference
self._next = next_ # next node reference
# -------------- doubly linked base methods ----------- #
def __init__(self):
"""Create an emtpy list."""
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, self._header, None) # header is before trailer
self._header._next = self._trailer # trailer is after header
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def _insert_between(self, e, predecessor, successor):
"""Add element e between two existing nodes and return new node."""
newest = self._Node(e, predecessor, successor) # linked to neighbors
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node(self, node):
"""Delete nonsentinel node from the list and return its element."""
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element # record deleted element
node._prev = node._next = node._element = None # deprecate node
return element # return deleted element
def __str__(self):
if self.is_empty():
return "[]"
expr = []
current = self._header
while current._next != self._trailer:
current = current._next
expr.append(current._element)
return str(expr)
#----------------------------- Linked Deque --------------------------------
class LinkedDeque(_DoublyLinkedBase): # inherite from _DoublyLinkedBase
"""Double-ended queue implementation based on a doubly linked list."""
def first(self):
"""Return (but do not remove) the element at the front of the deque."""
if self.is_empty():
raise Empty('Deque is empty')
first_node = self._header._next
return first_node._element # first node after the header
def last(self):
"""Return (but do not remove) the element at the back of the deque."""
if self.is_empty():
raise Empty('Deque is empty')
last_node = self._trailer._prev
return last_node._element # last node before the trailer
def insert_first(self, e):
"""Add an element to the front of the deque."""
# use inherited method
self._insert_between(e, self._header, self._header._next) # insert after header
def insert_last(self, e):
"""Add an element to the back of the deque."""
self._insert_between(e, self._trailer._prev, self._trailer) # insert before trailer
def delete_first(self):
"""Remove and return the element from the front of the deque.
Raise Empty exception if the deque is empty.
"""
if self.is_empty():
raise Empty('Deque is empty')
# use inherited method
self._delete_node(self._header._next)
def delete_last(self):
"""Remove and return the element from the back of the deque.
Raise Empty exception if the deque is empty.
"""
if self.is_empty():
raise Empty('Deque is empty')
self._delete_node(self._trailer._prev)
Q = LinkedDeque()
print(Q)
[Q.insert_first(i) for i in range(5, 0, -1)]
print(Q)
[Q.insert_last(i) for i in range(6, 11)]
print(Q)
Q.delete_last()
print(Q)
Q.delete_first()
print(Q)
Lab 4.5 The Positional List ADT
# Positional list implemented with doubly linked list data strcuture
#--------------------- Inherite Class #DoublyLinkedBase of Lab 4.5
class _DoublyLinkedBase:
"""A base class providing a doubly linked list representation."""
# ------------ nested Node class ---------- #
class _Node:
"""Lightweight, nonpublic class for storing a doubly linked node."""
__slots__ = '_element', '_prev', '_next'
def __init__(self, element, prev, next_):
self._element = element
self._prev = prev # previous node reference
self._next = next_ # next node reference
# -------------- doubly linked base methods ----------- #
def __init__(self):
"""Create an emtpy list."""
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, self._header, None) # header is before trailer
self._header._next = self._trailer # trailer is after header
self._size = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def _insert_between(self, e, predecessor, successor):
"""Add element e between two existing nodes and return new node."""
newest = self._Node(e, predecessor, successor) # linked to neighbors
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node(self, node):
"""Delete nonsentinel node from the list and return its element."""
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element # record deleted element
node._prev = node._next = node._element = None # deprecate node
return element # return deleted element
def __str__(self):
if self.is_empty():
return "[]"
expr = []
current = self._header
while current._next != self._trailer:
current = current._next
expr.append(current._element)
return str(expr)
#------ Lab4.7 Positional list implemented with doubly linked list data strcuture -------------------
class PositionalList(_DoublyLinkedBase): # inherited from _DoublyLinkedBase
"""A sequential container of elements allowing positional access."""
# -------------- nested Position class --------------- #
class Position:
"""An absrtraction representing the location of a single element."""
def __init__(self, container, node):
"""Constructor should not be invoked by user."""
self._container = container # reference to the list instance that contains the specified node
self._node = node
# ** With the container reference, we can roubstly detect when a caller
# sends a position instance that does not belong to the indicated list.
def element(self):
"""Return the element stored at this Position."""
return self._node._element
def __eq__(self, other):
"""Return True if other is a Position representing the same location."""
return type(other) is type(self) and other._node is self._node
def __ne__(self, other):
"""Return True if other does not representing the same location."""
return not (self == other) # oppositie of __eq__
# -------------------- utility methods -------------------- #
def _validate(self, p):
"""Return position's node, or raise appropriate error if invalid."""
if not isinstance(p, self.Position):
raise TypeError('p must be proper Position type')
# verify if the Position belong to this list
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._next is None: # `None`: convention for deprecated nodes
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
"""Return Position instance for given node. (or None if sentinel)."""
if node is self._header or node is self._trailer:
return None # boundary violation
else:
return self.Position(self, node) # legitimate position
# ------------------------ accessor ------------------------ #
def first(self):
"""Return the first Position in the list (or NOne if list is empty)."""
return self._make_position(self._header._next)
def last(self):
"""Return the last Position in the list (or None if list is empty)."""
return self._make_position(self._trailer._prev)
def before(self, p):
"""Return the Position just before Position p (or None if p is first)."""
node = self._validate(p)
return self._make_position(node._prev)
def after(self, p):
"""Return the Position just after Position p (or None if p is last)."""
node = self._validate(p)
return self._make_position(node._next)
def __iter__(self):
"""Generate a forward iteration of the elements of the list."""
cursor = self.first()
while cursor is not None:
yield cursor.element()
cursor = self.after(cursor)
def __str__(self):
"""String representation of PositionalList."""
return str([e for e in self])
# ----------------------- mutator ---------------------- #
# override inherited version to return Position, rather than Node
def _insert_between(self, e, predecessor, successor):
"""Add element between exisitng nodes and return new Position."""
node = super()._insert_between(e, predecessor, successor)
return self._make_position(node)
def add_first(self, e):
"""Insert elelment e at the front of the list and return new Position."""
return self._insert_between(e, self._header, self._header._next)
def add_last(self, e):
"""Insert element e at the back of the list and return new Position."""
return self._insert_between(e, self._trailer._prev, self._trailer)
def add_before(self, p, e):
"""Insert element e into list before Position p and return new Position."""
original = self._validate(p)
return self._insert_between(e, original._prev, original)
def add_after(self, p, e):
"""Insert element e into list after Position p and return new Position."""
original = self._validate(p)
return self._insert_between(e, original, original._next)
def delete(self, p):
"""Remove and return the element at Position p."""
original = self._validate(p)
return self._delete_node(original) # inherited method returns element
def replace(self, p , e):
"""Replace the element at Position p with e.
Return the element formerly at Position p.
"""
original = self._validate(p)
old_value = original._element # temporarily store old element
original._element = e # replace with new element
return old_value # return the old element value
# Testing PostionalList
L = PositionalList()
print(L)
[L.add_first(i) for i in range(5, 0, -1)]
print(L)
[L.add_last(i) for i in range(6, 11)]
print(L)
first = L.first()
second = L.after(first)
last = L.last()
second_last = L.before(last)
print('First:', first.element())
print(L.before(first))
print('Last:', last.element())
print('After first:', second.element())
print('Before last:', second_last.element())
L.add_after(second, 2.5)
L.add_before(second_last, 8.5)
print(L)
L.delete(second_last)
L.replace(second, -100)
print(L)
Lab 5 Trees
Lab 5.1 General Trees
The relationships in a tree are hierarchical, with some objects being “above” and some “below” others.
#Lab 5.1 General Trees
#Tree
class Tree:
"""Abstract base class representing a tree structure."""
# ------------------- nested Position class -------------------- #
class Position:
"""An abstraction representing the location of a single element."""
def element(self):
"""Return the element stored at this Position."""
raise NotImplementedError('must be implemented by subclass')
def __eq__(self, other):
"""Return True if other Position represents the same location."""
raise NotImplementedError('must be implemented by subclass')
def __ne__(self, other):
"""Return True if other does not represent the same location."""
return not (self == other) # opposite of __eq__
# --- abstract methods that concrete subclass must support --- #
def root(self):
"""Return Position representing the tree's root (or None if empty)."""
raise NotImplementedError('must be implemented by subclass')
def parent(self):
"""Return Position representing p's parent (or None if p is root)."""
raise NotImplementedError('must be implemented by subclass')
def num_children(self, p):
"""Return the number of chldren that Position p has."""
raise NotImplementedError('must be implemented by subclass')
def children(self, p):
"""Generate an iteration of Positions representing p's children."""
raise NotImplementedError('must be implemented by subclass')
def __len__(self):
"""Return the total number of elements in the tree."""
raise NotImplementedError('must be implemented by subclass')
# -------- concrete methods implemented in this class -------- #
def is_root(self, p):
"""Return True if Position p represents the root of the tree."""
return self.root() == p
def is_leaf(self, p):
"""Return True if Position p does not have any children."""
return self.num_children(p) == 0
def is_empty(self):
"""Return True if the tree is empty."""
return len(self) == 0
#--------- Computing Depth ---------------------
def depth(self, p):
"""Return the number of levels separating Position p from the root."""
if self.is_root(p):
return 0
else:
return 1 + self.depth(self.parent(p))
#--------- O(n^2) worst-case time --------------
def _height1(self, p):
"""Return the height of the tree."""
return max(self.depth(p) for p in self.positions() if self.is_leaf(p))
# time is linear in size of subtree
def _height2(self, p):
"""Return the height of the subtree rooted at Position p."""
if self.is_leaf(p):
return 0
else:
return 1 + max(self._height2(c) for c in self.children(p))
#--------- wrap the non-public `_height2` with a public `height` method ---------
def height(self, p=None):
"""Return the height of the subtree rooted at Position p.
If p is None, return the height of the entire tree.
"""
if p is None:
p = self.root()
return self._height2(p)
ใน functions
def root จะ return ค่า root ถ้าไม่มีจะ return None
def parent จะ return ตำแหน่งของ parent ถ้าไม่มี return None
def num_children return จำนวน children
def children สร้าง children โดยใช้การ iteration
def __len__ return จำนวนelement ทั้งหมดใน tree
def is_root return TRUE ออกมาถ้าตำแหน่ง p แทนที่ root ของ
def is_leaf return TRUE ออกมาถ้าตำแหน่ง p ไม่มี children
def is_empty return TRUE ออกมาถ้า Tree ว่าง
def depth return จำนวน level ออกมา (ใช้วิธี recursive)
def _height1 return height ของ tree
def _height2 return height ของ subtree root
def height return height ของ subtree root ถ้า p เป็น None return height tree ทั้งหมด
Lab 5.2 Binary Trees
#Tree
class Tree:
"""Abstract base class representing a tree structure."""
# ------------------- nested Position class -------------------- #
class Position:
"""An abstraction representing the location of a single element."""
def element(self):
"""Return the element stored at this Position."""
raise NotImplementedError('must be implemented by subclass')
def __eq__(self, other):
"""Return True if other Position represents the same location."""
raise NotImplementedError('must be implemented by subclass')
def __ne__(self, other):
"""Return True if other does not represent the same location."""
return not (self == other) # opposite of __eq__
# --- abstract methods that concrete subclass must support --- #
def root(self):
"""Return Position representing the tree's root (or None if empty)."""
raise NotImplementedError('must be implemented by subclass')
def parent(self):
"""Return Position representing p's parent (or None if p is root)."""
raise NotImplementedError('must be implemented by subclass')
def num_children(self, p):
"""Return the number of chldren that Position p has."""
raise NotImplementedError('must be implemented by subclass')
def children(self, p):
"""Generate an iteration of Positions representing p's children."""
raise NotImplementedError('must be implemented by subclass')
def __len__(self):
"""Return the total number of elements in the tree."""
raise NotImplementedError('must be implemented by subclass')
# -------- concrete methods implemented in this class -------- #
def is_root(self, p):
"""Return True if Position p represents the root of the tree."""
return self.root() == p
def is_leaf(self, p):
"""Return True if Position p does not have any children."""
return self.num_children(p) == 0
def is_empty(self):
"""Return True if the tree is empty."""
return len(self) == 0
#--------- Computing Depth ---------------------
def depth(self, p):
"""Return the number of levels separating Position p from the root."""
if self.is_root(p):
return 0
else:
return 1 + self.depth(self.parent(p))
#--------- O(n^2) worst-case time --------------
def _height1(self, p):
"""Return the height of the tree."""
return max(self.depth(p) for p in self.positions() if self.is_leaf(p))
# time is linear in size of subtree
def _height2(self, p):
"""Return the height of the subtree rooted at Position p."""
if self.is_leaf(p):
return 0
else:
return 1 + max(self._height2(c) for c in self.children(p))
#--------- wrap the non-public `_height2` with a public `height` method ---------
def height(self, p=None):
"""Return the height of the subtree rooted at Position p.
If p is None, return the height of the entire tree.
"""
if p is None:
p = self.root()
return self._height2(p)
#Lab 5.2
#BinaryTree
class BinaryTree(Tree):
"""Abstract base class representing a binary tree structure."""
# ---------------- additional abstract methods ---------------- #
def left(self, p):
"""Return a Position representing p's left child.
Return None if p does not have a left child.
"""
raise NotImplementedError('must be implemented by subclass')
def right(self, p):
"""Return a Position representing p's right child.
Return None if p does not have a right child.
"""
raise NotImplementedError('must be implemented by subclass')
# -------- concrete methods implemented in this class --------- #
def sibling(self, p):
"""Return a Position representing p's sibling (or None if no sibling)."""
parent = self.parent(p)
if parent is None: # p must be the root
return None # root has no sibling
else:
if p == self.left(parent): # if p is left child
return self.right(parent) # return right child, possibly None
else:
return self.left(parent) # otherwise p is right child and return left child
def children(self, p):
"""Generate an iteration of Positions representing p's children."""
if self.left(p) is not None:
yield self.left(p)
if self.right(p) is not None:
yield self.right(p)
ในส่วนของภาพ => จะเป็น binary tree ที่ทุก node จะมี left children และ right children ที่มี Level ทั้งหมด 4 --> 0 ถึง 3 ในส่วนของโปรแกรม => นำข้อมูล class Tree จาก Lab ที่ 1 มาใช้ใน class BinaryTree ==== Function ภายใน ==== def left return ตำแหน่งของ left child ถ้าไม่มี left child return None def right return ตำแหน่่งของ right child ถ้าไม่มี right child return None def sibling return ตำแหน่่งของ sibling ถ้าไม่มี sibling return None def children สร้างตำแหน่งของ children โดยใช้การ iteration โดยใช้ yield แทน return คือเมื่อเรียกใช้ function นั้่น ๆ จะถูกระงับและส่งข้อมูลกลับมา
Lab 5.3 Implementing Tree
#Linked Binary Tree
class LinkedBinaryTree(BinaryTree):
"""Linked representation of a binary tree structure."""
# -------------- nested _Node class ---------------- #
class _Node:
"""Lightweight, nonpublic class for storing a node."""
__slots__ = '_element', '_parent', '_left', '_right'
def __init__(self, element, parent=None, left=None, right=None):
self._element = element
self._parent = parent
self._left = left
self._right = right
# -------------- nested Position class ---------------- #
class Position(BinaryTree.Position): # inherited from `BinaryTree.Position` class
"""An abstraction representing location of a single element."""
def __init__(self, container, node):
"""Constructor should not be invoked by user."""
self._container = container
self._node = node
def element(self):
"""Return the element stored at this Position."""
return self._node._element
def __eq__(self, other):
"""Return True if other is a Position representing the same location."""
return type(self) == type(other) and self._node == other._node
# ---------------- utilities methods ------------------- #
def _validate(self, p):
"""Return associated node, if position is valid."""
if not isinstance(p, self.Position):
raise TypeError('p must be proper Position type')
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._parent is p._node: # convention for deprecated nodes
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
"""Return Position instance for given node (or None if no need)."""
# container is this `LinkedBinaryTree` instance (self)
return self.Position(self, node) if node is not None else None
# --------------- binary tree constructor ---------------- #
def __init__(self):
"""Create an initially empty binary tree."""
self._root = None
self._size = 0
# ------------------ public accessor --------------------- #
def __len__(self):
"""Return the total number of elements in the tree."""
return self._size
def root(self):
"""Return the root Postion of the tree (or None if tree is empty)."""
return self._make_position(self._root)
def parent(self, p):
"""Return the Position of p's parent (or None if p is root)."""
node = self._validate(p)
return self._make_position(node._parent)
def left(self, p):
"""Return the Position of p's left child (or None if on left child)."""
node = self._validate(p)
return self._make_position(node._left)
def right(self, p):
"""Return the Position of p's right child (or None if no right child)."""
node = self._validate(p)
return self._make_position(node._right)
def num_children(self, p):
"""Return the number fo children of Position p."""
node = self._validate(p)
count = 0
if node._left is not None: # left child exists
count += 1
if node._right is not None: # right child exists
count += 1
return count
# --------------- nonpublic update methods ---------------- #
def _add_root(self, e):
"""Place element e at the root of an empty tree and return new Position.
Raise ValueError if tree nonempty.
"""
if self._root is not None: raise ValueError('Root exists')
self._size = 1
self._root = self._Node(e)
return self._make_position(self._root)
def _add_left(self, p, e):
"""Create a new left child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p invalid or p already has a left child.
"""
node = self._validate(p) # parent node
if node._left is not None: raise ValueError('Left child exists')
node._left = self._Node(e, node) # left child
self._size += 1
return self._make_position(node._left)
def _add_right(self, p, e):
"""Create a new right child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p is invalid or p already has a right child.
"""
node = self._validate(p) # parent child
if node._right is not None: raise ValueError('Right child exists')
node._right = self._Node(e, node) # right child
self._size += 1
return self._make_position(node._right)
def _replace(self, p, e):
"""Replace the element at position p with e, and return old element."""
node = self._validate(p)
old_element = node._element
node._element = e
return old_element
def _delete(self, p):
"""Delete the node at Position p, and replace it with its child, if any.
Return the element that had been stored at Position p.
Raise ValueError if Position p is invalid or p has two children.
"""
node = self._validate(p)
if self.num_children(p) == 2: raise ValueError('p has two children')
child = node._left if node._left else node._right # might be None (no child)
# update parent reference
if child is not None:
child._parent = node._parent # child's grandparent becomes parent
# update child reference
if node is self._root:
self._root = child # child becomes root
else:
parent = node._parent
if node is parent._left:
parent._left = child
else:
parent._right = child
node._parent = node # convention for deprecated node
self._size -= 1
return node._element
def _attach(self, p, t1, t2):
"""Attach tree t1 and t2 as left and right subtrees of external p."""
node = self._validate(p)
if not self.is_leaf(p): raise ValueError('position must be leaf')
if not (type(self) is type(t1) is type(t2)): # all 3 trees must be same type
raise TypeError('Tree types must match')
self._size += (len(t1) + len(t2))
if not t1.is_empty(): # attached t1 as left subtree of node
node._left = t1._root
t1._root._parent = node
t1._root = None # set t1 instance to empty
t1._size = 0
if not t2.is_empty(): # attach t2 as right subtree of node
node._right = t2._root
t2._root._parent = node
t2._root = None # set t2 instance to empty
t2._size = 0
เอา class จาก Lab 2 Function ที่สำคัญ def _add_root เพิ่มตำแหน่ง root ใน tree และ return ตำแหน่ง root def _add_left เพิ่มตำแหน่ง left child ต้องใส่ ตำแหน่ง และ ค่าของ left child def _add_right เพิ่มตำแหน่ง right child ต้องใส่ ตำแหน่ง และ ค่าของ right child def _replace แทนที่ค่าไปตำแหน่งที่เรากำหนด และ return old element def _delete ลบ node ตำแหน่ง p และแทนที่ด้วย child def _attach เพิ่ม tree ทั้งset ใส่ค่า t1(left) และ t2(right) ของตำแหน่ง P
Lab 5.4 Implementing Tree: Testing LinkedBinaryTree class
#Linked Binary Tree
class LinkedBinaryTree(BinaryTree):
"""Linked representation of a binary tree structure."""
# -------------- nested _Node class ---------------- #
class _Node:
"""Lightweight, nonpublic class for storing a node."""
__slots__ = '_element', '_parent', '_left', '_right'
def __init__(self, element, parent=None, left=None, right=None):
self._element = element
self._parent = parent
self._left = left
self._right = right
# -------------- nested Position class ---------------- #
class Position(BinaryTree.Position): # inherited from `BinaryTree.Position` class
"""An abstraction representing location of a single element."""
def __init__(self, container, node):
"""Constructor should not be invoked by user."""
self._container = container
self._node = node
def element(self):
"""Return the element stored at this Position."""
return self._node._element
def __eq__(self, other):
"""Return True if other is a Position representing the same location."""
return type(self) == type(other) and self._node == other._node
# ---------------- utilities methods ------------------- #
def _validate(self, p):
"""Return associated node, if position is valid."""
if not isinstance(p, self.Position):
raise TypeError('p must be proper Position type')
if p._container is not self:
raise ValueError('p does not belong to this container')
if p._node._parent is p._node: # convention for deprecated nodes
raise ValueError('p is no longer valid')
return p._node
def _make_position(self, node):
"""Return Position instance for given node (or None if no need)."""
# container is this `LinkedBinaryTree` instance (self)
return self.Position(self, node) if node is not None else None
# --------------- binary tree constructor ---------------- #
def __init__(self):
"""Create an initially empty binary tree."""
self._root = None
self._size = 0
# ------------------ public accessor --------------------- #
def __len__(self):
"""Return the total number of elements in the tree."""
return self._size
def root(self):
"""Return the root Postion of the tree (or None if tree is empty)."""
return self._make_position(self._root)
def parent(self, p):
"""Return the Position of p's parent (or None if p is root)."""
node = self._validate(p)
return self._make_position(node._parent)
def left(self, p):
"""Return the Position of p's left child (or None if on left child)."""
node = self._validate(p)
return self._make_position(node._left)
def right(self, p):
"""Return the Position of p's right child (or None if no right child)."""
node = self._validate(p)
return self._make_position(node._right)
def num_children(self, p):
"""Return the number fo children of Position p."""
node = self._validate(p)
count = 0
if node._left is not None: # left child exists
count += 1
if node._right is not None: # right child exists
count += 1
return count
# --------------- nonpublic update methods ---------------- #
def _add_root(self, e):
"""Place element e at the root of an empty tree and return new Position.
Raise ValueError if tree nonempty.
"""
if self._root is not None: raise ValueError('Root exists')
self._size = 1
self._root = self._Node(e)
return self._make_position(self._root)
def _add_left(self, p, e):
"""Create a new left child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p invalid or p already has a left child.
"""
node = self._validate(p) # parent node
if node._left is not None: raise ValueError('Left child exists')
node._left = self._Node(e, node) # left child
self._size += 1
return self._make_position(node._left)
def _add_right(self, p, e):
"""Create a new right child for Position p, storing element e.
Return the Position of new node.
Raise ValueError if Position p is invalid or p already has a right child.
"""
node = self._validate(p) # parent child
if node._right is not None: raise ValueError('Right child exists')
node._right = self._Node(e, node) # right child
self._size += 1
return self._make_position(node._right)
def _replace(self, p, e):
"""Replace the element at position p with e, and return old element."""
node = self._validate(p)
old_element = node._element
node._element = e
return old_element
def _delete(self, p):
"""Delete the node at Position p, and replace it with its child, if any.
Return the element that had been stored at Position p.
Raise ValueError if Position p is invalid or p has two children.
"""
node = self._validate(p)
if self.num_children(p) == 2: raise ValueError('p has two children')
child = node._left if node._left else node._right # might be None (no child)
# update parent reference
if child is not None:
child._parent = node._parent # child's grandparent becomes parent
# update child reference
if node is self._root:
self._root = child # child becomes root
else:
parent = node._parent
if node is parent._left:
parent._left = child
else:
parent._right = child
node._parent = node # convention for deprecated node
self._size -= 1
return node._element
def _attach(self, p, t1, t2):
"""Attach tree t1 and t2 as left and right subtrees of external p."""
node = self._validate(p)
if not self.is_leaf(p): raise ValueError('position must be leaf')
if not (type(self) is type(t1) is type(t2)): # all 3 trees must be same type
raise TypeError('Tree types must match')
self._size += (len(t1) + len(t2))
if not t1.is_empty(): # attached t1 as left subtree of node
node._left = t1._root
t1._root._parent = node
t1._root = None # set t1 instance to empty
t1._size = 0
if not t2.is_empty(): # attach t2 as right subtree of node
node._right = t2._root
t2._root._parent = node
t2._root = None # set t2 instance to empty
t2._size = 0
#Lab 5.4
T = LinkedBinaryTree()
print('# T:', len(T))
# test udpate methods
nodes = []
nodes.append(T._add_root('0'))
nodes.append(T._add_left(nodes[0], '1'))
nodes.append(T._add_right(nodes[0], '2'))
print('# T:', len(T))
nodes.append(T._add_left(nodes[1], '3'))
nodes.append(T._add_right(nodes[1], '4'))
nodes.append(T._add_left(nodes[2], '5'))
nodes.append(T._add_right(nodes[2], '6'))
print('# T:', len(T))
# test public access methods
for i in range(len(T)):
node = nodes[i]
element = node.element()
parent = T.parent(node).element() if T.parent(node) is not None else 'None'
left = T.left(node).element() if T.left(node) is not None else 'None'
right = T.right(node).element() if T.right(node) is not None else 'None'
num_children = T.num_children(node)
print('p' + str(i) + ': ' + element,
'parent: ' + parent,
'left: ' + left,
'right: ' + right,
'children: ' + str(num_children))
# test replace
old = T._replace(nodes[0], '-1')
print('Replace ' + old + ' to ' + nodes[0].element())
# test delete
T._delete(nodes[5])
print('node 2 left child:', T.left(nodes[2]))
print('node 2 children:', T.num_children(nodes[2]))
T._add_left(nodes[2], '5')
print('node 2 left child:', T.left(nodes[2]).element())
# test depth and height
print('depth at p6:', T.depth(nodes[6]))
print('height:', T.height())
มี 5 อย่าง 1.จะเป็นส่วนเพิ่ม root , left child, right child 2.แยกว่าที่เราเพิ่มแต่ละอันคืออะไร parent, left, right, children 3.ทดสอบใช้ function replace 4.ทดสอบใช้ function delete 5.ทดสอบใช้ function depth และ height
Lab 5.5 Tree implementation – Preorder, Inorder, and Postorder Traversals
#Lab5.7 Tree Implementation - Preorder, Inorder, and Postorder Traversals
class Node(object):
def __init__(self, data = None):
self.left = None
self.right = None
self.data = data
# for setting left node
def setLeft(self, node):
self.left = node
# for setting right node
def setRight(self, node):
self.right = node
# for getting the left node
def getLeft(self):
return self.left
# for getting right node
def getRight(self):
return self.right
# for setting data of a node
def setData(self, data):
self.data = data
# for getting data of a node
def getData(self):
return self.data
# in this we first print the root node and then traverse towards leftmost node and then to the rightmost node
def preorder(Tree):
if Tree:
print(Tree.getData(), end = ' ')
preorder(Tree.getLeft())
preorder(Tree.getRight())
return
# in this we traverse first to the leftmost node, then print its data and then traverse for rightmost node
def inorder(Tree):
if Tree:
inorder(Tree.getLeft())
print(Tree.getData(), end = ' ')
inorder(Tree.getRight())
return
# in this we first traverse to the leftmost node and then to the rightmost node and then print the data
def postorder(Tree):
if Tree:
postorder(Tree.getLeft())
postorder(Tree.getRight())
print(Tree.getData(), end = ' ')
return
if __name__ == '__main__':
root = Node('R')
root.setLeft(Node('A'))
root.setRight(Node('B'))
root.left.setLeft(Node('C'))
root.left.setRight(Node('D'))
root.left.left.setLeft(Node('F'))
root.right.setLeft(Node('E'))
root.right.left.setLeft(Node('G'))
root.right.left.setRight(Node('H'))
print('Preorder Traversal:')
preorder(root)
print('\nInorder Traversal:')
inorder(root)
print('\nPostorder Traversal:')
postorder(root)
"""
INPUT
R
/ \
A B
/ \ /
C D E
/ / \
F G H
OUTPUT:
Preorder Traversal:
R A C F D B E G H
Inorder Traversal:
F C A D R G E H B
Postorder Traversal:
F C D A G H E B R
"""
def preorder ทำงานเป็น recursive --> Node Left Right def Inorder ทำงานเป็น recursive --> Left Node Right def postorder ทำงานเป็น recursive --> Left Right Node
Lab 6 Graph
Lab 6.1.1 Graph implementation in Python
#Lab6.1.1 Graph Implementation
class Graph(object):
def __init__(self, graph_dict=None):
""" initializes a graph object
If no dictionary or None is given,
an empty dictionary will be used
"""
if graph_dict == None:
graph_dict = {}
self.__graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.__graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.__generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] = []
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
def __generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges = []
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
def __str__(self):
res = "vertices: "
for k in self.__graph_dict:
res += str(k) + " "
res += "\nedges: "
for edge in self.__generate_edges():
res += str(edge) + " "
return res
if __name__ == "__main__":
g = { "a" : ["d"],
"b" : ["c"],
"c" : ["b", "c", "d", "e"],
"d" : ["a", "c"],
"e" : ["c"],
"f" : []
}
graph = Graph(g)
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print("Add vertex:")
graph.add_vertex("z")
print("Vertices of graph:")
print(graph.vertices())
print("Add an edge:")
graph.add_edge({"a","z"})
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
print('Adding an edge {"x","y"} with new vertices:')
graph.add_edge({"x","y"})
print("Vertices of graph:")
print(graph.vertices())
print("Edges of graph:")
print(graph.edges())
เป็นการนำข้อมูล dict มาทำงานในรูปแบบ graph โดยสามารถเพิ้ม vertex, edges หรือ เพิ่ม vertex หรือ เพิ่ม edge
def vertices() ทำหน้าที่แปลงข้อมูล dictionary เป็น list และ return ข้อมูลออกมา
def edges() ทำหน้าที่จัดกลุ่มให้อยู่ใน List เช่น [{a,b},{c,d}]
def add_vertex() ทำหน้าที่เพิ่ม vertex ได้ตามที่เรากำหนด
def add_edge({}) เพิ่ม edgeเข้าไป เช่น ({"a","z"})
def __generate_edges() ทำหน้าที่สร้าง edges
Lab 6.1.2 Graph implementation in Python using Adjacency List
#Lab6.1.2 Graph implementation in Python using Adjacency List
class AdjacencyList(object):
def __init__(self):
self.List = {}
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present
if fromVertex in self.List.keys():
self.List[fromVertex].append(toVertex)
else:
self.List[fromVertex] = [toVertex]
def printList(self):
for i in self.List:
print(i,'->',' -> '.join([str(j) for j in self.List[i]]))
if __name__ == '__main__':
g = AdjacencyList()
g.addEdge(0, 1)
g.addEdge(0, 4)
g.addEdge(4, 1)
g.addEdge(4, 3)
g.addEdge(1, 0)
g.addEdge(1, 4)
g.addEdge(1, 3)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 4)
g.printList()
เป็นโปรแกรมที่ทำงานเป็น Graph ด้วย Adjacency List มี 2 functions สำคัญ 1.def addEdge() เพิ่ม edge โดยต้องใส่ 2 ค่า 2.def printList() นำข้อมูลมาแสดงข้อมูลโดยมากำหนดรูปแบบการนำโดยใช้ ->
Lab 6.2 Breadth First Search Graph Traversal
#Lab6.2 Breadth First Search Graph Traversal
class Graph():
def __init__(self):
self.vertex = {}
# for printing the Graph vertexes
def printGraph(self):
for i in self.vertex.keys():
print(i,' -> ', ' -> '.join([str(j) for j in self.vertex[i]]))
# for adding the edge beween two vertexes
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
def BFS(self, startVertex):
# Take a list for stoting already visited vertexes
visited = [False] * len(self.vertex)
# create a list to store all the vertexes for BFS
queue = []
# mark the source node as visited and enqueue it
visited[startVertex] = True
queue.append(startVertex)
while queue:
startVertex = queue.pop(0)
print(startVertex, end = ' ')
# mark all adjacent nodes as visited and print them
for i in self.vertex[startVertex]:
if visited[i] == False:
queue.append(i)
visited[i] = True
if __name__ == '__main__':
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.printGraph()
print('BFS:')
g.BFS(2)
Lab 6.3 Depth First Search Graph Traversals
#Lab6.3 Depth First Search Graph Traversal
class Graph():
def __init__(self):
self.vertex = {}
# for printing the Graph vertexes
def printGraph(self):
print(self.vertex)
for i in self.vertex.keys():
print(i,' -> ', ' -> '.join([str(j) for j in self.vertex[i]]))
# for adding the edge beween two vertexes
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
def DFS(self):
# visited array for storing already visited nodes
visited = [False] * len(self.vertex)
# call the recursive helper function
for i in range(len(self.vertex)):
if visited[i] == False:
self.DFSRec(i, visited)
def DFSRec(self, startVertex, visited):
# mark start vertex as visited
visited[startVertex] = True
print(startVertex, end = ' ')
# Recur for all the vertexes that are adjacent to this node
for i in self.vertex.keys():
if visited[i] == False:
self.DFSRec(i, visited)
if __name__ == '__main__':
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.printGraph()
print('DFS:')
g.DFS()
Lab 6.4 Detect Cycle in Directed Graph
#Lab6.4 Detect Cycle in Directed Graph
#Time Complexity: O(|V| + |E|)
class Graph():
def __init__(self):
self.vertex = {}
# for printing the Graph vertexes
def printGraph(self):
for i in self.vertex.keys():
print(i,' -> ', ' -> '.join([str(j) for j in self.vertex[i]]))
# for adding the edge beween two vertexes
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
# This function will return True if graph is cyclic else return False
def checkCyclic(self):
visited = [False] * len(self.vertex)
stack = [False] * len(self.vertex)
for vertex in range(len(self.vertex)):
if visited[vertex] == False:
if self.checkCyclicRec(visited, stack, vertex) == True:
return True
return False
# Recursive function for finding the cycle
def checkCyclicRec(self, visited, stack, vertex):
# Mark the current node in visited and also add it to the stack
visited[vertex] = True
stack[vertex] = True
# mark all adjacent nodes of the current node
for adjacentNode in self.vertex[vertex]:
if visited[adjacentNode] == False:
if self.checkCyclicRec(visited, stack, adjacentNode) == True:
return True
elif stack[adjacentNode] == True:
return True
# The node needs to be poped from
# recursion stack before function ends
stack[vertex] = False
return False
if __name__ == '__main__':
graph = Graph()
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)
graph.printGraph()
if graph.checkCyclic() == 1:
print ("Graph has a cycle")
else:
print ("Graph has no cycle")
Lab 6.5 Detect Cycle in Undirected Graph
#Lab6.5 Detect Cycle in Undirected Graph
#Time Complexity: O(|V| + |E|)
class Graph():
def __init__(self):
self.vertex = {}
# for printing the Graph vertexes
def printGraph(self):
for i in self.vertex.keys():
print(i,' -> ', ' -> '.join([str(j) for j in self.vertex[i]]))
# for adding the edge beween two vertexes
def addEdge(self, fromVertex, toVertex):
# check if vertex is already present,
if fromVertex in self.vertex.keys() and toVertex in self.vertex.keys():
self.vertex[fromVertex].append(toVertex)
self.vertex[toVertex].append(fromVertex)
else:
# else make a new vertex
self.vertex[fromVertex] = [toVertex]
self.vertex[toVertex] = [fromVertex]
# This function will return True if graph is cyclic else return False
def checkCyclic(self):
visited = [False] * len(self.vertex) # Marking all vertices as not visited
for vertex in range(len(self.vertex)):
# Call the recursive function only if not visited
if visited[vertex] == False:
if self.checkCyclicRec(visited, -1, vertex) == True:
return True
return False
# Recursive function for finding the cycle
def checkCyclicRec(self, visited, parent, vertex):
# Mark the current node in visited
visited[vertex] = True
# mark all adjacent nodes of the current node
for adjacentNode in self.vertex[vertex]:
if visited[adjacentNode] == False:
if self.checkCyclicRec(visited, vertex, adjacentNode) == True:
return True
elif parent != adjacentNode:
return True
return False
if __name__ == '__main__':
graph = Graph()
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)
graph.printGraph()
if graph.checkCyclic() == 1:
print ("Graph has a cycle")
else:
print ("Graph has no cycle")
g1 = Graph()
g1.addEdge(0,1)
g1.addEdge(1,2)
g1.printGraph()
if g1.checkCyclic() == 1:
print ("Graph has a cycle")
else:
print ("Graph has no cycle")
Lab 7 Searching Algorihms
Lab 7.1 Binary Search Algorithm
#Lab1.3 Binary Search Algorithm
def binary_search(data, target, low, high):
"""Return True if target is found in indicated portion of a Python list.
The search only considers the portion from data[low] to data[high] inclusive."""
if low > high:
return False #interval is empty; no match
else:
mid = (low + high)//2
if target == data[mid]: #found a match
return True
elif target < data[mid]:
#return on the portion left of the middle
return binary_search(data, target, low, mid - 1)
else:
#recur on the portion right of the middle
return binary_search(data, target, mid + 1, high)
data = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
print(binary_search(data, 37, 0, len(data)-1))
print(binary_search(data, 10, 0, len(data)-1))
print(binary_search(data, 7, 0, len(data)-1))
print(binary_search(data, 9, 0, len(data)-1))
print(binary_search(data, 20, 0, len(data)-1))
print(binary_search(data, 13, 0, len(data)-1))
Lab 7.2 Binary Search Tree
#Lab5.8 Binary Search Tree
class Node(object):
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(self, data):
''' For inserting the data in the Tree '''
if self.data == data:
return False # As BST cannot contain duplicate data
elif data < self.data:
''' Data less than the root data is placed to the left of the root '''
if self.leftChild:
return self.leftChild.insert(data)
else:
self.leftChild = Node(data)
return True
else:
''' Data greater than the root data is placed to the right of the root '''
if self.rightChild:
return self.rightChild.insert(data)
else:
self.rightChild = Node(data)
return True
def minValueNode(self, node):
current = node
# loop down to find the leftmost leaf
while(current.leftChild is not None):
current = current.leftChild
return current
def delete(self, data):
''' For deleting the node '''
if self is None:
return None
''' if current node's data is less than that of root node,
then only search in left subtree else right subtree '''
if data < self.data:
self.leftChild = self.leftChild.delete(data)
elif data > self.data:
self.rightChild = self.rightChild.delete(data)
else:
# deleting node with one child
if self.leftChild is None:
temp = self.rightChild
self = None
return temp
elif self.rightChild is None:
temp = self.leftChild
self = None
return temp
# deleting node with two children
# first get the inorder successor
temp = self.minValueNode(self.rightChild)
self.data = temp.data
self.rightChild = self.rightChild.delete(temp.data)
return self
def find(self, data):
''' This function checks whether the specified data is in tree or not '''
if(data == self.data):
return True
elif(data < self.data):
if self.leftChild:
return self.leftChild.find(data)
else:
return False
else:
if self.rightChild:
return self.rightChild.find(data)
else:
return False
def preorder(self):
'''For preorder traversal of the BST '''
if self:
print(str(self.data), end = ' ')
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
def inorder(self):
''' For Inorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.inorder()
print(str(self.data), end = ' ')
if self.rightChild:
self.rightChild.inorder()
def postorder(self):
''' For postorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.postorder()
if self.rightChild:
self.rightChild.postorder()
print(str(self.data), end = ' ')
class Tree(object):
def __init__(self):
self.root = None
def insert(self, data):
if self.root:
return self.root.insert(data)
else:
self.root = Node(data)
return True
def delete(self, data):
if self.root is not None:
return self.root.delete(data)
def find(self, data):
if self.root:
return self.root.find(data)
else:
return False
def preorder(self):
if self.root is not None:
print()
print('Preorder: ')
self.root.preorder()
def inorder(self):
print()
if self.root is not None:
print('Inorder: ')
self.root.inorder()
def postorder(self):
print()
if self.root is not None:
print('Postorder: ')
self.root.postorder()
if __name__ == '__main__':
tree = Tree()
tree.insert(16)
tree.insert(18)
tree.insert(11)
tree.insert(10)
tree.insert(26)
tree.insert(14)
tree.insert(13)
tree.insert(21)
tree.insert(20)
print(tree.find(1))
print(tree.find(26))
''' Following tree is getting created:
16
/ \
11 18
/ \ \
10 14 26
/ /
13 21
/
20
'''
tree.preorder()
tree.inorder()
tree.postorder()
print('\n\nAfter deleting 26')
tree.delete(26)
tree.preorder()
tree.inorder()
tree.postorder()
print('\n\nAfter deleting 16')
tree.delete(16)
tree.preorder()
tree.inorder()
tree.postorder()
Lab 7.3 Breadth First Traversal
#Lab 5.9 Breadth First Traversal
class Node(object):
def __init__(self, data = None):
self.leftChild = None
self.rightChild = None
self.data = data
def height(node):
if node is None:
return 0
else:
leftHeight = height(node.leftChild)
rightHeight = height(node.rightChild)
if leftHeight > rightHeight:
return leftHeight + 1
else:
return rightHeight + 1
def breadthFirstTraversal(root):
if root == None:
return 0
else:
h = height(root)
for i in range(1, h + 1):
printBFT(root, i)
def printBFT(root, level):
if root is None:
return
else:
if level == 1:
print(root.data, end = ' ')
elif level > 1:
printBFT(root.leftChild, level - 1)
printBFT(root.rightChild, level - 1)
if __name__ == '__main__':
root = Node('R')
root.leftChild = Node('A')
root.rightChild = Node('B')
root.leftChild.leftChild = Node('C')
root.leftChild.rightChild = Node('D')
root.leftChild.leftChild.leftChild = Node('F')
root.rightChild.leftChild = Node('E')
root.rightChild.leftChild.leftChild = Node('G')
root.rightChild.leftChild.rightChild = Node('H')
breadthFirstTraversal(root)
Lab 7.4 Finding Root to Leaf Paths
#Lab 5.11 Finding Root to Leaf Paths
# Use a path array path[] to store current root to leaf path. Traverse from root to all leaves in top-down fashion.
# While traversing, store data of all nodes in current path in array path[]. When we reach a leaf node, print the path
# array.
class Node(object):
def __init__(self, data = None):
self.left = None
self.right = None
self.data = data
def printPath(node, path = []):
if node is None:
return
path.append(node.data)
if (node.left is None) and (node.right is None):
print(' '.join([str(i) for i in path if i != 0]))
else:
printPath(node.left, path)
printPath(node.right, path[0:1])
if __name__ == '__main__':
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
printPath(root)
Lab 8 Sorting Algorithms
Lab 8.1 Bubble Sort
#Lab8.1 Bubble Sort
def bubble_sort(collection):
length = len(collection)
for i in range(length-1):
swapped = False
for j in range(length-1-i):
if collection[j] > collection[j+1]:
swapped = True
collection[j], collection[j+1] = collection[j+1], collection[j]
if not swapped: break # Stop iteration if the collection is sorted.
return collection
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(bubble_sort(unsorted), sep=',')
Lab 8.2 Cocktail Sort
#Lab8.2 Cocktail Sort
def cocktail_shaker_sort(unsorted):
"""
Pure implementation of the cocktail shaker sort algorithm in Python.
"""
for i in range(len(unsorted)-1, 0, -1):
swapped = False
for j in range(i, 0, -1):
if unsorted[j] < unsorted[j-1]:
unsorted[j], unsorted[j-1] = unsorted[j-1], unsorted[j]
swapped = True
for j in range(i):
if unsorted[j] > unsorted[j+1]:
unsorted[j], unsorted[j+1] = unsorted[j+1], unsorted[j]
swapped = True
if not swapped:
return unsorted
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
cocktail_shaker_sort(unsorted)
print(unsorted)
Lab 8.3 Gnome Sort
#Lab8.3 Gnome Sort
def gnome_sort(unsorted):
"""
Pure implementation of the gnome sort algorithm in Python.
"""
if len(unsorted) <= 1:
return unsorted
i = 1
while i < len(unsorted):
if unsorted[i-1] <= unsorted[i]:
i += 1
else:
unsorted[i-1], unsorted[i] = unsorted[i], unsorted[i-1]
i -= 1
if (i == 0):
i = 1
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
gnome_sort(unsorted)
print(unsorted)
Lab 8.4 Insertion Sort
#Lab8.4 Insertion Sort
def insertion_sort(collection):
for index in range(1, len(collection)):
while index > 0 and collection[index - 1] > collection[index]:
collection[index], collection[index - 1] = collection[index - 1], collection[index]
index -= 1
return collection
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(insertion_sort(unsorted))
Lab 8.5 Shell Sort
#Lab8.5 Shell Sort
def shell_sort(collection):
# Marcin Ciura's gap sequence
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
for gap in gaps:
i = gap
while i < len(collection):
temp = collection[i]
j = i
while j >= gap and collection[j - gap] > temp:
collection[j] = collection[j - gap]
j -= gap
collection[j] = temp
i += 1
return collection
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(shell_sort(unsorted))
Lab 8.6 Selection Sort
#Lab8.6 Selection Sort
def selection_sort(collection):
length = len(collection)
for i in range(length - 1):
least = i
for k in range(i + 1, length):
if collection[k] < collection[least]:
least = k
collection[least], collection[i] = (
collection[i], collection[least]
)
return collection
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(selection_sort(unsorted))
Lab 8.7 Quick Sort
#Lab8.7 Quick Sort
def quick_sort(ARRAY):
ARRAY_LENGTH = len(ARRAY)
if( ARRAY_LENGTH <= 1):
return ARRAY
else:
PIVOT = ARRAY[0]
GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
LESSER = [ element for element in ARRAY[1:] if element <= PIVOT ]
return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [ int(item) for item in user_input.split(',') ]
print( quick_sort(unsorted) )
Lab 8.8 Merge Sort
#Lab8.8 Merge Sort
def merge_sort(collection):
length = len(collection)
if length > 1:
midpoint = length // 2
left_half = merge_sort(collection[:midpoint])
right_half = merge_sort(collection[midpoint:])
i = 0
j = 0
k = 0
left_length = len(left_half)
right_length = len(right_half)
while i < left_length and j < right_length:
if left_half[i] < right_half[j]:
collection[k] = left_half[i]
i += 1
else:
collection[k] = right_half[j]
j += 1
k += 1
while i < left_length:
collection[k] = left_half[i]
i += 1
k += 1
while j < right_length:
collection[k] = right_half[j]
j += 1
k += 1
return collection
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(merge_sort(unsorted))
Lab 8.9 Bucket Sort
#Lab8.4 Insertion Sort
def insertion_sort(collection):
for index in range(1, len(collection)):
while index > 0 and collection[index - 1] > collection[index]:
collection[index], collection[index - 1] = collection[index - 1], collection[index]
index -= 1
return collection
#Lab8.9 Bucket Sort
import math
DEFAULT_BUCKET_SIZE = 5
def bucketSort(myList, bucketSize=DEFAULT_BUCKET_SIZE):
if(len(myList) == 0):
print('You don\'t have any elements in array!')
minValue = myList[0]
maxValue = myList[0]
# For finding minimum and maximum values
for i in range(0, len(myList)):
if myList[i] < minValue:
minValue = myList[i]
elif myList[i] > maxValue:
maxValue = myList[i]
# Initialize buckets
bucketCount = math.floor((maxValue - minValue) / bucketSize) + 1
buckets = []
for i in range(0, bucketCount):
buckets.append([])
# For putting values in buckets
for i in range(0, len(myList)):
buckets[math.floor((myList[i] - minValue) / bucketSize)].append(myList[i])
# Sort buckets and place back into input array
sortedArray = []
for i in range(0, len(buckets)):
insertion_sort(buckets[i])
for j in range(0, len(buckets[i])):
sortedArray.append(buckets[i][j])
return sortedArray
if __name__ == '__main__':
try:
raw_input # Python 2
except NameError:
raw_input = input # Python 3
user_input = raw_input('Enter numbers separated by a comma:\n').strip()
unsorted = [int(item) for item in user_input.split(',')]
print(bucketSort(unsorted))
Lecturer, Blogger, Traveler, and Software Developer ที่ชอบอ่านบทความใหม่ๆ ตลอดเวลา ชอบหาวิธีสร้าง Inspiration เป็นชีวิตจิตใจ มีความฝันอยากทำ CREATIVE PRODUCT ที่สามารถเปลี่ยนแปลงโลกให้ดีขึ้น และอยากถ่ายรูปสถานที่ท่องเที่ยวรอบโลก สอนหนังสือ ชอบแลกเปลี่ยนความรู้ และเขียน WEBSITE, MOBILE APP, GAME, ETC ที่เป็นประโยชน์กับโลกใบนี้