ใบงานที่ 10 การเรียงลำดับข้อมูล (Sorting)

ตอบ

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

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

วิธีการเรียงลำดับ
เนื่องจากมีวิธีการมากมายที่สามารถใช้ในการเรียงลำดับข้อมูลได้ บางวิธีก็มีขั้นตอนการจัดเรียงเป็นแบบง่าย ๆ ตรงไปตรงมา แต่ใช้เวลาในการจัดเรียงลำดับนาน และบางวิธีก็มีขั้นตอนในการจัดเรียงลำดับแบบซับซ้อนยุ่งยากแต่ใช้เวลาในการจัดเรียงไม่นานนัก ดังนั้นจึงควรศึกษาวิธีการจัดเรียงลำดับด้วยวิธีการต่าง ๆ เพื่อเลือกใช้วิธีการที่ดีและเหมาะสมกับระบบงานนั้นที่สุด วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ
(1)การเรียงลำดับแบบภายใน (internal sorting)เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก
(2) การเรียงลำดับแบบภายนอก(external sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลักและหน่วยความจำสำรองนอกเหนือจากเวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน
การเรียงลำดับแบบเลือก (selection sort)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยู่ทีละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับถ้าเป็นการเรียงลำดับจากน้อยไปมาก
1. ในรอบแรกจะทำการค้นหาข้อมูลตัวที่มีค่าน้อยที่สุดมาเก็บไว้ที่ตำแหน่งที่ 1
2. ในรอบที่สองนำข้อมูลตัวที่มีค่าน้อยรองลงมาไปเก็บไว้ที่ตำแหน่งที่สอง
3. ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกค่าในที่สุดจะได้ข้อมูลเรียงลำดับจากน้อยไปมากตามที่ต้องการ

ในรอบที่ 1 ทำการเปรียบเทียบข้อมูลเพื่อค้นหาข้อมูลที่มีค่าน้อยที่สุด คือ 22นำไปวางที่ตำแหน่งที่ 1 สลับตำแหน่งกับ 35ในรอบที่ 2 ทำการเปรียบเทียบอีกเพื่อค้นหาค่าที่น้อยที่สุดรองลงมาโดยเริ่มค้นตั้งแต่ตำแหน่งที่ 2 เป็นต้นไปได้ค่าน้อยที่สุดคือ 35นำไปวางที่ตำแหน่งที่ 2 สลับตำแหน่งกับ 67ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่งถึงรอบสุดท้ายคือรอบที่ 7 จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามที่ต้องการการจัดเรียงลำดับแบบเลือกเป็นวิธีที่ง่ายและตรงไปตรงมา แต่มีข้อเสียตรงที่ใช้เวลาในการจัดเรียงนานเพราะแต่ละรอบต้องเปรียบเทียบกับข้อมูลทุกตัว ถ้ามีจำนวนข้อมูลทั้งหมด n ตัว ต้องทำการเปรียบเทียบทั้งหมดรอบเป็นดังนี้รอบที่ 1 เปรียบเทียบเท่ากับ n −1 ครั้งรอบที่ 2 เปรียบเทียบเท่ากับ n – 2 ครั้ง
...
รอบที่ n – 1 เปรียบเทียบเท่ากับ 1 ครั้งn – 1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละจำนวนครั้งของการเปรียบเทียบทั้งหมด
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง
การเรียงลำดับแบบฟอง (Bubble Sort)เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1. ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2. ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีกำหนดให้มีข้อมูล n จำนวน การเปรียบเทียบเริ่มจากคู่แรกหรือคู่สุดท้ายก็ได้ ถ้าเริ่มจากคู่สุดท้ายจะเปรียบเทียบข้อมูลที่ตำแหน่ง n-1 กับ n ก่อนแล้วจัดเรียงให้อยู่ในตำแหน่งที่ถูกต้อง ต่อไปเปรียบเทียบข้อมูลที่ตำแหน่ง n-2 กับ n-1 ทำเช่นนี้ไป เรื่อย ๆจนกระทั่งถึงข้อมูลตัวแรก และทำการเปรียบเทียบในรอบอื่นเช่นเดียวกันจนกระทั่งถึงรอบสุดท้ายที่เหลือข้อมูล 2 ตำแหน่งสุดท้าย เมื่อการจัดเรียงเสร็จเรียบร้อยทุกตำแหน่งก็จะ

ได้ข้อมูลเรียงลำดับตามที่ ต้องการจากตัวอย่าง การเปรียบเทียบจะเริ่มเปรียบเทียบจากคู่หลัง ในรอบที่ 1 เปรียบเทียบข้อมูลที่ตำแหน่งที่ 7 กับ 8 ได้ว่า 43 น้อยกว่า 82 ให้ทำการสลับตำแหน่งกันเพื่อให้ค่าที่น้อยกว่าอยู่ก่อนต่อไปเปรียบเทียบข้อมูลตำแหน่งที่ 6 กับ 7 ได้ว่า43 น้อยกว่า 99 ให้ทำการสลับตำแหน่งกันอีก ทำการเปรียบเทียบเช่นนี้ในคู่ต่อไปเรื่อย ๆ จนกระทั่งในรอบที่ 2 ทำการเปรียบเทียบข้อมูลจากคู่หลังมาคู่หน้าเช่นกัน แต่จะเปรียบเทียบถึงตำแหน่งที่ 2เท่านั้นจนกระทั่งได้ค่าต่ำสุดรองลงมาไว้ในตำแหน่งที่ 2 ในรอบต่อไปก็ทำในทำนองเดียวกันจนกระทั่งถึงรอบสุดท้ายคือรอบที่ 7 จะเหลือข้อมูลที่ต้องเปรียบเทียบคู่เดียวคือข้อมูลในตำแหน่งที่ 7 กับ 8เมื่อการจัดเรียงเสร็จเรียบร้อยเราจะได้ข้อมูลที่มีการเรียงลำดับจากน้อยไปมากตามที่ต้องการการจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมากนัก เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่เข้าใจง่าย แต่ประสิทธิภาพการทำงานค่อนข้างต่ำพอ ๆ กับการเรียงลำดับแบบเลือกในหัวข้อที่ผ่านมาถ้ามีจำนวนข้อมูลทั้งหมด n ตัวไม่ว่าข้อมูลเป็นอย่างไรก็ตามต้องทำการเปรียบเทียบทั้งหมด n −1 รอบ และจำนวนครั้งของการเปรียบเทียบในแต่ละรอบเป็นดังนี้

กรณีที่แย่ที่สุดจำนวนครั้งของการเปรียบเทียบดังนี้
รอบที่ 1 เปรียบเทียบเท่ากับ n − 1 คู่
รอบที่ 2 เปรียบเทียบเท่ากับ n − 2 คู่
...
รอบที่ n −1 เปรียบเทียบเท่ากับ 1 คู่จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง 
กรณีที่ดีที่สุด
คือ กรณีที่ข้อมูลมีการเรียงลำดับในตำแหน่งที่ถูกต้องอยู่แล้ว โดยจะทำการเปรียบเทียบในรอบที่ 1 รอบเดียวเท่านั้น ก็สามารถสรุปได้ว่าข้อมูลเรียงลำดับเรียบร้อยแล้ว ถ้ามีจำนวนข้อมูลทั้งหมด n จำนวนจำนวนครั้งของการ
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้ว ใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็นสองส่วนถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วนอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมด จะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไปจนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการถ้าเป็นการเรียงลำดับจากน้อยไปมากการเปรียบเทียบเพื่อหาตำแหน่งให้กับค่าหลักตัวแรกเริ่มจากข้อมูลในตำแหน่งแรกหรือสุดท้ายก็ได้ ถ้าเริ่มจากข้อมูลที่ตำแหน่งที่ 1เป็นค่าหลัก พิจารณาเปรียบเทียบค่าหลักกับข้อมูลในตำแหน่งสุดท้าย ถ้าค่าหลักมีค่าน้อยกว่าให้เปรียบเทียบกับข้อมูลในตำแหน่งรองสุดท้ายไปเรื่อย ๆ จนกว่าจะพบค่าที่น้อยกว่าค่าหลักแล้วให้สลับตำแหน่งกันหลังจากสลับตำแหน่งแล้วนำค่าหลักมาเปรียบเทียบกับข้อมูล ในตำแหน่งที่ 2, 3,ไปเรื่อย ๆ จนกว่าจะพบค่าที่มากกว่าค่าหลักสลับตำแหน่งเมื่อเจอข้อมูลที่มากกว่าค่าหลัก ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งได้ตำแหน่งที่ถูกต้องของค่าหลักนั้น ก็จะแบ่งกลุ่มข้อมูลออกเป็นสองส่วน ส่วนแรกข้อมูลทั้งหมดมีค่าน้อยกว่าค่าหลักและส่วนที่สองข้อมูลทั้งหมดมีค่ามากกว่าค่า

จากการเปรียบเทียบข้างต้นในที่สุดก็ได้ตำแหน่งที่วางค่าหลัก 44 ซึ่งข้อมูลจะถูกแบ่งเป็น 2 ส่วน ส่วนที่ 1 ข้อมูลทั้งหมดมีค่าน้อยกว่าค่าหลัก และส่วนที่ 2 ข้อมูลทั้งหมดมีค่ามากกว่าค่าหลัก นำแต่ละส่วนไปดำเนินการเปรียบเทียบในลักษณะเดียวกันจนกระทั่งข้อมูลทั้งหมดเรียงลำดับจากน้อยไปมากตามต้องการการจัดเรียงลำดับแบบเร็วเป็นวิธีที่ค่อนข้างซับซ้อน แต่ประสิทธิภาพการทำงานค่อนสูง เนื่องจากใช้เวลาในการเรียงลำดับน้อย ถ้ามีข้อมูลทั้งหมด n ตัวจำนวนครั้งของการเปรียบเทียบเป็นดังนี้ กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งแล้วข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n log2 n ครั้ง
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปมากหรือจากมากไปน้อย หรือค่าหลักที่เลือกในแต่ละครั้งเป็นค่าหลักที่น้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้จำนวนครั้งของการเปรียบเทียบ
= (n −1) + (n −2) + . . . + 3 + 2 + 1
= n (n −1) / 2 ครั้ง
การเรียงลำดับแบบแทรก (insertion sort)เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ที่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับจะ
1. เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2. จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยจะก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน

ถ้ามีจำนวนข้อมูลเป็น n การจัดเรียงแบบแทรกจะมีการจัดเรียงทั้งหมดเท่ากับ n − 1 รอบ จำนวนครั้งของการเปรียบเทียบในแต่ละรอบแตกต่างกันขึ้นอยู่กับลักษณะการจัดเรียงของข้อมูลนั้น กรณีที่ดีที่สุด คือ กรณีข้อมูลทั้งหมดจัดเรียงในตำแหน่งที่ต้องการเรียบร้อยแล้ว กรณีนี้ในแต่ละรอบมีการเปรียบเทียบเพียงครั้งเดียว เพราะฉะนั้นจำนวนครั้งของการเปรียบเทียบเป็นดังนี้จำนวนครั้งของการเปรียบเทียบ = n − 1 ครั้ง
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับในตำแหน่งที่กลับกัน เช่น ต้องการเรียงลำดับจากน้อยไปมาก แต่ข้อมูลมีค่าเรียงลำดับจากมากไปน้อย จำนวนครั้งของการเปรียบเทียบในแต่ละรอบดังนี้
ในรอบที่ 1 จำนวนครั้งของการเปรียบเทียบเป็น 1 ครั้ง
ในรอบที่ 2 จำนวนครั้งของการเปรียบเทียบเป็น 2 ครั้ง
จำนวนครั้งของการเปรียบเทียบ
= 1 + 2 + 3 + . . . +(n −2) + (n −1)
= n (n −1) / 2
การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1. เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน นั่นคือถ้าข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่วยก่อน
2. การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว แล้วนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่ม ๆตามลำดับการเข้ามา
3. ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อย ๆ จนหมดทุกกลุ่ม
4. ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำเช่นนี้ไปเรื่อย ๆ จนกระทั่งครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ

เมื่อจัดกลุ่มในรอบแรกเสร็จแล้วรวบรวมข้อมูลในทุกกลุ่มเริ่มตั้งแต่ข้อมูลในกลุ่ม 0 จนถึงกลุ่ม 9 ได้ข้อมูลเรียงตามลำดับดังนี้

ในรอบที่ 2 เมื่อทำการจัดกลุ่มเรียบร้อยแล้วให้รวบรวมข้อมูลในทุกกลุ่มเริ่มจากข้อมูลในกลุ่ม 0จนถึงกลุ่ม 9 ได้ข้อมูลเรียงตามลำดับดังนี้11 22 29 35 40 43 47 55 58 67 82 99
การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม เช่นถ้ามีจำนวนข้อมูล n ตัว และในแต่ละกลุ่มใช้วิธีจัดเก็บข้อมูลในแถวลำดับ ต้องกำหนดให้แต่ละกลุ่มมีสมาชิกได้ n ตัวเท่ากับจำนวนข้อมูลเผื่อไว้กรณีที่ข้อมูลทั้งหมดมีค่าในหลักนั้น ๆเหมือนกัน ถ้าเป็นเลขจำนวนใช้ทั้งหมด 10 กลุ่มกลุ่มละ n ตัวรวมทั้งหมดมีขนาดเท่ากับ (10 x n)

ใบงานที่ 9 โครงสร้างข้อมูลแบบทรี Tree

ตอบ
ทรี (Tree)ป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมัความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใชสำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับ โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆโหนด เรียกโหนดดั้งกล่าวว่า โหนดแม่(Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหดราก (Root Node) Data Structure โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน รียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree)และถามโหนดหนึ่งเป็นโหดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีทแยกจากกัน (Disjoint Trees)

2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น

3.ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกันหรือทรีที่มีรูปร่างของทรีเหมือนกันโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด

4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5.กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่นในรูปโหนด “B” มีกำลังเป็น 1 เพราะมีทรีย่อย คือ {“D”}ส่วนโหนด “C” มีค่ากำลังเป็นสองเพราะมีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}

