โครงสร้างข้อมูลและอัลกอริธึม: คู่มือฉบับสมบูรณ์สำหรับโปรแกรมเมอร์

อินฟอร์เมเทค ดิจิตอล » Recursos » โครงสร้างข้อมูลและอัลกอริธึม: คู่มือฉบับสมบูรณ์สำหรับโปรแกรมเมอร์

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

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

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

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

เมื่อคุณเลือกโครงสร้างข้อมูลที่เหมาะสม โปรแกรมของคุณก็จะสามารถจัดการได้ ข้อมูลจำนวนมาก โดยไม่ต้องเหนื่อยเลยสักนิด; หากเลือกไม่ดี แม้แต่แอปพลิเคชันขนาดเล็กก็อาจทำงานช้าลง กินหน่วยความจำมากเกินไป หรือกลายเป็นสิ่งที่ดูแลรักษายากในระยะยาว

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

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

จากมุมมองทางทฤษฎี นักเขียนอย่างนิคลาอุส เวิร์ธ ได้เผยแพร่แนวคิดนี้มาตั้งแต่ช่วงทศวรรษ 70 แล้วว่า อัลกอริทึม + โครงสร้างข้อมูล = โปรแกรมหลายทศวรรษต่อมา สิ่งนี้ก็ยังคงเป็นความจริงเช่นเดิม: ไม่ว่าคุณจะเขียนโปรแกรมด้วย Java, Python, C++ หรือจบจากหลักสูตรเร่งรัด สิ่งที่จะเป็นที่ประจักษ์ในระหว่างการสัมภาษณ์งานและโครงการจริงจังก็คือ การรู้วิธีเลือกและผสมผสานทั้งสององค์ประกอบนั้นได้อย่างดี

เหตุใดพวกมันจึงมีความสำคัญมากในด้านการเขียนโปรแกรม?

ในการใช้งานจริงทุกรูปแบบ ไม่ว่าจะดูเรียบง่ายเพียงใด คุณก็ต้องทำงานกับข้อมูลอยู่เสมอ: เงินเดือน, ผลิตภัณฑ์, ผู้ใช้, ธุรกรรม, เส้นทาง, เอกสารบันทึกข้อมูลต่างๆ เป็นต้น คำถามไม่ได้อยู่ที่ว่าคุณจะจัดการกับข้อมูลหรือไม่ แต่คุณจะจัดระเบียบข้อมูลอย่างไรเพื่อให้โค้ดของคุณทำงานได้รวดเร็ว ชัดเจน และดูแลรักษาง่าย

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

ในส่วนของอัลกอริธึมนั้น ช่วยให้ ประมวลผลข้อมูลนั้นอย่างมีประสิทธิภาพ: จัดเรียง กรอง ค้นหาองค์ประกอบ ค้นหาเส้นทางที่เหมาะสมที่สุด ตรวจจับรูปแบบด้วย การทำเหมืองข้อมูลเพิ่มประสิทธิภาพการใช้ทรัพยากร ฯลฯ ปัญหาหลายอย่างที่ดูยากจะกลายเป็นเรื่องง่ายเมื่อคุณค้นพบการผสมผสานที่ลงตัวระหว่างอัลกอริทึมและโครงสร้างข้อมูล

ในการสัมภาษณ์ทางเทคนิคสำหรับการพัฒนาซอฟต์แวร์ แทบจะไม่พบคำถามใดที่ไม่เกี่ยวข้องกับหัวข้อเหล่านี้โดยตรง บางครั้งคำถามจะกล่าวถึงโครงสร้างอย่างชัดเจน เช่น "กำหนดให้มีต้นไม้ไบนารี..." และบางครั้งก็เป็นไปโดยนัย เช่น "เราต้องการนับจำนวนหนังสือที่ผู้เขียนแต่ละคนเขียน" ซึ่งแนะนำให้ใช้โครงสร้างข้อมูลแบบต้นไม้ไบนารี ตารางแฮชหรือแผนที่คีย์-ค่า.

นอกจากนี้ การฝึกอบรมอย่างเป็นทางการและแบบวิชาชีพมักเกี่ยวข้องกับด้านนี้ มหาวิทยาลัยและหลักสูตรการศึกษาระดับสูงหลายแห่งมีวิชาเกี่ยวกับ... โครงสร้างข้อมูลและอัลกอริธึมโดยมีหลักสูตรอย่างเป็นทางการ ข้อกำหนดเบื้องต้น การเรียนภาคทฤษฎีและภาคปฏิบัติ การสอบ และการบ้าน เนื่องจากถือเป็นวิชาหลักสำหรับวิศวกรซอฟต์แวร์ทุกคน

ข้อกำหนดเบื้องต้นและพื้นฐานที่จำเป็น

