สรุปการเรียน DTS05-24-06-2552

Queue

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

ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
enqueue (queue, newElement)หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์
dequeue (queue, element)หมายถึง การนำออกจากส่วนหน้าของคิวและให้ ข้อมูลนั้นกับ element

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

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

การดำเนินการเกี่ยวกับคิว
การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าเป็น null และจำนวน
สมาชิกเป็น 0
2. Enqueue การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue การนำข้อมูลออกจากคิว
4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว


การแทนที่ข้อมูลของคิวแบบอะเรย์
การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายามนำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflowการนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่าunderflowในกรณีที่เป็นคิวแบบวงกลมคิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อย ๆ จนกระทั่ง rearมีค่าน้อยกว่า front อยู่หนึ่งค่าคือ rear = front - 1


การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงานธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวนลูกค้าในคิวที่เหมาะสมว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อยที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือในระบบปฏิบัติการ (OperationSystem) ในเรื่องของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากรระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงาน
ตามลำดับความสำคัญ

สรุปการเรียน DTS04-22-07-2552

Stack

เป็นโครงสร้างข้อมูลแบบเชิงเส้น ที่มีการใส่ข้อมูลเข้า และนำข้อมูลออกเพียงด้านเดียว ดังนั้น ข้อมูลที่เข้าไปอยู่ใน stack ก่อนจะออกจาก stack หลังข้อมูลที่เข้าไปใน stack ทีหลัง นั่นคือ การ "เข้าทีหลังแต่ออกก่อน" (Last In First Out : LIFO

การกระทำ(Operation) ที่เกี่ยวข้องกับโครงสร้างข้อมูลแบบ Stack
ปฏิบัติการพื้นฐานของสแตกได้แก่ push คือการนำข้อมูลเก็บในสแตก และ pop คือการนำข้อมูลออกจากสแตก ซึ่งทั้งสองกระบวนการ จะกระทำที่ส่วนบนสุดของสแตกเสมอ โดยปกติแล้วมักกำหนดให้มีตัวชี้ส่วนบนสุดของสแตก เรียกว่า top ส่วนปฏิบัติการอื่น ๆ เป็นปฏิบัติการที่เกี่ยวเนื่องกับการ push และ pop มีดังนี้
การสร้างสแตก (CREATE)
การทดสอบว่า stack ว่างหรือไม่(EMPTY)
การทดสอบว่า stack เต็มหรือไม่(FULL)
การทำให้ stack เป็น stack ว่าง(CLEAR)
การนำข้อมูลเข้าสู่สแตก (Push) กระทำที่ส่วนบนของสแตก (Top) ซึ่งต้องมีการตรวจสอบก่อนว่าสแตกเต็มหรือไม่
และการนำข้อมูลออกจากสแตก (Pop) กระทำที่ส่วนบนของสแตกเช่นกัน โดยตรวจสอบว่ามีสมาชิกอยู่ในสแตกหรือไม่ (ตรวจสอบว่าสแตกว่างเปล่าหรือไม่)


การนำข้อมูลเข้าไปในกองซ้อน (Push)

เป็นการดำเนินการที่นำข้อมูลเข้าไปเก็บไว้ด้านบนสุดของกองซ้อน (Top of the Stack) เรื่อย ๆ จนกว่ากองซ้อนไม่สามารถนำข้อมูลเข้าไปเก็บได้
จะเรียกว่า กองซ้อนเต็ม (Stack Full)

การนำข้อมูลออกจากกองซ้อน (Pop)
การทำงานจะตรงข้ามกับ Push
จะดึงเอาข้อมูลที่อยู่บนสุดออกมาก่อน แต่ก่อนที่จะดึงจะมีการตรวจสอบว่ากองซ้อนว่างหรือไม่
ถ้าว่างจะไม่สามารถนำข้อมูลออกได้ แสดงว่ากองซ้อนว่าง (Stack Empty)
ถ้าไม่ว่างจะนำเอาข้อมูลออกแล้วเลื่อนตัวชี้ไปยังตำแหน่งถัดลงไป


ตัวอย่างของ stack
1. การหยิบกินของขนมเตสโต้ที่อยู่ในกล่องทรงกระบอก ซึ่งมันจะมีการบรรจุแผ่นมันฝรั่งให้เต็มกระบอก เวลาหยิบกินก็ต้องหยิบกินแผ่นข้างบนก่อน ซึ่งแผ่นข้างบนก็หมายถึงแผ่นที่บรรจุทีหลังนั้นเอง
2. การยกข้าวสารในกระสอบซึ่งมันจะมีการวางเรียงกันเป็นชั้น ๆ เวลาที่เราจะยกข้าวที่ละกระสอบเราก็ต้องยกกระสอบที่อยู่ข้างบนสุดก่อน ซึ่งกระสอบที่อยู่บนสุดเป็นกระสอบที่มาหลังสุด
3. การหยิบแผ่นซีดีที่อยู่ในกล้องบรรจุหลายสิบแผ่น เวลาหยิบก็ต้องหยิบแผ่นที่อยู่บนสุดก่อน
4. การใช้สก็อตเทฟ เวลาเราจะใช้เราก็ต้องใช้แผ่นที่อยู่บนสุดก่อน
5. การจอดรถที่มีการจดหลาย ๆ ชั้นซ้อนกัน เวลารถที่มาก่อนจะถอยออก ก็ต้องให้รถที่มันที่หลังที่ขวางรถเราอยู่ให้ถอยออกไปก่อนเราถึงจะถอยรถของเราได้

สรุปการเรียน DTS03-15-07-2552

Linked List

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

สรุปการเรียน DTS02-01-07-2552

Set and String

โครงสร้างข้อมูล Set

เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
ตัวดำเนินการของเซ็ต (Set operators)
ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้น


โครงสร้างข้อมูล String

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

สตริง คือ อะเรย์ของอักขระ
เช่น char a[6]
อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของstring จะจบด้วย \0 หรือ null character เช่น
char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
char a[ ]=“HELLO”;

การกำหนดสตริง
การกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว
(String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์

การกำหนดค่าให้กับสตริงนั้น เราจะใช้เครื่องหมาย double
quote (“ ”) เช่น “abc” คือ ชุดของอักขระที่มีขนาด 4 (รวม \0 ด้วย)
ตัวอย่าง

S e m i \0
adrress 16 17 18 19 20


#define NME “Semi”
main ( ){
char *cpntr;
cpntr=NME;
printf(“con\n”);
printf(“%s, %u, %c\n”, “con”, “duc”,*“tor”);
printf(““%s, %u, %c\n”, NME, NME,*NME);
printf(““%s, %u, %c\n”, cpntr, cpntr,*cpntr);
}

ผลการรันโปรแกรม

con
con, 37, t
Semi, 16, S
Semi, 16, S


การกำหนดค่าคงตัวสตริงให้แก่ตัวแปรพอยต์เตอร์และอะเรย์

สามารถกำหนดค่าคงตัวสตริงให้พอยเตอร์
หรืออะเรย์ได้ในฐานะค่าเริ่มต้น
เช่น main ( ) {
char ary[ ] = “This is the house. ”;
char *cpntr=“This is the door.”;
printf(“%s %s”,ary,cpntr);
}

ผลการรัน
This is the house. This is the door.


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

อะเรย์ของสตริงที่ยาวไม่เท่ากัน
ทำได้เฉพาะเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น