6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง (Height)หรือความ ลึก (Depth)

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

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

โครงสร้างทรีที่แต่ละโหนดมีลิงค์ฟิลด์แค่สองลิงค์ฟิลด์ ซึ่งช่วยให้ประหยัดเนื้อที่ในการจัดเก็บได้มาก เรียกโครงสร้างทรีที่แต่ละโหนดมีจำนวนโหนดลูกไม่เกินสองหรือแต่ละโหนดมีจำนวน ทรีย่อยไม่เกินสองนี้ว่า ไบนารีทรี (Binary Tree)

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)

สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ถ้ากำหนดให้ Lคือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ L มีจำนวนโหนด 2L - 1โหนด
นั้นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่ มี L ระดับ สามารถคำนวณได้จากสูตรดั้งนี้

การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดั้งต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จบให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆโหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)

มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์

(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก

(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์
เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบเช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้

ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree)เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของโหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน

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

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

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

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

ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

ใบงานที่ 8 โครงสร้างข้อมูลแบบ Link List

ตอบ

โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)             
             โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมากอย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่องเมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวกเนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มากในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า    การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใดลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง
              สมมติว่าเราจะแทนชุดข่าวสารที่ประกอบด้วย A,B,C ลักษณะการแทนจะเป็นไปตามรูปซึ่งเป็นภาพแสดงแนวคิดการเก็บแบบหนึ่งส่วนการเก็บข่าวสาร A,B,C แท้จริงแล้วจะเป็นในรูปไหนก็ได้แต่ก็ต้องสอดคล้องกับแนวความคิดนี้ รูปที่ 3 แสดงถึงความเป็นไปได้อีกแบบหนึ่งเมื่อข่าวสาร A,B,C อยู่ในพื้นที่ความจำ

