ข้ามไปเนื้อหา

โครงสร้างข้อมูล

จากวิกิพีเดีย สารานุกรมเสรี
ตารางแฮช หนึ่งในโครงสร้างข้อมูล

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูล (อังกฤษ: data structure) คือวิธีการจัดระเบียบและจัดเก็บข้อมูล ซึ่งมักได้รับการเลือกใช้เพื่อให้สามารถเข้าถึงข้อมูลได้อย่างมีประสิทธิภาพ[1][2][3] โครงสร้างข้อมูลคือการทำให้แบบชนิดข้อมูล [en]เกิดขึ้นจริง (physical implementation) โดยกำหนดวิธีการจัดระเบียบข้อมูล รูปแบบการจัดเก็บข้อมูล ตลอดจนฟังก์ชันหรือการดำเนินการที่ใช้จัดการกับข้อมูลดังกล่าว

โครงสร้างข้อมูลมีความสัมพันธ์อย่างใกล้ชิดกับแบบชนิดข้อมูลนามธรรม (Abstract Data Type; ADT)[4] โดยโครงสร้างข้อมูลอธิบายวิธีการแทนข้อมูลในหน่วยความจำและวิธีการดำเนินการกับข้อมูลนั้น ขณะที่แบบชนิดข้อมูลนามธรรมอธิบายรูปแบบเชิงตรรกะหรือโครงสร้างเชิงพีชคณิตของชนิดข้อมูล กล่าวคือ ระบุว่ามีการดำเนินการใดบ้างที่สามารถกระทำได้และให้ผลลัพธ์อย่างไร โดยไม่ระบุวิธีการนำการดำเนินการเหล่านั้นไปสร้างจริง ตัวอย่างเช่น กองซ้อน (stack) ในฐานะแบบชนิดข้อมูลนามธรรมกำหนดเพียงการดำเนินการ เช่น push และ pop ส่วนโครงสร้างข้อมูลอาจนำสแตกไปสร้างจริงด้วยแถวลำดับ (array) หรือรายการโยง (linked list) (ซึ่งให้ผลลัพธ์เหมือนกันแต่มีรายละเอียดการทำงานแตกต่างกัน[4] อย่างไรก็ตาม นักวิชาการบางส่วนไม่ได้แยกใช้คำว่า "แบบชนิดข้อมูลนามธรรม" ออกจาก "โครงสร้างข้อมูล" อย่างชัดเจน แต่ใช้คำว่า "โครงสร้างข้อมูล" เพื่อหมายถึงทั้งลักษณะเชิงตรรกะและการนำไปสร้างจริงของชนิดข้อมูล[5]

ตัวอย่าง

[แก้]
ลำดับชั้นมาตรฐานของแบบชนิดข้อมูลในภาษาโปรแกรม Python 3

โครงสร้างข้อมูลมีหลายประเภท ซึ่งโดยทั่วไปสร้างขึ้นจากชนิดข้อมูลพื้นฐาน (primitive data type) ที่เรียบง่ายกว่า ตัวอย่างที่เป็นที่รู้จัก ได้แก่:[6]

  • แถวลำดับ (array): คือชุดของข้อมูลหลายตัวที่จัดเรียงตามลำดับ โดยทั่วไปสมาชิกทั้งหมดจะเป็นชนิดข้อมูลเดียวกัน (ทั้งนี้ขึ้นอยู่กับภาษาโปรแกรม บางภาษาอาจบังคับให้สมาชิกทุกตัวเป็นชนิดเดียวกัน ขณะที่บางภาษาอนุญาตให้แต่ละตัวเป็นชนิดข้อมูลที่แตกต่างกันได้) สมาชิกแต่ละตัวเข้าถึงได้ด้วยดัชนีจำนวนเต็ม (integer index) ที่ระบุตำแหน่งของข้อมูล โดยทั่วไปแถวลำดับจะจัดเก็บสมาชิกไว้ในพื้นที่หน่วยความจำที่ต่อเนื่องกัน แม้ว่าจะไม่ใช่ข้อกำหนดเสมอไป แถวลำดับอาจมีขนาดคงที่หรือสามารถปรับขนาดได้
  • รายการโยง (linked list) หรือเรียกสั้น ๆ ว่า ลิสต์ (list) คือโครงสร้างข้อมูลเชิงเส้นที่ประกอบด้วยสมาชิกซึ่งเรียกว่าโหนด (node) โดยแต่ละโหนดเก็บค่าของตนเองและมีตัวชี้ไปยังโหนดถัดไปในรายการโยง ข้อได้เปรียบหลักของรายการโยงเหนือแถวลำดับคือสามารถแทรกหรือลบข้อมูลได้อย่างมีประสิทธิภาพโดยไม่ต้องย้ายข้อมูลส่วนที่เหลือ อย่างไรก็ตาม การดำเนินการบางอย่าง เช่น การเข้าถึงสมาชิกแบบสุ่ม (random access) จะทำได้ช้ากว่าแถวลำดับ
  • เรคอร์ด [en] (record) หรือเรียกอีกชื่อว่า ทูเพิล (tuple) หรือสตรักต์ (struct) เป็นโครงสร้างข้อมูลแบบรวม (aggregate data structure) ซึ่งเป็นค่าที่ประกอบด้วยค่าอื่น ๆ หลายค่า โดยทั่วไปมีจำนวนและลำดับคงที่ และเข้าถึงสมาชิกผ่านชื่อ สมาชิกของเรคอร์ดมักเรียกว่าเขตข้อมูล (field) หรือสมาชิก (member) ในการเขียนโปรแกรมเชิงวัตถุ (object-oriented programming; OOP) เรคอร์ดมักเรียกว่าโครงสร้างข้อมูลแบบดั้งเดิม (plain old data structure; POD) เพื่อแยกความแตกต่างจากวัตถุ[7]
  • ยูเนียน (union) เป็นชนิดข้อมูลที่สามารถเก็บข้อมูลได้หลายชนิดตามที่กำหนดไว้ แต่ในเวลาใดเวลาหนึ่งจะเก็บค่าได้เพียงชนิดเดียวเท่านั้น สมาชิกทั้งหมดใช้พื้นที่หน่วยความจำร่วมกัน จึงมีขนาดเท่ากับสมาชิกที่มีขนาดใหญ่ที่สุด ยูเนียนแตกต่างจากเรคอร์ด [en]ซึ่งสามารถเก็บค่าของสมาชิกทุกตัวได้พร้อมกัน แท็กยูเนียน (tagged union) หรือเรียกว่า ดิสคริมิเนเต็ดยูเนียน (discriminated union) แวเรียนต์เรคอร์ด (variant record) หรือ ผลรวมชนิดข้อมูล (sum type) เป็นยูเนียนที่มีฟิลด์เพิ่มเติมสำหรับระบุชนิดของข้อมูลที่กำลังจัดเก็บอยู่ ทำให้สามารถใช้งานยูเนียนได้อย่างปลอดภัยและลดข้อผิดพลาดจากการเข้าถึงข้อมูลผิดชนิด[ต้องการอ้างอิง]
  • ตารางแฮช (hash table) หรือแฮชแมป (hash map) เป็นโครงสร้างข้อมูลที่ช่วยให้สามารถค้นหาค่าจากคีย์ได้อย่างรวดเร็ว โดยใช้ฟังก์ชันแฮช (hash function) เพื่อแปลงคีย์ให้เป็นตำแหน่งดัชนีในแถวลำดับ ทำให้โดยเฉลี่ยสามารถเข้าถึงข้อมูลได้ในเวลาเชิงคงที่ (constant time) ตารางแฮชมักใช้ในพจนานุกรม แคช และการทำดัชนีฐานข้อมูล อย่างไรก็ตาม อาจเกิดการชนกันของค่าแฮช (hash collision) ซึ่งส่งผลต่อประสิทธิภาพ จึงมีการใช้เทคนิคต่าง ๆ เช่น chaining และ open addressing เพื่อจัดการปัญหาดังกล่าว
  • กราฟ (graph) เป็นโครงสร้างข้อมูลที่ประกอบด้วยโหนดซึ่งเชื่อมต่อกันด้วยเส้นเชื่อม (edge) เพื่อแทนความสัมพันธ์ระหว่างสิ่งต่าง ๆ กราฟสามารถใช้สร้างแบบจำลองของเครือข่ายสังคม เครือข่ายคอมพิวเตอร์ ระบบขนส่ง และระบบอื่น ๆ อีกมากมาย โดยประกอบด้วยจุดยอด (vertex) และเส้นเชื่อม (edge) กราฟอาจเป็นแบบมีทิศทาง (directed) หรือไม่มีทิศทาง (undirected) และอาจมีวัฏจักร (cycle) หรือไม่มีวัฏจักรก็ได้ ขั้นตอนวิธีสำหรับการท่องกราฟที่สำคัญ ได้แก่ การค้นหาแบบกว้างก่อน (breadth-first search; BFS) และการค้นหาแบบลึกก่อน (depth-first search; DFS)
  • กองซ้อน (stack) และแถวคอย (queue): เป็นชนิดข้อมูลนามธรรม (abstract data type) ที่สามารถนำไปสร้างด้วยแถวลำดับหรือรายการโยงได้ กองซ้อนมีการดำเนินการหลักสองอย่าง ได้แก่ push (เพิ่มข้อมูลไว้ด้านบนสุดของสแตก) และ pop (นำข้อมูลด้านบนสุดออก) ซึ่งทำงานตามหลัก "เข้าหลัง ออกก่อน" (Last In, First Out; LIFO) ส่วนแถวคอยมีการดำเนินการหลักคือ enqueue (เพิ่มข้อมูลที่ท้ายแถวคอย) และ dequeue (นำข้อมูลจากหน้าแถวคอยออก) ซึ่งทำงานตามหลัก "เข้าก่อน ออกก่อน" (First In, First Out; FIFO)
  • ต้นไม้ (tree) เป็นโครงสร้างข้อมูลที่ใช้แทนลำดับชั้นของข้อมูล ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยเส้นเชื่อม โดยมีโหนดหนึ่งเป็นราก (root) และโหนดอื่น ๆ เป็นส่วนย่อย (subtree) ต้นไม้ถูกใช้อย่างแพร่หลายในขั้นตอนวิธีและการจัดเก็บข้อมูลหลายรูปแบบ ต้นไม้ที่นิยมใช้ ได้แก่ ต้นไม้ทวิภาค (binary tree) โดยเฉพาะฮีป (heap) ต้นไม้ AVL และต้นไม้แบบบี (B-tree) ซึ่งช่วยให้การค้นหา การเรียงลำดับ และการแทนข้อมูลแบบลำดับชั้นทำได้อย่างมีประสิทธิภาพ
  • ทรัย (trie) หรือ ต้นไม้คำนำหน้า (prefix tree) เป็นโครงสร้างข้อมูลแบบต้นไม้ชนิดพิเศษที่ใช้สำหรับค้นหาสตริงได้อย่างมีประสิทธิภาพ โดยแต่ละโหนดแทนอักขระหนึ่งตัวของสตริง และเส้นเชื่อมระหว่างโหนดแทนลำดับของอักขระ โครงสร้างนี้เหมาะสำหรับงานต่าง ๆ เช่น ระบบเติมคำอัตโนมัติ (autocomplete) ระบบตรวจสอบการสะกดคำ (spell-checking) และการสร้างพจนานุกรม เนื่องจากสามารถค้นหาและดำเนินการกับข้อมูลตามคำนำหน้าของสตริงได้อย่างรวดเร็ว
  • เซต (set) เป็นโครงสร้างข้อมูลที่ใช้เก็บสมาชิกที่ไม่ซ้ำกันและไม่มีลำดับ การดำเนินการที่สำคัญ ได้แก่ การเพิ่มและลบสมาชิก การตรวจสอบว่าสมาชิกอยู่ในเซตหรือไม่ รวมถึงการดำเนินการทางเซต เช่น ยูเนียน อินเตอร์เซกชัน และผลต่างของเซต

การใช้งาน

[แก้]

โครงสร้างข้อมูลที่มีประสิทธิภาพมีความสำคัญต่อการจัดการชุดข้อมูลขนาดใหญ่ และเป็นพื้นฐานสำคัญของการออกแบบขั้นตอนวิธี ฐานข้อมูลเชิงสัมพันธ์มักใช้ต้นไม้แบบบีเป็นดัชนี (index) สำหรับการค้นคืนข้อมูล[8] ขณะที่คอมไพเลอร์มักใช้ตารางแฮชในการค้นหาตัวระบุ (identifier) ระบบไฟล์และเสิร์ชเอนจินก็อาศัยโครงสร้างข้อมูลเฉพาะทางอย่างกว้างขวางเช่นกัน[9][10] ร็อบ ไพก์ (Rob Pike) นักวิทยาศาสตร์คอมพิวเตอร์และโปรแกรมเมอร์ชาวแคนาดา ผู้ร่วมสร้างภาษาโปรแกรมโกและระบบปฏิบัติการ Plan 9 กล่าวว่า การเลือกใช้โครงสร้างข้อมูลมักส่งผลต่อประสิทธิภาพของโปรแกรมมากกว่าการเลือกใช้ขั้นตอนวิธี[11] เนื่องจากขั้นตอนวิธีที่เหมาะสมมักเห็นได้ชัดอยู่แล้ว โครงสร้างข้อมูลถูกใช้เพื่อจัดระเบียบข้อมูลทั้งในหน่วยเก็บข้อมูลหลัก (แรม) และหน่วยเก็บข้อมูลสำรอง เช่น ดิสก์จัดเก็บข้อมูล[12]

การทำให้เกิดผล

[แก้]

การนำโครงสร้างข้อมูลไปใช้ให้เกิดผล (implementation) คือการเขียนชุดของฟังก์ชันหรือโปรแกรมย่อย (subroutines) เช่น การแทรกข้อมูล การลบข้อมูล การท่องโครงสร้างข้อมูล หรือการค้นหาข้อมูล เพื่อสร้างและจัดการอินสแตนซ์ของโครงสร้างข้อมูลนั้น โครงสร้างข้อมูลสามารถนำไปสร้างได้ด้วยภาษาโปรแกรมและเทคนิคการเขียนโปรแกรมที่หลากหลายโครงสร้างข้อมูลเป็นการนำแนวคิดไปใช้งานจริง (concrete implementation) เพียงรูปแบบหนึ่ง แตกต่างจากแบบชนิดข้อมูลนามธรรม (ADT) ซึ่งอธิบายพฤติกรรมและการดำเนินการของข้อมูลโดยไม่ขึ้นกับวิธีการนำไปใช้งาน ชนิดข้อมูลนามธรรมเดียวกันอาจมีโครงสร้างข้อมูลที่ใช้สร้างได้หลายรูปแบบ เช่น ADT แบบลิสต์ (list)[13] อาจนำไปใช้งานด้วยรายการโยงหรือแถวลำดับพลวัตก็ได้ ดังนั้น ประสิทธิภาพของโครงสร้างข้อมูลจึงขึ้นอยู่กับวิธีการนำไปใช้งานจริง และมักประเมินจากทั้งการวิเคราะห์เชิงทฤษฎีและการทดสอบสมรรถนะ (benchmark)[14]

โครงสร้างข้อมูลตั้งอยู่บนพื้นฐานของความสามารถของคอมพิวเตอร์ในการจัดเก็บและเข้าถึงข้อมูลที่ตำแหน่งต่าง ๆ ในหน่วยความจำ ซึ่งแต่ละตำแหน่งจะระบุด้วยแอดเดรส (address) ที่โปรแกรมสามารถอ้างอิงและจัดการได้ โครงสร้างข้อมูลบางชนิด เช่น แถวลำดับและเรคอร์ด อาศัยการคำนวณแอดเดรสของสมาชิกจากตำแหน่งเริ่มต้นและออฟเซต (offset) โดยใช้การคำนวณทางคณิตศาสตร์ ในทางตรงกันข้าม โครงสร้างข้อมูลแบบเชื่อมโยง เช่น รายการโยง อาศัยการเก็บแอดเดรสของสมาชิกถัดไปไว้ภายในโครงสร้างข้อมูลเอง เพื่อเชื่อมโยงสมาชิกแต่ละตัวเข้าด้วยกัน โครงสร้างข้อมูลจำนวนมากใช้ทั้งสองแนวทางร่วมกัน เช่น ต้นไม้ ตารางแฮช และกราฟ ส่วนโครงสร้างข้อมูลบางชนิด เช่น XOR linked list [en] ใช้เทคนิคที่ซับซ้อนกว่านั้นในการจัดเก็บความเชื่อมโยงระหว่างสมาชิก การใช้งานโครงสร้างข้อมูลมักประกอบด้วยชุดของฟังก์ชันหรือขั้นตอนวิธีสำหรับสร้าง เข้าถึง ปรับปรุง และลบข้อมูลภายในโครงสร้างนั้น โดยทั่วไป ประสิทธิภาพของโครงสร้างข้อมูลจะพิจารณาควบคู่กับการดำเนินการที่รองรับ เนื่องจากโครงสร้างข้อมูลเดียวกันอาจมีประสิทธิภาพแตกต่างกันไปตามลักษณะของการใช้งาน แนวคิดดังกล่าวนำไปสู่แบบชนิดข้อมูลนามธรรม ซึ่งนิยามชนิดข้อมูลจากชุดของการดำเนินการและคุณสมบัติทางคณิตศาสตร์ของการดำเนินการเหล่านั้น โดยไม่กำหนดรายละเอียดของการนำไปใช้งานจริง[15]

ภาษาที่สนับสนุน

[แก้]

ภาษาแอสเซมบลีส่วนใหญ่และภาษาระดับต่ำมักไม่มีโครงสร้างข้อมูลระดับสูงให้ใช้งานโดยตรง ผู้เขียนโปรแกรมต้องจัดการหน่วยความจำและกำหนดรูปแบบการจัดเก็บข้อมูลด้วยตนเอง ส่วนภาษาโปรแกรมระดับสูงส่วนใหญ่มีโครงสร้างข้อมูลพื้นฐานเป็นส่วนหนึ่งของภาษา เช่น แถวลำดับในภาษาซี และแถวลำดับหลายมิติในภาษาปาสคาล รวมถึงสตรักต์ (struct) เรคอร์ด (record) และชนิดข้อมูลอื่น ๆ[16][17]

นอกจากนี้ ภาษาโปรแกรมสมัยใหม่มักจัดเตรียมไลบรารีมาตรฐานที่รวมโครงสร้างข้อมูลและขั้นตอนวิธีที่ใช้บ่อยไว้ เช่น Standard Template Library [en] (STL) ของภาษา C++, Java Collections Framework [en] ของภาษาจาวา และ .NET collections [en] ของ .NET นอกจากนั้นภาษาโปรแกรมสมัยใหม่ยังสนับสนุนการเขียนโปรแกรมเชิงโมดูล [en]และการซ่อนสารสนเทศ [en] โดยแยกส่วนติดต่อ (interface) ออกจากรายละเอียดการดำเนินการ (implementation) ทำให้ผู้ใช้สามารถใช้งานโครงสร้างข้อมูลผ่านคลาส แบบชนิดข้อมูลนามธรรม หรือไลบรารี โดยไม่จำเป็นต้องทราบรายละเอียดภายใน และโครงสร้างข้อมูลจำนวนมากยังมีรุ่นที่รองรับการประมวลผลพร้อมกัน [en] เพื่อให้หลายเธรด (thread) สามารถเข้าถึงข้อมูลร่วมกันได้อย่างปลอดภัย เช่น การใช้กลไกล็อก (lock) หรืออัลกอริทึมแบบไม่ใช้ล็อก (lock-free)[18]

ดูเพิ่ม

[แก้]

อ้างอิง

[แก้]
  1. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (พิมพ์ครั้งที่ 3rd). The MIT Press. น. 9. ISBN 978-0262033848. A data structure is a way to store and organize data in order to facilitate access and modifications.
  2. ↑ Black, Paul E. (15 ธันวาคม 2004). "data structure". ใน Pieterse, Vreda; Black, Paul E. (บ.ก.). Dictionary of Algorithms and Data Structures [online]. National Institute of Standards and Technology. สืบค้นเมื่อ 2018-11-06. An organization of information, usually in memory, for better algorithm efficiency, such as queue, stack, linked list, heap, dictionary, and tree, or conceptual unity, such as the name and address of a person. It may include redundant information, such as length of the list or number of nodes in a subtree.{{cite book}}: CS1 maint: date auto-translated (ลิงก์)
  3. ↑ "Data structure". Encyclopaedia Britannica. 17 เมษายน 2017. สืบค้นเมื่อ 2018-11-06. way in which data are stored for efficient search and retrieval{{cite encyclopedia}}: CS1 maint: date auto-translated (ลิงก์)
  4. 1 2 "1.2 Abstract Data Types". Virginia Tech - CS3 Data Structures & Algorithms. ข้อมูลเก่าจากแหล่งเดิมเมื่อ 2023-02-10. สืบค้นเมื่อ 2023-02-15.
  5. ↑ Wegner, Peter; Reilly, Edwin D. (2003-08-29). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. น. 507–512. ISBN 978-0470864128.
  6. ↑ Seymour, Lipschutz (2014). Data structures (พิมพ์ครั้งที่ Revised first). New Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.
  7. ↑ Walter E. Brown (กันยายน 29, 1999). "C++ Language Note: POD Types". Fermi National Accelerator Laboratory. ข้อมูลเก่าจากต้นฉบับ เมื่อ 2016-12-03. สืบค้นเมื่อ 6 ธันวาคม 2016.{{cite web}}: CS1 maint: date auto-translated (ลิงก์)
  8. ↑ Gavin Powell (2006). "Chapter 8: Building Fast-Performing Database Models". Beginning Database Design. Wrox Publishing. ISBN 978-0-7645-7490-0. ข้อมูลเก่าจากต้นฉบับเมื่อ 2007-08-18.
  9. ↑ Smith, Roderick W. (2000). The Multi-boot Configuration Handbook (ภาษาอังกฤษ). Que Publishing. น. 303. ISBN 978-0-7897-2283-6.
  10. ↑ Mehta, Dinesh P.; Sahni, Sartaj (21 กุมภาพันธ์ 2018). Handbook of Data Structures and Applications (ภาษาอังกฤษ). Taylor & Francis. น. 799. ISBN 978-1-4987-0188-4.{{cite book}}: CS1 maint: date auto-translated (ลิงก์)
  11. ↑ "Rob Pike's 5 Rules of Programming". www.cs.unc.edu. สืบค้นเมื่อ 11 พฤษภาคม 2026.{{cite web}}: CS1 maint: date auto-translated (ลิงก์)
  12. ↑ "When data is too big to fit into the main memory". Indiana University Bloomington - Data Structures (C343/A594). 2014. ข้อมูลเก่าจากต้นฉบับ เมื่อ 2018-04-10.
  13. ↑ Tsiknis, George K. "UNIT 3: Concrete Data Types" (PDF). CICS 216. สืบค้นเมื่อ 11 พฤษภาคม 2026.{{cite web}}: CS1 maint: date auto-translated (ลิงก์)
  14. ↑ Horowitz, Ellis; Sahni, Sartaj (1984). Fundamentals of data structures. Rockville: Computer Science Press. ISBN 9780914894209. An algorithm's behavior pattern or performance profile is measured in terms of the computing time and space that are consumed while the algorithm is processing.
  15. ↑ Nievergelt, Jürg; Widmayer, Peter (2000-01-01), "Chapter 17 - Spatial Data Structures: Concepts and Design Choices", ใน Sack, J. -R.; Urrutia, J. (บ.ก.), Handbook of Computational Geometry, Amsterdam: North-Holland, น. 725–764, ISBN 978-0-444-82537-7, สืบค้นเมื่อ 2023-11-12
  16. ↑ "The GNU C Manual". Free Software Foundation. สืบค้นเมื่อ 2014-10-15.
  17. ↑ Van Canneyt, Michaël (กันยายน 2017). "Free Pascal: Reference Guide". Free Pascal. ข้อมูลเก่าจากแหล่งเดิมเมื่อ 2026-01-22.{{cite web}}: CS1 maint: date auto-translated (ลิงก์)
  18. ↑ Mark Moir and Nir Shavit. "Concurrent Data Structures" (PDF). cs.tau.ac.il. ข้อมูลเก่าจากต้นฉบับ (PDF) เมื่อ 2011-04-01.
เข้าถึงจาก "https://th.wikipedia.org/w/index.php?title=โครงสร้างข้อมูล&oldid=13209554"