DTS 08-11/08/2009

สรุปเรื่อง คิว (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) ก็จะเอาข้อมูลก่อนปมหัวออก ก็คือข้อมูลที่เข้าแรกๆสุด เมื่อใดที่รายการหรือคิวว่าง ก็คือตอนที่ปมหัวชี้มาที่ตัวเองนั่นเอง

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

DTS06-28/07/2009

#include"iostream.h"

#include"iomanip.h"



int main()

{
cout << setw(6) << 1 << endl;

cout << setw(6) << 15 << endl;

cout << setw(6) << 378 << endl;

cout << setw(6) << 4600 << endl;

cout << setw(6) << 666666 << endl;

cout << "============================" << endl;

cout << "Name Score Grade" << endl;

cout << "============================";

cout << endl;

cout << setw(6) << "Krirk" << setw(10) << 90 << setw(6) << "A";

cout << endl;

cout << setw(6) << "Pung" << setw(10) << 78 << setw(6) << "B";

cout << endl;

cout << setw(6) << "Tum" << setw(10) << 17 << setw(6) << "F";

cout << endl;

cout << setw(6) << "Keakai" << setw(10) << 100 << setw(6) << "A";


return 0;

}

DTS 05-28/07/2009

สรุปเรื่อง Linked List
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อ แต่ละอิลิเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คือ Data จะเก็บข้อมูลของอิลิเมนท์ และ ส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์
ในส่วนของ data อาจจะเป็นรายการเดี่ยวหรือเป็นเรคคอร์ดก็ได้
ในส่วนของ link จะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไป ในโหนดสุดท้ายจะเก็บค่า Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการสิ้นสุดของลิสต์
ในลิงค์ลิสต์จะมีตัวแปรสำหรับชี้ตำแหน่งลิสต์ (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต์ ซึ่งก็ คือ โหนดแรกของลิสต์นั่นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสต์จะเป็น 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)