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

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

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

การใช้งาน

โครงสร้างข้อมูลทำหน้าที่เป็นพื้นฐานสำหรับประเภทข้อมูลนามธรรม (ADT) ADT กำหนดรูปแบบตรรกะของชนิดข้อมูล โครงสร้างข้อมูลใช้รูปแบบทางกายภาพของชนิดข้อมูล [5]

โครงสร้างข้อมูลประเภทต่างๆ นั้นเหมาะสมกับการใช้งานประเภทต่างๆ และบางประเภทก็มีความเชี่ยวชาญเป็นพิเศษสำหรับงานเฉพาะ ตัวอย่างเช่น ฐานข้อมูลเชิงสัมพันธ์มักใช้ดัชนีB-treeสำหรับการดึงข้อมูล[6]ในขณะที่การใช้งานคอมไพเลอร์มักใช้ตารางแฮชเพื่อค้นหาตัวระบุ [7]

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

การนำไปใช้

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

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

ตัวอย่าง

Python 3 ลำดับชั้นประเภทมาตรฐาน.png

โครงสร้างข้อมูลมีหลายประเภท โดยทั่วไปสร้างขึ้นจากประเภทข้อมูลดั้งเดิมที่ง่ายกว่า: [10]

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

นอกจากนี้กราฟและต้นไม้ไบนารีเป็นโครงสร้างข้อมูลอื่นๆ ที่ใช้กันทั่วไป

รองรับภาษา

ภาษาแอสเซมบลีส่วนใหญ่และภาษาระดับต่ำบางภาษาเช่นBCPL (Basic Combined Programming Language) ขาดการสนับสนุนโครงสร้างข้อมูลในตัว ในทางกลับกันภาษาโปรแกรมระดับสูงจำนวนมากและภาษาแอสเซมบลีระดับสูงบางภาษา เช่นMASMมีไวยากรณ์พิเศษหรือการสนับสนุนในตัวอื่นๆ สำหรับโครงสร้างข้อมูลบางอย่าง เช่น บันทึกและอาร์เรย์ ตัวอย่างเช่นภาษา C (สายตรงของ BCPL) และภาษาPascalรองรับโครงสร้างและบันทึกตามลำดับ นอกเหนือจากเวกเตอร์ ( อาร์เรย์หนึ่งมิติ) และอาร์เรย์หลายมิติ[12] [13]

ภาษาโปรแกรมส่วนใหญ่มีกลไกของไลบรารีบางประเภทที่ช่วยให้การนำโครงสร้างข้อมูลไปใช้ซ้ำโดยโปรแกรมต่างๆ ภาษาสมัยใหม่มักมาพร้อมกับไลบรารีมาตรฐานที่ใช้โครงสร้างข้อมูลทั่วไป ตัวอย่างคือC ++ แม่แบบไลบรารีมาตรฐานของJava คอลเลกชันกรอบและMicrosoft .NET Framework

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

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

ดูเพิ่มเติม

อ้างอิง

  1. ^ คอร์เมน โธมัส เอช.; ไลเซอร์สัน, ชาร์ลส์ อี.; ริเวสต์, โรนัลด์ แอล.; สไตน์, คลิฟฟอร์ด (2009). บทนำสู่อัลกอริทึม ฉบับที่ 3 ( ฉบับที่ 3) สำนักพิมพ์เอ็มไอที ISBN 978-0262033848.
  2. แบล็ก, พอล อี. (15 ธันวาคม พ.ศ. 2547) "โครงสร้างข้อมูล" . ใน Pieterse, Vreda; แบล็ก, พอล อี. (สหพันธ์). พจนานุกรมของอัลกอริทึมและโครงสร้างข้อมูล [ออนไลน์] สถาบันมาตรฐานและเทคโนโลยีแห่งชาติ. สืบค้นเมื่อ2018-11-06 .
  3. ^ "โครงสร้างข้อมูล" . สารานุกรมบริแทนนิกา . 17 เมษายน 2560 . สืบค้นเมื่อ2018-11-06 .
  4. ^ เวนเนอร์ ปีเตอร์; ไรลีย์, เอ็ดวิน ดี. (2003-08-29). สารานุกรมวิทยาการคอมพิวเตอร์ . ชิเชสเตอร์ สหราชอาณาจักร: John Wiley and Sons หน้า 507–512. ISBN 978-0470864128.
  5. ^ "ประเภทข้อมูลนามธรรม" . มหาวิทยาลัยเวอร์จิเนียเทค - โครงสร้าง CS3 ข้อมูลและอัลกอริทึม
  6. ^ เกวิน พาวเวลล์ (2006). "บทที่ 8: การสร้างโมเดลฐานข้อมูลที่ทำงานได้รวดเร็ว" . เริ่มต้นการออกแบบฐานข้อมูล Wrox สิ่งพิมพ์ ISBN 978-0-7645-7490-0.
  7. ^ "1.5 แอปพลิเคชันของตารางแฮช" . มหาวิทยาลัย Regina - CS210 Lab: ตารางแฮช
  8. ^ "เมื่อข้อมูลมีขนาดใหญ่เกินกว่าจะใส่ลงในหน่วยความจำหลักได้" . homes.sice.indiana.edu .
  9. ^ Dubey, RC (2014). เทคโนโลยีชีวภาพขั้นสูง: สำหรับ B Sc และ M Sc นักเรียนของเทคโนโลยีชีวภาพและวิทยาศาสตร์ชีวภาพอื่น นิวเดลี: S Chand. ISBN 978-81-219-4290-4. OCLC  883695533 .
  10. ^ มัวร์ Lipschutz (2014) โครงสร้างข้อมูล (แก้ไขครั้งที่ 1) นิวเดลี ประเทศอินเดีย: McGraw Hill Education ISBN 9781259029967. OCLC  927793728 .
  11. ^ วอลเตอร์ อี. บราวน์ (29 กันยายน 2542) "ภาษา C ++ หมายเหตุ: ประเภท POD" Fermi National Accelerator ห้องปฏิบัติการ เก็บถาวรจากต้นฉบับเมื่อ 2016-12-03 . สืบค้นเมื่อ6 ธันวาคม 2559 .
  12. ^ "คู่มือ GNU C" . มูลนิธิซอฟต์แวร์เสรี สืบค้นเมื่อ2014-10-15 .
  13. ^ แวน Canneyt ไมเคิล (กันยายน 2017) "ฟรี Pascal: คู่มืออ้างอิง" . ฟรี ปาสกาล
  14. ^ มาร์ค Moir และเนียร์ชาวิต "โครงสร้างพร้อมกันข้อมูล" (PDF) cs.tau.ac.il .

บรรณานุกรม

อ่านเพิ่มเติม

ลิงค์ภายนอก