โปรแกรมกำหนดโครงสร้างข้อมูลเซตโดยไม่ใช้คลาส set ของไลบรารีใน Python

สมมติว่าเราต้องการนำโครงสร้างข้อมูลเซต (Set) มาใช้ด้วยเมธอดต่อไปนี้:

• Constructor สร้างอินสแตนซ์เซตใหม่
• add(val) แทรกจำนวนเต็ม val เข้าเซต
• exists(val) ตรวจสอบว่า val อยู่ในเซตหรือไม่
• remove(val) ลบ val ออกจากเซต

เช่น ถ้าสร้างเซต s เรียก s.add(10), s.add(20), s.add(10), s.exists(10), s.remove(10), s.exists(10), s.exists(20) ผลลัพธ์จะเป็น:

• s.add(10) แทรก 10
• s.add(20) แทรก 20
• 10 อยู่ใน s แล้ว ไม่เกิดอะไร
• s.exists(10) คืนค่า True เพราะ 10 อยู่
• ลบ 10 ด้วย s.remove(10)
• s.exists(10) คืนค่า False เพราะ 10 ถูกลบ และสมาชิกมีได้เพียงครั้งเดียว
• s.exists(20) คืนค่า True เพราะ 20 ยังอยู่

ขั้นตอนการแก้ปัญหา

1. กำหนด Constructor:
   • buckets := แมปว่าง จะเก็บรายการข้อมูล
2. กำหนดฟังก์ชัน add(val):
   • ถ้า exists(val) เป็น False เพิ่ม val เข้า buckets[val]
3. กำหนดฟังก์ชัน exists(val):
   • คืนค่า True ถ้า val ใน buckets[val] มิฉะนั้น False
4. กำหนดฟังก์ชัน remove(val):
   • ลบ buckets[val]

ตัวอย่างการใช้งาน

from collections import defaultdict

class MySet:
    def __init__(self):
        self.buckets = defaultdict(list)
    def add(self, val):
        if not self.exists(val):
            self.buckets[val].append(val)
    def exists(self, val):
        return val in self.buckets[val]
    def remove(self, val):
        del self.buckets[val]

s = MySet()
s.add(10)
s.add(20)
s.add(10)
print(s.exists(10))
s.remove(10)
print(s.exists(10))
print(s.exists(20))

อินพุต

s = MySet() s.add(10) s.add(20) s.add(10) s.exists(10) s.remove(10) s.exists(10) s.exists(20)

เอาต์พุต

True False True