บทที่ 1

พื้นฐานโครงสร้างข้อมูล


วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objectives)
หลังจากเรียนบทนี้แล้วนักศึกษาจะมีความสามารถดังนี้

  1. ศึกษาขั้นตอนการพัฒนาซอฟต์แวร์
  2. บอกลักษณะโครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม
  3. อธิบายความหมายโครงสร้างข้อมูล/ชนิดข้อมูล
  4. เขียนโครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม
  5. เข้าใจโครงสร้างข้อมูลกับภาษาเขียนโปรแกรม
  6. จัดบอร์ดเชิงปฏิบัติการ “พื้นฐานโครงสร้างข้อมูล”
  7. สนทนาเชิงปฏิบัติการ “โครงสร้างข้อมูลเบื้องต้นและโครงสร้างข้อมูลนามธรรม”
  8. อธิบายคำศัพท์ได้ 12 คำ

 

บทที่ 1
พื้นฐานโครงสร้างข้อมูล
                คอมพิวเตอร์เป็นอุปกรณ์ที่สร้างขึ้นมาเพื่อใช้จัดการและเปลี่ยนแปลงข้อมูลข่าวสาร (Information) ดังนั้น จึงต้องมีการศึกษาถึงการควบคุมดูแลการทำงานของคอมพิวเตอร์ที่ยุ่งเกี่ยวกับข้อมูลข่าวสาร เมื่อมีการเปลี่ยนแปลงแก้ไขหรือเพื่ออำนวยประโยชน์ที่ต้องการการทำงานเพื่อนแก้ไขปัญหาต่าง ๆ ด้วยระบบคอมพิวเตอร์จะประกอบด้วยส่วนต่าง ๆ ทางด้านฮาร์ดแวร์ (Hardware) เช่น ซีพียู (CPU) หน่วยความจำ (Memory) อุปกรณ์รับส่งข้อมูล(Input/Output Device)และซอฟแวร์(Software)ที่นำมาใช้ควบคุมการทำงานของฮาร์ดแวร์ เพื่อแก้ไขปัญหานั้น ๆ ในการแก้ไขปัญหาจึงต้องมีกระบวนการพัฒนาซอฟต์แวร์ (Software Development) ที่เป็นขั้นตอนมาใช้ดังนี้

ขั้นตอนการพัฒนาซอฟแวร์

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

การออกแบบระบบ
                เนื่องจากระบบคอมพิวเตอร์ไม่สามารถที่จะเข้าใจและแกไขปัญหาบางอย่างได้ จึงต้องมีวิธีการที่จะแก้ไขปัญหาโดยการออกแบบระบบ ซึ่งเป็นการวางแผนออกแบบที่แยกแยะออกเป็นปัญหาย่อย และพิจารณาสร้างชุดคำสั่งเพื่อแก้ไขปัญหาย่อยนั้น จากนั้นมารวมกันเป็นระบบที่สามารถแก้ไขปัญหาทั้งหมด มีลักษณะการวางแผนออกแบบจากบนลงล่าง (Top-down Design) ซึ่งประกอบด้วย 2 ส่วนหลัก ๆ คือ
                1. โครงสร้างข้อมูล (Data Strutcure) ใช้ควบคุมและจัดการกับข้อมูลของปัญหานั้น ๆ หรือที่เรียกว่าชนิดข้อมูลมีโครงสร้าง เรียกสั้น ๆ ว่าชนิดข้อมูล เช่น ชนิดข้อมูลอาร์เรย์ ชนิดข้อมูลสแตก และชนิดข้อมูลลิ้งค์ ลิสต์ การออกแบบระบบต้องเลือกใช้โครงสร้างข้อมูลอย่างเหมาะสมเพื่อจัดการกับข้อมูลที่ใช้ในระบบ
                2. การออกแบชุดคำสั่ง (Module Design) ในการแก้ไขปัญหาจะต้องมีกระบวนการทำงานเพื่อให้ได้มาซึ่งข้อมูลข่าวสารหรือเอ้าท์พุต ที่ต้องการโดยชุดคำสั่งเป็นส่วนประกอบของระบบ จึงต้องมีการออกแบบการทำงานที่เป็นชุดคำสั่งหรือโมดุลนั้นๆ และเรียกว่า อัลกอรึทึม ได้เป็น

โครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม

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

  1. ความถูกต้อง
  2. ระยะเวลาการทำงาน
  3. จำนวนพื้นที่ใช้งาน
  4. ความเรียบง่าย
  5. ความเหมาะสมที่สุด

การเขียนคำสั่งและรวมกัน
                การเขียนคำสั่ง (Coding) คือ การเขียนคำสั่งต่าง ๆ ของโปรแกรมให้ทำงานเป็นไปตามโครงสร้างข้อมูลและอัลกอริทึมด้วยภาษาเขียนโปรแกรมภาหนึ่ง ถ้าโครงสร้างข้อมูลและอัลกอริทึมถูกออกแบบไว้เป็นอย่างดีทำให้กระบวนการแปลงคำสั่งจากภาษาเขียนให้เป็นภาษาเครื่องก็จะง่ายไม่ยุ่งยากลำบาก
                การรวมกัน (Integration) เป็นกระบวนการนำคำสั่งต่าง ๆ ที่เขียนเป็นแต่ละชุดคำสั่งมารวมกันและให้มีการทำงานร่วมกันได้เป็นซอฟต์แวร์โปรแกรมขึ้นมา
                การเขียนโปรแกรมที่ดีนั้นจะต้องมีความถูกต้องในการทำงาน สามารถอ่านคำสั่งและทำความเข้าใจได้ง่าย จึงต้องมีโครงสร้างการเขียนโปรแกรมที่ดี ซึ่งมีวิธีการเข้ามาช่วยเหลือในการเขียนโดยพิจารณาได้จากเรื่องต่อไปนี้
                1. การเขียนโปรแกรมควรเป็นแบบบนลงล่าง (Top-Down) โดยเฉพาะกับปัญหาที่มีขนาดใหญ่หรือมีความซับซ้อน จึงควรแยกปัญหาใหญ่ออกเป็นปัญหาย่อย ๆ จากการเขียนคำสั่งทั้งหมดในโปรแกรม ก็แยกเป็นชุดคำสั่งย่อย ๆ
                2. ใช้โครงสร้างควบคุมการทำงาน (Control Structure) ในการเขียนโปรแกรมหรือชุดคำสั่ง เช่น การใช้เงื่อนไข IF การใช้วนลูปแบบต่าง ๆ
                3. ควรใช้ตัวแปรที่เป็นแบบโลคอล (Local Variable) และใช้กับชุดคำสั่งเพื่อแก้ปัญหาย่อย
                4. ควรใช้ตัวแปรพารามิเตอร์ (Parameter)  กับชุดคำสั่งเพื่อแก้ไขปัญหาย่อย หลีกเลี่ยงที่จะใช้ตัวแปรที่เป็นแบบโกลบอล และตัวพารามิเตอร์ควรมีการป้องกันหากมีการแก้ไขค่า
                5. นำตัวแปรค่าคงที่ ( Constant Variable) มาใช้ จะช่วยให้การเขียนโปรแกรมมีความยืดหยุ่นมากขึ้นและอ่านเข้าใจง่าย
                6. การเขียนโปรแกรมควรมีการจัดพื้นที่หรือบรรทัดว่างเพื่อให้อ่านสะดวก มีการย่อหน้าเพื่อจัดระดับของคำสั่งและมีลักษณะที่เป็นกรอบ

ทดสอบความถูกต้อง

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

การดูแลระบบ

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

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

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

 

