ความรู้เบื้องต้นเกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึม

ความรู้เบื้องต้นเกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึม

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

ประเภทของโครงสร้างข้อมูล
ประเภทของโครงสร้างข้อมูล แบ่งออกเป็น 2 ประเภท คือ
1) โครงสร้างข้อมูลทางกายภาพ (Physical Data Structure)
เป็นโครงสร้างข้อมูลที่ใช้โดยทั่วไปในภาษาคอมพิวเตอร์แบ่งเป็น 2 ประเภท ตามลักษณะข้อมูล คือ
1.1) ข้อมูลเบื้องต้น (Primitive Data Types) ได้แก่
– จำนวนเต็ม (Integer)
– จำนวนทศนิยม (Floatting)
– ข้อมูลบูลีน (Boolean)
– จำนวนจริง (Real)
– ข้อมูลอักขระ (Character)
1.2) ข้อมูลโครงสร้าง (Structured Data Types) ได้แก่
– แถวลำดับ (Array)
– ระเบียนข้อมูล (Record)
– แฟ้มข้อมูล(File)
2) โครงสร้างข้อมูลทางตรรกะ (Logical Data Structure)
เป็นโครงสร้างข้อมูลที่เกิดจากการจินตนาการของผู้ใช้ แบ่งเป็น 2 ประเภท คือ
2.1) โครงสร้างข้อมูลแบบเชิงเส้น (Linear Data Structures) ความสัมพันธ์ของข้อมูลจะเรียงต่อเนื่องกัน เช่น
– ลิสต์ (List)
– สแตก (Stack)
– คิว (Queue)
– สตริง (String)
2.2) โครงสร้างข้อมูลแบบไม่เชิงเส้น (Non-Linear Data Structures) ข้อมูลแต่ละตัวสามารถมีความสัมพันธ์กับข้อมูลอื่นได้หลายตัว ได้แก่
– ทรี (Tree)
– กราฟ (Graph)

การดำเนินการกับโรงสร้างข้อมูล (Data Structure Operation)
วิธีการดำเนินการกับข้อมูลที่นิยมใช้กันมาก มี 4 แบบ
1) การเข้าถึงเรคคอร์ด ( Traversing)
2) การค้นหา (Searching)
3) การเพิ่ม (Inserting)
4) การลบ (Deleting)
ยังมีการจัดการกับข้อมูลอีก 2 อย่าง คือ
1) การเรียงข้อมูล (Sorting)
2) การรวมข้อมูล (Merging)

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

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

อัลกอริทึม (Algorithm)
อัลกอริทึม คือ วิธี หรือ ขั้นตอนการแก้ปัญหาอย่างเป็นขั้นตอน มีระบบ ช่วยให้การแก้ปัญหานั้น ๆ มีประสิทธิภาพ ซึ่งอัลกอริทึมที่นิยมใช้กันมาก ได้แก่
1) อัลกอริทึมแบบแตกย่อย(Divide-and-conquer) จะนำปัญหาหลักมาทำการแตกย่อยแล้วนำคำตอบที่ได้จากการแตกย่อยมารวมเข้าด้วยกัน
2) อัลกอริทึมแบบเคลื่อนที่ (Dynamic Programming) เป็นการหลีกเลี่ยงการคำนวณเพื่อหาคำตอบซ้ำ ๆ ซาก ๆ ซึ่งหากมีการคำนวณซ้ำอีก ก็นำคำตอบที่เก็บไว้มาใช้ได้
3) อัลกอริทึมแบบทางเลือก (Greedy Algorithm) จะหาคำตอบโดยเลือกทางเลือกที่ดีที่สุดที่พบได้ในขณะนั้น
ขั้นตอนที่ดีควรมีคุณสมบัติดังนี้
1) มีความถูกต้อง
2) ใช้เวลาในการปฏิบัติงานน้อยที่สุด
3) สั้น กระชับ
4) ใช้หน่วยความจำน้อยที่สุด
5) มีความยืดหยุ่นในการใช้งาน
6) ใช้เวลาในการพัฒนาน้อยที่สุด
7) ง่ายต่อการทำความเข้าใจ