เพื่อให้ได้ประโยชน์สูงสุดจากการศึกษาโครงสร้างข้อมูลและอัลกอริธึม การมีความคุ้นเคยกับภาษาโปรแกรมทั่วไป เช่น จะเป็นประโยชน์อย่างมาก ภาษาจาวา, ไพธอน หรือ ซี++คุณไม่จำเป็นต้องเป็นผู้เชี่ยวชาญ แต่คุณต้องคุ้นเคยกับแนวคิดพื้นฐาน เช่น ตัวแปร ชนิดข้อมูล เงื่อนไข ลูป ฟังก์ชัน และการส่งผ่านพารามิเตอร์

นอกจากนี้ การเข้าใจแนวคิดเรื่อง ก็ช่วยได้มากเช่นกัน ความซับซ้อนของอัลกอริทึม และสัญกรณ์ Big O: วิธีที่เวลาในการประมวลผลหรือการใช้หน่วยความจำเพิ่มขึ้นเมื่อขนาดข้อมูล (n) เพิ่มขึ้น การรู้วิธีแยกแยะความแตกต่างระหว่าง O(1), O(log n), O(n), O(n log n) และ O(n²) ช่วยให้คุณสามารถเปรียบเทียบทางเลือกต่างๆ ได้อย่างมีวิจารณญาณและให้เหตุผลในการตัดสินใจของคุณได้

อีกแง่มุมที่สำคัญคือการที่เคยทะเลาะกับ... การแก้ปัญหาแบบฝึกหัดการเขียนโปรแกรมแบบมีโครงสร้าง โจทย์ตรรกะเล็กๆ แบบฝึกหัดง่ายๆ ฯลฯ ยิ่งคุณฝึกฝน "สัญชาตญาณ" ของคุณให้สามารถแยกแยะปัญหาออกเป็นขั้นตอนได้มากเท่าไหร่ ก็ยิ่งจะง่ายขึ้นที่จะเห็นว่าโครงสร้างข้อมูลใดเหมาะสมกับแต่ละกรณี

หลักสูตรบางหลักสูตรระบุไว้อย่างชัดเจน ข้อกำหนดเบื้องต้นหรือข้อกำหนดร่วม สำหรับวิชาโครงสร้างข้อมูลและอัลกอริทึม คุณต้องผ่านวิชาพื้นฐานการเขียนโปรแกรม การเขียนโปรแกรม 1 หรือคณิตศาสตร์เชิงดิสครีตมาก่อน ซึ่งก็สมเหตุสมผล เพราะหากไม่มีพื้นฐานที่แข็งแกร่งในด้านการเขียนโปรแกรมและตรรกะขั้นพื้นฐาน ก็很容易ที่จะรู้สึกท้อแท้กับวิชานี้

สุดท้ายนี้ การมีความคุ้นเคยกับสิ่งต่างๆ บ้างก็เป็นสิ่งสำคัญ สภาพแวดล้อมเชิงปฏิบัติในโลกแห่งความเป็นจริง (เช่น โปรเจ็กต์เว็บขนาดเล็ก สคริปต์ หรือแอปพลิเคชันคอนโซล) ช่วยให้คุณเห็นภาพได้ชัดเจนขึ้นว่าคุณจะนำโครงสร้างแต่ละอย่างไปใช้เพื่ออะไร แทนที่จะมองว่าเป็นเพียงเรื่องทางวิชาการเท่านั้น

โครงสร้างข้อมูลที่ใช้กันทั่วไปมากที่สุด

ในวิทยาการคอมพิวเตอร์มีโครงสร้างข้อมูลมากมายอย่างไรก็ตาม มีกลุ่มฟังก์ชัน "พื้นฐาน" บางกลุ่มที่ถูกใช้ซ้ำแล้วซ้ำอีก ได้แก่ อาร์เรย์ (เวกเตอร์), สแต็ก, คิว, ลิงค์ลิสต์, ต้นไม้, กราฟ, ไทร และตารางแฮช การเข้าใจวิธีการทำงาน การดำเนินการที่แต่ละฟังก์ชันมีให้ และต้นทุนโดยทั่วไปของฟังก์ชันเหล่านั้น เป็นกุญแจสำคัญในการเขียนโปรแกรมได้อย่างราบรื่น

ตอนนี้เรากำลังจะไป ทบทวนแต่ละรายการโดยนำเสนอแนวคิดหลัก การดำเนินงานทั่วไป และตัวอย่างปัญหาที่มักพบในชั้นเรียน แบบฝึกหัด และการสัมภาษณ์งานสำหรับนักพัฒนาซอฟต์แวร์

อาร์เรย์

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