บิต (Bit)
                เป็นหน่วยที่เล็กที่สุดในการทำงานของคอมพิวเตอร์ที่แสดงเป็นสถานะได้ 2 สถานะ คือ เปิดกับปิด จึงกำหนดเป็นการเก็บค่าได้ 2 ค่า คือ 0 กับ 1 เรียกว่าไบนารี่ดิจิต (Binary Digit)

ไบต์ (Byte)
                เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดค่าได้มากขึ้น เช่น 3 บิต มาต่อเรียงกันจะทำให้เกิดสถานะที่ต่างกันคือ 000,001,010,100,011,010, และ 111 ก็จะได้เป็น 8 สถานะ เมื่อนำบิตมาเรียงต่อรวมกันเป็น 8 บิต เรียกว่าไบต์ มี 256 สถานะ และกำหนดเป็นโครงสร้างข้อมูลที่มีขนาดเล็กที่สุดที่ใช้งานได้ มีค่าตั้งแต่ 0 – 255 (00000000 – 11111111)

เลขจำนวนเต็ม (Integer)
                เป็นการนำบิตหลาย ๆ บิตมาเรียงต่อรวมกันเพื่อกำหนดเป็นเลขจำนวนเต็ม ซึ่งได้เป็นระบบเลขฐานสอง โดยแต่ละบิตมีความหมายเป็นเลขยกกำลังสอง เช่น 20 = 1, 23 = 8 หรือ
21 + 22 +25 = 2+4+32 = 38 เลขที่ได้เป็นเลขจำนวนเต็มบวก ถ้าต้องการเป็นเลขจำนวนเต็มลบ จะต้องใช้วิธีการเรียกว่า One-complement Notation โดยการเปลี่ยนค่าของบิตที่เป็น 0 ให้เป็น 1 และค่าที่เป็น 1 ให้เป็น 0 เช่น 00100110 = 38 เมื่อสลับค่าจะได้บิต 11011001 = -38 ด้วยวิธีนี้ทำให้เก็บค่าได้ทั้งเลขจำนวนเต็มบวกและเต็มลบ ซึ่งมีบิตซ้ายสุดเป็นตัวกำหนดให้มีค่าบวกหรือลบเรียกว่า Sign Bit เมื่อนำบิตมาเรียงต่อกัน 16 บิตได้เป็นเลขจำนวนเต็มฐานสิบ มีอีกวิธีคือ Two-complement Notation โดยการบวกค่า 1 เข้าไปกับค่าของ One-complement Notation  เช่นจาก 11011001 = -38 เมื่อบวก 1 จะได้ 11011010 = -38 เช่นกัน แต่วิธีนี้จำทำให้เก็บค่าได้มากกว่า คือ มีตั้งแต่ -2n-1 ถึง 2n-1 -1 ดังต่อไปนี้
1000000000000000 = -32768                         0000000000000000 = 0
1000000000000001 = -32767                         0000000000000001 = 1
1000000000000010 = -32766                         0000000000000010 = 2

1111111111111101 = -3                                  0111111111111101 = 32765
1111111111111110 = -2                                  0111111111111110 = 32766
1111111111111111 = -1                                  0111111111111111 = 32767

 

 

เลขจำนวนจริง (Real Number)
                เป็นรูปแบบของตัวเลขที่มีเลขทศนิยมเรียกว่า Floating – point Number โดยทำการแบ่งบิตออกเป็นสองส่วน โดยบิตที่อยู่ด้านซ้ายเก็บค่าเป็นตัวเลขจำนวนเต็ม เรียกว่า แมนทิสสา (Mantissa) การเก็บค่าเป็นแบบเดียวกับตัวเลขจำนวนเต็ม ส่วนบิตที่อยู่ด้านขวาเก็บค้าเป็นจำนวนหลักของ เลขทศนิยมเรียกว่า เอ็กซ์โพเนนท์ (Exponent) ในการเก็บจะใช้วิธี Two – complement Notation ซึ่งได้มาจากเลขยกกำลังของ 10 เช่น .01 = 10-2, 6.25 x 10-2 การเก็บค่าเลขทศนิยมจะใช้บิตจำนวน 32 บิต โดยแบ่งส่วนที่เป็นแมนทิสสาจำนวน 24 บิต และส่วนที่เป็นเอ็กซ์โพเนนท์จำนวน 8 บิต ดังนี้
                00000000000000000000000000000000 = 0
                00000000000000000000110000000011 = 12000
                00000000000000000000010111111111 = 0.5
                00000000000000000000010111111010 = 0.000005
                11111111011010001001111111111110 = -387.53

