Data Structure and Algorithm

เอกสารประกอบการสอน โครงสร้างขอ้ มูลและอัลกอริทึม (Data Structure and Algorithm) เรยี บเรียงโดย นา้ เพ็ญ พรหมประสิทธ์ิ

เอกสารประกอบการสอน โครงสร้างข้อมลู และอลั กอรทิ มึ (Data Structure and Algorithm) เรียบเรียงโดย น้าเพ็ญ พรหมประสทิ ธิ์ สาขาวิชาคอมพิวเตอร์ธุรกจิ ปกี ารศึกษา 2564

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

(2) สารบญั คานา หน้า สารบัญ (1) ลกั ษณะรายวชิ า (2) การแบ่งหน่วยเรยี น บทเรยี น หัวขอ้ (4) จดุ ประสงค์การสอน (5) การประเมนิ ผลรายวชิ า (7) ตารางกาหนดน้าหนักคะแนน (11) กาหนดการสอน (12) หน่วยเรยี นท่ี 1 โครงสร้างขอ้ มลู เบื้องต้น (13) 1 1.1 ความหมายโครงสร้างข้อมลู และอัลกอริทึม 2 1.2 โครงสรา้ งข้อมลู พนื้ ฐาน 4 1.3 ประเภทของโครงสร้างข้อมูลและอลั กอริทึม 5 1.4 เครื่องมอื ในการพฒั นาอลั กอริทมึ 6 1.5 โครงสร้างการควบคุมพืน้ ฐาน 8 หนว่ ยเรียนที่ 2 อาร์เรย์และลิงค์ลิสต์ (Array and Link list) 14 2.1 โครงสร้างอารเ์ รย์ 15 2.2 ชนดิ ของอารเ์ รย์ 16 2.3 โครงสรา้ งลงิ คล์ ิสต์ 24 2.4 ลิงค์ลสิ ตแ์ บบทิศทางเดียว 26 หนว่ ยเรยี นท่ี 3 ควิ (Queues) 31 3.1 โครงสรา้ งคิว 32 3.2 การดาเนนิ การของคิว 33 3.3 การแทนคิวดว้ ยอาร์เรย์ 34 หน่วยเรียนท่ี 4 สแตก (Stack) 43 4.1 โครงสรา้ งสแตก 44 4.2 การดาเนนิ การของสแตก 45 4.3 การแทนสแตกดว้ ยอารเ์ รย์ 47 หนว่ ยเรียนที่ 5 ไบนารที รี (Binary Tree) 55 5.1 โครงสรา้ งทรี 56 5.2 ชนิดของทรี 57 5.3 การเขา้ ถงึ ข้อมูลในไบนารีทรี 61 5.4 ทรกี บั การดาเนินการด้านนิพจน์ 66 5.5 การแทนโครงสรา้ งไบนารีทรีแบบซเี ควนเชยี ล 68 เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมูลและอลั กอริทึม

(3) สารบัญ (ตอ่ ) หน่วยเรยี นท่ี 6 5.6 การแปลงทรีเป็นไบนารีทรี หนา้ หน่วยเรียนท่ี 7 กราฟ (Graph) 70 6.1 ความหมายและลักษณะของกราฟ 73 หน่วยเรยี นที่ 8 6.2 ประเภทของกราฟ 74 บรรณานกุ รม 6.3 การแทนขอ้ มูลกราฟ 75 6.4 การดาเนนิ การบนกราฟ 76 6.5 การทอ่ งไปในกราฟ 85 การเรยี งลาดับข้อมูล (Sorting) 87 7.1 การจัดเรยี งข้อมูลแบบเลือก 89 7.2 การจัดเรียงข้อมูลแบบบับเบลิ 90 7.3 การจดั เรียงข้อมูลแบบแทรก 94 7.4 การจดั เรยี งข้อมูลแบบเชลล์ 101 7.5 การจัดเรยี งข้อมลู แบบฮีพ 103 7.6 การจัดเรยี งข้อมลู แบบควิก 106 7.7 การจัดเรยี งข้อมูลแบบผสาน 129 การค้นหาข้อมลู (Searching) 134 8.1 การค้นหาข้อมลู แบบเรียงลาดับ 136 8.2 การค้นหาข้อมูลแบบทวิภาค 137 8.3 การค้นหาข้อมูลแบบไบนารเี ซริ ท์ ทรี 140 8.4 การค้นหาข้อมลู แบบแฮชช่ิง 143 156 164 เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอลั กอริทึม

(4) ลักษณะรายวิชา 1. รหัสและชื่อวิชา 13-132-207 โครงสร้างขอ้ มูลและอัลกอริทึม (Data Structures and Algorithms) 2. สภาพรายวชิ า หมวดวชิ าเฉพาะ กลุ่มวิชาชีพบงั คบั 3. ระดับรายวิชา ระดับประกาศนยี บัตรวชิ าชีพช้ันสูง 4. พน้ื ฐาน ไม่มี 5. เวลาศึกษา 54 คาบเรียนตลอด 18 สัปดาห์ ทฤษฎี 3 คาบ ปฏิบัติ 0 คาบต่อ สปั ดาห์ และนักศึกษาจะต้องใช้เวลาศึกษาคน้ ควา้ นอกเวลา 6 ช่วั โมง ต่อสัปดาห์ 6. จานวนหน่วยกิต 3 หนว่ ยกิต 7. จดุ มงุ่ หมายรายวิชา 1. เพอื่ ให้เข้าใจโครงสร้างข้อมูลแบบตา่ ง ๆ 2. เพ่ือให้เขา้ ใจวธิ กี ารการเรียงลาดับขอ้ มูล 3. เพอ่ื ให้เข้าใจวิธกี ารการคน้ หาขอ้ มูล 4. เพื่อให้เขา้ ใจการพฒั นาและการวิเคราะห์อลั กอริทมึ 8. คาอธิบายรายวิชา ศึกษาเกี่ยวกับรูปแบบของโครงสร้างข้อมูล อาร์เรย์ สแต็ก คิว ลิงค์ ลิสท์ และไบนารีทรี อัลกอริทึมพื้นฐานและโครงสร้างข้อมูล ข้ันตอน วิธีการการเรียงลาดับข้อมูล การพัฒนาอัลกอริทึม การวิเคราะห์ อัลกอริทมึ อยา่ งงา่ ย การเขียนโปรแกรมเชิงโครงสรา้ ง เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอริทมึ

(5) การแบง่ หนว่ ยเรยี น/บทเรยี น/หวั ขอ้ หนว่ ย หนว่ ยเรยี น/บทเรียน/หัวข้อ เวลา (คาบ) ที่ ทฤษฏี ปฏิบตั ิ 1 โครงสร้างขอ้ มูลเบือ้ งต้น 30 1.1 ความหมายโครงสร้างข้อมลู และอัลกอริทมึ 1.2 โครงสรา้ งข้อมูลพ้ืนฐาน 60 1.3 ประเภทของโครงสรา้ งขอ้ มูลและอลั กอริทึม 1.4 เครอ่ื งมือในการพฒั นาอลั กอริทึม 30 1.5 โครงสรา้ งการควบคุมพื้นฐาน 60 60 2 อาร์เรยแ์ ละลิงคล์ ิสต์ (Array and Link list) 2.1 โครงสร้างอารเ์ รย์ 2.2 ชนดิ ของอารเ์ รย์ 2.3 โครงสร้างลงิ คล์ ิสต์ 2.4 ลงิ ค์ลสิ ตแ์ บบทศิ ทางเดยี ว 3 ควิ (Queues) 3.1 โครงสรา้ งควิ 3.2 การดาเนินการของคิว 3.3 การแทนคิวด้วยอารเ์ รย์ 4 สแตก (Stack) 4.1 โครงสร้างสแตก 4.2 การดาเนนิ การของสแตก 4.3 การแทนสแตกดว้ ยอารเ์ รย์ 5 ไบนารที รี (Binary Tree) 5.1 โครงสรา้ งทรี 5.2 ชนิดของทรี 5.3 การเขา้ ถงึ ข้อมลู ในไบนารที รี 5.4 ทรีกบั การดาเนินการด้านนิพจน์ 5.5 การแทนโครงสร้างไบนารที รีแบบซีเควนเชียล 5.6 การแปลงทรีเปน็ ไบนารีทรี 6 กราฟ (Graph) 30 6.1 ความหมายและลกั ษณะของกราฟ 6.2 ประเภทของกราฟ 6.3 การแทนขอ้ มูลกราฟ 6.4 การดาเนนิ การบนกราฟ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอลั กอริทึม

(6) เวลา (คาบ) ทฤษฏี ปฏบิ ตั ิ หนว่ ย หน่วยเรยี น/บทเรียน/หวั ข้อ 12 0 ที่ 6.5 การทอ่ งไปในกราฟ 90 7 การเรียงลาดบั ข้อมูล (Sorting) 7.1 การจดั เรยี งข้อมูลแบบเลือก 48 0 7.2 การจดั เรยี งข้อมลู แบบบับเบิล 7.3 การจัดเรียงข้อมลู แบบแทรก 7.4 การจดั เรยี งข้อมลู แบบเชลล์ 7.5 การจดั เรยี งข้อมูลแบบฮีพ 7.6 การจัดเรยี งข้อมูลแบบควิก 7.7 การจัดเรยี งข้อมลู แบบผสาน 8 การคน้ หาข้อมูล (Searching) 8.1 การค้นหาข้อมลู แบบเรยี งลาดับ 8.2 การค้นหาข้อมูลแบบทวภิ าค 8.3 การคน้ หาข้อมลู แบบไบนารีเซริ ์ททรี 8.4 การคน้ หาข้อมลู แบบแฮชช่ิง รวม เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทมึ

(7) จดุ ประสงค์การสอน หน่วย หนว่ ยเรียน/บทเรียน/หัวข้อ เวลา (คาบ) ท่ี ทฤษฎี ปฏิบัติ 1 โครงสร้างข้อมลู เบือ้ งตน้ 30 1.1 รู้ความหมายโครงสรา้ งขอ้ มลู และอัลกอริทึม 1.1.1 บอกความหมายโครงสรา้ งขอ้ มูล 60 1.1.2 บอกความหมายอัลกอริทมึ 1.2 เข้าใจโครงสรา้ งข้อมูลพื้นฐาน 30 1.2.1 อธบิ ายและยกตัวอย่างโครงสรา้ งขอ้ มลู พืน้ ฐาน 1.3 รู้ประเภทของโครงสร้างข้อมูลและอลั กอรทิ ึม 1.3.1 บอกประเภทของโครงสร้างข้อมลู 1.3.2 บอกประเภทของอลั กอริทึม 1.4 เข้าใจเคร่ืองมือในการพัฒนาอลั กอริทึม 1.4.1 อธบิ ายเครอ่ื งมือพัฒนาอัลกอริทมึ 1.4.2 เขยี นผงั งานและรหสั เทยี ม 1.5 อธบิ ายโครงสร้างการควบคมุ พ้ืนฐาน 1.5.1 อธิบายและยกตวั อย่างโครงสร้างการควบคุมพืน้ ฐาน 1.5.2 เขยี นผงั งานและหาผลลัพธ์โครงสรา้ งการควบคุม พืน้ ฐาน 2 อารเ์ รย์และลิงคล์ สิ ต์ (Array and Link list) 2.1 รู้โครงสรา้ งอารเ์ รย์ 2.1.1 อธิบายความหมายอาร์เรย์ 2.1.2 อธิบายโครงสรา้ งของอาร์เรย์ 2.2 เขา้ ใจชนดิ ของอารเ์ รย์ 2.2.1 หาผลลัพธก์ ารทางานของอาร์เรย์ 1 มติ ิ 2.2.2 หาผลลัพธ์การทางานของอาร์เรย์ 2 มติ ิ 2.3 รู้โครงสรา้ งของลิงคล์ สิ ต์ 2.3.1 อธิบายความหมายลิงค์ลสิ ต์ 2.3.2 อธบิ ายโครงสร้างของลงิ ค์ลิสต์ 2.4 สรา้ งลิงคล์ สิ ต์แบบทศิ ทางเดยี ว 2.4.1 ยกตัวอยา่ งโครงสร้างลงิ คล์ สิ ต์แบบทิศทางเดียว 2.4.2 หาผลลพั ธ์การทางานของลงิ ค์ลิสต์แบบทิศทางเดียว 3 คิว (Queues) 3.1 รู้โครงสรา้ งควิ 3.1.1 บอกลกั ษณะโครงสร้างคิว เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอัลกอริทมึ

(8) หนว่ ย หนว่ ยเรียน/บทเรียน/หวั ข้อ เวลา (คาบ) ที่ ทฤษฎี ปฏบิ ัติ 3.2 เขา้ ใจการดาเนินการของควิ 60 3.2.1 อธบิ ายการนาเขา้ ข้อมูลของคิว (Enqueue) 3.2.2 อธบิ ายการนาข้อมูลออก (Dequeue) 60 3.3 สร้างการแทนควิ ดว้ ยอารเ์ รย์ 3.3.1 ยกตวั อยา่ งและแก้ปญั หาการแทนคิวด้วยอารเ์ รย์ 3.3.2 แกป้ ัญหาการแทนคิวดว้ ยอาร์เรย์ 3.3.3 แก้ปัญหาการแทนควิ ด้วยวงกลม 4 สแตก (Stack) 4.1 รู้โครงสร้างสแตก 4.1.1 บอกลักษณะโครงสรา้ งสแตก 4.2 เขา้ ใจพื้นฐานการดาเนินการกับสแตก 4.3.1 อธิบายการนาเขา้ ข้อมูล (push) 4.3.2 อธิบายการดึงข้อมูลออก (pop) 4.3.3 อธิบายตาแหนง่ บนสดุ (top) 4.3 สร้างการแทนสแตกดว้ ยอารเ์ รย์ 4.3.1 หาผลลพั ธ์การแทนสแตกดว้ ยอารเ์ รย์ 4.3.2 แก้ปัญหาการประยุกตใ์ ชง้ านสแตกในการแปลงรปู นพิ จน์ทางคณติ ศาสตร์ 5 ไบนารีทรี (Binary Tree) 5.1 รู้โครงสร้างทรี 5.1.1 บอกลักษณะโครงสรา้ งทรี 5.2 เข้าใจชนดิ ของทรี 5.2.1 อธบิ ายและหาผลลพั ธ์ทรีท่ัวไป 5.2.2 อธบิ ายและหาผลลัพธ์ไบนารีทรี 5.3 สรา้ งการเข้าถึงขอ้ มลู ในไบนารที รี 5.3.1 ยกตัวอยา่ งและหาผลลพั ธ์การเขา้ ถึงแบบ พรีออร์เดอร์ 5.3.2 ยกตัวอย่างและหาผลลพั ธ์การเข้าถงึ แบบอินออเดอร์ 5.3.3 ยกตวั อย่างและหาผลลพั ธ์การเข้าถึงแบบ โพสต์ออเดอร์ 5.4 แก้ปญั หาทรีกับการดาเนินการด้านนพิ จน์ 5.4.1 หาผลลพั ธ์ทรีกับการดาเนนิ การด้านนพิ จน์ 5.5 แก้ปญั หาการแทนโครงสรา้ งไบนารที รีแบบซเี ควนเชยี ล 5.5.1 หาผลลัพธก์ ารแทนโครงสร้างไบนารีทรแี บบ เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

