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

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

โครงสร้างข้อมูลแต่ละแบบจะเหมาะสมกับงานที่แตกต่างกัน และโครงสร้างข้อมูลบางแบบก็ออกแบบมาสำหรับบางงานโดยเฉพาะ อย่างเช่น ต้นไม้แบบบีจะเหมาะสำหรับระบบงานฐานข้อมูล

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

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

ภาพรวม

แก้
  • โครงสร้างข้อมูลอาร์เรย์ ใช้เก็บอิลีเมนต์ที่มีชนิดข้อมูลชนิดเดียวกันจำนวนนวนหนึ่งแมีลำดับเฉพาะ อิลีเมนต์ของอาร์เรย์เข้าถึงโดยใช้เลขจำนวนเต็มระบุตำแหน่งของอิลีเมนต์ที่ต้องการ อาร์เรย์อาจมีขนาดจำกัด หรืออาจขยายขนาดได้
  • เรคคอร์ด (อาจเรียกเป็น ทูเปิ้ล หรือสตรัค ) เรคคอร์ด เป็นโครงสร้างข้อมูลชนิดหนึ่งในลุ่มโครงสร้างข้อมูลแบบง่าย ค่าข้อมูลของมันเป็นค่าซึ่งสามารถใส่ค่าของเรคคอร์ดอื่น โดยปกติเรคคอร์ดมีขนาดคงที่ และเรียงลำดับ ใช้ชื่อเป็นดัชนี อิลีเมนต์ของเรคคอร์ดมัดเรียกว่าฟิลด์ หรือ สมาชิก
  • แฮช หรือ ดิกชันนารี หรือ แมพ เป็นโครงสร้างข้อมูลที่ยืดหยุ่นมากกว่าเรคคอร์ด ซึ่งการเก็บข้อมูลจะเป็นแบบคู่ของ ชื่อ-ค่า และสามารถเพิ่มหรือลบข้อมูลได้อย่างอิสระ
  • ยูเนียน (Union) การนิยามยูเนียน จะระบุจำนวนของชนิดข้อมูลดั้งเดิมที่อาจใช้ใส่อินสแตนท์ เช่น "float หรือ long integer" ยูเนียนแตกต่างจากเรคคอร์ด คือ เรคคอร์ดสามารถใส่ข้อมูลได้ทั้งชนิด float และ integer แต่ยูเนียนสามารถใช้ใส่ข้อมูลได้ชนิดเดียว
  • แท็กยูเนียน tagged union (มักเรียกว่า แวเรียน แวเรียนเรคคอร์ด หรือดิสจอยส์ยูเนียน ) เป็นโครงสร้างที่บรรจุฟิลด์เพิ่มเติมที่ชี้ชนิดข้อมูลป้จจุบันของมัน เพื่อการขยายชนิดข้อมูลอย่างปลอดภัย
  • เซต เป็นโครงสร้างข้อมูลนามธรรมซึ่งสามารถเก็บค่าเฉพาะ โดยไม่ต้องมีลำดับ และไม่มีค่าที่ซ้ำกัน ค่าที่เก็บในเซต ไม่สามารถนำออกมาได้ แต่จะใช้การทดสอบว่าค่าที่ต้องการมีในเซตหรือไม่ และคำตอบที่ได้เป็นค่าบูลีน ว่า มี หรือไม่มี
  • วัตถุ เป็นโครงสร้างที่บรรจุฟิลด์ข้อมูลได้เช่นเดียวกับเรคคอร์ด และยังมีโค้ดของโปรแกรมสำหรับทำงานกับข้อมูลนั้นด้วย สำหรับโครงสร้างข้อมูลที่ไม่มีโคัด มักเรียว่า plain old data structure.

โครงสร้างข้อมูลชนิดอื่นๆ สามารถสร้างขึ้นมาได้ แต่มักแปรหรือ ประกอบขึ้นใหม่จากโครงสร้างข้อมูลข้างต้น

หลักการพื้นฐาน

แก้

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

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

แก้

ภาษาแอสเซมบลีส่วนใหญ่ และภาษาระดับต่ำบางภาษา เช่น BCPL (Basic Combined Programming Language) ไม่สนับสนุนการมีโครงสร้างข้อมูล ภาษาโปรแกรมระดับสูงส่วนใหญ่และภาษาแอสเซมบลีระดับสูงบางภาษา เช่น MASM มีรูปแบบคำสั่งพิเศษ หรือ ฟังก์ชันบางอย่างที่สนับสนุนโครงสร้างข้อมูลเช่น เวกเตอร์ vectors (อาร์เรย์หนึ่งมิติ) ในภาษา C หรืออาร์เรย์หลายมิติในภาษา ปาสคาล (Pascal) ภาษาโปรแกรมส่วนใหญ่ รวมส่วนสำคัญ ๆไว้โดยใช้กลไกไลบรารี ซึ่งช่วยให้โครงสร้างข้อมูลนั้นนำไปใช้ในโปรแกรมอื่น ๆ ได้ ภาษาโปรแกรมที่ทันสมัยมักมีไลบรารีมาตรฐานซึ่งมีโครงสร้างข้อมูลทั่วไปรวมอยู่ในภาษาด้วย ตัวอย่างเช่น Standard Template Library ของภาษา C++ Java Collections Framework และ Microsoft's .NET Framework เป็นต้น ภาษาโปรแกรมที่ทันสมัยมักสนับสนุนการเขียนโปรแกรมแบบโมดูล หรือการแยกอินเตอร์เฟซของโมดูลไลบรารี ออกจากการดำเนินการ บางภาษาจัดเตรียมชนิดข้อมูลที่ช่วยให้ผู้ใช้ซ่อนรายละเอียดการดำเนินการด้วย เช่น คลาสของภาษา C++ Java และ .NET Framework เป็นต้น โครงสร้างข้อมูลหลายตัวมีเวอร์ชันที่สามารถทำงานพร้อมกัน ซึ่งสามารถคำนวณหลาย ๆ เทร็ด (threads) ที่เข้าถึงโครงสร้างข้อมูลพร้อมกันได้

ดูเพิ่ม

แก้