รูปการแทนโครงสร้างแบบลิงค์ลิสต์
               ข่าวสาร A อยู่ที่ตำแหน่ง 5000 ดูได้จากค่าที่ตำแหน่ง 6000 ผู้ใช้จะต้องรู้ว่า head node ของค่าชุดนี้อยู่ที่แอดเดรส 6000 ส่วนค่า A,B,C ผู้ใช้ไม่ทราบว่าอยู่ที่ใดยกเว้นแต่จะตามพอยน์เตอร์เข้าไป จากตำแหน่ง 6000 เรารู้ว่าค่าที่อยู่ที่ตำแหน่ง 5000 คือค่าแรก (ค่า A ) จากส่วนพอยน์เตอร์ของ A (ที่ตำแหน่ง 5001) เรารู้ว่าค่าถัดไป (ค่าB) อยู่ที่ตำแหน่ง 5600 เราตามพอยน์เตอร์ไปยังตำแหน่ง 5600 พบ B ค่าพอยน์เตอร์ของ B ที่ตำแหน่ง 5601 เป็นแอดเดรสของค่าถัดไป (ค่า C) ซึ่งอยู่ที่ตำแหน่ง 5508 จากค่า C เมื่อพิจารณาค่าพอยน์เตอร์ของ C พบว่าค่า - 1 ซึ่งหมายถึงว่าสิ้นสุดของค่าชุดนี้แล้ว อนึ่งผู้ใช้ไม่สามาร5นำค่า A หรือ B หรือ C มาใช้โดยตรงอย่าในอาร์เรย์ ผู้ใช้ต้องเดิน เข้าไปหาค่าเหล่านี้ลักษณะการหาค่าแบบนี้คล้าย ๆ กับการหาค่าในเทปซึ่งเรียกว่า การหาค่าแบบลำดับ (sequential access) ซึ่งในทางปฏิบัติสำหรับระบบโปรแกรมภาษาชั้นสูงเราอาจใช้อาร์เรย์เป็นตัวเก็บค่า A,B,C และใช้อีกหนึ่งอาร์เรย์เป็นตัวเก็บพอยน์เตอร์ดังรูปซึ่งผู้ใช้ต้องทราบว่าค่าแรกของข่าวสารชุดนี้อยู่ที่ตำแหน่งที่ 2 ในอาร์เรย์ INFO (3)