(9) หน่วย หนว่ ยเรยี น/บทเรียน/หัวข้อ เวลา (คาบ) ท่ี ทฤษฎี ปฏบิ ตั ิ ซเี ควนเชยี ล 30 5.6 สรา้ งการแปลงทรีเป็นไบนารีทรี 12 0 5.6.1 หาผลลัพธ์การแปลงทรีเปน็ ไบนารีทรี 6 กราฟ (Graph) 6.1 รู้ความหมายและลักษณะของกราฟ 6.1.1 บอกความหมายของกราฟ 6.1.2 บอกลกั ษณะของกราฟ 6.2 เขา้ ใจประเภทของกราฟ 6.2.1 อธบิ ายและยกตวั อยา่ งกราฟมีทศิ ทาง 6.2.2 อธิบายและยกตวั อยา่ งกราฟไม่มีทิศทาง 6.2.3 อธบิ ายและยกตวั อย่างกราฟมีนา้ หนัก 6.2.4 อธิบายและยกตวั อยา่ งกราฟไม่มนี ้าหนัก 6.3 แก้ปญั หาการแทนขอ้ มลู กราฟ 6.3.1 หาผลลพั ธ์การแทนข้อมูลกราฟดว้ ยอารเ์ รย์และ เมทริกซ์ 6.3.2 หาผลลัพธ์การแทนข้อมลู กราฟดว้ ยลงิ คล์ สิ ต์ 6.3.3 หาผลลพั ธ์จานวนเสน้ ทางระหวา่ งโหนด 6.4 แกป้ ญั หาการดาเนนิ การบนกราฟ 6.4.1 หาผลลพั ธ์การเพิม่ บนกราฟ 6.4.2 หาผลลพั ธ์การลบบนกราฟ 6.5 สรา้ งการท่องไปในกราฟ 6.5.1 หาผลลัพธ์การทอ่ งแบบแนวกวา้ ง 6.5.2 หาผลลัพธ์การทอ่ งแบบแนวลึก 7 การเรียงลาดบั ข้อมลู (Sorting) 7.1 ร้แู ละเข้าใจการจดั เรยี งข้อมลู แบบเลอื ก 7.1.1 อธิบายและยกตวั อย่างการจดั เรยี งข้อมลู แบบเลือก 7.1.2 แกไ้ ขปัญหาและหาผลลัพธ์จดั เรียงข้อมลู แบบเลือก 7.2 รู้และเข้าใจการจดั เรียงขอ้ มูลแบบบบั เบลิ 7.2.1 อธิบายและยกตัวอยา่ งการจัดเรียงข้อมูล แบบบับเบิล 7.2.2 แกไ้ ขปัญหาและหาผลลพั ธ์การจัดเรยี งขอ้ มลู แบบบบั เบิล 7.3 รแู้ ละเข้าใจการจัดเรยี งข้อมูลแบบแทรก 7.3.1 อธบิ ายและยกตวั อยา่ งการจดั เรียงขอ้ มลู แบบแทรก เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มูลและอลั กอริทึม

(10) หนว่ ย หน่วยเรยี น/บทเรียน/หวั ข้อ เวลา (คาบ) ที่ ทฤษฎี ปฏบิ ตั ิ 7.3.2 แกไ้ ขปัญหาและหาผลลพั ธ์การจดั เรียงขอ้ มลู 12 0 แบบแทรก 7.4 รแู้ ละเข้าใจการจัดเรียงขอ้ มลู แบบเชลล์ 7.4.1 อธบิ ายและยกตวั อยา่ งการจดั เรยี งข้อมลู แบบเชลล์ 7.4.2 แก้ไขปัญหาและหาผลลัพธ์การจดั เรียงข้อมลู แบบเชลล์ 7.5 รู้และเข้าใจการจัดเรยี งขอ้ มลู แบบฮีพ 7.5.1 อธบิ ายและยกตวั อย่างการจดั เรียงข้อมลู แบบฮีพ 7.5.2 แกไ้ ขปัญหาและหาผลลพั ธ์การจัดเรียงข้อมลู แบบฮีพ 7.6 รแู้ ละเขา้ ใจการจัดเรยี งขอ้ มลู แบบควกิ 7.6.1 อธิบายและยกตัวอยา่ งการจดั เรียงข้อมูลแบบควกิ 7.6.2 แก้ไขปัญหาและหาผลลัพธ์การจัดเรียงข้อมูลแบบ ควิก 7.7 รู้และเข้าใจการจัดเรยี งขอ้ มูลแบบผสาน 7.7.1 อธบิ ายและยกตัวอยา่ งการจัดเรียงข้อมูลแบบผสาน 7.7.2 แกไ้ ขปัญหาและหาผลลพั ธ์การจัดเรียงข้อมูลแบบ ผสาน 8 การคน้ หาข้อมูล (Searching) 8.1 อธิบายการคน้ หาข้อมลู แบบเรียงลาดบั 8.1.1 หาผลลพั ธ์การคน้ หาข้อมลู แบบเรยี งลาดบั 8.2 อธิบายการค้นหาข้อมลู แบบทวิภาค 8.2.1 หาผลลพั ธ์การค้นหาข้อมูลแบบทวิภาค 8.3 อธบิ ายการค้นหาแบบไบนารีเซิร์ททรี 8.3.1 แกไ้ ขปัญหาและหาผลลัพธ์การค้นหาแบบไบนารี เซริ ท์ ทรี 8.3.2 แก้ไขปญั หาและหาผลลัพธ์การดาเนินการกับไบ นารีเซริ ท์ ทรี 8.3.3 แกไ้ ขปัญหาและหาผลลัพธก์ ารทางานของต้นไม้ AVL 8.4 อธิบายการค้นหาข้อมูลแบบแฮชช่งิ 8.4.1 คานวณฟังกช์ ันแฮชชิ่ง 8.4.2 แก้ไขปญั หาและหาผลลพั ธ์การแกป้ ญั หาการชนของ คีย์ เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทมึ

(11) การประเมนิ ผลรายวชิ า เอกสารประกอบการสอนวิชาโครงสร้างข้อมูล ได้แบ่งออกเป็น 9 หน่วยเรียน โดยมีความ สอดคล้องและครอบคลุมเนอ้ื การวัดผลและประเมนิ ผลรายวิชาดาเนนิ การดังน้ี 1. วธิ ีการ ดาเนินการรวบรวมข้อมูลเพ่ือการประเมินผล แยกเป็น 4 ส่วน โดย แบง่ คะแนนแตล่ ะสว่ นจากคะแนนเต็มทง้ั รายวิชา 100 คะแนน ดงั น้ี 2. เกณฑผ์ า่ นรายวิชา 1.1 การทดสอบแตล่ ะหน่วยเรียน 70 คะแนน หรอื ร้อยละ 70 3. เกณฑ์ค่าระดับคะแนน 1.2 การปฏิบตั ใิ บงาน 10 คะแนน หรอื รอ้ ยละ 10 1.3 งานท่ไี ดร้ บั มอบหมาย 10 คะแนน หรือร้อยละ 10 1.4 พิจารณาจิตพิสัย (กิจนิสัย ความตั้งใจ การเข้าร่วมกิจกรรม) 10 คะแนน หรอื ร้อยละ 10 โดยจัดแบ่งน้าหนกั คะแนนในแต่ละหนว่ ยตามตารางหน้าถดั ไป 2.1 ผู้ท่ีจะผ่านรายวิชาน้ีจะต้องมีเวลาเข้าช้ันเรียนไม่น้อยกว่าร้อย ละ 80 2.2 ได้คะแนนรวมท้ังรายวิชาไม่น้อยกว่าร้อยละ 50 ของคะแนน รวม 3.1 พิจารณาตามเกณฑ์ผ่านข้อ 2 ผู้ไม่ผ่านตามเกณฑ์ข้อ 2 จะ ได้รบั คะแนน F 3.2 ผู้สอบผ่านเกณฑ์ข้อ 2 จะได้รับค่าระดับคะแนน ตามเกณฑ์ ดงั นี้ คะแนนร้อยละ 80 – 100 ได้ 4 หรอื A คะแนนร้อยละ 75 – 79 ได้ 3.5 หรือ B+ คะแนนร้อยละ 70 – 74 ได้ 3 หรอื B คะแนนร้อยละ 65 – 69 ได้ 2.5 หรอื C+ คะแนนร้อยละ 60 – 64 ได้ 2 หรอื C คะแนนร้อยละ 55 – 59 ได้ 1.5 หรอื D+ คะแนนร้อยละ 50 – 54 ได้ 1 หรือ D เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอริทึม

(12) ตารางกา้ หนดนา้ หนกั คะแนน เลขที่ คะแนนรายหน่วยเรียน คะแนน น้าหนักคะแนน หน่วย และนา้ หนักคะแนน รายหน่วย พทุ ธพิ สิ ยั ทกั ษะพสิ ัย ชอื่ หน่วยเรียน ความรู้ ความ ้จา ความเ ้ขาใจ การน้าไปใ ้ช ูสงก ่วา 1 โครงสร้างข้อมลู และอลั กอริทึม 5 1210 1 เบื้องต้น 1 2 อาร์เรย์และลงิ ค์ลสิ ต์ (Array and 5 1120 Link list) 1 2 3 ควิ (Queues) 5 1120 2 2 4 สแตก (Stack) 10 1 3 4 0 2 2 5 ไบนารีทรี (Binary Tree) 10 1 3 4 0 6 กราฟ (Graph) 7 1220 7 การเรยี งลาดบั ข้อมูล (Sorting) 13 2 4 5 0 8 การค้นหาข้อมูล (Searching) 15 3 4 6 0 ก คะแนนภาควิชาการ (สอบ) 70 11 20 26 0 13 ข คะแนนภาคผลงาน(ทม่ี อบหมาย) 20 ค คะแนนภาคจติ พสิ ยั 10 รวมทังสิน 100 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอริทมึ

(13) ก้าหนดการสอน สปั ดาห์ท่ี คาบเรยี นท่ี รายการสอน หมายเหตุ 1 1-3 ความหมายโครงสรา้ งข้อมูลและอลั กอริทึม 2 4-6 โครงสร้างขอ้ มูลพน้ื ฐาน 3 7-9 ประเภทของโครงสรา้ งขอ้ มูลและอลั กอริทึม 4 10-12 เครอ่ื งมือในการพฒั นาอลั กอริทึม 5 13-15 โครงสรา้ งการควบคุมพื้นฐาน 6 16-18 7 19-21 โครงสร้างอาร์เรย์ 8 22-24 ชนดิ ของอาร์เรย์ 9 25-27 โครงสร้างลิงคล์ ิสต์ 10 28-30 ลงิ ค์ลิสตแ์ บบทศิ ทางเดียว 11 31-33 12 34-36 โครงสรา้ งควิ การดาเนนิ การของควิ การแทนควิ ด้วยอาร์เรย์ โครงสรา้ งสแตก การดาเนินการของสแตก การแทนสแตกดว้ ยอารเ์ รย์ โครงสร้างทรี ชนิดของทรี การเขา้ ถงึ ข้อมลู ในไบนารที รี ทรกี ับการดาเนนิ การด้านนิพจน์ การแทนโครงสรา้ งไบนารที รีแบบซเี ควนเชียล การแปลงทรีเปน็ ไบนารีทรี ความหมายและลกั ษณะของกราฟ ประเภทของกราฟ การแทนข้อมลู กราฟ การดาเนินการบนกราฟ การทอ่ งไปในกราฟ การจดั เรยี งข้อมลู แบบเลือก การจดั เรียงข้อมูลแบบบับเบิล การจัดเรยี งข้อมลู แบบแทรก การจดั เรียงข้อมลู แบบเชลล์ การจดั เรยี งข้อมลู แบบฮีพ การจดั เรียงข้อมลู แบบควกิ การจัดเรยี งข้อมูลแบบผสาน เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอริทมึ

(14) สปั ดาห์ท่ี คาบเรียนที่ รายการสอน หมายเหตุ 13 37-39 การคน้ หาข้อมลู แบบเรยี งลาดับ การคน้ หาข้อมูลแบบทวภิ าค 14 40-42 การค้นหาข้อมลู แบบไบนารีเซิร์ททรี 15 43-45 การค้นหาข้อมลู แบบแฮชชิ่ง เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

1 ชือ่ หน่วยเรยี น : โครงสร้างข้อมูลเบื้องต้น (Data Structure) รหสั วิชา 13-132-207 หน่วยเรียนท่ี 1 เวลาสอน 3 คาบ ชอ่ื บทเรยี น 1.1 ความหมายโครงสรา้ งขอ้ มลู และอัลกอริทมึ 1.2 โครงสร้างข้อมลู พื้นฐาน 1.3 ประเภทของโครงสรา้ งข้อมลู และอัลกอริทึม 1.4 เครอื่ งมือในการพัฒนาอลั กอริทมึ 1.5 โครงสร้างการควบคุมพ้ืนฐาน จดุ ประสงคก์ ารสอน 1.1 รคู้ วามหมายโครงสร้างข้อมูลและอัลกอริทึม 1.1.1 บอกความหมายโครงสร้างข้อมูล 1.1.2 บอกความหมายอัลกอริทึม 1.2 เขา้ ใจโครงสร้างข้อมลู พน้ื ฐาน 1.2.1 อธบิ ายและยกตวั อย่างโครงสรา้ งข้อมูลพ้นื ฐาน 1.3 รปู้ ระเภทของโครงสร้างข้อมูลและอัลกอริทึม 1.3.1 บอกประเภทของโครงสรา้ งข้อมลู 1.3.2 บอกประเภทของอลั กอรทิ ึม 1.4 เข้าใจเครื่องมือพฒั นาอลั กอริทมึ 1.4.1 อธิบายเคร่ืองมือพัฒนาอัลกอรทิ ึม 1.4.2 เขยี นผงั งานและรหสั เทยี ม 1.5 อธบิ ายโครงสร้างการควบคมุ พ้ืนฐาน 1.5.1 อธิบายและยกตวั อยา่ งโครงสรา้ งการควบคุมพ้นื ฐาน 1.5.2 เขียนผังงานและหาผลลพั ธโ์ ครงสร้างการควบคุมพื้นฐาน เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอลั กอรทิ ึม