ลองนึกภาพอาร์เรย์ขนาด 4 ที่บรรจุค่า 1, 2, 3 และ 4 แต่ละตำแหน่งมีค่าเป็น ดัชนี (0, 1, 2, 3) และคุณสามารถเข้าถึงองค์ประกอบใดๆ ได้โดยตรงด้วยดัชนีในเวลาคงที่ O(1) ทำให้อาร์เรย์มีประสิทธิภาพมากสำหรับการอ่านแบบสุ่ม

มีสองประเภทหลัก: อาร์เรย์หนึ่งมิติ (แถวเดียวขององค์ประกอบ) และ อาร์เรย์หลายมิติ (ตัวอย่างเช่น เมทริกซ์ ซึ่งเป็นอาร์เรย์ของอาร์เรย์) ภาษาโปรแกรมหลายภาษาเสนอทั้งสองรูปแบบนี้โดยธรรมชาติ หรือมีความแตกต่างเล็กน้อยในด้านไวยากรณ์และประสิทธิภาพ

การดำเนินการพื้นฐานกับอาร์เรย์โดยทั่วไปได้แก่:

• แทรก: การวางองค์ประกอบในตำแหน่งที่กำหนด ซึ่งในอาร์เรย์แบบคงที่อาจเกี่ยวข้องกับการเลื่อนองค์ประกอบอื่นๆ
• รับ: การเข้าถึงองค์ประกอบที่ดัชนีที่กำหนด โดยทั่วไปใช้เวลา O(1)
• ลบ: ลบหรือทำเครื่องหมายว่าว่างเปล่าสำหรับองค์ประกอบในตำแหน่งที่ระบุ โดยปกติจะทำได้โดยการเลื่อนองค์ประกอบไปทางซ้าย
• ขนาดตรวจสอบจำนวนองค์ประกอบที่จัดเก็บไว้ หรือความจุสูงสุดของอาร์เรย์

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

กองซ้อน

แบตเตอรี่ เป็นโครงสร้างข้อมูลเชิงเส้นที่ยึดหลักการ LIFO: Last In, First Out (เข้าหลัง ออกก่อน) ลองนึกภาพกองหนังสือที่วางซ้อนกัน คุณสามารถหยิบหรือวางหนังสือได้จากด้านบนเท่านั้น

พฤติกรรมนี้หมายความว่า เราจะเข้าถึงเฉพาะองค์ประกอบที่อยู่ด้านบนสุดของสแต็กเท่านั้นเราไม่สามารถลบองค์ประกอบตรงกลางได้หากไม่ลบองค์ประกอบด้านบนออกก่อน โครงสร้างนี้จึงเหมาะอย่างยิ่งสำหรับการจำลองประวัติการกระทำ (ยกเลิก) การเรียกใช้ฟังก์ชันแบบซ้อนกัน การนำทาง (ย้อนกลับ/ไปข้างหน้า) เป็นต้น

การดำเนินการกับสแต็กโดยทั่วไปมีดังนี้:

• ผลัก: เพิ่มรายการใหม่ที่ด้านบนสุด
• ป๊อป: ดึงและส่งคืนองค์ประกอบที่อยู่ด้านบนสุด เพื่อลดขนาดของสแต็ก
• ด้านบนหรือแอบดู: ตรวจสอบองค์ประกอบด้านบนโดยไม่ต้องลบออก
• มันว่างเปล่าตรวจสอบว่าแบตเตอรี่หมดหรือไม่

ในการสัมภาษณ์งาน อาจพบปัญหาต่างๆ ดังต่อไปนี้: ประเมินนิพจน์ในรูปแบบสัญกรณ์โพสต์ฟิกซ์ (RPN) การเรียงลำดับองค์ประกอบโดยใช้เพียงสแต็ก หรือการตรวจสอบว่าสตริงของวงเล็บ (และสัญลักษณ์อื่นๆ) มีความสมดุลอย่างเหมาะสมหรือไม่โดยใช้ push และ pop

ในทางปฏิบัติ การใช้งานภายในของภาษาต่างๆ จำนวนมาก (ตัวอย่างเช่น สแต็กการเรียกใช้ระบบ) ทำงานโดยยึดหลักการเดียวกันนี้ แม้ว่าเราจะมองไม่เห็นหลักการเหล่านั้นโดยตรงก็ตาม

คิว

หาง นี่เป็นโครงสร้างข้อมูลเชิงเส้นอีกแบบหนึ่ง แต่แทนที่จะใช้หลักการ LIFO (เข้าก่อนออกก่อน) มันใช้โมเดล FIFO (เข้าก่อนออกก่อน) ตัวอย่างที่ชัดเจนที่สุดคือแถวของผู้คนที่รอซื้อตั๋วในโรงภาพยนตร์

