หน่วย1_พื้นฐาน

โครงสร้ างข้อมูลและขัน้ ตอนวิธี 3901-2002 IT DATA STRUCTURE AND ALGORITHM

โครงสร้ างข้ อมูล (DATA STRUCTURE) โครงสร้ างหรือลักษณะเฉพาะของชุดข้อมูลที่ใช้ในระบบคอมพิวเตอร์ เกิดจากการนําชนิดข้อมูล ต่างๆ มารวมกันจนกลายเป็นโครงสร้ าง การจัดการข้อมูลในหน่วยความจําภายในเครื่องคอมพิวเตอร์ ให้มีความสัมพันธ์กันภายในกลุ่ม ข้อมูลให้มีรูปแบบหรือข้อกําหนดท่ีชัดเจนในการกําหนดคุณสมบัติ เพื่อสร้ างความสัมพันธ์ภายในกลุ่มข้อมูล ซึ่งมีอยู่หลายรูปแบบ เช่น Array, Link-List, Stack, Queue, Tree เป็นต้น

ประเภทของโครงสร้ างข้ อมูล  แบ่งออกเป็ น 2 ประเภท 1. โครงสร้ างข้ อมูลเชิงเส้ น (Linear Data Structure) 2. โครงสร้ างข้อมูลไม่เชิงเส้น (Non-Linear Data Structure) 1. โครงสร้ างข้อมูลเชิงเส้น เป็นรูปแบบโครงสร้ างของการจัดเก็บข้อมูล ที่มีการ จัดเรียงข้อมูลให้ต่อเนื่องกันและเข้าถึงข้อมูลตามลําดับ เช่น โครงสร้ างข้อมูลแบบ Linked List, Stack และ Queue

ประเภทของโครงสร้ างข้ อมูล 2. โครงสร้ างข้อมูลไม่เชิงเส้น เป็นรูปแบบโครงสร้ างของการจัดเก็บข้อมูล ที่มีการจัดเรียงข้อมูลไม่ต่อเนื่องกันใช้ วิธีการเข้าถึงข้อมูลด้วยการระบุตําแหน่งเช่นโครงสร้ างข้อมูลแบบ Tree และ Graph เป็นต้น

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

อัลกอริทึม (ALGORITHM) เป็นวิธีการแสดงลําดับขัน้ ตอนในการทํางานหรือแก้ ไขปัญหาอย่างใดอย่าง ห นึ่ง เ ช่น ก า ร กํา ห น ด ขั น้ ต อ น เ พื่อ แ ก้ ปัญ ห า ก า ร จัด เ รีย ง เ อ ก ส า ร ใ น แฟ้มข้ อมูล หรือการกําหนดอัลกอริทึมในการค้ นหาข้ อมูลในแฟ้มข้ อมูล ทัง้ หมด เป็นต้ น อัลกอริทึมท่ีดีควรมีคุณสมบัติ ดังนี ้ 1. มีลาํ ดับขัน้ ตอนทํางาน ก่อน-หลัง ชัดเจน 2. เข้าใจง่ายและไม่กํากวม 3. สามารถประมวลผลการทํางานด้วยคอมพิวเตอร์ได้ 4. การทํางานของอัลกอริทึมจะต้องสิน้ สุด หลังจากดําเนินงานตาม ระยะเวลาที่กําหนด

ตัวอย่างอัลกอริทึม : การต้ มไข่ไก่ อลั กอริทมึ ท่ี 2 อลั กอริทมึ ท่ี 1 1 ต้มนํา้ ให้เดือด 2 ใสไ่ ข่ 1 ต้มนํา้ ให้เดือด 3 รอ 5 นาที 2 ใสไ่ ข่ 4 ดบั ไฟ / ปิดเตา 3 รอ 10 นาที 4 ดบั ไฟ / ปิดเตา ผลลพั ธ์ท่ีได้ = ไขต่ ้ม 5 ปอกไข่

ขั้นตอนในการแก้ ปั ญหา 1. ศึกษาปั ญหา 2. วิเคราะห์ปั ญหา 1. Input 2. Output 3. Process 3. ออกแบบอัลกอริทึม 1. ภาษาเขียน 2. ผังงาน 3. รหัสเทียม 4. วิเคราะห์อัลกอริทึม 5. เขียนโปรแกรมคอมพิวเตอร์

กระบวนการทาํ งานของคอมพิวเตอร์ 1. ขัน้ ตอนการนําข้ อมูลเข้ า Input 2. ขัน้ ตอนเก่ียวกับการประมวลผล Process 3. ขัน้ ตอนการนําข้ อมูลออก Output Input Process Output

ตัวอย่ างการวิเคราะห์ : การต้ มไข่ ไก่ Process Input 1 ต้มนํา้ ให้เดือด Process 2 ใสไ่ ข่ Process 3 รอ 10 นาที 4 ดบั ไฟ / ปิดเตา Process 5 ปอกไข่ Output 6 ไขต่ ้มสกุ

ผังงาน (FLOWCHART) เป็นเคร่ืองมือท่ีใช้ ออกแบบระบบงานด้ วยสัญลักษณ์ ช่วยให้ มีโครงสร้ างของระบบงานท่ีเป็ น ลําดับขัน้ ตอนและเข้ าใจได้ ง่าย แบ่งออกเป็น 2 ประเภท 1. ผังงานระบบ (System Flowchart) 2. ผังงานโปรแกรม (Program Flowchart)

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

รหัสเทียม (PSEUDO CODE) ใช้ อธิบายการทํางานของอัลกอริธึม ทําให้ ไม่ต้ องเขียนอธิบายด้ วย code ไม่ขึน้ กับภาษาคอมพิวเตอร์ภาษาใดภาษาหน่ึง อาจเป็นภาษาไทยหรือภาษาอื่นก็ได้ แต่การใช้ ภาษาอังกฤษจะสะดวกที่สุด เป็นคําส่ังที่มีลักษณะการเขียนใกล้ เคียงกับภาษาอังกฤษ แต่มีโครงสร้ างเกือบจะเป็นภาษาโปรแกรม

ตัวอย่ างการเขียนรหัสเทียม BEGIN READ A, B SUM = A+B IF SUM > 10 THEN PRINT SUM ELSE PRINT A-B END

ให้ นศ.เขียนอัลกอริทึมและโฟลว์ชาร์ ตของโปรแกรมที่กําหนดให้ ต่อไปนี ้ 1. โปรแกรมคํานวณหาค่า y ของสมการ y = x^2+2x+10 2. โปรแกรมแสดงยอดขาย ถ้ าซือ้ สินค้ ามากกว่า 1,000 บาท มีส่วนลดให้ 100 บาท 3. โปรแกรมแสดงยอดขายของร้ านค้ าแห่งหนึ่ง มีโปรโมชั่นลดราคา ดังนี ้ • ถ้าผู้ชายลดให้ 50 บาท • ถ้าผู้หญิงลดให้ 100 บาท 4. โปรแกรมแสดงขนาดของการใช้ ยาตามอายุผู้ใช้ • อายุมากกว่า 10 ปี แสดงข้อความรับประทานครัง้ ละ 3 ช้อนชา • อายุ 6-10 ปี แสดงข้อความรับประทานครัง้ ละ 2 ช้อนชา • อายุ 2-5 ปี แสดงข้อความรับประทานครัง้ ละ 1 ช้อนชา • เด็กอายุต่ํากว่า 1 ปี ห้ามรับประทาน