องค์ประกอบของการจัดทำอัลกอริทึม
1) การวิเคราะห์ (Analysis)
– พิจารณาสิ่งที่โจทย์ต้องการ
– พิจารณารูปแบบของผลลัพธ์ที่โจทย์ต้องการ
– พิจารณาข้อมูลนำเข้า
– พิจารษหาวิธีการ หรือสูตรในการแก้ปัญหาที่ต้องการ
– เลือกโปรแกรมภาษาที่จะใช้เขียนโปรแกรม
– กำหนดตัวแปรต่าง ๆ ที่ใช้แทนข้อมูลในโปรแกรม
– จัดลำดับขั้นตอนการดำเนินการเขียนโปรแกรมเพื่อแก้ปัญหาของโจทย์
2) การออกแบบ (Design)
– ผังงาน (Flowchart) เป็นการอธิบายขั้นตอนการทำงานโดยการใช้สัญลักษณ์รูปภาพแสดงความหมาย หรือกำหนดลำดับการทำงาน ดูเป็นระเบียบชัดเจน เข้าใจง่าย แต่อาจใช้เนือที่มาก และยุ่งยาก
– รหัสเทียม (Pseudo Code) เป็นการอธิบายขั้นตอนการประมวลผลโดยใช้วลีภาษาอังกฤษ ใช้คำสั้น ๆ กระทัดรัด ใช้เนื้อที่อธิบายทำงานน้อย แต่อาจเข้าใจยากสำหรับผู้เริ่มเขียนโปรแกรม
3) การเขียนโปรแกรม (Coding/Programming)
พัฒนาการของภาษาโปรแกรม
– ภาษาเครื่อง เป็นเลขฐานสอง 0 และ 1
– ภาษาแอสเซมบลี เป็นเลขฐานสิบหก
– ภาษาระดับสูง ใช้ภาษาอังกฤษในการเขียน เช่น ปาสคาล เป็นต้น
– ภาษายุคที่ 4 หรือ 4GL เช่น JAVA หรือพวก .net เป็นต้น
ภาษาสำหรับการเขียนโปรแกรม มีรูปแบบที่สั้น กระชับ รัดกุม และมีข้อกำหนดดังต่อไปนี้
1. ตัวแปรต้องเขียนด้วยตัวอักษร หรือตัวอักษรปนตัวเลข
2. การกำหนดค่าตัวแปร ใช้เครื่องหมาย
3. นิพจน์ที่เป็นการคำนวณจะมีลำดับขั้นตอนของการคำนวณตามลำดับ คือ วงเล็บ ยกกำลัง คูณหรือหาร บวกหรือลบ ถ้าเครื่องหมายระดับความสำคัญเท่ากัน จะคำนวณจากซ้ายไปขวา
4. ข้อความไปยังขั้นตอน ใช้รูปแบบคือ goto เลขที่ขั้นตอน
5. การเลือกทำตามเงื่อนไขจ จะต้องทำการตรวจสอบเงื่อนไขก่อนทำ จะมีแบบทางเลือกเดียว คือ ใช้คำสั่ง if และสองทางเลือก คือ ใช้คำสั่ง if…else
6. การทำงานแบบซ้ำ แบบทดสอบเงื่อนไขก่อนทำ ใช้คำสั่ง while แบบทำก่อนทดสอบเงื่อนไข ใช้คำสั่ง do…whileและแบบรู้จำนวนการวนรอบ จะใช้คำสั่ง for
7. คำอธิบาย เป็นข้อความที่อธิบายรายละเอียดของขั้นตอนการทำงาน หรือ หมายเหตุ (Comment) จะเขียนอยู่ในเครื่องหมาย /และ/
4) การทดสอบและแก้ไขข้อผิดพลาดของโปรแกรม (Testing and Debugging)
เป็นขั้นตอนการตรวจสอบโปรแกรมที่เขียนว่าทำงานถูกต้องตามความต้องการหรือไม่
– ข้อผิดพลาดทางไวยกรณ์ (Syntax Error) เป็นข้อผิดพลาดที่เกิดจากการเขียนคำสั่งที่ผิดไวยกรณ์ของภาษาที่ใช้เขียนโปรแกรมนั้น ๆ
– ข้อผิดพลาดที่เกิดขึ้นขณะรันโปรแกรม (Run-Time Error) เป็นข้อผิดพลาดที่เกิดขึ้นขณะทำการรันโปรแกรม ส่วนใหญ่เกิดจากการคำนวณตัวเลข
5) การจัดทำเอกสารและบำรุงรักษา (Documentation and Maintenance)
การจัดทำเอกสาร
1. คำบรรยายลักษณะของโปรแกรม
2. คำอธิบายพร้อมผังงานหรือรหัสเทียม
3. รายการโปรแกรม (Program Listing)
4. ผลการทดสอบโปรแกรม
5. จัดทำเอกสารต่าง ๆ ที่เกี่ยวข้องกับระบบ/โปรแกรม ได้แก่
– เอกสารแสดงการวิเคราะห์ และออกแบระบบ : System Manual สำหรับผู้พัฒนาระบบโปรแกรม
– เอกสารอธิบายวิธีการใช้ระบบ/โปรแกรม : User Manual สำหรับผู้ใช้ระบบ/โปรแกรม
6. สามารถทำควบคู่ไปกับการเขียนโปรแกรม
7. อาจทำเป็นคู่มือ เอกสารที่อยู่ในโปรแกรม (Online Manual)
การบำรุงรักษาโปรแกรมหมายถึง การแก้ไขข้อผิดพลาดที่พบระหว่างการทดสอบ หรือการใช้งาน ซึ่งอาจเป็นการเปลี่ยนข้อมูลที่ต้องการใช้ใหม่ การปรับปรุงข้อมูลให้ทันเหตุการณ์อยู่เสมอ การปรับเปลี่ยนโครงสร้างบนหน้าจอ เป็นต้น

การวัดประสิทธิภาพของอัลกอริทึม
สิ่งที่ต้องพิจารณา
1) โปรแกรมนั้นใช้เนื้อที่ความจำ (Memory) มากน้อยเพียงใด
2) โปรแกรมนั้นใช้อัลกอริทึม (Algorithm) ที่เร็วเพียงใด
ในทางทฤษฎี จะระบุความเร็วการทำงานของอัลกอริทึม โดยพิจารณา หรือประมวลผลจำนวนข้อมูลที่อัลกอริทึมนั้นกระทำก่อนที่จะได้ผลลัพธ์ว่ามีการทำงานกี่ครั้ง จำนวนครั้งแทนด้วย N ความเร็วในการทำงานเรียกว่า ฟังก์ชั่น บิ๊กโ-อ (big-oh) : Order of N หรือ O(N)