ในคิวมาตรฐาน องค์ประกอบต่างๆ คือ พวกเขาเพิ่มเข้ามาในตอนท้ายและถอนออกในตอนเริ่มต้นมาก่อนได้ก่อน ทำให้เหมาะสำหรับการจัดการงานที่ค้างอยู่ กระบวนการของระบบปฏิบัติการ คำขอจากเซิร์ฟเวอร์ คิวการพิมพ์ ฯลฯ

การดำเนินการคิวขั้นพื้นฐานประกอบด้วย:

• เข้าคิว: เพิ่มรายการใหม่ที่ท้ายคิว
• คิว: ลบและคืนค่าองค์ประกอบที่อยู่ตอนต้น
• ด้านหน้าหรือด้านบน: ตรวจสอบรายการแรกโดยไม่ต้องนำออก
• มันว่างเปล่าตรวจสอบว่าคิวว่างหรือไม่

ในการแข่งขันเขียนโปรแกรม เป็นเรื่องปกติที่พวกเขาจะถามคุณ เช่น สร้างโครงสร้างข้อมูลแบบ Stack โดยใช้คิวสองตัวกลับลำดับขององค์ประกอบ k ตัวแรกในคิวโดยไม่เปลี่ยนแปลงส่วนที่เหลือ หรือสร้างเลขฐานสองตั้งแต่ 1 ถึง n โดยใช้คุณสมบัติ FIFO ของคิว

นอกจากหางแบบพื้นฐานแล้ว ยังมีรูปแบบอื่นๆ อีก เช่น หางทรงกลมคิวลำดับความสำคัญหรือคิวคู่ (deque) ซึ่งนำเสนอการดำเนินการเพิ่มเติมและปรับปรุงประสิทธิภาพในบางสถานการณ์

รายการที่เชื่อมโยง

รายการเชื่อมโยง โครงสร้างแบบลิสต์เชื่อมโยง (Linked List) ก็เป็นโครงสร้างเชิงเส้นเช่นกัน แต่ในเชิงโครงสร้างภายในนั้นแตกต่างจากอาร์เรย์มาก แทนที่จะใช้บล็อกหน่วยความจำที่ต่อเนื่องกัน มันประกอบด้วยโหนดที่กระจัดกระจายซึ่งเชื่อมต่อกันด้วยการอ้างอิงหรือตัวชี้

แต่ละโหนดโดยทั่วไปประกอบด้วยสองส่วน: ข้อมูล ประกอบด้วยข้อมูลที่จะถูกจัดเก็บและตัวชี้ (หรือหลายตัว) ที่ชี้ไปยังโหนดถัดไปในลำดับ (และในกรณีของรายการเชื่อมโยงสองทาง ก็จะชี้ไปยังโหนดก่อนหน้าด้วย) รายการจะถูกจัดการผ่านการอ้างอิงไปยังส่วนหัว ซึ่งชี้ไปยังโหนดแรก และในรายการที่ซับซ้อนกว่านั้น จะมีการเก็บรักษาการอ้างอิงไปยังส่วนท้ายไว้ด้วย

มีสองรูปแบบหลัก:

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

การดำเนินการทั่วไปบนรายการเชื่อมโยง ได้แก่:

• แทรกที่ส่วนหัว: แทรกโหนดใหม่ที่ต้นรายการ
• แทรกที่ท้ายเพิ่มโหนดเข้าไปที่ส่วนท้ายสุด และอัปเดตคิวหากมีอยู่แล้ว
• ลบ: ลบโหนดที่ระบุ โดยปรับตัวชี้ของโหนดข้างเคียง
• ลบที่ส่วนหัวลบโหนดแรกและย้ายส่วนหัวไปยังโหนดถัดไป
• ค้นหา: วนลูปผ่านรายการเพื่อค้นหาค่าที่ต้องการ
• มันว่างเปล่าตรวจสอบว่าส่วนหัวเป็นค่าว่างหรือไม่ ซึ่งหมายความว่ารายการไม่มีองค์ประกอบใดๆ

ปัญหาลักษณะนี้พบได้มากมายในห้องเรียนและการสัมภาษณ์งาน กลับลำดับรายการเชื่อมโยงตรวจสอบว่ามีวงจรหรือไม่ (โดยปกติจะใช้อัลกอริธึม "เต่ากับกระต่าย") หาโหนด N โดยนับจากท้าย หรือลบโหนดที่ซ้ำกัน โดยต้องจัดการกับตัวชี้อย่างระมัดระวังเสมอ

โครงสร้างข้อมูลแบบลิสต์เชื่อมโยง (Linked List) ถูกนำมาใช้กันอย่างแพร่หลายในการใช้งานต่างๆ ตารางแฮชที่มีการเชื่อมโยงรายการความสัมพันธ์ในกราฟ และโครงสร้างข้อมูลแบบไดนามิกที่องค์ประกอบถูกแทรกและลบออกบ่อยครั้ง

