ยินดีต้อนรับ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software Engineer

ความสำคัญของอัลกอริทึมและโครงสร้างข้อมูล

• โครงสร้างข้อมูล และ อัลกอริทึม ช่วยให้เรา
  • แก้ ปัญหาในชีวิตประจำวัน
  • ด้วย โค้ดที่มีประสิทธิภาพ
• คอร์สนี้สามารถสอนด้วย ภาษาโปรแกรมใดก็ได้

อัลกอริทึมและโครงสร้างข้อมูล

• อัลกอริทึม: ชุดคำสั่งที่ใช้แก้ปัญหา

  1. ออกแบบ

     

  2. เขียนโค้ด

     

• โครงสร้างข้อมูล: ใช้เก็บและจัดการข้อมูลระหว่างรันอัลกอริทึม
  • โครงสร้างข้อมูล ขั้นสูง: linked list, stack, queue...

Linked list

• ลำดับของข้อมูลที่เชื่อมต่อกันผ่าน link

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

Linked list - โครงสร้าง

• ข้อมูลไม่จำเป็นต้องเก็บในบล็อกหน่วยความจำที่ต่อเนื่องกัน
• ข้อมูลสามารถอยู่ที่ address หน่วยความจำใดก็ได้ที่ว่างอยู่

Singly linked list

• link เดียว: singly linked list

Doubly linked list

• สอง link ทั้งสองทิศทาง: doubly linked list

Linked list - การใช้งานจริง

• นำไปใช้สร้างโครงสร้างข้อมูลอื่น:
  • stack
  • queue
  • กราฟ
• เข้าถึงข้อมูลโดยเลื่อนไปข้างหน้าและข้างหลังได้
  • เว็บเบราว์เซอร์
  • เพลย์ลิสต์เพลง

Linked list - คลาส Node

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

Linked list - คลาส LinkedList

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

Linked list - เมธอด

• insert_at_beginning()
• remove_at_beginning()
• insert_at_end()
• remove_at_end()
• insert_at()
• remove_at()
• search()
• ...

Linked list - insert_at_beginning

Linked list - insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:

Linked list - insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head

Linked list - insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node

Linked list - insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node

Linked list - insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node

Linked list - search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

Linked list - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

Linked list - search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

Linked list - ตัวอย่าง

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

Linked list - ตัวอย่าง

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 

Linked list - ตัวอย่าง

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")

Linked list - ตัวอย่าง

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python