งานวิชาโครงสร้างข้อมูล

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

2. ให้แสดง ระดับของแบบชนิดข้อมูล (hierarchy of data types) ที่นำมาใช้กับคอมพิวเตอร์ โดยให้ระบุ ระดับ แบบชนิดข้อมูล และที่มาของข้อมูลในแต่ละระดับ

ระดับ แบบชนิดข้อมูล ที่มา
2 ข้อมูลในระดับความคิด สร้างโดยจินตนาการของนักเขียนโปรแกรม เพื่อแก้ปัญหา
ที่ต้องการ
1 ข้อมูลในระดับโปรแกรม สร้างด้วยภาษาคอมพิวเตอร์ระดับสูง
0 ข้อมูลในระดับเครื่อง ฮาร์ดแวร์ที่มีให้ใช้ได้


3. จงยกตัวอย่างข้อมูลในระดับโปรแกรมมา 5 ตัวอย่าง
- จำนวนเต็ม (integer)
- จำนวนจริง (real)
- อักขระ (character)
- สตริง (string)
- บูลีน (boolean)

4. จงแสดงตัวอย่างของโครงสร้างข้อมูลแบบเชิงเส้น และโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
(1) โครงสร้างข้อมูลแบบเชิงเส้น (linear data structures)
เช่น
- ลิสต์ (list)
- สแตก (stack)
- คิว (queue)
- ดีคิว (deque)
(2) โครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น (non-linear data structures)
เช่น
- ทรี (tree)
- กราฟ (graph)

5. โครงสร้างข้อมูลทางกายภาพ และโครงสร้างข้อมูลทางตรรกะเป็นอย่างไร จงอธิบายพร้อมยกตัวอย่างประกอบ

โครงสร้างข้อมูลทางกายภาพ (Physical data structures) เป็นโครงสร้างข้อมูลทั่วไปที่มีใช้ในภาษาคอมพิวเตอร์ ซึ่งแบ่งออกเป็นข้อมูล 2 ประเภทตามลักษณะข้อมูล
(1) ข้อมูลพื้นฐาน (primitive data types)
เป็นข้อมูลพื้นฐานซึ่งมีโครงสร้างข้อมูลไม่ซับซ้อนจะต้องมีในภาษาคอมพิวเตอร์ทุกภาษา ตัวอย่างของข้อมูลประเภทนี้ เช่น
- จำนวนเต็ม (integer)
- จำนวนจริง (real)
- ตัวอักขระ (character)
(2) ข้อมูลโครงสร้าง (structured data types)
เป็นข้อมูลที่มีโครงสร้างสลับซับซ้อน เกิดจากการนำโครงสร้างข้อมูลเบื้องต้นมาประกอบกันเป็นโครงสร้างข้อมูลที่หลากหลายขึ้น ข้อมูลที่ใช้ในเครื่องคอมพิวเตอร์ยุคแรกเป็นข้อมูลเบื้องต้นเท่านั้น แต่ในปัจจุบันภาษาคอมพิวเตอร์เกือบทุกภาษามีข้อมูลโครงสร้างด้วยแทบทั้งสิ้น ตัวอย่างข้อมูลโครงสร้าง เช่น
- แถวลำดับ (array)
- เซต (set)
- ระเบียนข้อมูล (record)
- แฟ้มข้อมูล (file)

โครงสร้างข้อมูลทางตรรกะ (logical data structures) เป็น โครงสร้างข้อมูลที่เกิดจากจินตนาการของผู้ใช้เพื่อใช้แก้ปัญหาในโปรแกรมที่สร้างขึ้น จำแนกได้เป็น 2 ประเภท
(1) โครงสร้างข้อมูลแบบเชิงเส้น (linear data structures)
เป็นชนิดข้อมูลที่ความสัมพันธ์ของข้อมูลเรียงต่อเนื่องกัน โดยข้อมูลตัวที่ 2 อยู่ต่อจาก ข้อมูลตัวที่ 1 ข้อมูลตัวที่ 3 อยู่ต่อจากข้อมูลตัวที่ 2 และข้อมูลตัวที่ n อยู่ต่อจากข้อมูลตัวที่ n - 1 (ดูรายละเอียดเพิ่มเติมได้ในบทที่ 5) ตัวอย่างโครงสร้างข้อมูลแบบเชิงเส้น เช่น
- ลิสต์ (list)
- สแตก (stack)
- คิว (queue)
- ดีคิว (deque)
- สตริง (string)
(2) โครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น (non-linear data structures)
เป็นชนิดข้อมูลที่ข้อมูลแต่ละตัวสามารถมีความสัมพันธ์กับข้อมูลอื่นได้หลายตัว
ตัวอย่างโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
- ทรี (tree)
- กราฟ (graph)


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

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

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

