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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

[แก้] โครงสร้างข้อมูลแบบต่าง ๆ

  • โครงสร้างข้อมูลเชิงเส้น
    • รายการ (list)
      • แถวลำดับ (array)
        • Bitmaps
          • Images
          • Heightfields
        • Parallel array
      • รายการโยง (linked list)
        • Skip list
        • Unrolled linked list
        • Xor linked list
      • VList
    • Associative array (a.k.a. dictionary or map)
    • ตารางแฮช (hash table)
    • กองซ้อน (stack)
    • แถวคอย (queue)
    • Deque
    • Buffer gap
  • กราฟ (คณิตศาสตร์) (graph)
    • Adjacency list
    • Disjoint-set data structure
    • Graph-structured stack
    • Scene graph
    • ต้นไม้ (tree)
      • M-Way Tree
        • ต้นไม้แบบบี (b-tree)
      • ต้นไม้ค้นแบบทวิภาค (binary search tree)
          • AVL tree
          • Red-black tree
          • Scapegoat tree
          • Splay tree
          • van Emde Boas tree
        • Radix tree
        • Interval tree
      • ฮีป (heap)
        • Binary heap
        • Binomial heap
        • Fibonacci heap
        • 2-3 heap
        • Soft heap
      • ต้นไม้แจงส่วน (parse tree)
      • Quadtree and Octree
      • Suffix tree
      • Trie
        • Patricia trie
  • โครงสร้างข้อมูลแบบอื่นๆ

[แก้] ดูเพิ่ม

  • รายชื่อโครงสร้างข้อมูล