ตัวอักษร (Character)
                เป็นการเก็บค่าที่เป็นตัวอักษร แต่เนื่องจากคอมพิวเตอร์ไม่สามารถเข้าใจจึงใช้เลขจำนวนเต็มสื่อความหมายแทนโดยใช้บิตจำนวน 8 บิต เรียกว่า Bit String ซึ่งค่าตัวเลขที่ได้จะกำหนดเป็นตัวอกษรหนึ่งตัว ดังนั้นจะได้ตัวอักษรทั้งหมด 256 ตัวที่เรียกว่าเอ็บซีดิก (EBCDIC) เช่น
 ตัวอักษรA จะมีค่า 01000001 = 65 หรือ B มีค่า 01000010 = 66 ประกอบด้วยอักษรตัวเล็ก ตัวใหญ่ ตัวเลข และตัวอักษรพิเศษ และที่ใช้เพียง 7 บิตเรียกว่าวหัสแอสกี (ASCII Code) ใช้ครึ่งเดียวของเอ็บซีดิกแต่การทำงานรวดเร็วกว่า เมื่อใดที่นำตัวอักษรหลาย ๆ ตัวมาเรียงต่อกันก็จะได้เป็นข้อความ เช่น AB จะได้เป็น 0100000101000010 หากต้องการเก็บจำนวนรูปแบบของตัวอักษรมากกว่านี้ก็สามารถทำได้โดยการเพิ่มจำนวนบิตเข้าไป ซึ่งขึ้นกับสถาปัตยกรรมของคอมพิวเตอร์จะรับได้หรือไม่ เช่นใช้ 10 บิตก็จะได้ตัวอักษร 1024 รูปแบบ

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

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

โครงสร้างข้อมูลเบื้องต้น

โครงสร้างข้อมูล
เรียบง่าย

โครงสร้างข้อมูลซับซ้อน

การจัดการแฟ้มข้อมูล

เชิงเส้น

ไม่เป็นเชิงเส้น

ไบนารี

N-อาร์เรย์

เลขจำนวนเต็ม

อาร์เรย์

สแตก

ไบนารีทรี

กราฟ

แฟ้มข้อมูลลำดับ

เลขทศนิยม

สตริง

คิว

ไบนารีเสิร์ชทรี

ทรี

แฟ้มข้อมูลโดยตรง

บูลีน

เรคคอร์ด

ลิ้งลิสต์

 

เสิร์ชทรี M-ทาง

แฟ้มข้อมูลลำดับเชิงดัชนี

ตัวอักษร

 

 

 

บีทรี

แฟ้มข้อมูลหลายคีย์

 

 

 

 

บี*-ทรีมบีพลัว-ทรี

 

 

 

 

 

ทราย

 

รูปที่ 1.1 ประเภทของโครงสร้างข้อมูล

                1. โครงสร้างข้อมูลเบื้องต้น (Primitive Data Structure) เป็นชนิดข้อมูลที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอย เมื่อต้องการเก็บค่าสามารถเรียกใช้งานได้ทันที บางครั้งเรียกว่าชนิดข้อมูลพื้นฐาน (Base Type) หรือสร้างมาให้ใช้ด้วยภาษานั้น ๆ
                ส่วนโครงสร้างข้อมูลแบบอื่น ๆ จะมีโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ เมื่อต้องการใช้จะต้องกำหนดรูปแบบรายละเอียดโครงสร้างขึ้นมาก่อนเรียกว่าข้อมูลชนิดผู้ใช้กำหนด