ต้นไม้

ต้นไม้หนึ่งต้น โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างข้อมูลแบบลำดับชั้นที่ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบ แตกต่างจากกราฟทั่วไป ต้นไม้ไม่มีวงจร: จะมีราก ลูก พ่อแม่ พี่น้อง ใบ ระดับ และต้นไม้ย่อยเสมอ โดยมีการจัดระเบียบแบบ "ครอบครัว" หรือ "แผนผังองค์กร"

ต้นไม้มีประโยชน์มากเมื่อเราต้องการ แสดงถึงความสัมพันธ์แบบลำดับชั้น หรือแบ่งปัญหาใหญ่ให้เป็นปัญหาย่อยๆ เช่น ระบบไฟล์ เมนู โครงสร้าง DOM ในเบราว์เซอร์ แผนผังการตัดสินใจในปัญญาประดิษฐ์ เป็นต้น

มีต้นไม้หลากหลายสายพันธุ์ ได้แก่:

• ต้นไม้ N-aryแต่ละโหนดสามารถมีโหนดลูกได้จำนวนมาก (และอาจมีจำนวนมาก)
• ต้นไม้สมดุล: รักษาโครงสร้างสาขาให้มีความลึกใกล้เคียงกันเพื่อหลีกเลี่ยงประสิทธิภาพการทำงานที่ลดลง
• ต้นไม้ไบนารีแต่ละโหนดจะมีลูกได้สูงสุดสองตัว (ซ้ายและขวา)
• ต้นไม้ค้นหาแบบไบนารี (BST): โครงสร้างข้อมูลแบบต้นไม้ไบนารีที่มีคุณสมบัติว่า ค่าทุกอย่างทางด้านซ้ายของโหนดจะมีค่าน้อยกว่า และค่าทุกอย่างทางด้านขวาจะมีค่ามากกว่า (โดยพิจารณาจากเกณฑ์การเรียงลำดับบางอย่าง)
• ต้นไม้ AVL สีแดง-ดำ 2-3 และรูปแบบอื่นๆนี่คือโครงสร้างข้อมูลแบบต้นไม้ค้นหาที่สมดุล ซึ่งรับประกันขีดจำกัดความซับซ้อนที่ดีในการแทรก ลบ และค้นหาข้อมูล

ในทางปฏิบัติ แบบฝึกหัดที่ใช้บ่อยที่สุดคือ... ต้นไม้ไบนารี และ y ต้นไม้ค้นหาไบนารีปัญหาทั่วไปได้แก่ การคำนวณความสูงของต้นไม้ การหาค่าสูงสุดลำดับที่ k ใน BST การแสดงรายการโหนดที่อยู่ห่างจากรากในระยะทางที่กำหนด หรือการหาบรรพบุรุษของโหนดใดโหนดหนึ่ง

นอกจากนี้ อัลกอริทึมการท่องไปในโครงสร้างข้อมูล (แบบเรียงลำดับก่อน แบบเรียงลำดับตาม) แบบเรียงลำดับหลัง และแบบทีละระดับ ยังเป็นพื้นฐานสำคัญสำหรับกระบวนการต่างๆ ที่ตามมาอีกมากมาย เช่น การพิมพ์แบบเรียงลำดับ การประเมินนิพจน์ การแปลงโครงสร้างข้อมูลเป็นต้นไม้ และการแปลงกลับจากต้นไม้ เป็นต้น

กราฟ

กราฟ มันเป็นการขยายแนวคิดของต้นไม้โดยอนุญาตให้มีวงจรและการเชื่อมต่อแบบใดก็ได้ระหว่างโหนด ประกอบด้วยเซตของจุดยอด (โหนด) และเซตของขอบที่เชื่อมต่อจุดยอดเป็นคู่ๆ ซึ่งบางครั้งอาจมีน้ำหนักหรือต้นทุนที่เกี่ยวข้องด้วย

กราฟมีหลายประเภท: ไม่มีทิศทาง (ขอบไม่มีทิศทางที่แน่นอน ความสัมพันธ์เป็นแบบสองทิศทาง) และ กำกับ (ขอบมีจุดเริ่มต้นและจุดสิ้นสุด) นอกจากนี้ยังสามารถจำแนกได้เป็นขอบที่มีน้ำหนักหรือไม่มีน้ำหนัก ขอบที่เชื่อมต่อกันหรือไม่เชื่อมต่อกัน ขอบที่มีหรือไม่มีวัฏจักร เป็นต้น

ในการเขียนโปรแกรม กราฟมักจะแสดงด้วยสองวิธีพื้นฐาน:

