ความรู้พื้นฐานเกี่ยวกับ โครงสร้างข้อมูล (Introduction to Data Structure)

ความรู้พื้นฐานเกี่ยวกับ โครงสร้างข้อมูล (Introduction to Data Structure)

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

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

1.การพัฒนาโปรแกรม(program Development)

การพัฒนาโปรแกรมจัดว่าเป็นสิ่งสำคัญของผู้เขียนโปรแกรมหรือ โปรแกรมเมอร์(programmer) และนักวิเคราะห์ระบบ (analyst) อย่างมาก เพราะเป็นวิธีการในการอธิบายระบบงานอย่างเป็นขั้นตอน ซึ่งองค์ประกอบของการพัฒนาโปรแกรมมี 7 ขั้นตอน คือ

1.1 ขั้นตอนการวิเคราะห์ปัญหา(Analysis the Problem)
– การระบุสิ่งที่ต้องการ(What)
– การระบุผลลัพธ์ที่ต้องการ(Output)
– การระบุข้อมูลนำเข้า(Input)
– การระบุตัวแปรที่ใช้(Variable)
– วิธีการประมวลผล(Process)

1.2 ขั้นตอนการออกแบบโปรแกรม(Design a Program)
– ผังงาน(Flowchart)
– รหัสเทียม(Pseudo-code)

1.3 ขั้นตอนการเขียนโปรแกรม(Coding Program)
เป็นการนำเอาผลที่ได้จากขั้นตอนการออกแบบโปรแกรมมาเขียนเป็นคำสั่งด้วยภาษาคอมพิวเตอร์(Computer Programming Language) สำหรับการเขียนโปรแกรมแต่ละภาษามีกฏไวยากรณ์(Syntax) ของแต่ละภาษาเป็นตัวกำหนดวิธีการเขียนโดยผู้เขียนโปรแกรมสามารถเลือกใช้ภาษาโปรแกรมได้ตามต้องการ ในที่นี้ได้แบ่งโ)รแกรมภาษาคอมพิวเตอร์ออกเป็น 5 ยุคได้แก่
– ยุคที่หนึ่ง ภาษาเครื่อง(Machine Language)
– ยุคที่สอง ภาษาแอสเซมบลี(Assembly Language)
– ยุคที่สาม ภาษาระดับสูง(High Level Language)
– ยุคที่สี่ ภาษาระดับสูงมาก(Very High Level Language หรือ 4GLs)
– ยุคที่ห้า ภาษาธรรมชาติ(Natural Language หรือ 5GLs)

1.4 ขั้นตอนการตรวจสอบข้อผิดพลาดของโปรแกรม(Testing And Debugging)
หลังจากผ่านขั้นตอนการเขียนโปรแกรมด้วยภาษาใดภาษาหนึ่งแล้ว ขั้นตอนนี้เป็นการตรวจสอบข้อผิดพลาด(Error) ว่าโปรแกรมที่เขียนขึ้นมานั้นผิดหลักไวยากรณ์ของภาษานั้นๆหรือไม่ ซึ่งการตรวจสอบนี้อาจจะตรวจสอบจากขั้นตอนการทำงานของโปรแกรมโดยทดสอบการเขียนและผลลัพธ์ลงบยกระดาษ หรือที่เรียกว่าการตรวจสอบด้วยตนเอง(Self Checking) อีกวิธีหนึ่งก็คือ การตรวจสอบด้วยตัวแปลภาษาโปรแกรม(Compile) วิธีการนี้เมื่อพบข้อผิดพลาดก็จะแจ้งให้ทราบ และความผิดพลาดทั้งหมด สามารถจำแนกได้ 3 ประเภท ดังนี้
– ความผิดพลาดทางวากนสัมพันธ์(Syntax Error)
– ความผิดพลาดขณะทำงาน(Run-Time Error)
– ความผิดพลาดทางตรรกะ(Logical Error)

