สรุป คิว (queue)
คิวหรือแถวคอย (อังกฤษ: queue) เป็นประเภทข้อมูลอย่างย่อที่มีลักษณะการเรียงลำดับข้อมูล ในการเข้า-ออกในลักษณะเข้าก่อนออกก่อน FIFO (First In First Out) กล่าวคือข้อมูลที่เข้าแรกๆจะได้ออกก่อน คล้ายคนต่อคิวที่มาก่อนจะได้ซื้อของก่อน จึงเรียกว่า แถวคอย หรือ คิวแถวคอย หรือ คิว จึงจัดเป็นวิธีการจัดการเข้า-ออกของข้อมูลอีกแบบหนึ่ง เป็นโครงสร้างข้อมูลที่นำมาใช้ในการทำงานของโปรแกรมคอมพิวเตอร์หลายประการ อาทิการเข้าคิวในการทำงานของเครือข่าย การออกแบบการทำงานระบบท่อ (pipeline) เป็นต้นจุดเด่นของคิวคิวสามารถจัดการการเข้า-ออกของข้อมูล ใช้เก็บข้อมูลที่ต้องการจัดเรียงเป็นระบบ โดยพิจารณาข้อมูลตามลำดับ ในทำนอง ใครถึงก่อนมีสิทธิ์ได้ใช้ก่อน จึงใช้ในการเรียงลำดับในการแบ่งปันทรัพยากรที่มีอยู่จำกัดในการทำงาน เช่น การรอคิวการทำงานของเครื่องพิมพ์ในสำนักงาน เป็นต้นบริการที่มักจะมีเอาข้อมูลใหม่เข้าท้ายคิว (enqueue)เอาข้อมูลออกจากหัวคิว (dequeue)ดูข้อมูลที่อยู่หัวคิว (peek) ทำคิวว่าง ตรวจสอบความว่างของคิว (empty)ความเร็วที่ใช้ในการทำงานการทำงานของคิวไม่จำเป็นต้องไล่พิจารณาสมาชิกทุกตัว เป็นเพียงแต่การพิจารณาข้อมูลที่เข้าแรกสุดออกจากคิว และเอาข้อมูลใหม่เข้าท้ายคิว การทำงานของคิวจึงมีความเร็วคงที่ (O (1))วิธีการสร้างคิวการสร้างคิวทำได้โดยแถวลำดับประกอบกับจำนวนเต็ม ที่เก็บดัชนีของหัวคิวและท้ายคิว สองตัว หรือใช้ รายการโยงสองชั้นวน(circular doubly linked list)คิวแถวลำดับสำหรับการใช้แถวลำดับในการทำคิวนั้น (array queue) ตอนเริ่มต้นเราจะให้ดัชนีของหัวคิวและท้ายคิวชี้ที่ศูนย์ เมื่อเข้าคิว (enqueue) ก็จะเก็บข้อมูลตรงดัชนีท้าย พร้อมทั้งเพิ่มค่าดัชนีท้ายคิวจะไปอีกหนึ่ง (increament) ในทางตรงกันข้ามหากเอาข้อมูลตัวแรกออกจากคิว (dequeue) ก็คืนค่าสมาชิกตัวที่ดัชนีหัวคิวชี้อยู่พร้อมทั้งเพิ่มค่าดัชนีหัวคิวไปอีกหนึ่ง (decrement) หากดัชนีหัวคิววิ่งไล่ทับดัชนีท้ายคิวแสดงว่า คิวนั้นเป็นคิวว่าง (empty queue) ไม่ควร dequeue อีกเพราะจะทำให้การทำงานรวนได้ (ควรตรวจสอบก่อน dequeue)เนื่องจากแถวลำดับมีขนาดจำกัดในบางครั้งอาจมีการทำคิววนรอบ (circular array queue) กล่าวคือบางครั้งคิวอาจมีการ enqueue และ dequeue สลับกันทำให้ดัชนีหัวคิวเลื่อนๆออกไปจนจะตกขอบขวาของแถวลำดับ ทำให้มีเนื้อที่ของแถวลำดับด้านหน้าเหลือไม่ได้ใช้จึงมีการวนเอาหางคิว มาแทนส่วนหน้าของแถวลำดับ กล่าวคือเมื่อท้ายคิวตกขอบขวาของแถวลำดับ ก็จะมีการเริ่มดัชนีท้ายคิวที่ศูนย์ใหม่และต่อท้ายคิวมาเรื่อยๆ ข้อด้อยของวิธีนี้คือ เมื่อท้ายคิวมาทับหัวคิวอีกครั้งจะตีความไม่ได้ว่าคิวเต็มแถวลำดับ หรือคิวว่างกันแน่ จึงอาจใช้ตัวแปรขนาด (size) หรือตัวแปรอื่นๆช่วยในการบอกว่าคิวว่างหรือไม่คิวรายการโยงสองชั้นวนสำหรับการใช้รายการโยงสองชั้นวน(circular doubly linked list) ในการทำนั้น โดยหัวคิวจะอยู่ที่ปมสุดท้ายนี้ (กล่าวคือเป็นปมก่อนที่จะชี้ปมหัว เพราะว่าเป็นรายการวน) ส่วนท้ายคิวอยู่ที่ปมแรก เมื่อเข้าคิว (enqueue) ก็เพิ่มปมใหม่หลังปมหัว เมื่อจะเอาข้อมูลแรกออกจากคิว (dequeue) ก็จะเอาข้อมูลก่อนปมหัวออก ก็คือข้อมูลที่เข้าแรกๆสุด เมื่อใดที่รายการหรือคิวว่าง ก็คือตอนที่ปมหัวชี้มาที่ตัวเองนั่นเอง
วันอังคารที่ 25 สิงหาคม พ.ศ. 2552
วันจันทร์ที่ 10 สิงหาคม พ.ศ. 2552
DTS 07-04/08/2009
สรุปเรื่อง Stack
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop (s) การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกการแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ ส่วนของ Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก และ Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมาสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operator ก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การดำเนินงานพื้นฐานของสแตก
การทำงานต่าง ๆ ของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop (s) การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกการแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ ส่วนของ Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก และ Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับสแตก
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมาสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operator ก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
วันอาทิตย์ที่ 2 สิงหาคม พ.ศ. 2552
DTS05-28/07/2009
เรื่อง Linked List
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่างๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อ แต่ละอิลิเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดประกอบไปด้วย 2 ส่วน คือ
1. Data จะเก็บข้อมูลของอิลิเมนท์
2. Link Field ทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์ในส่วนของ data จะเป็นรายการเดี่ยวหรือเรคคอร์ดก็ได้ ส่วนของ link เป็นส่วนที่เก็บตำแหน่งของโหนดถัดไป ถ้าในโหนดสุดท้ายจะเก็บค่า Null (ไม่มีค่าใดๆ ไม่มีการเชื่อมโยง) เป็นตัวบอกการสิ้นสุดโครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์แบ่งเป็น 2 ส่วน คือ
1. Head Structure ประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต์ (Count) พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง (Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)2. Data Node Structure ประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลถัดไปกระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่าง ผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Node หน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องกรข้อมูลนำเข้า ลิสต์ ข้อมูลและตำแหน่ง ผลลัพธ์ สิลต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Node หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูลนำเข้า ข้อมูลและตำแหน่ง ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search list หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverse หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node, รวมฟิลด์ในสิสต์, คำนวณค่าเฉลี่ยนของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Node หน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น EmptyList หน้าที่ ทดสอบว่าลิสต์ว่าง ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง เป็นเท็จ ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น FullList หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามรถมีโหนดอื่น
9. ฟังก์ชั่น list count หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy list หน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ ผลลัพธ์ ไม่มีลิสต์Linked List แบบซับซ้อน1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้น
คือ เป็นแบบวงกลม2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer) และตัวชี้ข้อมูลถัดไป (forward pointer)
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่างๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อ แต่ละอิลิเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดประกอบไปด้วย 2 ส่วน คือ
1. Data จะเก็บข้อมูลของอิลิเมนท์
2. Link Field ทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์ในส่วนของ data จะเป็นรายการเดี่ยวหรือเรคคอร์ดก็ได้ ส่วนของ link เป็นส่วนที่เก็บตำแหน่งของโหนดถัดไป ถ้าในโหนดสุดท้ายจะเก็บค่า Null (ไม่มีค่าใดๆ ไม่มีการเชื่อมโยง) เป็นตัวบอกการสิ้นสุดโครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์แบ่งเป็น 2 ส่วน คือ
1. Head Structure ประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต์ (Count) พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง (Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)2. Data Node Structure ประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลถัดไปกระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่าง ผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Node หน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องกรข้อมูลนำเข้า ลิสต์ ข้อมูลและตำแหน่ง ผลลัพธ์ สิลต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Node หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการข้อมูลนำเข้า ข้อมูลและตำแหน่ง ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search list หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverse หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node, รวมฟิลด์ในสิสต์, คำนวณค่าเฉลี่ยนของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Node หน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น EmptyList หน้าที่ ทดสอบว่าลิสต์ว่าง ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง เป็นเท็จ ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น FullList หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามรถมีโหนดอื่น
9. ฟังก์ชั่น list count หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ ข้อมูลนำเข้าลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน destroy list หน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ ผลลัพธ์ ไม่มีลิสต์Linked List แบบซับซ้อน1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้น
คือ เป็นแบบวงกลม2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer) และตัวชี้ข้อมูลถัดไป (forward pointer)
สมัครสมาชิก:
บทความ (Atom)