9. จงอธิบายการแทนค่าข้อมูลต่อไปนี้
9.1 การแทนค่าจำนวนเต็ม
คอมพิวเตอร์เก็บค่าโดยเอาบิตมาเรียงกัน หากคอมพิวเตอร์ใช้ 16 บิต แทนข้อมูลชนิดจำนวนเต็ม สามารถแทนค่าได้ทั้งหมด 2ยกกำลัง16 เท่ากับ 65536 แต่เนื่องจากต้องการให้แทนค่าได้ทั้งจำนวนเต็มบวกและจำนวนเต็มลบ จึงต้องแบ่งค่าแทนออกเป็น 2 ส่วน โดยใช้บิตลำดับที่16 (หรือเรียกว่า บิต 15) เป็นตัวบอกว่าเลขนั้นเป็นบวกหรือลบ เรียกว่า Signed Bit การแทนเลขลบจะใช้วิธีการกลับบิตของเลขบวก
9.2 การแทนค่าจำนวนจริง
จำนวนจริง คือ ตัวเลขที่มีทศนิยม ซึ่งข้อมูลชนิดนี้สามารถใช้แทนตัวเลขที่มีขนาดใหญ่มากๆ หรือเล็กมากๆ ในขณะที่จำนวนเต็มไม่สามารถใช้แทนได้
การแทนเลขแบบนี้ประกอบด้วย 2 ส่วน คือ ส่วนของแมนทิสซา หรือ ฟังก์ชั่น และส่วนของแคแรกเทอริสติก หรือเลขชี้กำลัง ซึ่งเขียนในรูปแบบวิทยาศาสตร์

9.3 การแทนค่าอักขระ
คอมพิวเตอร์ใช้ 8 บิต หรือ 1 ไบต์ แทน 1 อักขระ ซึ่ง 8 บิต สามารถแทนค่าัทั้งหมดได้ 256 ค่า รหัสอักขระมาตรฐานที่ใช้คือ ASCll ซึ่งย่ีอมาจาก American Standard Code for Information Interchange

9.4 การแทนค่าบูลีน
ข้อมูลชนิดบูลีนมีเพียง 2 ค่า คือ TRUE และ FALSE ในทางทฤษฏีแล้วใช้เพียง 1 บิต ก็เพียงพอ แต่ในทางปฏิบัติ คอมพิวเตอร์มักใช้ 1 ไบต์ในการเก็บ เพราะสามารถเข้าถึงได้ง่ายกว่า โดยทั่วไปจะแทน FALSE ด้วย 0 คะแนน และแทน TRUE ด้วย 1 หรือค่าอื่นๆ

9.5 การแทนค่าอาร์เรย์
ชุดข้อมูลจะต้องเรียงติดต่อกัน หมายถึง ในอาร์เรย์จะมีข้อมูลตัวที่ 1 ตัวที่ 2 ตัวที่ 3 เรียงติดต่อเรื่อยไปจนถึงตัวที่ n ซึ่งเป็นตัวสุดท้ายของอาร์เรย์
อาร์เรย์จะมีโครงสร้างเป็นแบบเชิงเส้น ดังนั้น เราสามารถระบุค่าถัดไปหรือค่าก่อนหน้าของแต่ละค่าในอาร์เรย์ได้
ขนาดที่จำกัด หมายถึงอาร์เรย์นั้นๆจะต้องสามารถระบุจำนวนข้อมูลทั้งหมดในนั้นได้ อาจจะมีจำนวนมากหรือน้อยก็แล้วแต่การใช้งาน
9.6 การแทนค่าสตริง หรือสายอักขระ
ในภาษาซีไม่มีข้อมูลชนอดสตริงโดยเฉพาะ แต่ซีสร้างข้อมูลชนิดสตริงจากอาร์เรย์ 1 มิติของอักขระ สตริงจบด้วยอักขระ NUL (ASCll 0 หรือ 0x00) หรือเขียนในภาษาซี คือ '\0' ซึ่งอักขระนี้ไม่ใช่ส่วนหนึ่งของสตริง การดำเนินการกับสตริงทำได้โดยผ่านคลังมาตรฐาน