(Uses-defined Type) ดังนี้
                2. โครงสร้างข้อมูลแบบเรียบง่าย (Simple Data Structure) จะมีสมาชิกที่เป็นโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ มีรูปแบบง่าย ๆ ไม่ซับซ้อน สามารถทำความเข้าใจและสร้างขึ้นมาใช้งานได้ง่าย
                3. โครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) เป็นโครงสร้างที่ความซับซ้อนมากขึ้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงต่อกันเป็นแนวเส้น
               
4. โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) เป็นโครงสร้างที่มีความซับซ้อนเช่นกัน ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงกันในรูปแบบไบนารี่ ที่จัดเรียงสมาชิกมีการแยกออกเป็นสองทาง และแบบ N- อาร์เรย์ ที่จัดเรียงสมาชิกมีการแยกออกได้หลายทางหลายรูปแบบไม่แน่นอน
5. โครงสร้างการจัดการแฟ้มข้อมูล (File Organization) เป็นโครงสร้างสำหรับนำข้อมูลเก็บไว้ในหน่วยความจำสำรอง โดยข้อมูลจะอยู่ในรูปแบบโครงสร้างข้อมูลอื่น และมีวิธีการจัดการโดยการนำโครงสร้างข้อมูลอื่น ๆ มาช่วย
โครงสร้างข้อมูลต่าง ๆที่กล่าวมาอาจต้องมีการควบคุมการทำงานที่เกี่ยวข้องกับข้อมูลและส่วนที่มาเกี่ยวข้องให้เป็นไปตามที่ต้องการเรียกว่า โครงสร้างข้อมูลนามธรรม ลักษณะโครงสร้างจะแบ่งออกเป็น 2 ส่วน คือ ส่วนข้อมูลและส่วนปฏิบัติการ โดนภายในจะมีรายลเอียดการทำงานต่าง ๆ ประกอบด้วยโครงสร้างการจัดเก็บข้อมูลและอัลกอริทึม เมื่อใดที่เรียกใช้งานโครงสร้างนามธรรมในส่วนรายละเอียดการทำงานจะไม่ถูกเกี่ยวข้องหรือมีผลกระทบโดยถูกปิดบังไว้ จะเห็นว่าโครงสร้างข้อมูลซับซ้อนจะเป็นโครงสร้างข้อมูลนามธรรมที่ต้องมีส่วนการจัดเก็บข้อมูลและส่วนปฏิบัติการ

โครงสร้างข้อมูลกับภาษาเขียนโปรแกรม

                ภาษาเขียนโปรแกรม (Programming Language) ช่วยให้ผู้เขียนโปรแกรมสามารถกำหนดโครงสร้างข้อมูลที่มีความหมายให้กับตำแปร เนื่องจากตัวแปรเหล่านี้ต้องเก็บค่าตามลักษณะของโครงสร้างข้อมูลที่ได้กำหนดมาและส่วนของการปฏิบัติการที่ช่วยให้การทำงานกับโครงสร้างข้อมูลมีความถูกต้อง ภาษาเขียนโปรแกรมหลายภาษาจะมีแนวทางที่แตกต่างกันในการกำหนดโครงสร้างข้อมูลมาให้ใช้ เช่น ภาษาซี(C) อนุญาตให้โครงสร้างข้อมูลตัวอักษรกับเลขจำนวนเต็มสามารถใช้ร่วมกันและคำนวณได้ ภาษาปาสคาล (Pascal) จะต้องประกาศตัวแปรอย่างชัดเจนว่ากำหนดโครงสร้างข้อมูลเป็นแบบใด ขณะที่ภาษาฟอร์แทรน(Fortran) เป็นการประกาศปิดบังไว้จึงไม่ต้องกำหนดโครงสร้างข้อมูลให้กับตัวแปร

นายธีระทัศน์ เสียงอ่อน
5039011012