วิชาโครงสร้างข้อมูลและอัลกอริทึม Data Structures and Algorithms with Python Programming by Aj.NesT the Series

วิชาโครงสร้างข้อมูลและอัลกอริทึม
Data Structures and Algorithms with Python Programming by Aj.NesT the Series

>>> Click Lecture for Full Course Data Structures and Algorithms <<<

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

FunctionDescription
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

This image has an empty alt attribute; its file name is image-31.png
#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

This image has an empty alt attribute; its file name is image-33.png
#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

Binary Search
File:Binary search tree example.gif - Wikimedia Commons
#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))

Aj. NesT The Series on sabemailAj. NesT The Series on sabfacebookAj. NesT The Series on sabinstagramAj. NesT The Series on sabtwitterAj. NesT The Series on sabyoutube
Aj. NesT The Series
at GlurGeek.Com
Lecturer, Blogger, Traveler, and Software Developer ที่ชอบอ่านบทความใหม่ๆ ตลอดเวลา ชอบหาวิธีสร้าง Inspiration เป็นชีวิตจิตใจ มีความฝันอยากทำ CREATIVE PRODUCT ที่สามารถเปลี่ยนแปลงโลกให้ดีขึ้น และอยากถ่ายรูปสถานที่ท่องเที่ยวรอบโลก สอนหนังสือ ชอบแลกเปลี่ยนความรู้ และเขียน WEBSITE, MOBILE APP, GAME, ETC ที่เป็นประโยชน์กับโลกใบนี้

Leave a Reply

Copyright © 2021 GlurGeek.Com. All Rights Reserved.