• เมทริกซ์ประชิด: เมทริกซ์ที่แต่ละช่องแสดงว่ามีเส้นเชื่อมระหว่างจุดยอด i และ j หรือไม่ (และอาจรวมถึงน้ำหนักของเส้นเชื่อมด้วย)
• รายการที่อยู่ติดกัน: สำหรับแต่ละจุดยอด จะมีการจัดเก็บรายการของจุดยอดข้างเคียง ซึ่งช่วยประหยัดหน่วยความจำในกราฟแบบเบาบาง

อัลกอริทึมการท่องไปในแผนที่แบบคลาสสิกที่สุดคือ... การค้นหาแบบกว้าง (BFS) และ การค้นหาเชิงลึก (DFS)ทั้งสองอย่างถูกใช้เป็นองค์ประกอบพื้นฐานสำหรับปัญหามากมาย เช่น การตรวจสอบว่ากราฟเชื่อมต่อกันหรือไม่ การตรวจจับวงจร การค้นหาส่วนประกอบที่เชื่อมต่อกัน เป็นต้น

ในการทดสอบทางเทคนิค มักจะถูกขอให้เขียนโปรแกรมค้นหาแบบ BFS และ DFS ตรวจสอบว่ากราฟเป็นโครงสร้างต้นไม้หรือไม่ นับจำนวนขอบ หรือทำการค้นหา เส้นทางที่สั้นที่สุด ระหว่างสองโหนด (ตัวอย่างเช่น บนแผนที่เมือง) โดยใช้อัลกอริทึมต่างๆ เช่น Dijkstra หรือ BFS ในกราฟที่ไม่ถ่วงน้ำหนัก

ต้นไม้แบบลองหรือคำนำหน้า

การทดลอง (หรือโครงสร้างข้อมูลแบบต้นไม้คำนำหน้า) เป็นโครงสร้างข้อมูลรูปทรงต้นไม้ที่ได้รับการปรับให้เหมาะสมสำหรับการจัดการสตริงของตัวอักษร โดยเฉพาะอย่างยิ่งมีประโยชน์เมื่อทำงานกับพจนานุกรมคำ ระบบเติมคำอัตโนมัติ หรือการค้นหาคำนำหน้า

ในโครงสร้างข้อมูลแบบไทร (trie) แต่ละโหนดโดยทั่วไปจะแทนอักขระ และเส้นทางจากโหนดรากไปยังโหนดบางโหนดจะบ่งบอกถึงอักขระนั้น เต็มคำโดยปกติแล้ว โหนดคำสุดท้ายจะถูกทำเครื่องหมายด้วยวิธีใดวิธีหนึ่ง (เช่น ด้วยตัวบ่งชี้แบบบูลีน) เพื่อแยกแยะออกจากคำนำหน้าธรรมดา

ถ้าเราเก็บคำว่า “top”, “thus” และ “their” ไว้ในโครงสร้างข้อมูลแบบไทร (trie) เราจะใช้เส้นทางเริ่มต้นร่วมกันบางส่วนสำหรับคำที่ขึ้นต้นด้วยตัวอักษรเดียวกัน ทำให้สามารถค้นหาและแนะนำคำโดยใช้คำนำหน้าได้ เวลาที่มีประสิทธิภาพมากโดยจะแปรผันตามความยาวของคำที่เรากำลังค้นหา ไม่ใช่ตามจำนวนคำทั้งหมดที่จัดเก็บไว้

การดำเนินการและปัญหาที่พบบ่อยเกี่ยวกับการใช้ไทร (Tries) ได้แก่: นับจำนวนคำที่ถูกจัดเก็บไว้พิมพ์คำทั้งหมดตามลำดับตัวอักษร จัดเรียงองค์ประกอบของอาร์เรย์โดยการแทรกเข้าไปในไทร สร้างคำที่ถูกต้องจากชุดตัวอักษร หรือสร้างโครงสร้างที่คล้ายกับพจนานุกรม T9

ในบริบทของการสัมภาษณ์ โครงสร้างพื้นฐานนี้อาจไม่ใช่สิ่งที่บริษัทต่างๆ จะถามถึงบ่อยที่สุด แต่ก็เป็นสิ่งที่พบเห็นได้ทั่วไปในบริษัทที่ทำงานร่วมกับ... การค้นหา การประมวลผลคำ หรือระบบแนะนำ.

ตารางแฮชและการแฮช

การแฮช เป็นเทคนิคในการกำหนดคีย์ตัวเลข (แฮช) ให้กับข้อมูลแต่ละส่วนอย่างเป็นระบบ เพื่อให้เราสามารถจัดเก็บและเรียกใช้ข้อมูลได้ในเวลาคงที่ โดยใช้คีย์นั้นเป็นดัชนีในโครงสร้างภายใน ซึ่งโดยทั่วไปคืออาร์เรย์