รูปการแทนลิงค์ลิสต์ด้วยอาร์เรย์ 2 ชุด
ลิงค์ลิสต์เดี่ยว (Singly Linked List) 
  ลิงค์ลิสต์เดี่ยวหมายถึงลิงค์ลิสต์ที่แต่ละข่าวสารมีการแสดงออกถึงลำดับก่อนหลังอย่างชัดเจนโดยใช้พอยน์เตอร์นั่นคือในแต่ละข่าวสารจะมีส่วนที่บอกว่าข่าวสารตัวต่อไปอยู่ที่ใดแต่ละข่าวสารจะเรียกว่าโหนด (node) แต่ละโหนดจะมี 2 ช่อง ดูรูปที่ 1 เป็นตัวอย่างเราจะใช้สัญลักษณ์ต่อไปนี้ในการเรียกชื่อแต่ละโหนด
              NODE(P) หมายถึงโหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์P 
              INFO(P) หมายถึงส่วนข่าวสารของโหนดที่ถูกชี้โดย P 
              LINK(P) หมายถึงส่วนแอดเดรสของโหนดที่ถูกชี้P
              ในระบบการแทนโดยลิงค์ลิสต์เราจะสมมติว่าหน่วยความจำจะประกอบด้วยชิ้นส่วนความจำเป็นชิ้น ๆ ดังรูปที่ 2 (เรียกว่าโหนด)แทนที่จะเป้นแบบพื้นที่ความจำติดต่อกันไปดังอาร์เรย์ชิ้นส่วนความจำทั้งหมดนี้จะคล้องกันเป็นลิงค์ลิสต์เดี่ยวขนาดมหึมาซึ่งที่รวมความจำนี้เรียกว่า storage pool หรือหน่วยเก็บข้อมูลส่วนรวมเมื่อผู้ใช้ต้องการพื้นที่เก็บข่าวสารก็เรียกเอาโหนดจาก storage pool ถ้าผู้ใช้ไม่ต้องการใช้โหนดใดก็คืนโหนดนั้นไปยัง storage poolเพื่อผู้อื่นจะได้ใช้โหนดแรกของ storage pool จะถูกชี้โดยพอยน์เตอร์ที่ชื่อ AVAIL
  แนวความคิดเรื่อง storage pool นั้น ตีความได้ในงานจริง ๆ เช่น storage pool อาจประกอบด้วยเก้าอี้นั่งทั้งหมดในเครื่องบินโดยสารลำหนึ่งหรือเป็นจำนวนที่นั่งที่ยังไม่ได้จองของสายการบินหนึ่งในเวลาใด ๆ
               1.1การจัดสรรหน่วยเก็บข้อมูล(Storage Allocate) การจัดสรรหน่วยเก็บข้อมูลเป็นการนำโหนดออกจากหรือคืนโหนดสู่ storage pool ซึ่งจะสมมติว่ากระทำโดยฟังก์ชัน 2 ชุด คือ ALLOCATE P และ FREE P ซึ่งจะนิยามดังนี้
              ALLOCATE P :นำโหนดหนึ่งออกจาก ALLOCATE P แล้วให้พอยน์เตอร์P ชี้ไปยังโหนดนั้น
              FREE P : คืนโหนดที่ถูกชี้โดย P ไปยัง storage pool
             การทำงานของ ALLOCATE P ดูได้จากรูปที่ 6 ซึ่งสมมติว่า storage pool ประกอบด้วยโหนด5 โหนด หลังการประมวลผล storage pool จะประกอบด้วย 4 โหนดและโหนดP เป็นโหนดที่นำมาใช้ได้ ฟังก์ชัน ALLOCATE P สามารถเขียนเป็นชุดคำสั่งได้ดังนี้
             1.IF AVAIL = - 1 THEN แจ้งผู้ใช้ว่าไม่มีโหนดเหลือใน storage pool; 
             2.P = AVAIL ; / * ให้ P ชี้ไปยังโหนดแรก * /
             3.AVAIL = LINK (AVAIL) ; / * ดูรูปที่ 4.7 * /