2 หน่วยเรียนที่ 1 โครงสรา้ งขอ้ มูลเบ้ืองต้น (Data Structure) โครงสร้างข้อมูลเปน็ ความรพู้ ื้นฐานสาหรับการเรมิ่ ตน้ พฒั นาหรือเขียนโปรแกรมคอมพวิ เตอร์ โดยโครงสร้างขอ้ มูลแต่ละชนิดมีความแตกตา่ งกัน การเลือกโครงสร้างข้อมูลเพ่ือนาไปใช้ในการพัฒนา อลั กอริทึมสาหรบั แก้ปญั หาจึงจาเป็นตอ้ งใช้โครงสร้างข้อมูลทีแ่ ตกต่างกัน 1.1 ความหมายโครงสร้างข้อมลู และอัลกอริทมึ 1.1.1 ความหมายโครงสรา้ งขอ้ มูล นักวิชาการไดใ้ ห้ความหมายของคาว่า “โครงสรา้ งข้อมลู ” ไว้หลายความหมาย ดังนี้ วิวัฒน์ อภิสิทธ์ิภิญโญ และอมร มุสิกสาร (2550 : 11) ได้ให้ความหมายของโครงสร้างข้อมูล ไว้วา่ โครงสรา้ งขอ้ มลู คือ รปู แบบวธิ กี ารจดั ระเบยี บของขอ้ มลู ทไ่ี ด้จากการดาเนินการทางคณิตศาสตร์ (Operations) เพ่อื ให้สามารถจัดการกับข้อมลู ที่ใช้กบั ระบบคอมพิวเตอร์ได้ ณัฐพงษ์ วารีประเสริฐ และสุธี พงศาสกุลชัย (2552 : 4) ได้ให้ความหมายของโครงสร้าง ข้อมูลไว้ว่า โครงสร้างข้อมูล หมายถึง โครงสร้างหรือลักษณะเฉพาะชุดข้อมูลท่ีใช้ในระบบ คอมพิวเตอร์ โดยเกิดจากการนาเข้าข้อมูลชนิดต่าง ๆ มาประกอบเข้าด้วยกันจนกลายเป็นโครงสร้าง ข้อมูลท่ีสามารถรองรับขอ้ มลู ตามความสมั พนั ธ์ภายในชดุ ขอ้ มูลนั้นได้ วุฒิพงษ์ เขื่อนดิน (2553 : 2) ได้ให้ความหมายของโครงสร้างข้อมูลไว้ว่า โครงสร้างข้อมูล หมายถึง การจัดรูปแบบข้อมูลหรือวิธีการจัดระบบข้อมูลเข้าไว้ด้วยกัน มีการกาหนดนิยาม ความสัมพันธ์ภายในกลุ่มของข้อมูลไว้อย่างชัดเจน เพื่อให้ข้อมูลมีลักษณะที่เหมาะสมสาหรับใช้ใน ระบบคอมพวิ เตอร์ วิไลพร กุลตังวัฒนา (2554 : 1) ได้ให้ความหมายของโครงสร้างข้อมูลไว้ว่า โครงสร้างข้อมูล หมายถึง การรวมข้อมูลต่าง ๆ เข้าไว้เป็นกลุ่ม โดยจะกาหนดลักษณะของการรวบรวมข้อมูล หรือ ความสัมพันธ์ของกลุ่มข้อมูลท่ีถูกจัดเก็บในหน่วยความจาไว้อย่างชัดเจน เพื่อให้ได้ข้อมูลที่อยู่ใน รปู แบบที่เหมาะสมสาหรบั การใชง้ านในโปรแกรมคอมพิวเตอร์ วิษณุ ช้างเนียม (2556 : 1) ได้ให้ความหมายของโครงสร้างข้อมูลไว้ว่า โครงสร้างข้อมูล หมายถึง การจดั การข้อมูลในหน่วยความจาภายในเคร่ืองคอมพิวเตอร์ หรือในบางคร้ังเป็นการจัดการ ข้อมูลในดิสก์ ให้มีความสัมพันธ์กันภายในกลุ่มข้อมูลให้มีรูปแบบและข้อกาหนดที่ชัดเจนใน การ กาหนดคุณสมบัติ เพ่ือสร้างความสัมพันธ์ภายในกลุ่มข้อมูล รูปแบบการเก็บข้อมูลท่ีอยู่ในรูปแบบ โครงสร้างข้อมูล กล่าวโดยสรุปได้ว่า โครงสร้างข้อมูล หมายถึง วิธีการจัดการระเบียบของกลุ่มข้อมูลที่มี ความสัมพันธ์กัน โดยมีการกาหนดคุณสมบัติชัดเจน เพื่อให้เหมาะสมสาหรับการใช้ในโปรแกรม คอมพวิ เตอร์ 1.1.2 ความหมายอลั กอริทมึ นักวิชาการไดใ้ ห้ความหมายของคาว่า “อลั กอรทิ มึ ” ไว้หลายความหมาย ดงั นี้ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอัลกอริทึม

3 ขนิษฐา นามี (2548 : 3) ได้ให้ความหมายของอัลกอริทึมไว้ว่า อัลกอริทึม หมายถึง ลาดับ ข้ันตอนในการทางานของโปรแกรมเพ่ือแก้ปัญหาใดปัญหาหน่ึง ซึ่งถ้าปฏิบัติตามข้ันตอนอย่างถูกต้อง แล้ว จะตอ้ งสามารถชว่ ยแกป้ ัญหาหรือประมวลผลตามตอ้ งการไดส้ าเรจ็ วิวัฒน์ อภิสิทธ์ิภิญโญ และอมร มุสิกสาร (2550 : 11) ได้ให้ความหมายของอัลกอริทึมไว้ว่า อัลกอริทึม หมายถึง รูปแบบของการกาหนดการทางานอย่างเป็นขั้นตอน ซึ่งผ่านการวิเคราะห์และ แยกแยะเพื่อการแก้ปัญหาต่าง ๆ ตามลาดับขั้น ความสาคัญของอัลกอริทึมน้ันจะช่วยให้ผู้ที่ออกแบบ ระบบสามารถวางรูปแบบของกระบวนการ กาหนดการทางาน การวิเคราะห์ระบบและทราบถึงจุดที่ ต้องแก้ไขเมื่อพบปัญหาได้ และถ้าหากมีการออกแบบอัลกอริทึมที่ดีมีประสิทธิภาพก็จะทาให้ระบบมี การทางาท่มี ีประสิทธิภาพด้วย ณัฐพงษ์ วารีประเสริฐ และสุธี พงศาสกุลชัย (2552 : 14) ได้ให้ความหมายของอัลกอริทึมไว้ วา่ อัลกอริทึม หมายถงึ ขั้นตอนหรือวิธีการ ซึ่งมีเป้าหมายหรือแนวทางในการปฏบิ ัติชัดเจน เพ่ือใช้ใน การแกไ้ ขปัญหาต่าง ๆ ใหไ้ ด้มาซ่ึงผลลพั ธท์ ี่ถูกต้องอย่างมีประสิทธิภาพ โดยข้ันตอนหรือวธิ ีการเหล่านี้ จะมีหลายรูปแบบตามแต่ลักษณะของปัญหาที่เผชิญ ในกระบวนการทางานของคอมพิวเตอร์ อัลกอริทึมจะมีความสาคัญมาก เน่ืองจากเป็นวิธีการท่ีใชใ้ นการแก้ปัญหาหรือกระบวนการดาเนินงาน ที่มีความซับซ้อน โดยอาศัยการจัดรูปแบบข้อมูลเพ่ือลดความซับซ้อนและเพ่ิมประสิทธิภาพในการ แก้ไขปัญหาได้อีกด้วย อัลกอริทึมที่ใช้น้ันอาจมีมากกว่าหน่ึงอัลกอริทึมท่ีสามารถแก้ไขปัญหาเดียวกัน ได้ แต่จะมีความเหมาะสมกับปัญหาน้ันหรือไม่ จาเป็นต้องมีการวิเคราะห์อัลกอริทึม เพื่อให้ได้ อัลกอรทิ ึมทส่ี ามารถแก้ไขปญั หาดังกลา่ วไดด้ ีท่สี ุด วฒุ ิพงษ์ เขอื่ นดิน (2553 : 3) ได้ให้ความหมายของอัลกอรทิ ึมไว้ว่า อัลกอริทึม หมายถึง การ อธิบายข้ันตอนการทางานของโปรแกรมที่จะพัฒนาข้ึน ซ่ึงผ่านการวิเคราะห์และแยกแยะงาน เพื่อ แก้ปัญหาใดปัญหาหนึ่ง โดยอธิบายอย่างเป็นลาดับขั้นตอน ให้ผู้เป็นเจ้าของหรือผู้รับผิดชอบได้ ตรวจสอบความถูกต้องในแต่ละขั้นตอนของโปรแกรมได้ โดยที่ผู้เป็นเจ้าของหรือผู้รับผิดชอบไม่ จาเป็นตอ้ งเขยี นโปรแกรมเปน็ วิไลพร กุลตังวัฒนา (2554 : 2) ได้ให้ความหมายของอัลกอริทึมไว้ว่า อัลกอริทึม หมายถึง ลาดับข้ันตอนในการทางานของโปรแกรมคอมพิวเตอร์ เพื่อใช้สาหรับการแก้ปัญหาใด ๆ โดยแต่ละ ปัญหาสามารถมีข้ันตอนวิธีการแก้ปัญหาได้หลายรูปแบบ โดยแต่ละแบบจะใช้เนื้อที่ในหน่วยความจา และใช้เวลาในการประมวลผลไม่เท่ากัน ซ่ึงสามารถเขียนขั้นตอนวิธีในรูปแบบของผังงานหรือรหัส เทียมก็ได้ วิษณุ ชา้ งเนยี ม (2556 : 1) ได้ให้ความหมายของอัลกอริทึมไว้ว่า อัลกอรทิ ึม หมายถึง วิธีการ แสดงลาดับข้ันตอนในการทางานหรือแก้ไขปัญหาอย่างใดอย่างหนึ่ง เช่น การกาหนดเพื่อแก้ไขปัญหา จัดเรยี งเอกสารในแฟม้ ขอ้ มลู เปน็ ต้น กลา่ วโดยสรุปได้วา่ อัลกอรทิ ึม หมายถงึ ขั้นตอนวธิ ีในการทางานของโปรแกรม เพือ่ การแกไ้ ข ปัญหาต่าง ๆ โดยผ่านการคิดและวิเคราะห์ เพ่ือความถูกต้องในการทางานและเพ่ิมประสิทธิภาพใน การแก้ไขปญั หา เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ มึ

4 1.2 โครงสร้างขอ้ มลู พ้นื ฐาน ระบบคอมพิวเตอร์ก่อนท่ีจะนาเอาข้อมูลท่ีได้มาจัดเก็บในเครื่องคอมพิวเตอร์น้ัน จะต้องผ่าน กระบวนการจัดรูปแบบของข้อมูลกอ่ น โดยพน้ื ฐานของโครงสรา้ งข้อมูลทีใ่ ช้ในระบบคอมพิวเตอร์น้ันมี หลายรูปแบบ (วิวัฒน์ อภิสทิ ธ์ภิ ญิ โญ และอมร มสุ กิ สาร, 2550 : 12-15) คอื 1.2.1 บิต (Bit) เป็นรูปแบบของตัวเลขที่ใช้แทนค่าด้วยตัวเลข 0 และ 1 เม่ือเทียบกับสถานะการทางานของ คอมพิวเตอร์จะใช้แทน กระแสไฟฟ้าที่กาหนดการเปิด-ปิด (On-Off) ภายในหน่วยความจาของ คอมพวิ เตอร์ เชน่ สวติ ซเ์ ปิด-ปิด 1.2.2 ไบต์ (Byte) หรืออักขระ (Character) เป็นรูปแบบของการแทนค่าบิตจานวน 8 บิต โดยสามารถใช้แทน ค่าได้ท้งั ตัวเลข (Numeric) ตวั อกั ษร (Alphabet) และสัญลักษณ์พเิ ศษ (Special Character) 1.2.3 ฟิลด์ (Field) หรือเขตข้อมูล เป็นกลุม่ ของอักขระที่รวมกันแล้วมีความหมายแทนเรื่องใดเร่ืองหน่ึง โดยส่วน ใหญ่จะมีการจดั แบง่ เขตของการเก็บขอ้ มลู เชน่ ฟิลด์ช่อื นามสกุล เพศ อายุ เกรดเฉล่ีย 1.2.4 เรคอร์ด (Record) หรือระเบียน เป็นการรวมฟิลด์ที่มีความสัมพนั ธ์กนั จัดมารวมกัน เช่น เรคอร์ดข้อมูลนักศึกษา ประกอบดว้ ย ฟลิ ด์ชือ่ นามสกุล เพศ อายุ ระดับการศึกษา 1.2.5 ไฟล์ (File) หรือแฟ้มข้อมูล เป็นรูปแบบของการรวมกลุ่มเรคอรด์ ท่ีมีความสัมพันธ์กัน โดยท่ีแต่ละไฟล์จะ มขี ้อมูลของเรคอรด์ ท่ีไมซ่ า้ กัน เช่น ไฟลข์ อ้ มลู ลูกคา้ ไฟลข์ ้อมลู สินค้า 1.2.6 ฐานขอ้ มลู (Data base) เป็นการรวมไฟล์ข้อมูลหลาย ๆ ไฟล์ ท่ีมีความเก่ียวข้องกันมารวมเข้าด้วยกัน เพื่อประโยชน์ ในการเรียกใชง้ านอยา่ งรวดเรว็ ลดความซา้ ซอ้ นในการจัดเก็บข้อมูล เชน่ ฐานข้อมูลระบบงานทะเบยี น ตารางท่ี 1.1 โครงสร้างขอ้ มูลพื้นฐาน ช่อื นามสกุล เพศ อายุ ระดบั การศกึ ษา 1 ไบต์ สราดา สุธาพัฒ หญงิ 25 ปรญิ ญาโท 1 ฟิลด์ วนิสา อาระดา หญงิ 43 ปรญิ ญาตรี 1 ไฟล์ 1 เรคอร์ด อภสิ พทั ธ์ เลิศพรพิชัย ชาย 37 ปรญิ ญาตรี ปยิ กร หานทอง หญงิ 32 ปริญญาเอก เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอลั กอริทึม