La ตารางแฮช นี่คือโครงสร้างข้อมูลที่ใช้ประโยชน์จากกลไกนี้ แต่ละองค์ประกอบจะถูกจัดเก็บในรูปแบบคู่คีย์-ค่า: คีย์จะถูกแปลงเป็นดัชนีตารางโดยใช้ฟังก์ชันแฮช และค่า (หรือการอ้างอิงถึงค่า) จะถูกจัดเก็บไว้ที่นั่น ในภายหลัง เมื่อต้องการค้นหา ก็เพียงแค่ทำการแฮชคีย์อีกครั้งและเข้าถึงตำแหน่งที่ตรงกัน

ประสิทธิภาพของตารางแฮชขึ้นอยู่กับปัจจัยสำคัญสามประการ ได้แก่: ฟังก์ชันแฮช เลือกแล้ว (คุณต้องกระจายปุ่มให้ดีเพื่อหลีกเลี่ยงการกระจุกตัว) ขนาดโต๊ะ (ขนาดไม่เพียงพอทำให้เกิดการชนกันหลายครั้ง) และ วิธีการจัดการการชนกัน (การเชื่อมโยงด้วยลิสต์แบบเชื่อมโยง, การกำหนดแอดเดรสแบบเปิด ฯลฯ) สิ่งนี้คล้ายกับ ดัชนีในฐานข้อมูลซึ่งการเลือกโครงสร้างที่เหมาะสมจะช่วยปรับปรุงการค้นหาและการเข้าถึงให้ดียิ่งขึ้น

แบบฝึกหัดการเขียนโปรแกรมแฮชทั่วไปมักต้องการตัวอย่างเช่น: ค้นหาคู่สมมาตรในอาร์เรย์การสร้างกำหนดการเดินทางทั้งหมดขึ้นใหม่จากเที่ยวบินแต่ละเที่ยว การตรวจสอบอย่างรวดเร็วว่าอาร์เรย์หนึ่งเป็นเซตย่อยของอีกอาร์เรย์หนึ่งหรือไม่ หรือการตรวจสอบว่าอาร์เรย์สองอาร์เรย์ไม่ทับซ้อนกัน ทั้งหมดนี้โดยใช้ประโยชน์จากการค้นหาโดยประมาณ O(1) ของตารางแฮช

ในภาษาสมัยใหม่ส่วนใหญ่ โครงสร้างเช่น แผนที่, พจนานุกรม, แผนที่แฮช หรือเซตแฮช ระบบเหล่านี้ใช้ตารางแฮชเป็นกลไกภายใน แม้ว่าจะมีอินเทอร์เฟซระดับสูงให้โปรแกรมเมอร์ใช้งานได้ก็ตาม

ความสัมพันธ์ระหว่างอัลกอริทึมและโครงสร้างข้อมูลเป็นอย่างไร

การเลือกโครงสร้างข้อมูลส่งผลโดยตรงต่ออัลกอริทึมที่เหมาะสมและระดับความซับซ้อนของอัลกอริทึมนั้น ตัวอย่างเช่น อัลกอริทึมการค้นหาเชิงเส้นบนโครงสร้างข้อมูลแบบเชิงเส้น (linear search algorithm) รายการที่ไม่มีลำดับ มันวนลูปผ่านองค์ประกอบทีละรายการ หากเราเปลี่ยนโครงสร้างเป็นต้นไม้ค้นหาแบบสมดุลหรือตารางแฮช เราจะได้เวลาที่ดีขึ้นมาก

ตัวอย่างเช่น หากคุณต้องการค้นหาคีย์ซ้ำๆ ในชุดข้อมูลขนาดใหญ่ การจัดเก็บข้อมูลในรูปแบบอื่นอาจไม่เหมาะสม ตารางแฮชหรือต้นไม้ค้นหาแบบไบนารี มันช่วยให้คุณออกแบบอัลกอริธึมการค้นหาที่เร็วกว่าการใช้แถวข้อมูลที่ไม่เรียงลำดับแบบธรรมดามาก หลักการเดียวกันนี้สามารถนำไปใช้กับคิวลำดับความสำคัญและฮีปสำหรับการจัดตารางเวลาหรืออัลกอริธึมการหาเส้นทางที่สั้นที่สุดได้เช่นกัน