รูปการทำงานของ storage pool และคำสั่ง ALLOCATE P 
                    LINK(AVAIL) หมายถึงส่วนพอยน์เตอร์ของโหนดแรกซึ่งบอกค่าตำแหน่งของโหนดถัดไปใน storage pool ดังนั้นค่า AVAIL ใหม่ คือแอดเดรสของโหนดที่สอง (อนึ่งเราจะได้ผลเหมือนกันถ้าเขียนว่า AVAIL = LINK (P) แทนคำสั่งที่ 3 ) ก็เพียงแต่โยงลูกศรไปยังโหนดถัดไปการทำความเข้าใจระบบการใช้งานของลิงค์ลิสต์ไม่มีทางใดดีกว่าวาดรูปการทำงานของแต่ละคำสั่ง ต่อไปนี้จะแสดงวิธีการทำความเข้าใจแบบนี้ตลอดหนังสือเล่มนี้ดังนั้นของให้ผู้อ่านฝึกหัดตามไปด้วย
                    ต่อจากคำสั่ง ALLOCATE P เป็นการทำความเข้าใจกับคำสั่ง FREE P ชุดคำสั่งแทน FREE P จะเป็นดังนี้
                     1.IF AVAIL = - 1 THEN DO ; AVAIL = P; 
                     2. LINK(AVAIL) = - 1 
                     3. END ;
                     4. ELSE DO ; LINK(P) = AVAIL ; 
                     5. AVAIL = P; 6. END;
                   1.2 การนำข้อมูลเข้าสู่และออกจากลิงค์ลิสต์(Insertion and Deletion)
                   ก่อนอื่นขอให้พิจารณาดูการนำข่าวสาร 5 เข้าสู่อาร์เรย์A (ซึ่งมี 10 ช่อง) ที่ตำแหน่ง 3 ดังรูปที่ 10 เพื่อให้ค่าต่าง ๆ เรียงอยู่ในลำดับที่ถูกต้องจะเห็นได้ว่าในลักษณะนี้จะต้องมีการเลื่อนข่าวสารในอาร์เรย์อย่างมากเพื่อเปิดทางให้กับตัวที่เข้ามาใหม่กระบวนการเช่นนี้จะเสียเวลามากถ้าแต่ละข่าวสารเป็นเรคอร์ด (record) ขนาดใหญ่ในระบบที่มีการใช้ลิงค์ลิสต์ การนำข่าวสารเข้าหรือออกจะสะดวกมากเนื่องจากสามารถทำสำเร็จได้โดยคำสั่งไม่กี่คำสั่งเพื่อเปลี่ยนค่าพอยน์เตอร์อย่างมาก 2 ค่า เท่านั้น
                  1) การนำข้อมูลเข้า (Insertion) สมมติว่าเรามีลิงค์ลิสต์ H อยู่แล้ว (โหนดที่ถูกชี้โดย H คือ head node ของลิงค์ลิสต์นี้ ) และเราต้องการนำข่าวสารที่ถูกชี้โดยพอยน์เตอร์P (หรือโหนดP) ไปอยู่ต่อจากโหนดH1