5 1.3 ประเภทของโครงสรา้ งข้อมลู และอลั กอริทมึ 1.3.1 ประเภทของโครงสร้างข้อมูล ในระบบคอมพวิ เตอร์ จาแนกออกเปน็ 2 ประเภท (วิวฒั น์ อภิสทิ ธ์ภิ ิญโญ และอมร มุสิกสาร, 2550 : 15) คอื 1. โครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) เป็นรูปแบบของการ จัดเก็บข้อมูลที่มีการจัดเรียงข้อมูลให้ต่อเนื่องกัน และเข้าถึงข้อมูลตามลาดับ เช่น โครงสร้างข้อมูล แบบลิสต์ (List) สแตก (Stack) คิว (Queue) 2. โครงสร้างข้อมูลไม่เชิงเส้น (Non-Linear Structure) เป็นการจัดเก็บข้อมูล แบบไม่ต่อเนื่อง ใช้วิธีการเข้าถึงข้อมูลด้วยการระบุตาแหน่ง เช่น โครงสร้างข้อมูลแบบทรี (Tree) กราฟ (Graph) 1.3.2 ประเภทของอัลกอริทึม ประเภทของอลั กอริทึมแบ่งออกเปน็ 8 แบบ (วิษณุ ชา้ งเนียม, 2556 : 8-9) ดังนี้ 1. อัลกอริทึมแบบละโมบ (Greedy Algorithm) เป็นอัลกอริทึมที่มีลักษณะของ การแก้ไขปัญหาด้วยการเพิ่มประสิทธิภาพของการแก้ปัญหาให้เหมาะสมท่ีสุด (Optimization problems) เป็นรูปแบบอัลกอริทึมท่ีพิจารณาคาตอบท่ีดีท่ีสุดและคุ้มค่าท่ีสุดในการแก้ไขปัญหานั้น ๆ เชน่ ปัญหาการทอนเหรียญ คือ การเลอื กทอนเหรยี ญในหนว่ ยท่มี ขี นาดใหญท่ ่สี ุดก่อน 2. อั ล ก อ ริ ทึ ม แ บ บ พ ล วั ต (Dynamic Programming Algorithm) เป็ น อลั กอริทมึ ทมี่ ีลกั ษณะของการแก้ไขปญั หาด้วยการแบ่งปัญหาเป็นสว่ นเล็ก ๆ แล้วนาผลของปัญหาเล็ก ๆ ท่ีดีที่สุดนามาแก้ไขปัญหาใหญ่ท่ีเรียกว่า การแก้ไขปัญหาจากล่างขึ้นบน (Bottom-up approach) เชน่ การหาตวั เลข Fibonacci เปน็ ตน้ 3. อัลกอริทึมแบบวนซ้า (Recursive Algorithm) เป็นการแก้ไขปัญหาขั้น พื้นฐานด้วยการเรยี กใช้ตัวเองซ้า ๆ โดยนาข้อมูลปัญหาส่วนย่อยของปัญหาทั้งหมดกลับมาเป็นข้อมูล ในการแกไ้ ขปัญหา เช่น การหา Factorial 4. อัลกอริทึมแบบสุ่ม (Randomized Algorithm) เป็นอัลกอริทึมที่ใช้หลักการ สุ่มขอ้ มลู แลว้ นาขอ้ มูลท่ีเลอื กมาได้กระทากบั อัลกอรทิ ึมเพ่ือใหไ้ ดผ้ ลตามต้องการ เช่น Quick sort 5. อัลกอริทึมแบบย้อนรอยถอยหลัง (Backtracking Algorithm) เป็นอัลกอริทึม คน้ หาเส้นทางทกุ เสน้ ทางทีเ่ ป็นไปได้ เพือ่ หาคาตอบของปัญหาทีละส่วนย่อยว่า คาตอบนั้นเป็นคาตอบ ที่ถูกต้องหรือไม่ แต่ถ้าคาตอบน้ันไม่ใช่ส่วนหน่ึงของคาตอบจะถอยหลังกลับมาจุดเดิม และยกเลิก คาตอบนั้นและค้นหาคาตอบใหม่ เช่น การกาหนดสใี หก้ บั เมืองในแผนท่ี 6. อัลกอริทึมแบบแบ่งย่อยและเอาชนะ (Divide and Conquer Algorithm) เป็นอัลกอริทึมท่ีมีหลักการคิดโดยแยกปัญหาออกเป็น 2 ส่วน คือ ส่วนท่ี 1 แบ่งปัญหาออกเป็นส่วน เล็ก ๆ แล้วแก้ปัญหาในส่วนเล็ก ๆ น้ันก่อน และส่วนที่ 2 นาผลท่ีได้จากการแก้ปัญหาในส่วนเล็ก ๆ กลับมารวมกันใหม่ เช่น Quick sort Merge sort เป็นต้น 7. อัลกอริทึมแบบการลดและเอาชนะ (Decrease and Conquer Algorithm) เป็นอัลกอริทึมท่ีแก้ไขปัญหาด้วยการลดขนาดของปัญหาลง และเลือกขนาดของกลุ่มปัญหาท่ีต้องการ เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอลั กอรทิ ึม

6 แก้ปัญหา โดยละเวน้ ปัญหาบางส่วนไว้ก่อน เพื่อจะแก้ปัญหาที่มีขนาดเลก็ ลงกว่าเดิม เนื่องจากปัญหา ท่ีมีขนาดเล็กกว่าสามารถแก้ไขปัญหาได้งา่ ยกวา่ เชน่ การคน้ หาแบบไบนารีทรี 8. อัลกอริทึ มแ บ บ การแ ป ลงแ ละเอาช น ะ (Transform and Conquer Algorithm) เป็นการแก้ไขปัญหาด้วยวิธีการเปลี่ยนรูปแบบของปัญหาที่ต้องการแก้ไขให้อยู่ใน รปู แบบอื่นก่อน ด้วยคาดหวังเมื่อเปลี่ยนรปู แบบของปัญหาแลว้ จะสามารถแกป้ ัญหาได้งา่ ยและรวดเร็ว ข้ึน เชน่ การนาขอ้ มูลทีต่ ้องการคน้ หามาจดั เรยี งข้อมูลก่อน 1.4 เคร่อื งมอื ในการพัฒนาอัลกอริทึม วฒุ ิพงษ์ เขอื่ นดิน (2553 : 7-9) กาหนดเคร่ืองมอื ทใ่ี ช้ในการพัฒนาอลั กอรทิ มึ 2 ประเภท คอื 1.4.1 ผงั งาน (Flowchart) ผังงาน หมายถึง แผนภาพแสดงลาดับขั้นตอนการทางานของโปรแกรมคอมพิวเตอร์ ต้ังแต่ เริม่ ต้นจนสนิ้ สดุ กระบวนการ โดยใชส้ ญั ลกั ษณ์รปู ภาพและใชล้ ูกศรกาหนดทศิ ทางการดาเนินการ 1. ประเภทผงั งาน สามารถแบง่ ออกไดเ้ ปน็ 2 ประเภท คือ (1) ผังงานระบบ (System Flowchart) เป็นผังงานท่ีแสดงขั้นตอนการ ทางานของระบบงานทั้งหมดอย่างกว้าง ๆ ผังงานระบบจะแสดงความสัมพันธ์ระว่างการทางาน เอกสารต่าง ๆ แสดงถึงการไหลของข้อมูลว่ามีข้อมูลอะไรบ้าง มีการประมวลผลตรงข้ันตอนใด แต่จะ ไม่แสดงวธิ กี ารทางาน หรอื ขน้ั ตอนยอ่ ยของแต่ละงาน (2) ผังงานโปรแกรม (Program Flowchart) เป็นผังงานท่ีแสดงขั้นตอน การทางานของโปรแกรมคอมพิวเตอร์อย่างละเอียด เริ่มตั้งแต่การนาข้อมู ลเข้ามาในเครื่อง คอมพิวเตอร์ การประมวลผลข้อมูล โดยจะแสดงสูตรต่าง ๆ ท่ีใช้ในการคานวณ ตลอดจนการ เปรียบเทียบเง่ือนไข การกาหนดให้วนรอบการทางานและการแสดงผลลัพธ์ท่ีได้จากการประมวลผล ซึ่งผังงานโปรแกรมจะทาใหโ้ ปรแกรมเมอร์สามารถนาไปใช้ในการเขยี นโปรแกรมได้สะดวกรวดเร็ว 2. สัญ ลักษ ณ์ ตามมาตรฐานที่ ใช้ใน การเขียน ผังงาน กาห น ดโดย ISO (International Standard Organization) และ ANSI (American National Standard Institute) ตารางที่ 1.2 สัญลกั ษณก์ ารเขียนแผนผัง สัญลักษณ์ ชือ่ ความหมาย จุดปลาย (Terminal) จดุ เริม่ ต้นและจดุ สิ้นสุด อินพุท/เอาท์พุท การรับข้อมลู หรือแสดงผลข้อมูล (Input/Output) โดยไมร่ ะบุอุปกรณ์ การประมวลผล (Process) การประมวลผล หรอื การ การตดั สินใจ (Decision) กาหนดคา่ เร่ิมต้น การเปรยี บเทียบเงื่อนไข หรือ การตัดสินใจ เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอริทมึ

7 สัญลักษณ์ ชอ่ื ความหมาย เอกสาร (Document) การพิมพผ์ ลลัพธ์ทางเคร่ืองพิมพ์ จุดเช่ือม (Connector) จุดเชื่อมต่อในหน้าเดียวกัน เส้นแสดงการไหล (Flow แสดงทศิ ทางลาดบั ของการ Line) ทางาน การแสดงผล (Display) การแสดงผลลัพธ์ทางจอภาพ ตัวเชื่อม (Off-Page ตวั เชอื่ มต่อไปหน้าอน่ื Connector) ป้อนข้อมูลดว้ ยมือ การรบั ข้อมูลทางแป้นพิมพ์ (Keyboard Input) การทางานโดยไมใ่ ชค้ อมพวิ เตอร์ การควบคุมดว้ ยมอื (Manual Input) การรบั -แสดงผลข้อมลู โดยใช้ เทปแม่เหล็ก เทปแมเ่ หลก็ (Magnetic Tape) การรบั -แสดงผลข้อมลู โดยใช้ จานแมเ่ หล็ก จานแมเ่ หล็ก การรับ-แสดงผลข้อมูล โดย (Magnetic Disk) ใช้ดรัมแมเ่ หลก็ ดรัมแมเ่ หลก็ ใช้ในการทางานทก่ี าหนดไว้แลว้ (Magnetic Drum) ในโปรแกรม ณ จดุ ใดจุดหน่ึง การนาเอาขอ้ มลู ทีบ่ ันทึกไวต้ งั้ แต่ ขั้นตอนที่นยิ าม 2 ชดุ ขนึ้ ไปมารวมเปน็ ชุดเดียว (Predened process) การรวม (Merge) 1.4.2 รหสั เทยี ม (Pseudo Code) รหัสเทียม หมายถึง ข้ันตอนการทางานของโปรแกรมคอมพิวเตอร์ โดยใช้ภาษาอังกฤษและ ภาษาคอมพิวเตอร์ผสมผสานกัน และไม่คานึงถึงหลักไวยากรณ์ เพ่ือใช้ในการอธิบายโครงสร้างและ ลาดับขั้นตอนการทางานของโปรแกรม 1. รปู แบบการเขียนรหัสเทยี ม (1) การกาหนดคา่ และการคานวณ name = expression โดย name คือ ชือ่ ตวั แปรที่ใช้สาหรบั เกบ็ คา่ expression คือ ค่าข้อมูลหรือนพิ จน์ (2) การอา่ นและการรับขอ้ มลู เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอลั กอรทิ มึ

8 READ ใชส้ าหรบั การอา่ นค่าท่ีมอี ยู่แลว้ มาเก็บไวใ้ นตัวแปร เช่น การอ่าน ขอ้ มลู จากไฟล์ โดยจะทางานร่วมกับ OPEN (การเปิดไฟล์) Read variables_1 ,variables_2, variables_3 INPUT ใชส้ าหรบั การรบั คา่ ข้อมูลผ่านทางแป้นพิมพ์ Input variables_1 ,variables_2, variables_3 Variable คอื ตัวแปรท่ีใชเ้ กบ็ ขอ้ มลู ท่ีอ่านหรือรับเขา้ มา ซง่ึ สามารถกาหนด ได้ ตามจานวนตวั แปรทีต่ ้องการ โดยใช้เครื่องหมาย “,” คัน่ ระหว่างชือ่ ตัวแปร (3) การแสดงผลขอ้ มลู PRINT ใชส้ าหรับการพิมพค์ ่าข้อมูล หรอื ขอ้ ความ print variables_1 ,variables_2, variables_3 WRITE ใช้สาหรับการบนั ทึกข้อมลู ลงในแฟม้ ข้อมลู write variables_1 ,variables_2, variables_3 1.5 โครงสร้างการควบคุมพน้ื ฐาน การเขยี นโปรแกรมคอมพิวเตอร์ ใชโ้ ครงสรา้ งการควบคมุ พืน้ ฐาน ซงึ่ มี 3 รปู แบบพนื้ ฐาน ดังนี้ (โอภาส เอ่ยี มสริ ิวงศ์, 2557 : 27-33) 1.5.1 โครงสรา้ งควบคมุ แบบเรยี งล้าดับ (Sequence) เป็นการทางานแบบลาดับข้ันตอนต่อเน่ืองกับไปในลักษณะบนลงล่าง การประมวลผลจะ เป็นไปตามแต่ละชดุ คาส่งั ตามลาดบั Statement A Statement B Statement C : : ภาพที่ 1.1 โครงสร้างควบคมุ แบบเรยี งลาดบั Statement A Statement B Statement C ภาพที่ 1.2 ผังงานโครงสร้างควบคมุ แบบเรียงลาดับ เอกสารประกอบการสอนรายวิชาโครงสรา้ งขอ้ มลู และอัลกอริทึม

9 ตวั อยา่ งท่ี 1.1 รหสั เทยี มและอัลกอรทิ ึมโครงสร้างควบคุมแบบเรยี งลาดบั รหัสเทยี ม โปรแกรมภาษาซี INPUT name , string printf (“Input Your Data:”) PRINT name , string scanf (“%s”,&Data) INPUT id , number printf (“Input Your ID:) PRINT id , number scanf (“%d”,& ID) 1.5.2 โครงสรา้ งควบคมุ แบบเลือกการทา้ งาน (Selection) 1. การเปรียบเทียบเงื่อนไข IF… เพ่ือตรวจสอบเงื่อนไขเพียง 1 ทาง คือ ถ้าเง่ือนไข เป็นจริง จะทางานในส่วนท่กี าหนด แต่ถา้ เงื่อนไขเปน็ เท็จจะข้ามการทางานคาสั่งดังกลา่ วไป if (expression) Statement 1; ภาพท่ี 1.3 โครงสร้างควบคุมแบบเลอื กการทางาน 1 เงื่อนไข condition true Statement 1 false Statement 2 ภาพท่ี 1.4 ผงั งานโครงสรา้ งควบคุมแบบเลือกการทางาน 1 เงอ่ื นไข ตัวอย่างที่ 1.2 รหัสเทียมโครงสร้างควบคมุ แบบเลอื กการทางาน 1 เงอื่ นไข รหสั เทยี ม โปรแกรมภาษาซี IF age > 60 THEN if (age > 60) print Older { END IF printf (“Older”) print OK } printf (“OK”) เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอรทิ มึ

10 2. การเปรียบเทียบเงื่อนไข IF…..THEN…..ELSE เพ่ือตรวจสอบเง่ือนไขเพียง 2 ทางเลอื ก คือ ถา้ เง่อื นไขเป็นจรงิ จะทางานโมดลู หนงึ่ แตถ่ า้ เงอื่ นไขเปน็ เทจ็ กจ็ ะทางานอกี โมดูล if (expression) Statement A; else Statement B; ภาพที่ 1.5 โครงสรา้ งควบคมุ แบบเลือกการทางาน 2 เงอ่ื นไข Statement A true condition false Statement B ภาพที่ 1.6 ผังงานโครงสรา้ งควบคมุ แบบเลือกการทางาน 2 เงอ่ื นไข ตวั อยา่ งท่ี 1.3 รหัสเทยี มโครงสรา้ งควบคุมแบบเลอื กการทางาน 2 เงอ่ื นไข รหสั เทียม โปรแกรมภาษาซี IF age >= 56 THEN if (score >= 60) print Older { ELSE printf (“Older”) print Young } else END IF { print OK printf (“Young”) } printf (“OK”) 1.5.3 โครงสรา้ งควบคมุ แบบท้าซา้ (Repetition) โครงสร้างการทางานที่สั่งให้ประมวลผลชุดคาสั่งท่ีอยู่ภายในบล็อกของวงจรลูปจะทางานซ้า ไปเร่ือย ๆ ตามจานวนรอบทตี่ ้องการหรือตามเงือ่ นไขท่ีกาหนด เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอัลกอรทิ มึ