ในทางกลับกัน เมื่อออกแบบอัลกอริทึม คุณมักจะตระหนักว่าคุณต้องการคุณสมบัติบางอย่าง เช่น การเข้าถึงด้วยดัชนี การแทรกข้อมูลอย่างรวดเร็วที่จุดเริ่มต้น การสำรวจแบบลำดับชั้น การค้นหาแบบใช้คำนำหน้า เป็นต้น ความต้องการเหล่านี้จะเป็นตัวกำหนดการเลือกโครงสร้างของคุณ อาร์เรย์, รายการ, ต้นไม้, กราฟ, ตารางแฮช, ไทร...

การผสมผสานที่เหมาะสมระหว่างอัลกอริทึมและโครงสร้างข้อมูลนี้เองที่ทำให้สามารถสร้างแอปพลิเคชันที่ซับซ้อนได้ มีประสิทธิภาพและปรับขนาดได้หากปราศจากรากฐานที่ดี โซลูชันมักจะทำงานช้า เข้าใจยาก บำรุงรักษายาก หรือปรับเปลี่ยนไม่ได้เลยเมื่อปริมาณข้อมูลเพิ่มมากขึ้น

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

วิธีการเรียนรู้โครงสร้างข้อมูลและอัลกอริธึม

หลายคนรู้สึกติดขัดเมื่อพยายามเรียนรู้ด้วยตนเองโดยใช้แพลตฟอร์มต่างๆ เช่น LeetCode หรือ Codewarsเป็นเรื่องปกติที่จะเริ่มต้นด้วยแบบฝึกหัดที่ "ง่าย" แต่ก็ยังไม่รู้ว่าจะแก้ปัญหาอย่างไร จนสุดท้ายก็ไปดูเฉลยแล้วก็ยังไม่เข้าใจว่าจะทำซ้ำได้อย่างไร

แนวทางปฏิบัติที่เป็นรูปธรรมมักจะผสมผสานองค์ประกอบหลายอย่างเข้าด้วยกัน: ก. คำอธิบายเชิงทฤษฎีที่ดี โครงสร้างและอัลกอริทึมแต่ละแบบประกอบด้วยตัวอย่างภาพประกอบ แบบฝึกหัดพร้อมคำแนะนำมากมาย และหากเป็นไปได้ จะมีผู้ที่มีประสบการณ์คอยให้ความช่วยเหลือเพื่อพัฒนาทักษะการแก้ปัญหาของคุณให้ดียิ่งขึ้น

ในโลกที่ใช้ภาษาสเปน มีผู้เชี่ยวชาญที่มีประสบการณ์มากมายที่ได้มีส่วนช่วยอำนวยความสะดวกในการเรียนรู้ดังกล่าว ตัวอย่างหนึ่งคืองานของ ครูผู้มีประสบการณ์ด้านธุรกิจและการศึกษา ผู้ซึ่งได้ตีพิมพ์หนังสือและหลักสูตรเกี่ยวกับพื้นฐานการเขียนโปรแกรม ภาษาจาวา โครงสร้างข้อมูล และโจทย์การเขียนโปรแกรมพร้อมเกม ทำให้แนวคิดเหล่านี้เข้าถึงได้ง่ายในรูปแบบที่สนุกสนานและนำไปใช้ได้จริงในโครงการต่างๆ

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

หากคุณติดขัด การทำตามเส้นทางที่กำหนดไว้จะช่วยได้: เริ่มต้นด้วยอาร์เรย์และลิสต์โดยเริ่มจากโครงสร้างข้อมูลแบบ Stack และ Queue จากนั้นเป็น Tree และกราฟพื้นฐาน และสุดท้ายคือ Hash Table และ Trie โดยสลับระหว่างคำอธิบายเชิงทฤษฎี ตัวอย่างโค้ดขนาดเล็ก และแบบฝึกหัดด้วยตนเองมากมาย

เมื่อเตรียมตัวสำหรับการสัมภาษณ์ ควรทบทวนไม่เพียงแต่โครงสร้างเท่านั้น แต่ยังรวมถึง... อัลกอริธึมบรูทฟอร์ซ และอัลกอริธึมแบบคลาสสิกที่เกี่ยวข้อง (การสำรวจ การค้นหา การเรียงลำดับ การย้อนกลับแบบง่าย การเขียนโปรแกรมเชิงพลวัตขั้นพื้นฐาน) และตรวจสอบให้แน่ใจว่าคุณสามารถอธิบายด้วยวาจาได้ว่าเหตุใดคุณจึงเลือกโครงสร้างเฉพาะนั้น และอะไรคือผลลัพธ์ ความซับซ้อนของโซลูชันของคุณ.

เมื่อเวลาผ่านไปและ ความสม่ำเสมอสิ่งที่ตอนแรกดูเหมือนจะเป็นกำแพง กลับกลายเป็นชุดเครื่องมือที่คุ้นเคยซึ่งคุณใช้ได้อย่างเป็นธรรมชาติเมื่อเผชิญกับปัญหาใหม่ๆ

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