INSERT : PROCEDURE (X,H1) /* ต้องการนำข่าวสาร X เข้าไปต่อท้ายโหนดที่ถูกชี้โดย H1 ในลิงค์ลิสต์ที่มี head node H */ 
/* ให้ Q เป็นพอยน์เตอร์ที่จะใช้ชั่วคราว */ 
/* เราจะนำ X มาใช้โดยตรงไม่ได้ ต้องสร้างโหนดเพื่อเก็บ X เสียก่อน */
ALLOCATE Q ; 
INFO(Q) = X ;
/* ก่อนจะนำ X เข้า ต้องตรวจสอบกรณีพิเศษสองกรณีคือ (1) ตรวจสอบว่าลิงค์ลิสต์ H นี้ว่างเปล่าหรือไม่ (2) ตรวจสอบว่า H1 เป็นโหนดสุดท้ายหรือไม่ */
IF H = NULL / * สมมติว่าค่า NULL ทำงานเช่นเดียวกับ - 1 */ THEN /* แสดงว่าลิงค์ลิสต์ H ว่างเปล่า */ แจ้งให้ผู้ใช้ทราบและจบ ; 
IF LINK(H1) = NULL 
THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */
LINK (Q) = NULL;
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1); 
ELSE /* แสดงว่าโหนดH1 ไม่ใช่โหนดสุดท้าย
*/ LINK (Q) = LINK(H1); 
LINK (H1) = Q; 
/*ในที่สุดเราจะได้ลิงค์ลิสต์ใดแล้วแต่กรณี*/
หรือ
END
INSERT;

                     2)การนำข้อมูลออก (Deletion) ในการนี้เราต้องการนำข้อมูลในโหนดที่ต่อถัดจากโหนดH1 มาไว้ในตัวแปร X และให้คืนโหนดนั้นไปยัง storage pool
DELETE : PROCEDURE(X,H1) 
/* ฟังก์ชันนี้จะนำข่าวสารในโหนดที่ถัดจาก H1 ไปเก็บไว้ใน X แล้วคืนโหนดนั้นไปยัง storage pool*/ /* มีกรณีพิเศษที่ต้องพิจารณาสามกรณีคือ
1)ลิงค์ลิสต์ H ว่างเปล่า
2)ลิงค์ลิสต์ H ประกอบด้วยโหนดเดียว
3)โหนดH1 เป็นโหนดสุดท้าย */
IF H = NULL
THEN /*แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */ แจ้งให้ผู้ใช้ทราบ ,จบ ; 
IF LINK(H) = NULL THEN /* แสดงว่าลิงค์ลิสต์นั้นมีโหนดเดียว */แจ้งให้ผู้ใช้ทราบ , จบ; 
IF LINK (H) =NULL และ LINK(H1) = NULL THEN /* แสดงว่าโหนดH1 เป็นโหนดสุดท้าย */ แจ้งให้ผู้ใช้ทราบ , จบ ; 
/* เข้าสู่จุดนี้แสดงว่ามีโหนดต่อถัดจากโหนดH1 */ 
/* ให้ Q เป็นพอยน์เตอร์ชั่วคราว */