1.5 ขั้นตอนการทดสอบความถูกต้องของโปรแกรม(Testing and Validating)
หลังจากทดสอบแล้วว่าโปรแกรมที่เขียนมาใช้งาน ไม่เกิดข้อผิดพลาดใดๆ จะต้องนำโปรแกรมไปทดสอบความถูกต้องอีกครั้งหนึ่ง ซึ่งขั้นตอนนี้จะเป็นการทดสอบที่ละเอียดมากยิ่งขึ้น เช่น การทดสอบความเป็นไปได้ของโปรแกรมว่า ถ้าโปรแกรมให้ใส่วันที่จะต้องลองใส่วันที่ 33 ลงไป แล้วดูว่าโปรแกรมยอมรับหรือไม่ เพราะในความเป็นจริงแล้ววันที่จะต้องไม่เกิน 31 หรือการป้อนเพศชายลงไปในโปรแกรม แล้วทดลองป้อนจำนวนวันที่ลาคลอดซึ่งเพศจะไม่สามารคลอคลอดได้ นอกจากนั้นอาจจะตรวจสอบดูว่าการป้อนชื่อนั้นจะต้องป้อนเป็นตัวอักษรเท่านั้น ไม่สามารถที่จะป้อนเป็นตัวเลขได้ ถ้าโปรแกรมยอมรับตัวเลขก็ถือว่าไม่มีความถูกต้องเกิดขึ้น

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

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

2. การวัดประสิทธิภาพของขั้นตอนวิธี(Algorithm Efficiency)

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

3. ความหมายของโครงสร้างข้อมูล(Meaning of Data Structure)

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

4. การแทนที่โครงสร้างข้อมูลในหน่วยความจำหลัก(Memory Representation of Data Structure)

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

4.1 การแทนที่โครงสร้างข้อมูลในหน่วยความจำที่กำหนดขนาดใว้ก่อน(Static Memory Representation)
การแทนที่โครงสร้างข้อมูลในหน่วยความจำที่กำหนดขนาดใว้ก่อน เป็นการจองเนื้อที่ในหน่วยความจำทั้งจำนวนและขนาดของหน่วยความจำใว้แน่นอน ไม่สามารถที่จะเปลี่ยนแปลงขนาดได้

4.2 การแทนที่โครงสร้างข้อมูลในหน่วยความจำที่ไม่กำหนดขนาดใว้ก่อน(Dynamic Memory Representation)
การแทนที่โครงสร้างข้อมูลในหน่วยความจำที่ไม่กำหนดขนาดใว้ก่อนเป็นการจองเนื้อที่ที่แตกต่างจากวิธีการแรกคือ ไม่ได้กำหนดขนาดของหน่วยความจำใว้ล่วงหน้าว่าควรจะมีจำนวนเท่าใด ซึ่งสามารถที่จะยืดหยุ่นได้ตามข้อมูลที่มี อยู่ถ้าข้อมูลมีน้อยก็ใช้เนื้อที่น้อยแต่ถ้าข้อมูลมีมากก็จะใช้เนื้อที่มากตามไปด้วย

5. ประเภทของโครงสร้างข้อมูล(Type of Data Structure)

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

5.1 โครงสร้างข้อมูลแบบเชิงเส้น(Linear Data Structure)
โครงสร้างข้อมูลแบบเชิงเส้น เป็นโครงสร้างที่เก็บข้อมูลเรียงต่อกันไปเป็นเส้นตรง ได้แก่
– โครงสร้างข้อมูลแบบแถวลำดับ
– โครงสร้างข้อมูลแบบรายการโยง
– โครงสร้างข้อมูลแบบกองซ้อน
– โครงสร้างข้อมูลแบบแถวคอย

5.2 โครงสร้างข้อมูลแบบไม่เชิงเส้น(Non-Linear Data Struxture)
โครงสร้างข้อมูลแบบไม่เชิงเส้น เป็นโครงสร้างข้อมูลที่มีการจัดเก็บข้อมูล นั้นไม่ได้เรียงต่อกันไปเป็นเส้นตรง ทำให้ไม่สามารถนำข้อมูลเข้าและออกจากตำแหน่งใดๆ ก็ได้ โครงสร้างข้อมูลแบบไม่เชิงเส้น ได้แก่
– โครงสร้างข้อมูลแบบต้นไม้
– โครงสร้างข้อมูลแบบกราฟ

Leave a Reply

อีเมลของคุณจะไม่แสดงให้คนอื่นเห็น ช่องที่ต้องการถูกทำเครื่องหมาย *