11 1. ลูปท้าซ้าแบบ DO WHILE เป็นการวนลูปแบบ “ทาซ้าในขณะที่…” คือ มีการ ตรวจสอบเงื่อนไขก่อน หากเงื่อนไขเป็นจริง ก็จะทาซ้ากระบวนการภายในลูปไปเร่ือย ๆ จนกระท่ัง เง่ือนไขเป็นเทจ็ กจ็ ะหยดุ ทาและหลดุ ออกจากลูปไป DO Statement 1; WHILE (expression) ภาพที่ 1.7 โครงสรา้ งควบคุมแบบทาซ้าด้วย DO WHILE Statement 1 condition true false ภาพที่ 1.8 ผังงานโครงสรา้ งควบคมุ แบบทาซา้ ด้วย DO WHILE ตัวอย่างท่ี 1.4 รหัสเทยี มโครงสร้างควบคุมแบบการทาซา้ ดว้ ย DO WHILE รหัสเทียม โปรแกรมภาษาซี i=1 i=1; sum=0 sum=0; DO do { sum=sum+i i = i+1 sum = sum+i; WHILE i<=10 i++; } while (i <=10); เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอริทึม

12 2. ลูปท้าซ้าแบบ DO UNTIL เป็นการวนลูปแบบ “ทาซ้าจนกระทั่ง…” คือ ตรวจสอบเง่ือนไขว่าเป็นจริงหรือเท็จ หากเง่ือนไขยังคงเป็นเท็จก็จะทาซ้ากระบวนการภายในลูปไป เรื่อย ๆ จนกระท่ังเงอื่ นไขเปน็ จรงิ ก็จะหยุดทาและหลุดออกจากลปู ไป do Statement 1 ; until (expression) ภาพที่ 1.9 โครงสร้างควบคมุ แบบทาซา้ ดว้ ย DO UNTIL Statement 1 condition false true ภาพท่ี 1.10 ผังงานโครงสรา้ งควบคุมแบบทาซา้ ด้วย DO UNTIL ตัวอย่างท่ี 1.5 รหัสเทียมโครงสร้างควบคมุ แบบทาซา้ ดว้ ย DO UNTIL รหสั เทยี ม โปรแกรมภาษาซี i=1 i=1; sum=0 sum=0; DO do { sum=sum+i i = i+1 sum = sum+i; UNTIL i<=10 i++; } until (i <=10); เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอรทิ ึม

13 ตัวอยา่ งท่ี 1.6 จงเขยี นผังงานและโปรแกรมภาษาซี แสดงเลข 0-10 Start c=0 c<=10 true c = c+1 false Stop int c=0; printf(\"Show number from 1 to 10 \\n\"); while (c<=10); { printf(\"%d *,c); c++; } return 0; เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอรทิ มึ

14 ชอ่ื หน่วยเรียน : อาร์เรย์และลงิ คล์ ิสต์ (Array and Link list) รหสั วชิ า 13-132-207 หน่วยเรยี นท่ี 2 เวลาสอน 6 คาบ ช่อื บทเรียน 2.1 โครงสรา้ งอาร์เรย์ 2.2 ชนดิ ของอาร์เรย์ 2.3 โครงสร้างลงิ คล์ ิสต์ 2.4 ลิงคล์ สิ ต์แบบทศิ ทางเดียว จุดประสงค์การสอน 2.1 รู้โครงสรา้ งอาร์เรย์ 2.1.1 อธบิ ายความหมายอาร์เรย์ 2.1.2 อธบิ ายโครงสรา้ งของอาร์เรย์ 2.2 เขา้ ใจชนิดของอาร์เรย์ 2.2.1 หาผลลพั ธ์การทางานของอาร์เรย์ 1 มติ ิ 2.2.2 หาผลลัพธก์ ารทางานของอาร์เรย์ 2 มติ ิ 2.3 รโู้ ครงสรา้ งลงิ ค์ลสิ ต์ 2.3.1 อธิบายความหมายลงิ ค์ลิสต์ 2.3.2 อธบิ ายโครงสรา้ งของลิงคล์ สิ ต์ 2.4 สรา้ งลิงคล์ สิ ต์แบบทศิ ทางเดยี ว 2.4.1 ยกตัวอยา่ งโครงสร้างลิงค์ลิสต์แบบทิศทางเดยี ว 2.4.2 หาผลลัพธ์การทางานของลงิ ค์ลสิ ตแ์ บบทศิ ทางเดียว เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอลั กอริทมึ

15 หนว่ ยเรียนที่ 2 อาร์เรย์และลิงคล์ สิ ต์ (Array and Link list) อาร์เรย์และลิงค์ลิสต์เป็นโครงสร้างข้อมูลเชิงเส้นท่ีมีการจัดเรียงขอ้ มลู แบบต่อเนื่องและเข้าถึง ข้อมูลแบบลาดับ ซึ่งจดั เปน็ โครงสร้างข้อมูลพ้ืนฐานสาหรบั โครงสรา้ งขอ้ มูลแบบอนื่ ๆ โดยโครงสร้าง ข้อมูลแบบอาร์เรย์และลิงค์ลิสต์นาไปใช้ในโครงสร้างข้อมูล เช่น คิว (Queues) ไบนารีทรี (Binary Tree) สแตก (Stack) 2.1 โครงสรา้ งอาร์เรย์ 2.1.1 ความหมายอารเ์ รย์ นักวชิ าการได้ให้ความหมายของคาว่า “อาร์เรย์” ไว้หลายความหมาย ดงั น้ี โอภาส เอ่ียมสิริวงศ์ (2549 : 80) ได้ให้ความหมายของอาร์เรย์ไว้ว่า อาร์เรย์ หมายถึง การ รวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรช่ือเดียวกันแทนข้อมูลสมาชิกได้หลาย ๆ ตัวในคราวเดียวกัน ด้วยการใช้เลขดรรชนี (Index) หรือซับสคริปต์ (Subscript) เป็นตัวอ้างอิงตาแหน่งสมาชิกบนแถว ลาดับนน้ั ๆ บุญสืบ โพธิ์ศรี, รุ่งอรุณ ประจักจิตร์ และ สมเจตต์ ภิญญาคง (2551: 31) ได้ให้ความหมาย ของอาร์เรย์ไว้ว่า อาร์เรย์ หมายถึง ตัวแปรสาหรับการเก็บค่ากลุ่มที่มคี ่าชนิดเดียวกันที่เรียงตามลาดับ อย่างมีแบบแผน สามารถเข้าถึงค่าต่าง ๆ ในอาร์เรย์โดยอาศัย Index สมาชิกของอาร์เรย์จะต้องเป็น ขอ้ มูลที่มีลักษณะเดียวกนั และมีจานวนจากัด มีสมาชิกของอาร์เรย์จานวนแน่นอน อาจมากหรือน้อย กไ็ ด้ วฒุ ิพงษ์ เขอ่ื นดนิ (2553:23) ได้ให้ความหมายของอาร์เรย์ไว้วา่ อารเ์ รย์ หมายถึง เป็นตวั แปร ทมี่ กี ารกาหนดช่ือตวั แปรเพยี งชอื่ เดียว แต่สามารถกาหนดจานวนช่องที่ใชใ้ นการจดั เก็บข้อมลู ได้หลาย ช่อง ชนดิ ขอ้ มูลทจี่ ัดเกบ็ ในอาร์เรยช์ ดุ เดียวกันจะมีชนดิ ข้อมลู เพียงชนิดเดยี ว และการอ้างอิงถึงอารเ์ รย์ จะต้องระบุชอ่ งท่ีของอารเ์ รย์ เรียกวา่ Subscript หรอื Index วิไลพร กุลตังวัฒนา (2554 : 30) ได้ให้ความหมายของอาร์เรย์ไว้ว่า อาร์เรย์ หมายถึง โครงสร้างข้อมูลที่ใช้ตัวแปรเดียวเก็บข้อมูลชนิดเดียวกันไว้ และจะกาหนดจานวนข้อมูล หรือสมาชิก ของแถวลาดบั ไว้แน่นอน โดยจะใช้ดรรชนี (Index) ในการอ้างถงึ ตาแหน่งของข้อมูลในแถวลาดับ และ ต้องระบุดรรชนีในเคร่ืองหมายวงเล็บ ( ) หรือเครื่องหมายวงเล็บเหล่ียม [ ] ดังน้ันผู้ใช้สามารถเข้าถึง ขอ้ มลู ท่ตี อ้ งการไดท้ นั ที (Direct Access) โดยไม่ตอ้ งเข้าถงึ ข้อมูลกอ่ นหนา้ กล่าวโดยสรปุ ได้ว่า อาร์เรย์ หมายถึง ชุดของข้อมูลท่ีการจัดเก็บค่าตัวแปรชนิดเดียวกัน และ จดั เรียงลาดับก่อนหลัง สามารถเข้าถึงค่าต่าง ๆ โดยใช้เลขดรรชนี (Index) เป็นตัวอ้างองิ ตาแหน่งของ ขอ้ มลู ทาใหผ้ ้ใู ชส้ ามารถเข้าถึงขอ้ มูลทตี่ อ้ งการได้ทนั ที (Direct Access) 2.1.2 โครงสรา้ งของอารเ์ รย์ (Array Structure) โครงสร้างอาร์เรย์ จัดในรูปแบบของแถวและคอลัมน์ ซ่ึงมีท้ัง 1 มิติ 2 มิติ และ 3 มิติ โดยใช้ ตัวเลขเปน็ ตวั กากบั แถวและคอลัมน์ ดังภาพที่ 2.1 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอลั กอรทิ ึม

16 1 2 3 .. N 1 1 2 3 .. N 1 2 1 2 3 2 3 : 3 : N : N อาร์เรย์ 1 มติ ิ N อาร์เรย์ 3 มติ ิ อารเ์ รย์ 2 มิติ ภาพที่ 2.1 รปู แบบโครงสร้างอาร์เรยใ์ นรปู แบบมติ ิ โครงสร้างอารเ์ รยล์ ักษณะ (วิวฒั น์ อภสิ ิทธภ์ิ ญิ โญ และอมร มสุ ิกสาร, 2550 : 33) ดังน้ี 1. เป็นโครงสร้างเชิงเส้น (Linear Structure) คือ มีรูปแบบของการจัดเก็บข้อมูล เปน็ แนวเส้นตรงทีต่ ่อเนอ่ื งกนั 2. จัดเก็บข้อมูลแบบเรียงล้าดับ (Order) คือ นาข้อมูลที่ถูกนาเข้ามาจัดเก็บท่ีเป็น หมวดหมู่เดียวกัน หากบันทึกจะจัดเก็บเรียงแบบอันดับ เช่น เรียงลาดับของวันใน 1 สัปดาห์ Monday, Tuesday, Wednesday, …., Sunday 3. ข้อมูลภายในช่องจัดเก็บเป็นข้อมูลชนิดเดียวกัน (Homogenous Data Type) คือ หากใน 1 อาร์เรย์ มีช่องตาราง 5 ช่อง ทั้ง 5 ช่อง ก็จะต้องมีการบันทึกเป็นตัวเลขหรือ ตัวอักษรอยา่ งใดอยา่ งหน่ึงเท่าน้นั 4. มีการก้าหนดช่องตารางท่ีมีโครงสร้างตายตัว (Static Structure) คือ ช่อง ตารางที่ใช้ในการจัดเก็บข้อมูลทุกช่องต้องมีขนาดที่เท่ากัน มีการจัดเรียงในรูปแบบเชิงเส้น และ กาหนดจานวนของชอ่ งไว้อย่างตายตัว 5. การเข้าถึงข้อมูล สามารถเข้าถึงข้อมูลได้แบบสุ่ม (Random Access) คือ สามารถทจี่ ะเขา้ ถึงข้อมูลที่จดั เกบ็ ในช่องตารางใดก็ได้ 2.2 ชนดิ ของอาร์เรย์ 2.2.1. อาร์เรย์ 1 มติ ิ อาร์เรย์ 1 มติ ิ เป็นอาร์เรยท์ มี่ ีแถวเพียง 1 แถว แตจ่ ะมีคอลมั นห์ ลายคอลมั น์ ซงึ่ สามารถเขยี น ตามลกั ษณะตารางได้ 2 แบบ คือ อาร์เรย์แนวนอนและอารเ์ รยแ์ นวตง้ั ดังภาพที่ 2.2 เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มลู และอลั กอริทมึ

17 A A 123 1 2 อาร์เรย์แนวนอน 3 อารเ์ รย์แนวตั้ง ภาพท่ี 2.2 รูปแบบอารเ์ รย์แนวนอนและแนวตง้ั รปู แบบอารเ์ รย์ 1 มิติ A[l:u] ; A คือ ชอื่ ของอาร์เรย์ l คือ ค่าตา่ สุด u คอื คา่ สงู สุด โดยกาหนด ; ช่อื ของอาร์เรย์ : เปน็ การกาหนดชื่อให้กบั อาร์เรย์ เพอื่ ความสะดวกการเรียกใช้งาน ค่าต่าสดุ (Lower bound) : เป็นการระบเุ ปน็ ตาแหนง่ เร่ิมต้นของการจดั เก็บข้อมูล ค่าสูงสดุ (Upper bound) : เป็นการกาหนดตาแหน่งสูงสุดของการจดั เก็บข้อมลู เช่น ; A [-5 : 3] ช่อื อาร์เรย์ คอื A ค่าตา่ สุด คือ -5 ค่าสงู สดุ คอื 3 ในการกาหนดค่าของข้อมูลอาร์เรย์จะต้องระบุจานวนท่ีแน่นอน เพื่อจะกาหนดจานวนช่อง ภายในชุดอาร์เรย์ได้ และชนิดของข้อมูลจะต้องระบุเป็นชนิดเดียวกัน โดยรูปแบบของการกาหนดค่า จะตอ้ งระบตุ าแหนง่ ของอารเ์ รย์ ดงั น้ี รปู แบบ A [l:u] = N ; N คือ ค่าของข้อมูล รูปแบบอารเ์ รย์ท่ีเป็นการระบุรายละเอยี ด A[5] = 10 รูปแบบอาร์เรยท์ ่ีเป็นชอ่ งตาราง A 5 10 15 20 25 12345 การกาหนดค่าตัวแปร A ให้กับอาร์เรย์ที่มีการจองพ้ืนที่ของจานวนช่อง 5 ช่อง สาหรับข้อมูล ชนิด integer (เลขจานวนเต็ม) จานวน 5 ค่า ซึ่งจะทาให้เห็นความสัมพันธ์ของตาแหน่งของอาร์เรย์ และค่าข้อมูลว่ามกี ารจัดความสัมพันธ์แบบ 1 ต่อ 1 คือ ใน 1 ตาแหน่งมีข้อมูล 1 คา่ หรือ 1 ค่าข้อมูล ถกู จัดเก็บอยใู่ น 1 ตาแหนง่ ดงั ภาพที่ 2.3 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ ึม

18 ตาแหนง่ ค่าข้อมลู [1] 5 [2] 10 [3] 15 [4] 20 [5] 25 ภาพท่ี 2.3 ความสัมพนั ธอ์ ารเ์ รยแ์ บบ 1 ตอ่ 1 1. การหาจา้ นวนช่องของตารางของอารเ์ รย์ หากต้องการท่ีจะกาหนดขนาดของอาร์เรย์ทต่ี ้องการใช้งาน เพือ่ การเก็บข้อมลู มีสูตร ดงั น้ี จ้านวนช่องตาราง = (u-l) + 1 ; เมอ่ื u = คา่ สงู สุด l = คา่ ตา่ สดุ ตัวอยา่ งท่ี 2.1 ต้องการเก็บคะแนนสอบของนักศึกษาเลขประจาตัว 260001-260024 จงหาจานวน ช่องตารางของอาร์เรยใ์ นการจดั เก็บคะแนนทง้ั หมด ค่าสงู สดุ (u) = 260024 คา่ ต่าสดุ (l) = 260001 จากสตู ร จานวนช่องตาราง = (u-l) +1 = (260024-260001)+1 = 23 + 1 = 24  อาร์เรยช์ ุดน้มี จี านวนช่องตาราง 24 ชอ่ ง 2. การคา้ นวณหาตา้ แหน่งของ A(i) การหาตาแหน่งใด ๆ ของชุดอาร์เรย์ในหน่วยความจา จะใช้ตัวช้ีเป็นตัวหาตาแหน่ง สามารถหาได้จากสตู ร addr(a[i]) = b + (i-l1) x L ; เมอื่ b คือ ตาแหนง่ แรกทบี่ นั ทึกข้อมลู ในหนว่ ยความจา i คือ ตาแหน่งท่เี ป็นตวั ช้ี l1 คือ คา่ ต่าสุด L คือ ค่าความกว้างของชนดิ ข้อมูล เอกสารประกอบการสอนรายวชิ าโครงสรา้ งขอ้ มูลและอลั กอริทมึ

19 ตัวอย่างท่ี 2.2 อาร์เรย์ NEW จองพ้ืนท่ีไว้ 10 ช่อง คือ NEW [-3:6] ใช้ความกว้างของแต่ละช่อง จัดเก็บ 10 ไบต์เก็บในพ้ืนท่ีหน่วยความจาตาแหน่งแรกคือ 200 จงหา addr (NEW[6]) จากตัวอยา่ งระบุคา่ ได้ คือ b=200, i=3, l1=-3, L=10 addr(NEW[5]) = b + (i-l1) x L = 200 + (6-(-3)) x 10 = 200 + (9) x 10 = 290 ตารางที่ 2.1 ตาแหนง่ บนพนื้ ทีห่ นว่ ยความจา พน้ื ทบ่ี นหนว่ ยความจ้า ต้าแหนง่ อาร์เรย์ ตัวอย่างคา่ ขอ้ มลู 200 [-3] 5 210 [-2] 10 220 [-1] 15 230 [0] 20 240 [1] 25 250 [2] 30 260 [3] 35 270 [4] 40 280 [5] 45 290 [6] 50 จากตารางที่ 2.1 แสดงตารางแทนค่าพ้ืนท่ีบนหน่วยความจา (Address) เทียบกับ ตาแหน่ง อาร์เรย์ (index) ท่ีกาหนดค่าไว้คือ NEW[-3], NEW[-2], NEW[-1], NEW[0], NEW[1], NEW[2], NEW[3], NEW[4], NEW[5], NEW[6] และพื้นท่ีบนหน่วยความจาเร่มิ จัดเก็บจากตาแหน่งท่ี 200 ความกว้าง 10 ไบต์ ตาแหน่งต่อไปคือ 200, 210, 220, 230, 240, 250, 260, 270, 280, 290 ตามลาดับ ดังน้ันหากต้องการบันทึกข้อมูลลงในอาร์เรย์ช่องที่ 6 บนหน่วยความจาต้องบันทึกลง แอดเดรส 290 2.2.2 อารเ์ รย์ 2 มิติ อาร์เรย์ 2 มิติ เป็นอาร์เรย์ที่มีแถวหลายแถวและคอลัมน์หลายคอลัมน์ ซ่ึงถูกกากับด้วย ตาแหน่งของแถวและคอลัมน์ อาร์เรย์ A(M,N) สามารถท่ีจะกาหนดแสดงได้ในรูปแบบของตารางดัง ภาพที่ 2.4 เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอลั กอริทึม

20 แถว (Rows) คอลมั น์ (Column) 1 2 3 4 5…N 1 A(1,1) A(1,2) A(1,3) A(1,4) A(1,5) … A(1,N) 2 A(2,1) A(2,2) A(2,3) A(2,4) A(2,5) … A(2,N) 3 A(3,1) A(3,2) A(3,3) A(3,4) A(3,5) … A(3,N) 4 A(4,1) A(4,2) A(4,3) A(4,4) A(4,5) … A(4,N) 5 A(5,1) A(5,2) A(5,3) A(5,4) A(5,5) … A(5,N) :: : : : : : : M A(1,N) A(2,N) A(3,N) A(4,N) A(5,N) … A(M,N) ภาพที่ 2.4 รปู แบบอารเ์ รยใ์ นแบบตาราง รูปแบบอารเ์ รย์ 2 มิติ A[l1:u1 , l2:u2] ; เมอื่ A คือ ชื่อของอารเ์ รย์ l1 คือ ค่าต่าสุดของมติ ิที่ 1 u1 คือ ค่าสูงสดุ ของมติ ทิ ่ี 1 l2 คือ คา่ ต่าสดุ ของมิติท่ี 2 u2 คือ คา่ สูงสดุ ของมิตทิ ี่ 2 โดยกาหนด ; ช่อื ของอาร์เรย์ : เป็นการกาหนดชื่อใหก้ ับอาร์เรย์ เพอ่ื ความสะดวกการเรียกใช้งาน คา่ ตา่ สดุ (Lower bound) : เป็นการระบุเปน็ ตาแหน่งเริ่มต้นของการจัดเกบ็ ข้อมลู มติ ทิ ่ี 1 และมิติที่ 2 ค่าสูงสุด (Upper bound) : เป็นการกาหนดตาแหน่งสูงสุดของการจัดเก็บข้อมูล มติ ิท่ี 1 และมติ ทิ ่ี 2 มิติที่ 1 คือ อาร์เรย์ A ทีจ่ ัดเกบ็ ตาแหน่งตัง้ แต่ 1,..,M คา่ ต่าสุดคือ 1 คา่ สูงสดุ คือ M มิตทิ ี่ 2 คอื อาร์เรย์ A ที่จัดเก็บตาแหน่งต้งั แต่ 1,.,N คา่ ต่าสุดคอื 1 ค่าสงู สดุ คอื N เช่น ; A[1:3,1:3] ชือ่ อาร์เรย์ คอื A มติ ิที่ 1 ค่าตา่ สดุ คอื 1 คา่ สูงสุด คือ 3 มิตทิ ่ี 2 คา่ ตา่ สดุ คือ 1 ค่าสงู สดุ คือ 3 สามารถเขยี นให้อย่ใู นรปู เซตของอารเ์ รยไ์ ด้ ดังภาพท่ี 2.5 A[1:3,1:3] 1 1 =A(1,1) 1 1 =A(2,1) 1 1 =A(3,1) 2 2 =A(1,2) 2 2 =A(2,2) 2 2 =A(3,2) 3 3 =A(1,3) 3 3 =A(2,3) 3 3 =A(3,3) ภาพที่ 2.5 รปู แบบของการเขียนเซตของอาร์เรย์ 2 มิติ เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มูลและอลั กอริทมึ

21 จากตัวอย่าง ทาให้ได้จานวนเซตของอาร์เรยจ์ านวน 12 ตาแหน่ง ซ่งึ แบ่งเป็นเซตของมิติท่ี 1 จานวน 3 ตาแหน่ง เซตของมิติที่ 2 จานวน 3 ตาแหน่ง และเซตของมติ ทิ ี่ 3 จานวน 3 ตาแหนง่ ตารางของอาร์เรย์สามารถระบุเขียนแบบการระบุรายละเอียดได้ อาร์เรย์ A(M,N) ที่มีการ เร่มิ ต้นทีต่ าแหน่ง A(1,1) หากมกี ารจัดเก็บค่าข้อมูล ก็สามารถจดั เกบ็ ได้ตามตาแหน่ง 123 1 10 20 30 2 40 50 60 3 70 80 90 ภาพท่ี 2.6 รปู แบบอาร์เรยใ์ นการจัดเก็บค่าข้อมลู จากภาพท่ี 2.6 มีการจัดเกบ็ ค่าขอ้ มูลในตาราง ดังนี้ แถวที่ 1 มีคา่ ข้อมลู 10, 20, 30 จดั อยูใ่ นตาแหนง่ คือ [1,1] [1,2] [1,3] ตามลาดับ แถวท่ี 2 มคี ่าข้อมูล 40, 50, 60 จดั อยใู่ นตาแหนง่ คอื [2,1] [2,2] [2,3] ตามลาดบั แถวท่ี 3 มคี ่าขอ้ มูล 70, 80, 90 จดั อยใู่ นตาแหน่ง คอื [3,1] [3,2] [3,3] ตามลาดับ และค่าข้อมูลว่ามีการจัดความสัมพันธ์แบบ 1 ต่อ 1 คือ ใน 1 ตาแหน่งมีข้อมูล 1 ค่า หรือ 1 ค่าขอ้ มูลถกู จดั เกบ็ อย่ใู น 1 ตาแหนง่ ดงั ภาพท่ี 2.7 ตาแหน่ง ค่าข้อมลู [1,1] 10 [1,2] 20 [1,3] 30 [2,1] 50 [2,2] 60 [2,3] 70 [3,1] 90 [3,2] 100 [3,3] 110 ภาพท่ี 2.7 การระบุตาแหนง่ พร้อมค่าข้อมลู 1. การค้านวณหาจา้ นวนสมาชกิ การหาจานวนสมาชิกในอาร์เรย์ 2 มิติ นั้น จะต้องการทราบจานวนช่องของการ จดั เกบ็ ข้อมูล จึงจะสามารถหาจานวนสมาชกิ ของอารเ์ รย์ จากการคูณกันของจานวนของอาร์เรยใ์ นมิติ ที่ 1 และ 2 เอกสารประกอบการสอนรายวิชาโครงสรา้ งข้อมูลและอลั กอรทิ มึ

22 สตู รที่ 1 จ้านวนชอ่ งตาราง = (u-l) + 1 ; เมอ่ื u = คา่ สงู สุด สตู รท่ี 2 l = ค่าตา่ สดุ จ้านวนสมาชิก = M x N ตวั อย่างที่ 2.3 จงหาจานวนสมาชิกของอาร์เรย์ A[-1:3,1:5] = (3-(-1)) + 1 แยกหาจานวนชอ่ งของอาร์เรยแ์ ต่ละมิติ = (3+1) +1 จานวนช่องของอารเ์ รยม์ ิติท่ี 1 A[-1,3] =5 = (5-1) + 1 จานวนชอ่ งของอาร์เรย์มิติที่ 2 A[1:5] = 4+1 =5 จานวนสมาชกิ ของอาร์เรย์ A = 5X5 แสดงในรูปแบบของช่องตารางไดด้ งั น้ี = 25 12345 -1 A[-1,1] A[-1,2] A[-1,3] A[-1,4] A[-1,5] 0 A[0,1] A[0,2] A[0,3] A[0,4] A[0,5] 1 A[1,1] A[1,2] A[1,3] A[1,4] A[1,5] 2 A[2,1] A[2,2] A[2,3] A[2,4] A[2,5] 3 A[3,1] A[3,2] A[3,3] A[3,4] A[3,5] 2. การคา้ นวณหาต้าแหนง่ (Address) ของ A(i,j) อาร์เรย์ 2 มิติ จัดเรียงข้อมูลตามรูปแบบของแถวและคอลัมน์ โดยการจัดเรียงตาม รปู แบบของแถว (Row major) คอื การเริม่ อ่านคา่ ข้อมลู ของตาแหน่งแถวก่อนแลว้ ตามดว้ ยคอลัมนซ์ ่ึง อ่านในแนวนอน ดังภาพที่ 2.8 ส่วนการจัดเรียงรูปแบบของคอลัมน์ (Column major) คือ การเริ่ม อ่านค่าของตาแหนง่ คอลัมนก์ อ่ นแล้วตามด้วยแถวซึ่งอ่านค่าในแนวต้งั ดงั ภาพที่ 2.9 12345 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ภาพที่ 2.8 การจดั เรียงตามรูปแบบของแถว (Row major) เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอัลกอรทิ ึม

23 1 6 11 16 21 2 7 12 17 22 3 8 13 18 23 4 9 14 19 24 5 10 15 20 25 ภาพท่ี 2.9 การจดั เรยี งรูปแบบของคอลมั น์ (Column major) การคา้ นวณหาต้าแหน่ง addr[i,j] = b+L(u2-l2+1)(i-l1)+L(j-l2) ; เม่อื b คือ ตาแหน่งแรกทบ่ี ันทึกข้อมูล L คือ ความกว้างของชนดิ ขอ้ มูล i คือ ตาแหนง่ ท่เี ปน็ ตัวชขี้ องมติ ทิ ่ี 1 j คอื ตาแหนง่ ท่ีเปน็ ตัวชขี้ องมิตทิ ่ี 2 u2 คือ ค่าสูงสดุ ของมติ ิท่ี 2 l2 คือ ค่าตา่ สดุ ของมิติที่ 2 l1 คอื ค่าตา่ สดุ ของมติ ทิ ี่ 1 ตวั อยา่ งท่ี 2.4 จงหาตาแหน่งตัวชี้ของ addr(aa[2,4]) และ addr(aa[4,5] เม่ือกาหนดให้เร่ิมต้นเก็บ ข้อมูลในหน่วยความจาท่ีตาแหน่ง 300 ความกว้างของแต่ละช่องจัดเก็บได้ 10 ไบต์ กาหนดอาร์เรย์ aa(1:4,3:5) addr(aa[i,j]) = b+L(u2-l2+1)(i-l1)+L(j-l2) = 300 + 10(5-3+1)(i-1)+ 10(j-3) = 300 + 30(i-1) +10(j–3) = 300 + 30i – 30 + 10j -30 = 240 + 30i + 10j แทนค่า i และ j ด้วยตาแหน่งที่ตอ้ งการหาจากฟงั กช์ นั ดังนี้ 1. addr(aa[2,4])= 240 + 30(2) + 10(4) = 240 + 60 + 40 = 340 2. addr(aa[4,5])= 240 + 30(4) + 10(5) = 240 + 120 + 50 = 410 เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ ึม

24 จากตัวอยา่ งข้างตน้ สามารถแสดงเป็นตารางเทยี บตาแหน่งไดด้ ังน้ี พ้นื ท่บี นหนว่ ยความจา้ ตา้ แหน่งอารเ์ รย์ ตัวอย่างข้อมลู 300 [1,3] 1 310 [1,4] 2 320 [1,5] 3 330 [2,3] 4 340 [2,4] 5 350 [2,5] 6 360 [3,3] 7 370 [3,4] 8 380 [3,5] 9 390 [4,3] 10 400 [4,4] 11 410 [4,5] 12 จากการเทยี บค่าของตาแหนง่ อาร์เรยท์ ่ีมีการจองพื้นท่ีในหน่วยจาเริม่ ตน้ การบันทึกท่ี ตาแหน่ง 300 จัดเก็บข้อมูลช่องละ 10 ไบต์ ตาแหน่ง addr(aa[2,4]) บนหน่วยความจาตรงกับ ตาแหนง่ 340 และตาแหน่ง addr(aa[4,5]) ตรงกบั ตาแหน่ง 410 2.3 โครงสรา้ งลงิ ค์ลิสต์ 2.3.1 ความหมายลิงคล์ ิสต์ นักวชิ าการไดใ้ ห้ความหมายของคาวา่ “ลิงคล์ สิ ต์” ไวห้ ลายความหมาย ดงั นี้ ณัฐพงษ์ วารีประเสริฐ และสธุ ี พงศาสกุลชัย (2552 : 56) ได้ให้ความหมายของลิงค์ลิสต์ไว้ว่า ลงิ ค์ลิสต์ หมายถึง โครงสร้างท่ีจัดเก็บข้อมูลด้วยโหนดต่อเน่ืองกัน โดยแต่ละโหนดจะถูกระบุตาแหน่ง บนหน่วยความจา เพ่ือใช้อ้างอิงหรือเข้าถึงได้ ภายในโหนดประกอบด้วย 2 ส่วน คือ ส่วนท่ีจัดเก็บ ข้อมลู และส่วนท่ีจดั เก็บพอยนเ์ ตอร์ วุฒิพงษ์ เขื่อนดิน (2553 : 157) ได้ให้ความหมายของลิงค์ลิสต์ไว้ว่า ลิงค์ลิสต์ หมายถึง โครงสรา้ งข้อมลู ที่ออกแบบใหม้ ีลักษณะไม่เป็นเชิงเส้น เป็นการนาขอ่ มูลไปเก็บไว้ในหน่วยความจาและ นาข้อมูลออกไปใช้ภายหลัง ข้อมูลที่จัดเก็บ 1 รายการ เรียกวา่ 1 โหนด การนาข้อมูลเข้าจะต้องขอใช้ งานหน่วยความจาใหม่กอ่ นโดยใชพ้ อยนเ์ ตอร์ไปชีต้ าแหน่งหน่วยความจาที่จะใช้ กชกร ณ นครพนม และคณะ (2557 : 4-6) ได้ให้ความหมายของลิงค์ลิสต์ไว้ว่า ลิงค์ลิสต์ หมายถึง ข้อมูลที่ถูกนามาจัดเรียงกันในลักษณะต่อเนื่องเป็นเส้นตรงหรือไม่เรียงเป็นเส้นตรงติดต่อกัน ไปก็ได้ แต่ละโหนดมีตัวเชื่อมเรียกว่า พอยน์เตอร์ ชี้ไปยังโหนดถัดไป โดยโหนดสุดท้ายมีค่าเป็นว่า เรยี กว่า NULL เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมลู และอัลกอรทิ มึ

25 กล่าวโดยสรุปได้ว่า ลิงค์ลิสต์ หมายถึง ข้อมูลท่ีถูกนามาจัดเก็บเรียงกันในลักษณะเส้นตรง โดยข้อมูลจะถกู จัดเรยี งเปน็ ชุด ๆ เรยี กว่า โหนด (Node) ซึ่งแต่ละโหนดจะประกอบดว้ ยขอ้ มูล 2 ส่วน คอื ส่วนของข้อมลู (data) และส่วนลงิ คข์ อ้ มูล (link) Node data link ภาพที่ 2.10 ส่วนประกอบของโหนดในโครงสร้างลิงค์ลสิ ต์ 2.3.2 โครงสรา้ งของลิงค์ลิสต์ การเช่ือมโยงไปยังโหนดอื่น ๆ ของลิงค์ลิสต์จะใช้รูปแบบของพอยน์เตอร์เป็นตัวช้ีไปยังโหนด ต่อ ๆ ไป ดังนั้นลิงค์ลิสต์จึงมีรูปแบบของการจัดเก็บข้อมูลท่ีประกอบไปด้วยโหนดต่าง ๆ ท่ีจัดเก็บ ข้อมูลอยู่และทาการเช่อื มโยงโหนดเหลา่ น้ีด้วยพอยนเ์ ตอร์ ทาใหม้ ลี กั ษณะโครงสร้างดงั ภาพท่ี 2.11 Head 5 10 15 20 data link data link data link data link (a) (b) ภาพท่ี 2.11 โครงสรา้ งของลงิ ค์ลสิ ตใ์ นการเชื่อมโยง จากภาพที่ 2.11 (a) โหนดของลิงค์ลิสต์มีส่วนท่ีเป็นข้อมูลและการเชื่อมโยง โดยส่วนของการ เชื่อมโยงที่พอยน์เตอร์ในการกาหนดช้ีไปยังโหนดเริ่มต้น ปกติจะเรียกพอยน์เตอร์น้ีว่า Head และใน ตาแหนง่ สดุ ท้ายของโหนดที่ไม่มีการเชื่อมโยงไปยังโหนดอนื่ กจ็ ะมีการประกาศค่าเป็นลสิ ตว์ ่าง (Empty link list) ดงั ภาพที่ 2.11 (b) ลิงค์ลิสต์ถือเป็นโครงสร้างที่มีการทางานท้ังการเก็บข้อมูลและการเช่ือมโยงไปยังตาแหน่ง ตอ่ ไปมีลกั ษณะสาคัญ ดงั น้ี (วิวัฒน์ อภสิ ทิ ธภ์ิ ญิ โญ และอมร มุสิกสาร, 2550 : 89) 1. โครงสร้างข้อมูลเป็นรูปแบบเชิงเส้น (Linear Structure) มีลักษณะของการ เริ่มตน้ ค่าขอ้ มูลหนว่ ยแรกเปน็ หน่วยเร่ิมตน้ จากนั้นมหี นว่ ยต่อไปจะเห็นไดว้ า่ ลิงคล์ สิ ต์เริ่มชต้ี าแหนง่ ไป ยงั โหนดแรกและมกี ารช้ีไปยังตาแหนง่ ต่อไปจนถึงตาแหน่งโหนดสดุ ท้าย 2. โครงสร้างข้อมูลไม่ตายตัว (Dynamic Structure) ลักษณะของลิงค์ลิสต์เม่ือ ทาการประมวลผลสามารถที่จะปรับเปลี่ยนโครงสร้างได้โดยไม่ต้องกาหนดจองพื้นที่หน่วยความจาไว้ ลว่ งหนา้ สามารถที่จะทาการเพ่มิ โหนดหรอื ลบโหนดได้ทนั ที 3. โครงสร้างข้อมูลไม่เป็นล้าดับ (Non-Order Structure) โดยลักษณะของ โครงสร้างนั้นไม่จาเป็นต้องลาดับการจัดเก็บว่าจาก 1 ต้องเป็น 2 หรือเพิ่มค่าตามกาหนด แต่สามารถ ที่จะจดั โครงสรา้ งในลาดับใดกอ่ นกไ็ ด้ตามท่หี นว่ ยความจาจดั ให้ เอกสารประกอบการสอนรายวชิ าโครงสร้างขอ้ มลู และอัลกอรทิ มึ

26 2.4 ลิงค์ลิสตแ์ บบทิศทางเดยี ว (Single Linked List) 2.4.1 โครงสรา้ งลิงคล์ ิสตแ์ บบทิศทางเดยี ว ลิงค์ลิสต์แบบทิศทางเดียวเป็นลิงค์ลิสต์ที่มีการเช่ือมโยงด้วยพอยน์เตอร์ไปในทิศทางเดียวกัน คือ ชี้ไปยังโหนดที่อยู่ถัดไปในโครงสร้าง ซ่ึงลิงค์ลิสต์ในลักษณะน้ีถือเป็นรูปแบบพ้ืนฐานของลิงค์ลิสต์ แบบอ่ืน ๆ คือประกอบไปด้วยโหนดท่ีจัดเก็บข้อมูลและมีการเช่ือมโยง (วิวัฒน์ อภิสิทธ์ิภิญโญ และ อมร มุสกิ สาร, 2550 : 90-92) ดังภาพที่ 2.12 Node data link ภาพท่ี 2.12 โครงสรา้ งลิงค์ลิสตแ์ บบทศิ ทางเดียว เนื่องจากลิงค์ลิสต์เป็นโครงสร้างแบบไดนามิกคือไม่ตายตัวสามารถที่จะปรับโครงสร้างได้ ตลอดการประมวลผล ดังน้ันจึงมีการกาหนดโครงสร้างของลิงค์ลิสต์ให้มีส่วนประกอบสาคัญ 3 ประการคือ 1. โครงสร้างโหนดต้นลิสต์ (Head Node Structure) การท่ีโครงสร้างของลิงค์ ลิสต์มีโครงสร้างที่เป็นแบบไดนามิก ทาให้เกิดความไม่แน่นอนเร่ืองของจานวนโหนดว่าขณะปัจจุบัน เมื่อทาการประมวลผลจานวนโหนดถูกลบหรือเพิ่ม ซึ่งเป็นลักษณะที่เรียกว่า Meta data ถึงแม้ว่า สามารถตรวจสอบได้ด้วยการใช้พอยน์เตอร์เข้าไปนับจานวนแต่ละโหนดได้แต่จะเป็นการเสียเวลา เพราะจะต้องเร่ิมต้ังแต่โหนดแรก ดังน้ันจึงมีการกาหนดโครงสร้างของโหนดแรกของโครงสร้างซึ่งจะ เรียกว่า โหนดต้นลิสต์ (Head Node) มาใช้ในการเก็บข้อมูลเก่ียวกับจานวนของโหนดในโครงสร้าง หรอื ข้อมลู สาคัญอื่น ๆ count head ภาพท่ี 2.13 โครงสร้างโหนดต้นลสิ ต์ (Head structure) Count: การนับจานวนโหนดในลิสต์ เป็นส่วนประกอบของโหนดต้นลิสต์ที่ทาการ จดั เก็บจานวนโหนดภายในลิสต์ไมร่ วมโหนดต้นลิสตท์ าใหส้ ะดวกและรวดเร็วเม่ือต้องการทราบจานวน ของโหนดก็อ่านค่าได้จาก Count และจากภาพที่ แสดงให้ทราบว่ามีจานวนโหนดอยู่ในลิสต์ 4 โหนด ดว้ ยกนั count head 5 10 15 20 data link data link data link data link 4 ภาพที่ 2.14 จานวนโหนดทีอ่ ่านคา่ จาก count ของโหนดต้นลิสต์ 2. โครงสร้างโหนดข้อมูล (Data Node Structure) สาหรับโครงสร้างโหนด ขอ้ มูลของลงิ ค์ลสิ ต์น้ันโดยรปู แบบทวั่ ไปจะประกอบไปด้วย 2 ส่วน หลักหรือ 2 ฟิลด์หลักคือ ฟิลด์แรก เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอริทึม

27 เก็บในส่วนของข้อมูล และฟิลด์ที่ 2 เก็บค่าของการเช่ือมโยงในส่วนของการเชื่อมโยงก็จะใช้พอยน์ เตอรเ์ ปน็ ตัวเชอ่ื มโยงไปยงั โหนดอืน่ ๆ 5 10 15 data link data link data link ภาพที่ 2.15 โครงสร้างของโหนดขอ้ มลู 3. ทิศทางของพอยน์เตอร์ (Pointer Link) สาหรับทิศทางพอยน์เตอร์ของลิงค์ ลิสต์แบบทิศทางเดียว จะทาการช้ีไปยังทิศทางเดียวกันเสมอคือไปยังโหนดต่อไปในสมาชิก เมื่อไม่มี สมาชิกใดหรือโหนดใดอีก พอยนเ์ ตอร์กจ็ ะประกาศเป็นลิสตว์ า่ ง (Empty List) Empty list Head 5 10 15 20 data link data link data link data link ภาพท่ี 2.16 โครงสร้างของลิงค์ลสิ ตใ์ นการเชอ่ื มโยง 2.4.2 การท้างานของลิงคล์ สิ ต์แบบทศิ ทางเดียว 1. การสร้างลสิ ต์ (Create List) ก่อนที่จะมีการสร้างลิสต์จะยังไม่มีการช้ีไปท่ีโหนดใด แต่เม่ือมีการสร้างลิสต์ข้ึนมา เพ่ือที่จะนาไปใช้งาน จะต้องมีการประกาศค่าให้ชี้ไปยังโหนดเร่ิมต้น ทาให้ลิสต์ท่ีเป็นลิสต์ของพอยน์ เตอร์เร่ิมตน้ ที่ไมม่ กี ารช้ีค่า null และมีจานวนสมาชิกเป็นศูนย์ 0 count head ภาพท่ี 2.17 การสร้างลิสต์ 2. การเพ่มิ โหนด (Add Node) การเพ่ิมโหนด สามารถเพิ่มโหนดต่อ ๆ กันไปได้ โดยใช้ล้ิงค์เป็นตัวเชื่อมระหว่าง โหนด และกาหนดค่าสุดท้ายที่ไม่มีการชี้เป็นค่า nil ซ่ึงจานวนสมาชิกจะมีค่าเท่ากับจานวนโหนด ทง้ั หมด 3 10 20 30 count head ภาพที่ 2.18 การเพิ่มโหนด เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอลั กอริทมึ

28 3. การลบโหนด (Delete node) การลบโหนด สามารถลบทั้งโหนดและข้อมูลท่ีไม่ต้องการออกไป ซึ่งมหี ลักการง่าย ๆ ดว้ ยการเปลยี่ นลิ้งคข์ องโหนดก่อนหน้าที่ตอ้ งการลบให้ชไ้ี ปยงั ล้งิ ค์ของโหนดทตี่ ้องการลบ กอ่ นการลบโหนด 3 5 10 15 count head หลังการลบโหนด 2 5 ลบโหนด 15 count head ภาพที่ 2.19 การลบโหนด 4. การแทรกโหนด (Insert Node) เมื่อมีโหนดมาเพิ่มอกี ก็จะต้องเพ่ิมในลกั ษณะท่เี ป็นการแทรกเข้าไประหวา่ งโหนดเดิม และโหนดต้นลสิ ต์ การแทรกโหนดมี 4 รปู แบบดงั นี้ (1) การแทรกโหนดเมือ่ ลิสต์วา่ ง (Insert Into Empty List) ก่อนท่ีจะมีการแทรกโหนดจะมีการสร้างลิสต์ขึ้นมากาหนดพอยน์เตอร์ให้ชี้ ไปยังโหนดต้นลิสต์ หากไม่มีการช้ีต่อไปท่ีโหนดใด แสดงว่าเป็นลิสต์ที่ว่าเป็นลิสต์ท่ีว่างและเมื่อมีการ เพิม่ โหนดขึน้ มาใหม่ ก็จะมีการจองพื้นท่ีให้กับโหนดพร้อมกับค่าข้อมูล เม่อื ตอ้ งการลิงค์ของโหนดก่อน หน้าชม้ี ายังโหนดท่ีทาการแทรก ก่อนการแทรกโหนด 0 count head หลงั การแทรกโหนด 15 count ภาพท่ี 2.20hกeaาdรแทรกโหนดเมือ่ ลิสต์ว่าง จากภาพที่ 2.20 การแทรกโหนดจากโครงสร้างของลิงค์ลิสต์ว่าง และโหนด ที่เพิม่ ข้นึ มาใหมม่ ีข้อมูลคือ 5 และกาหนดลิงค์กจ็ ะเปน็ การแทรกโหนดทีเ่ สร็จเรยี บร้อย (2) การแทรกโหนดตา้ แหน่งกอ่ นหนา้ (Insert at Beginning) สาหรับการแทรกโหนดรูปแบบนี้กระทาได้ก็เมื่อมีโหนดอื่น ๆ อยู่ใน โครงสร้างแล้ว หากมีการเพ่มิ โหนดขึ้นมาใหมก่ ็จะแทรกไวก้ ่อนหน้าโหนดอนื่ ๆ เสมอ เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมลู และอลั กอริทมึ

29 ก่อนการแทรกโหนด 1 15 count head หลงั การแทรกโหนด 2 15 count head 5 ภาพท่ี 2.21 การแทรกโหนดตาแหน่งก่อนหน้า จากภาพที่ 2.21 เม่ือมีการเพ่ิมโหนดใหม่ข้ึนมาจะต้องเซตลิงค์ของโหนดให้ ช้ีไปยังโหนดเดิมก่อน ซึ่งจะทาให้โหนดข้อมูล 5 เช่ือมต่อโหนดข้อมูล 15 จากนั้นจึงกาหนดลิงค์ของ โหนดมาเชื่อมกนั (3) การแทรกโหนดตา้ แหนง่ กลาง (Insert in Middle) เม่ือมีการแทรกโหนดเข้าไปหลาย ๆ ตัว หากต้องการท่ีจะแทรกเขา้ ไปยัง ตาแหน่งกลางก็สามารถทาได้ตามหลักการคือ ช้ีลิงค์ของโหนดใหม่ไปยังลงิ ค์ที่โหนดตาแหน่งกอ่ นหน้า ชไ้ี ป จากน้ันเซตลิงค์ของตาแหนง่ โหนดกอ่ นหนา้ น้ันช้ีมาทโี่ หนดใหม่ ก่อนการแทรกโหนด 2 5 15 count head หลังการแทรกโหนด 3 5 15 count head 10 ภาพท่ี 2.22 การแทรกโหนดตาแหน่งกลาง จากภาพที่ 2.22 จะมโี ครงสร้างโหนดใหมข่ ึ้นมา เซตค่าลิงค์ไปที่โหนดที่เก็บ ขอ้ มูล 15 และค่าของลิงค์โหนดขอ้ มลู 5 ช้มี ายังโหนดที่จดั เกบ็ ขอ้ มลู 10 (4) การแทรกโหนดตา้ แหน่งทา้ ย (Insert at End) สาหรับการแทรกโหนดไปยังตาแหน่งท้ายจะมีการเซตลิ้งค์คล้ายกับการ แทรกโหนดท่ีตาแหน่งกลางเพียงแต่จะทาการตรวจสอบว่าตาแหน่งก่อนการแทรกมีค่าของล้ิงค์เป็น nil หรอื ไม่ หากใช่ก็ทาการแทรกไปยังตาแหนง่ นัน้ และกาหนดการล้ิงค์ไปยังโหนดใหม่ เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอัลกอรทิ ึม

30 กอ่ นการแทรกโหนด 3 5 10 15 count head หลังการแทรกโหนด 4 5 10 15 20 count head ภาพท่ี 2.23 การแทรกโหนดตาแหนง่ ท้าย ตวั อย่างท่ี 2.5 จงสรา้ งโหนดต้นลิสต์และเพ่ิมโหนด 10 แล้วดาเนินการต่อไปนี้ 1 10 count head 1. แทรกโหนด 5 ตาแหน่งก่อนหน้า 2 10 5 count head 2. แทรกโหนด 7 ตาแหนง่ กลาง 3 5 10 7 count head 3. ลบโหนดท้ายสุด 2 5 7 ลบ count head เอกสารประกอบการสอนรายวชิ าโครงสร้างข้อมลู และอัลกอรทิ มึ

31 ชอื่ หน่วยเรยี น : ควิ (Queues) รหสั วิชา 13-132-207 หนว่ ยเรียนที่ 3 ช่อื บทเรียน เวลาสอน 3 คาบ 3.1 โครงสรา้ งควิ 3.2 การดาเนนิ การของควิ 3.3 การแทนควิ ด้วยอารเ์ รย์ จดุ ประสงค์การสอน 3.1 รู้โครงสรา้ งคิว 3.1.1 บอกลกั ษณะโครงสรา้ งคิว 3.2 เข้าใจการดาเนนิ การของคิว 3.2.1 อธิบายการนาเข้าข้อมลู ของคิว (Enqueue) 3.2.2 อธบิ ายการนาขอ้ มูลออก (Dequeue) 3.3 เข้าใจการแทนควิ ดว้ ยอารเ์ รย์ 3.3.1 ยกตัวอย่างและแกป้ ัญหาการแทนควิ ดว้ ยอารเ์ รย์ 3.3.2 แก้ปัญหาการแทนควิ ด้วยอาร์เรย์ 3.3.3 แก้ปญั หาการแทนคิวดว้ ยวงกลม เอกสารประกอบการสอนรายวชิ าโครงสรา้ งข้อมูลและอัลกอรทิ มึ

32 หน่วยเรียนท่ี 3 คิว (Queues) คิวเป็นโครงสร้างข้อมูลแบบเชิงเส้น ท่ีมีลักษณะเฉพาะคือการนาเข้าข้อมูล (Enqueue) ทางด้านส่วนท้ายของคิว และการนาข้อมูลออก (Dequeue) ทางด้านส่วนหัวของคิว โดยข้อมูลที่เข้า มาก่อนจะต้องออกก่อน ส่วนข้อมูลที่เข้ามาทีหลังต้องออกหลัง ซ่ึงเป็นรูปแบบคล้ายกับการเข้าคิว เรียกว่า เขา้ ก่อนออกกอ่ น (First in First out) 3.1 โครงสรา้ งคิว คิวเป็นโครงสร้างข้อมูลที่มีลักษณะของการเข้าและออกของข้อมูลอย่างเป็นลาดับ ข้อมูลใด เข้ามาก่อนก็จะดาเนินการก่อน หากข้อมูลใดเข้ามาทีหลังก็จะดาเนินการทีหลัง เรียกว่า เข้าก่อนออก ก่อน หรือ First in first out (FIFO) คือ เมื่อต้องการนาเข้าข้อมูลจะต้องนาข้อมูลไปต่อส่วนท้ายของ คิว เรียกว่า rear และถ้าตอ้ งการนาข้อมูลออก จะต้องนาออกทางส่วนหัวของคิว ซึ่งเรียกว่า front นาออก นาเข้า (Dequeue) (Enqueue) ก่อน (front) หลงั (rear) (a) การเขา้ แถว (b) การทางานแบบคิวของคอมพวิ เตอร์ ภาพที่ 3.1 เปรยี บเทียบการทางานของควิ กับการเขา้ แถว โครงสรา้ งควิ มลี กั ษณะ (วิวัฒน์ อภสิ ทิ ธ์ิภญิ โญ และอมร มุสิกสาร, 2550 : 153) ดังน้ี 1. โครงสร้างข้อมูลเปน็ รูปแบบเชิงเส้น (Linear structure) ควิ จะมีการจัดข้อมูล ท่ีนาเข้ามาต่อเน่ืองกันไปโดยข้อมูลใดเข้ามาก่อนก็จะอยู่อันดับแรก และข้อมูลที่ตามเข้ามาทีหลังก็จะ เรียงกันไป 2. โครงสร้างเป็นแบบไม่ตายตัว (Dynamic structure) เน่ืองจากคิวสามารถที่ จะดาเนนิ การทงั้ การเพิ่มและลดขอ้ มูลได้ ทาใหข้ นาดของข้อมูลนั้นมกี ารเปล่ยี นแปลงตลอดเวลา 3. สามารถน้าเข้าและดึงข้อมูลออกได้ (Enqueue and Dequeue) โดยการ นาเข้าข้อมูลและการนาข้อมูลออกของคิวนั้นสามารถเพิ่มข้อมูลได้ในส่วนของ rear และดึงข้อมูลออก จากโครงสร้างในดา้ น front 4. ท้างานแบบเข้าก่อนออกก่อน (First in First out) โดยการดาเนินการกับ ข้อมูลนั้น หากการนาเข้าข้อมูลใดก่อนก็จะดาเนินการกับข้อมูลน้ันก่อนเรียงต่อเน่ืองกันไปจนกว่าจะ หมดรายการ เอกสารประกอบการสอนรายวิชาโครงสร้างข้อมูลและอลั กอรทิ มึ

33 3.2 การดา้ เนนิ การของควิ การดาเนินการพื้นฐานโครงสร้างข้อมูลแบบคิว คือ มีการนาเข้าข้อมลู ด้วยการต่อท้ายและดึง ข้อมลู ออกในส่วนหวั สามารถแบง่ ออกเปน็ 2 กรณี คอื 3.2.1 การนา้ เข้าข้อมลู (Enqueue) หากมีการนาเข้าข้อมูลแรกเข้าสู่คิวแล้วข้อมูลน้ีจะเป็นข้อมูลอันดับแรก และเม่ือมีการเพิ่ม ข้อมูลเข้ามาอีกข้อมูลใหม่เข้ามา จะต้องมีการตรวจสอบก่อนว่าคิวเต็ม (Overflow) หรือไม่ ถ้าไม่เต็ม จงึ จะสามารถเพิ่มขอ้ มลู ลงในคิวได้ โดยจะตอ่ ท้ายในส่วนของ rear ซ่ึงก็คอื rear =rear + 1 C 12 123 ABC AB Enqueue front rear front rear ภาพที่ 3.2 การดาเนนิ การ Enqueue จากภาพท่ี 3.2 เมื่อโครงสร้างของคิวนั้นมีข้อมูลคือ A และ B ซึ่งถือว่า C เป็นข้อมูลส่วนหัว และ B เป็นข้อมูลสว่ นท้าย เมอ่ื มกี ารนาเขา้ ข้อมูล C หรือ Enqueue ขอ้ มูลจะนาไปตอ่ ทา้ ยกบั ขอ้ มลู ที่ อยู่ในตาแหน่ง rear ซ่ึงก็คือการต่อท้าย B ทาให้เกิดการเปลี่ยนแปลงโครงสร้างของคิวก็คือตาแหน่ง rear จะเปลี่ยนจาก B เป็น C แทน 3.2.2 การน้าข้อมลู ออก (Dequeue) ก่อนการนาข้อมูลที่ตาแหน่งส่วนหัวออกจากคิว จะต้องมีการตรวจสอบว่า คิวว่าง (Underflow) หรือไม่ ถ้าไม่ว่างจึงสามารถดาเนินการนาข้อมูลออกจากคิวได้ โดยกระทาเฉพาะส่วน หวั หรอื front ของโครงสรา้ งเทา่ นั้น ซ่งึ กค็ ือ front = front +1 A 123 23 ABC Dequeue BC front rear front rear ภาพท่ี 3.3 การดาเนินการ Dequeue จากภาพที่ 3.3 โครงสร้างของคิวท่ีมีสมาชิก 3 ตัว เม่ือมีการ Dequeue ข้อมูลจะดาเนินการ ตาแหน่ง front นั้นหมายความว่าข้อมูล A จะถูกดึงออกไปทาให้ตาแหน่งของ front เล่ือนไปที่ ตาแหนง่ ตอ่ ไปกค็ ือ B เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอลั กอริทมึ

34 3.3 การแทนควิ ด้วยอารเ์ รย์ การแทนโครงสร้างคิวด้วยอาร์เรย์ จะต้องกาหนดจานวนของการจองพื้นที่บนหน่วยความจา และใชอ้ ารเ์ รยใ์ นการนาขอ้ มลู เขา้ ดา้ นท้ายและนาขอ้ มูลออกในส่วนหวั ดงั ภาพที่ 3.4 ข้อมลู ออก ข้อมูลเขา้ ภาพที่ 3.4 การนาเขา้ และนาออกข้อมูลในโครงสร้างอารเ์ รย์ 3.3.1 โครงสร้างของการแทนคิวด้วยอาร์เรย์ การแทนคิวด้วยอาร์เรย์จะต้องมีการระบุจานวนสูงสุดของพ้ืนท่ีเก็บข้อมูล (Maxsize) พร้อม กับกาหนดพอยน์เตอร์ข้ึนมาอีก 2 ตัว คือ front กับ rear เพ่ือใช้ในการช้ีค่าข้อมูลท่ีอยู่ส่วนหัวและ สว่ นท้าย [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 rear= 5 ABCD พน้ื ท่วี า่ ง Front Rear ภาพที่ 3.5 รปู แบบโครงสร้างการแทนคิวด้วยอาร์เรย์ จากภาพท่ี 3.5 มีการกาหนดโครงสร้างของอาร์เรย์ เพ่ือแทนคิวโดยกาหนดจานวนสูงสุดใน การจัดเก็บคือ 10 ช่อง และในโครงสร้างมีการนาเข้าข้อมูล คือ A B C D จัดเก็บในอาร์เรย์ Q[1] ถืง Q[4] พอยน์เตอร์จึงมีการชี้หัว front = Q[1]=A และพอยน์เตอร์ช้ีสว่ นท้าย rear = Q[4]=D และยังมี พ้ืนที่ว่างสาหรับการนาเข้าข้อมูลอีก 6 ช่อง ในกรณีที่มีการ Enqueue น้ันข้อมูลจะถูกนาในด้านของ rear และตอ่ ท้ายกันไปจนกระท่ังถึงจานวนช่องสูงสุด คิวน้ันก็จะเตม็ และไม่สามารถ Enqueue ได้อีก ดังภาพที่ 3.6 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] front= 1 ABCDEFGH I J rear= 10 Front rear ภาพที่ 3.6 การ Equeue จากภาพที่ 3.6 เมื่อมีการ Equeue ขอ้ มูลเขา้ จะกระทาที่ส่วนของ rear ทาให้ rear มกี ารเพ่ิม ตาแหน่งขึ้น เช่น เมอ่ื มกี าร Enqueue E ก็จะเพิ่มเข้ามาตอ่ ที่ Q[5] แทน และเมื่อ Enqueue เพ่ิมเติม เอกสารประกอบการสอนรายวิชาโครงสร้างขอ้ มลู และอัลกอรทิ ึม