ขอให้สังเกตว่าเราไม่สามารถนำโหนดH1 ออกโดยตรงได้ทั้งนี้เนื่องจากว่าเราไม่ทราบว่าโหนดก่อนโหนดH1 อยู่ที่ใด ถ้าจะในโหนดH1 ออกเราต้องหาว่าโหนดก่อนโหนดH1 อยู่ที่ใด ซึ่งจะทำได้โดยเดินเข้าไปในลิงค์ลิสต์ตั้งต้นจาก H ตามพอยน์เตอร์ไปเรื่อย ๆ จนกว่าจะพบโหนดH1 การเดินเข้าไปในลิงค์ลิสต์จะมีความสำคัญซึ่งเราจะอธิบายถึงวิธีการดังกล่าวในหัวข้อต่อไป
                      3)การท่องไปในลิงค์ลิสต์สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่าข่าวสาร X อยู่ในลิสต์นี้หรือไม่เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ ตั้งต้นจาก H การท่องไปในลิงค์ลิสต์ใหม่ไม่ได้ ดังนั้นเราจะใช้พอยน์เตอร์อีกตัวมาเป็นผู้ช่วย (auxiliary pointer) เพื่อดึงตัว H1 ไปยังโหนดถัดไ»
เมื่อเราเข้าใจถึงวิธีการท่องไปในลิงค์ลิสต์แล้ว อัลกอริทึม เพื่อหาค่า X จะเขียนได้ดังนี้
SEARCHX : PROCEDURE (X) ; 
/* อัลกอริทึมนี้จะหาว่า X อยู่ในลิงค์ลิสต์ H หรือไม่ */
/* ให้ H1 = เป็นพอยน์เตอร์ชั่วคราว */
IF H = NULL THEN แจ้งให้ผู้ใช้ทราบว่าลิงค์ลิสต์ H ว่างเปล่า , จบ ; 
H1 = H ; /* H1 ชี้ไปยังโหนดที่อยู่หัวของลิงค์ลิสต์ */
DO WHILE (INFO(H1)นX) 
IF LINK(H1) = NULL THEN GOTO OUT ; 
H1 = LINK(H1); 
END; 
OUT:IF INFO(H1) = X THEN แจ้งให้ผู้ใช้ทราบ , จบ; 
มิฉะนั้นแจ้งให้ผู้ใช้ทราบว่า X ไม่อยู่ในลิงค์ลิสต์ H ; 
END SEARCHX;
                     1.3 ลิงค์ลิสต์แบบวงกลม (Circular linked list)  เมื่อเราให้พอยน์เตอร์ของโหนดสุดท้ายในลิงค์ลิสต์(ที่มีโหนดแรกคือโหนด H) ชี้ไปยังโหนดแรก เราจะได้โครงสร้างลิงค์ลิสต์แบบวงกลมดังรูปที่18 โครงสร้างแบบนี้สะดวกกว่าแบบลิงค์ลิสต์เดี่ยวธรรมดาในแง่ที่ว่าถัดจากโหนดสุดท้ายก็เป็นโหนดแรกเลยดังนั้นการไล่พอยเตอร์จึงมีความสะดวกในบางครั้งเพราะพอยน์เตอร์จะไม่มีโอกาสตกหายไประหว่างการท่องไปในลิงค์ลิสต์
ลิงค์ลิสต์คู่ (Doubly Linked List)
                    ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่นถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK
                    เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยวจะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอนที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนดH1 ในลิงค์ลิสต์นั้นได้นอกจากนี้เรายังสามารถคืนโหนดH1 ไปสู่ storage pool โดยตรงได้อีกด้วยอย่าลืมว่าเราไม่สามารถคืนโหนดH1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว
                    2.1 การนำข่าวสารเข้าสู่ลิงค์สิสต์คู๋สมมติว่าแต่ละโหนดใน storage pool ดังนั้นคำสั่ง ALLOCATE P จะก่อกำเนิดโหนด
                   เราจะสมมติว่ามีลิงค์ลิสต์คู่อย่าแล้ว และจะนำโหนดP ซึ่งเก็บข่าวสาร X เข้าสู่ลิงค์ลิสต์นี้ ที่ตำแหน่งถัดจากโหนดH1 ซึ่งจะเห้นได้ว่ากระบวนการนี้สำเร็จได้โดยการเปลี่ยนค่าพอยน์เตอร์4 ค่าอย่างไรกีดีลำดับการเปลี่ยนค่าพอยน์เตอร์มีความสำคัญมาก ถ้าเราทำตามลำดับ (1),(2),(3),(4) จะไม่สำเร็จ ส่วนรูปที่ 23

ลิงค์ลิสต์ (Linked List)
 ลิสต์ (Lists) หรือรายการ ถือเป็นการจัดเก็บข้อมูลชนิดหนึ่งซึ่งข้อมูลเชื่อมต่อกันแบบเชิงเส้น แต่ละข้อมูลมักเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) โดยแบ่งโดยพื้นฐานได้ 2 แบบคือแบบทั่วไป (General) และแบบจำกัด (Restricted) ซึ่งแนวคิดของลิงค์ลิสต์จะกำหนดให้แต่ละสมาชิกจะประกอบด้วย ข้อมูล (Data) และลิงก์ (Link) โดยข้อมูลอาจประกอบด้วยหลายฟิลด์ก็ได้
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion) 
2. การลบ (Deletion) 
3. การปรับปรุง (Updation) 
4. การท่องเข้าไปในลิสต์ (Traversal)                   

ใบงานที่ 7 โครงสร้างข้อมูลแบบ Queue

ตอบ

คิว(Queue)เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสตซึ่งการเพิ่มข้อมูลจะกระทำทีปลายข้างหนึ่งซึ่งเรียกว่าสวนท้ายหรือเรียร์ (rear)และการนำข้อมูลออกจะ กระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกวา ส่วนหน้า หรือฟรอนต์(front)ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)

การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue ซึ่งมีรูปแบบคือenqueue (queue, newElement) หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์

การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือdequeue (queue, element)
หมายถึง การนำออกจากส่วนหน้า ของคิวและให้ ข้อมูลนั้นกับ element

การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ เรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว

การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว

การแทนที่ข้อมูลของคิวการแทนที่ข้อมูลของคิวสามารถทาได 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสค์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์

การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 3 ส่วนคือ พอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

การดำเนินการเกี่ยวกับคิวการดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue
2. Enqueue
3. Dequeue
4. Queue Front
5. Queue Rear
6. Empty Queue
7. Full Queue
8. Queue Count
9. Destroy Queue

Algorithm CreateQueue
Pre Nothing
Post Head has been allocated and initialized
Return Head’s address if successful, null if overflow
1. if (memory available)

allocate (newPrt)
2 newPtr->front = null pointer
3 newPtr->rear = null pointer
4 newPtr->count = 0
5 return newPtr
2. Else1 return null pointer 

End CreateQueue

Algorithm EnQueue

Queue has been create
Post Item data have been inserted
Return Boolean; True: if successful, False ifoverflow
1. if (queue full)
1 return false

1 allocate(newPtr)
2 newPtr->data = item
3 newPtr->next = null pointer
4 if (queue->count zero)
1 queue->front = newPtr
5 else1 queue->rear->next = newPtr
6 queue->rear = newPtr
7 queue->count = queue->count+1
8 return true
End EnQueue

Algorithm DeQueue
Queue has been create
Data at front of queue returned to userthrough item and front element deleted and recycled
Return Boolean; True: if successful, False ifunderflow
1. if (queue->count is 0)
1 return false
1 item = queue->front->data
2 deleteLoc = queue->front
3 if (queue->count 1)
1 queue->rear = null pointer
4 queue->front = queue->front->next
5 queue->count = queue->count-1
6 recycle(deleteLoc)
7 return true
End Dequeue
4.Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมา
Algorithm QueueFront
Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False ifunderflow

5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
Algorithm QueueRearPre
Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False if underflow
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
Algorithm EmptyQueue
Queue is a pointer to a queuehead node
Return Boolean; True: if empty, False if queuehas data
1. Return (queue->count equal 0)
End EmptyQueue
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
Algorithm FullQueue
Pre Queue is a pointer to a queue head node
Return Boolean; True: if full, False if room for anothernode
1. allocate (tempPtr)
2. if (allocation successful)
1 release (tempPtr)
2 return false
3. else
1 return true
End FullQueue
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
Algorithm QueueCount
Queue is a pointer to the queuehead node
Return Queue count
1. Return queue->count
End QueueCount

9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยในคิว

Algorithm DestroyQueue

Queue is valid queue
All data have been deleted and recycled
Return null pointer
1. pWalker = queue->front
2. Loop(pWalker not null)
1 deletePtr = pWalker
2 pWalker = pWalker->next
3 recycle (deletePtr)
4 recycle (queue)
5 return null pointer1.
End DestroyCount
การแทนที่ข้อมูลของคิวแบบอะเรย์

การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายาม นำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflow การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่า underflow ในการใส่สมาชิกลงในคิวจะต้องตรวจสอบ ก่อนว่าคิวเต็ม หรือไม่

จากตัวอย่าง จะเห็นได้ว่าอาจจะมีปัญหาในการนำเข้าข้อมูลในกรณีที่คิวเต็มแต่สภาพความเป็นจริงแล้ว front ไม้ได้อยู่ในช่องแรก ของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีก
วิธีการแก้ปัญหา ดั้งกล่าว จะใช้คิวที่เป็น แบบคิววงกลม(Circular Queue)ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด

จากตัวอย่าง จะเห็นได้ว่าอาจจะมีปัญหาในการนำเข้าข้อมูลในกรณีที่คิวเต็มแต่สภาพความเป็นจริงแล้ว front ไม้ได้อยู่ในช่องแรก ของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีกวิธีการแก้ปัญหา ดั้งกล่าว จะใช้คิวที่เป็น แบบคิววงกลม(Circular Queue)ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด