ลูกเเรดเตรียมพร้อมล่าเหยื่อ

สิ่งที่ได้รับจากการเรียนเตรียมฝึกประสบการณ์ชีพ คือ

ทักษะในการทำงานในอนาคตไม่ว่าจะเป็น

-บุคลิกภาพที่ดีในการทำงาน

-คุณลักษณะอันพึ่งประสงค์ที่ดีในการทำงาน

-ทั้งยังรู้เกี่ยวกับวัฒนธรรมของเเต่ละชาติที่เป็นประเทศผู้นำทางเศรษฐกิจ

-ทั้งยังฟื้นฟูความรู้ในอดีตที่บางครั้งอาจลืมเลือนตามกาลเวลา

การเรียนเตรียมฝึกในครั้งนี้จึงสามารถนำความรู้ทั้งหมดที่ได้เรียนเเละอบรมมาใช้ในชีวิตการทำงานในอนาคตและร่วมงานกับผู้อื่นได้

DTS10-08/09/2009

Unit 9 Graph (ต่อ)

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

1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9

2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS09-01/09/2009

Graphกราฟ (Graph)

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

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

การแทนกราฟในหน่วยความจำ
วิธีที่ง่ายและตรงไปตรงมาที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal)คือกระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง

การท่องไปในกราฟมี 2 แบบดังนี้
- การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
- การท่องแบบลึก (Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

DTS08-25/08/2009

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น(Hierarchical Relationship)ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่าง ๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล

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


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

การเขียนรูปแบบทรี อาจเขียนได้ 4แบบ คือ
-แบบที่มีรากอยู่ด้านบน
-แบบที่มีรากอยู่ด้านล่าง
-แบบที่มีรากอยู่ด้านซ้าย
-แบบที่มีรากอยู่ด้านขวา

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

DTS07-18/08/2009

สรุป Queue
โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นที่มีลักษณะของการทำงานตรงกันข้ามกับสแตกคือ หากมีการนำเข้าข้อมูลใดก่อนเมื่อต้องการเรียนใช้ก็จะเรียกใช้ข้อมูลที่เข้ามาก่อน ถือเป็นรูปแบบของการทำงานที่สามารถพบเห็นได้ในปัจจุบันมากที่สุดในลักษณะของการเรียงต่อแถวหากใครที่มาต่อแถวเพื่อทำกิจกรรมใดก่อนก็จะมีสิทธิ์ได้ทำกิจกรรมนั้น ๆ ก่อน คนที่มาทีหลังเป็นเช่นนี้ไปจนกว่าจะถึงลำดับสุดท้าย
โครงสร้างของคิว
- ข้อมูลใดเข้ามาก่อน ก็จะดำเนินการก่อน หากเข้ามาทีหลังก็จะดำเนินการทีหลังเราเรียกว่า First in first out (FIFO) หรือเข้าก่อนออกก่อน
สำหรับการที่มีข้อมูลเข้ามาให่ในคิวและต่อด้าน rear จะเรียกการดำเนินการในลักษณะนี้ว่าEnqueue และสำหรับการนำเอาข้อมูลในส่วน Front ออกไปจากคิวจะเรียกการดำเนินการในลักษณะนี้ว่า Dequeue
พื้นฐานการดำเนินการกับคิว
1. Enqueue หรือ การนำเข้าข้อมูลของคิวนั้นแรกเริ่มหากมีการนำเข้าข้อมูลแรกเข้าสู่คิวแล้วข้อมูลนี้จะเป็นข้อมูลอันดับแรกและเมื่อมีการเพิ่มข้อมูลเข้ามาอีกข้อมูลที่เพิ่มเข้ามาใหม่ก็จะต่อท้ายในส่วนของ rear นั่นก็คือ การต่อท้ายข้อมูลแรกนั่นเอง
ดังภาพ
2. Dequeue หรือ การนำข้อมูลออก ถือเป็นการดำเนินการพื้นฐานอีกประการของโครงสร้างคิวที่จะนำออกข้อมูลซึ่งถือเป็นสมาชิกของคิวโดย จะกระทำเฉพาะส่วนหัวหรือ Front ของโครงสร้างเท่านั้น
ดังภาพ
ทฤษฏีด้านการดำเนินการ
1. การดำเนินการสร้างคิว (Queue Create)การดำเนินการนี้เป็นขั้นแรกเริ่มของการจองพื้นที่บนหน่วยความจำเพื่อให้คิวนั้นสามารถที่จะเข้าใช้งานในการเก็บข้อมูลได้และค่าเริ่มต้นของคิวจะเป็นคิวที่ไม่มีข้อมูลหรือคิวว่าง
2. การดำเนินการ Enqueueการดำเนินการ Enqueue เป็นขั้นตอนของการนำเข้าข้อมูลเข้าสู่โครงสร้างคิว โดยการนำเข้าข้อมูลนั้นจะต้องทำงานเป็นกลไกที่ลำดับตามการมาก่อน หลัง สำหรับชนิดของข้อมูลนั้นต้องเป็นข้อมูลมาตรฐาน
3. การดำเนินการ Dequeueการ Dequeue จะดำเนินการดึงข้อมูลออกจากโครงสร้างซึ่งจะกระทำเฉพาะส่วนหัวของข้อมูลเท่านั้น
4. การดำเนินการตรวจสอบคิวว่างการตรวจสอบคิวว่างเพื่อที่จะไม่ให้เกิดข้อผิดพลาดในกรณีที่ต้องการนำเอาข้อมูลออกจากคิวซึ่งจะต้องมีการตรวจสอบก่อนทุกครั้ง เพราะถ้าหากคิวนั้นไม่มีข้อมูลอยู่แล้วพยายามดึงข้อมูลออกก็จะเกิดข้อผิดพลาด
5. การดำเนินการตรวจสอบคิวเต็มกรณีที่ต้องการนำเอาข้อมูลเข้าสู่โครงสร้างคิวจะต้องมีการตรวจสอบก่อนเสมอว่าคิวมีข้อมูลเต็มพื้นที่ที่จองไว้หรือยังหากข้อมูลนั้นเต็มพื้นที่ที่ไว้ก็จะไม่สามารถนำเข้าข้อมูลได้อีก
6. การดำเนินการล้างคิวการคิวเป็นการล้างข้อมูลที่ถูกจัดเก็บในโครงสร้าง
สรุป Queue (ต่อ)
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ด้วยลิงค์ลิสต์ (Link List Implemention Of Queue)
สำหรับการแทนคิด้วยโครงสร้างลิงค์ลิสต์นั้นมีลักษณะเช่นเดียวกันกับการแทนสแตกด้วยลิงค์ลิสต์ คือต้องการปรับโครงสร้างให้สามารถเพิ่มหรือลดได้แบบไม่ตายตัว(Dynamic) ซึ่งลักษณะของโครงสร้างก็ยังคงประกอบไปด้วยพอยน์เตอร์ในการชี้ตำแหน่งfront และ rear ส่วนการลิงค์ของข้อมูลแต่ละโหนดก็จะใช้พอยน์เตอร์ของแต่ละโหนดเชื่อมโยงกัน
จากภาพ เป็นรูปแบบของโครงสร้างคิวที่แทนด้วยลิงค์ลิสต์ คิวนี้จะประกอบด้วยโหนดต่างๆซึ่งก็คือเรคอร์คที่จัดเก็บข้อมูลและลิงค์ไปยังโหนดต่อไป การชี้ของพอยน์เตอร์ frontและ rear นั้นจะถูกเก็บเป็นโฆนดเช่นเดียวกันโดย front จะเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดตัวแรก ส่วน rear จะเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดสุดท้า้ย เมื่อมีการดำเนินการกับคิว ก็จะดำเนินการตามการทำงานคือการ Enqueue และ Dequeue การ Enqueue จะดำเนินการนำข้อมูลเพิ่มในส่วน rear ส่วนการ Dequeue จะดำเนินการในส่วนของ front
การดำเนินการกับคิวที่แทนด้วยโครงสร้างลิงค์ลิสต์สำหรับการดำเนินการที่สำคัญนั้นคือการดำเนินการ Enqueue การดำเนินการ Dequeue และการตรวจสอบคิวว่าง
1, การดำเนินการ Enqueueการดำเนินการ Enqueue ทำงานเช่นเดียวกันกับการแทรกโหนดในส่วนท้ายของลิสต์คือเมื่อมีการ Enqueue ข้อมูลใหม่เข้ามาก็จะเซตค่าของพอยน์เตอร์ให้ชี้มายังโหนด rear และกำหนดค่าการเชื่อมโยง = nil จากนั้นเซตพอยน์เตอร์ rear ให้ชี้มายังโหนดสุดท้ายแสดงได้ดังภาพ
2. การดำเนินการ Dequeueการดำเนินการ Dequeue จะดำเนินการในส่วน front หรือที่โหนดตัวแรกของโครงสร้างโดยเซตค่าพอยนเตอร์ที่ชี้ไปยังโหนดตัวแรกเปลี่ยนเป็นชี้ไปยังโหนดตัวถัดไป ทำให้โหนดตัวแรกถูกลบออกและโฆนดที่เป็นตัวแรกคือโหนดที่พอยน์เตอร์ front ชี้อยู่ปัจจุบัน ดังภาพ
3. การดำเนินการตรวจสอบคิวว่างการดำเนินการตรวจสอบคิวว่างเป็นการตรวสอบคิวว่ามีข้อมูลหรือไม่ เพื่อที่จะสามารถทราบได้ว่าหากในโครงสร้างนั้นมีข้อมูลอยู่ ก็สามารถที่จะทำการ Dequeu ข้อมูลออกไปได้ แต่ในกรณีที่คิวไม่มีข้อมูลก็จะมีการเซตค่าของโหนดที่จัดเก็บพอยน์เตอร์ front และ rear ให้มีค่าเป็น nil
การแทนที่ด้วยอาร์เรย์ (Array Implemention Of Queue)
การแทนโครงสร้างคิวด้วยอาร์เรย์นั้นจะทำให้สามารถกำหนดจำนวนของการจองพื้นที่บนหน่วยความจำได้และโดยเฉพาะอย่างยิ่งลักษณะการทำงานของคิวที่มีการทำงานของคิวที่มีการทำงานแบบเชิงเส้นจึงมีการใช้อาร์เรย์ในการนำข้อมูลเข้าด้านท้ายและนำข้อมูลออกในส่วนหัว
โครงสร้างของการแทนคิวด้วยอาร์เรย์
ในการแทนคิวด้วยอาร์เรย์นั้น จะต้องมีการระบุจำนวนสูงสุดของพื้นที่เก็บข้อมูล (Maxsize)พร้อมกันกับกำหนดพอยน์เตอร์ขึ้นมาอีก 2 ตัวคือ front และ rear เพื่อใช้นการชี้ค่าข้อมูลที่อยู่ส่วนหัวและส่วนท้ายดังภาพ
ส่วนการ Enqueue นั้นจะกระทำที่ส่วนของ Rear ทำให้ Rear มีการเพิ่มตำแหน่งขึ้นมา
ส่วนการ Dequeue นั้นจะกระทำที่ส่วนของ Front คือเลื่อน front จาก 0 ไปเป็น 1 ดังภาพ
การประยุกค์การใช้งานในระบบปฏิบัติการ
ตัวอย่างเช่น การทำบัฟเฟอร์ (Buffering)การทำบัฟเฟอร์จะใช้ในกรณีที่อัตราความเร็วในการทำงานของอุปกรณ์คอมพิวเตอร์มีการทำงานด้วยความเร็วที่แตกต่างกันยกตัวอย่างเช่น การทำงานของเครื่องพิมพ์กับ CPUซึ่งถือว่ามีการทำงานในอัตราความเร็วที่แตกต่างกันมาก แต่เมื่อต้องการส่งผ่านข้อมูลหากัน CPU ซึ่งมีการทำงานด้วยความเร็วจะทำการเก็บการประมวลผลส่งไปยังบัฟเฟอร์ก่อน เมื่อทำงานใดเสร็จบัฟเฟอร์ก็จะส่งต่อการทำงานให้เครื่องพิมพ์ทำงานจนกว่าจะหมดข้อมูลในบัฟเฟอร์สำหรับกาทำงานของ CPU และการของเครื่องพิมพ์

DTS06-04/08/2009

สแตก(stack)

สแตก(Stack) คืออะไร

ความรู้พื้นฐานเกี่ยวกับสแตก

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

สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแตกหรือ หรือเรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก

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

ส่วนประกอบของสแตก

การนำสแตกไปใช้งานนั้นไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ

ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น
นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร เปรียบเทียบส่วนประกอบของสแตกได้กับการให้ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Elements หรือสมาชิกของสแตก คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max Stack เป็นตัวบอกว่า กระป๋องนี้เก็บลูกเทนนิสได้มากที่สุดเท่าไร

การจัดการ กับสแตก

ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ การเพิ่มข้อมูลลงบนสแตก (pushing stack) และ การดึงข้อมูลออกจากสแตก (poping stack)

1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่

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


นิยาม Push (S,x)

ถ้าให้ S เป็นสแตก และ x เป็นข้อมูลที่ต้องการใส่ในสแตก หรือดึงออกสแตก กระบวนการ push (S, x ) หมายถึง การ push ข้อมูล x ลงสแตก โดยการ push จะเริ่มจากสแตกว่างโดยให้ค่า ท๊อปมีค่าเป็นศูนย์ เมื่อมีการ push ข้อมูลเข้าในสแตก ค่า ของท๊อปจะเปลี่ยนเพิ่มขึ้นทีละหนึ่งทุกครั้งที่ทำการ push

2. การดึงข้อมูลจากสแตก (Popping Stack) หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วย ท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่


นิยาม pop(S)

ถ้าให้ S เป็นสแตก การ pop(S) คือการนำข้อมูลบนสุดในสแตกออกจากสแตกและให้ค่าเป็นข้อมูลที่นำออกจากสแตก ดังนั้น คำสั่ง x = pop(S) ก็คือการนำข้อมูลที่ท๊อปของสแตกออกมา และใส่ค่าไว้ที่ x หรือการเซตค่า x ให้เท่ากับข้อมูลที่ดึงจากสแตก

ปัญหาที่เกิดขึ้นกับสแตก

คือขอผิดพลาดที่เกิดขึ้นซึ่งมีผลมาจากการจัดการสแตกมีดังนี้

สแตกเต็ม (Full Stack)

สแตกว่าง (Empty Stack)

สแตกเต็ม (Full Stack)
การ push สแตกทุกครั้งจะมีการตรวจสอบที่ว่างในสแตกว่ามีที่ว่างเหลือหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ push สแตกได้ ในกรณีเช่นนี้เราเรียกว่าเกิดสถานะล้นเต็ม (Stack Overflow) โดย การตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของ สแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก


2. สแตกว่าง (Empty Stack)

นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม

การ pop สแตกทุกครั้งจะมีการตรวจสอบข้อมูลในสแตกว่ามีข้อมูลในสแตกหรือไม่ ถ้าไม่มีข้อมูลในสแตก เหลืออยู่ เราก็ไม่สามารถทำการ pop สแตกได้ ในกรณีเช่นนี้เรียกว่าเกิดสถานะ สแตกจม (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่า สแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้

DTS05-28/07/2009

LINKED LIST

ลิงค์ลิสต์ เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของ element ต่างๆ โดยมีพอยน์เตอร์เป็นตัวเชื่อมต่อ ในแต่ละ element จะเรียกว่า node ซึ่งแต่ละโนดประกอบด้วย data (เก็บข้อมูลของอิลิเม้นท์) และ link field (เก็บตำแหน่งของโนดต่อไปในลิสต์)
โครงสร้างข้อมูลแบบลิงค์ลิสต์
1. Head Structure ประกอบด้วย Count, Pos และ head
2. Data Node Structure ประกอบด้วย Data และ Pointer ที่ชี้ไปยังข้อมูลตัวถัดไป

กระบวนงานและฟังก์ชันที่ใช้ดำเนินงานพื้นฐาน
1. Create List มีหน้าที่สร้างลิสต์ว่าง ผลลัพธ์ที่ได้คือ ลิสต์ว่าง และ count จะมีค่าป็น 0
2. Insert Node มีหน้าที่เพิ่มข้อมูลลงไปในลิสต์ในตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ลิสต์ ข้อมูล และตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะมีค่าเป็น 1 หรือ 2.....n ตามจำนวนของการ insert
3. Delete Node มีหน้าที่ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ มีข้อมูลนำเข้า ได้แก่ ข้อมูลและตำแหน่ง ส่วนผลลัพธ์ที่ได้คือ ลิสต์ที่มีการเปลี่ยนแปลง และ count จะลดจำนวนจากเดิมลงเรื่อย ตามจำนวนลิสต์ที่ลบไป
4. Search list มีหน้าที่ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ ผลลัพธ์ที่ได้ จะเป็นค่าจริงถ้าพบข้อมูล และจะเป็นค่าเท็จถ้าไม่พบข้อมูล

DTS04-21/07/2009

โครงสร้างข้อมูลแบบเซต (set) เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย จะมีตัวดำเนินงานของเซ็ต คือ
1.โครงสร้างแบบเชิงเส้น (linear) เป็นโครงสร้างที่ข้อมูลมีความสัมพันธ์แบบหนึ่งต่อหนึ่ง (one-to-one relationship) นั่นคือเราสามารถระบุถึงข้อมูลตัวถัดไปของข้อมูลได้
2.โครงสร้างแบบต้นไม้หรือแบบลำดับขั้น (tree or hierarchical) เป็นโครงสร้างที่ข้อมูลมีความสัมพันธ์กันแบบหนึ่งต่อหลาย (one-to-many relationship) นั่นคือ ข้อมูลตัวหนึ่งสามารถมีความสัมพันธ์กับข้อมูลในลำดับรองลงไปได้หลายตัว
3.โครงสร้างแบบกราฟหรือเครือข่าย (graph or network) เป็นโครงสร้างที่ข้อมูลมีความสัมพันธ์กันแบบหลายต่อหลาย (many-to-many relationship) นั่นคือ ข้อมูลตัวหนึ่ง ๆ อาจจะมีความสัมพันธ์กับข้อมูลตัวอื่น ๆ กี่ตัวก็ได้

โครงสร้างข้อมูลแบบสตริง
สติงเป็นโครงสร้างข้อมูลที่เป็นการรวบรวมโครสร้างข้อมูล Character ซึ่งเป็นตัวอักษรและสัญลักษณ์ ต่างๆเป็นข้อมูลที่ใช้กันอย่างมาก

DTS03-30/06/2009

อาร์เรย์หมายถึงการจัดชุดของข้อมูลที่เป็นชนิดเดียวกันที่กำหนดโดยรูปแบบของช่องตาราง
ที่จัดเก็บจะต้องเท่ากันทุกช่องโดยทั่วไปอาร์เรย์จะมี 1 มิติ 2 มิติ และหลายมิติ


อาร์เรย์ 1 มิติ
เป็นตัวแปรที่เก็บข้อมูลเพียงแถวเดียวหรือชั้นเดียวเช่น



ในการคำนวณหาสมาชิกของอาร์เรย์ 1 มิติทำได้ดังนี้
จำนวนสมาชิกของอาร์เรย์ = (u-l)+1
u คือค่าสูงสุด หรือ Upper bound
l คือค่าต่ำสุด หรือ Lower bound

ส่วน 2 มิติสามารถหาได้ดังนี้

จำนวนสมาชิก = M x N


รูปแบบของการประกาศตัวแปรอาร์เรย์มิติเดียว

type array-name[n];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือขนาดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น

เช่น int num[3];

การกำหนดข้อมูลให้กับตัวแปรอาร์เรย์
เราสามารถกำหนดไปพร้อมกับการประสร้างตัวแปรได้เลย เช่น

type array-name = {value-1,value-2,....value-n};

value-1,value-2 คือข้อมูลที่กำหนดให้ตัวแปรและต้องเป็นชนิดเดียวกับตัวแปรนั้น ๆ ด้วย เช่น

int number[3] = {23,-123,43};
char name[5] = "BENZ";

อาร์เรย์ 2 มิติ
มีลักษณะการกำหนดตำแหน่งแบบแถวและคอลัมน์

รูปแบบของการประกาศตัวแปรอาร์เรย์ 2 มิติ

type array-name[n][m];
type คือ ชนิดของตัวแปรอาร์เรย์ที่จะสร้างขึ้น เช่น int,float,char เป็นต้น
array-name คือ ชื่อของตัวแปรอาร์เรย์ที่ต้องตั้งให้สื่อและเข้ากับชนิดของตัวแปร
และจะต้องไม่ไปตรงกับคำสงวนของภาษาซีด้วย
n คือ จำนวนแถวของตัวแปรอาร์เรย์
m คือ จำนวนคอลัมน์ของตัวแปรอาร์เรย์

เช่น int num[3][5];

Structure โครงสร้างข้อมูล
หมายถึง การที่นำข้อมูลที่มีความเกี่ยวข้องกัน เช่น ข้อมูลของนักศึกษาที่อาจประกอบด้วย
ชื่อ,นามสกุล,อายุ,เพศ,ชั้นเรียน มารวมกันและจัดทำเป็นโครงสร้างข้อมูล ดังภาพ



แต่ในการเรียนใช้งานจริง ๆ เราจะต้องสร้างตัวแปรชนิดโครงสร้างขึ้นมาใช้งานจริง ๆ
ไม่สามารถใช้โครงสร้าง student ได้
การประกาศตัวแปรชนิดโครงสร้าง
struct name {
type var-1;
type var-2;
.....
type var-n;
} struct-variable;

struct คือ คำที่ใช้กำหนดโครงสร้างข้อมูล
(ต้องมีเสมอ)
name คือ ชื่อของโครงสร้างข้อมูลที่จะสร้างขึ้น
type var-1,type var-2 คือชื่อตัวแปร
ในกลุ่มโครงสร้างข้อมูล
struct-variable คือชื่อของตัวแปรชนิดโครงสร้าง
ที่ต้องการสร้างขึ้นจะมีลักษณะโครงสร้างภายใน
เหมือนกับโครงสร้างข้อมูลที่กำหนด


** กรณีประกาศตัวแปรโครงสร้างหลายตัวใช้คอมม่าขั้นหรือประกาศอีกแบบ เช่น
struct struct-name variable;

ตัวอย่าง
struct student student1;

*** เราสามารถประกาศ Structure หนึ่งเป็นสมาชิกของอีก Structure ก็ได้
แต่ต้องประกาศตัวที่จะนำไปใส่ไปไว้อีก Structure ก่อน

การอ้างถึงสมาชิกในตัวแปรชนิดโครงสร้าง
struct-name.variable-name
struct-name คือ ชื่อของตัวแปรชนิดโครงสร้าง (ไม่ใช่ชื่อโครงสร้าง)
. คือเครื่องหมายขั้นระหว่างชื่อตัวแปรชนิดโครงสร้างกับตัวแปรที่เป็นสมาชิก
variable-name คือชื่อของตัวแปรที่เป็นสมาชิก


การกำหนดข้อมูลให้ตัวแปรชนิดโครงสร้าง
เราสามารถกำหนดได้เหมือนตัวแปรทั่วไปแต่ต้องอ้างอิงถึงสมาชิกให้ถูกต้อง เช่น

student1.age = 15;
student1.sex = 'M';

กรณีถ้าเป็นอาร์เรย์ของตัวแปรชนิดโครงสร้างสามารถเขียนได้ดังนี้

student1[0].age = 15;
student1[1].sex = 'M';

ปฐมนิเทศ

โครงสร้างข้อมูล (DATA STRUCTURE)

ผู้สอน : อาจารย์ปรมัตถ์ปัญปรัชญ์ ต้องประสงค์

E-mail : phorramatpanyaprat@hotmail.com

การเก็บคะแนน 100 แบ่งออกเป็น 60:40

60 คะแนนมาจาก

- การนำเสนองานและมีส่วนร่วมในกิจกรรมเรียน 10

- จัดทำรายงาน/แบบฝึกหัด 30

- mid 20

-Final 40

DTS02-23/06/2009

โครงสร้างข้อมูลคือความสัมพันธ์ระหว่างข้อมูลที่อยู่ในโครงสร้างนั้นๆรวมทั้งกระบวนการในกรจัดการโครงสร้างข้อมูล ประกอบด้วยคำสองคำคือ

1.โครงสร้างคือความสัมพันธ์ของสมาชิก

2.ข้อมูลคือข้อเท็จจริงต่างๆซึ่งอาจจะป็นตัวเลขหรือไม่เป็นก็ได้

ประเภทของโครงสร้างข้อมูลแบ่งอกเป็น2ประเภทคือ

1.โครงสร้างข้อมูลทางกายภาพ

2.โครงสร้างข้อมูลทางตรรกะ

ในการเลือกใช้โครงสร้างข้มูลเบดนั้นต้องคำนึงถึง

1.โครงสร้างข้อมูลนั้นสามารถสร้างความสัมพันธ์ให้กับข้อมูลชุดนั้น

2.โครงสร้างนั้นต้องง่ายต่อการดำเนินการในระบบงาน

3.การแทนที่ข้อมูลในหน่วยความจำหลัก ในการเขียนโปรแกรมคอมพิวเตอร์ จะแทนที่ข้อมูลในหน่วยความจำหลักอยู่

3.1การแทนข้อมูลแบบสแตติก

3.2การแทนที่ข้อมูลแบบไดนามิก

4.ขั้นตอนวิธี ขั้นตอนวิธีที่ดีควรมีคุณสมบัติดังนั้

1.มีความถูกต้อง

2.ใช้เวลาในการปฏิบัติงานน้อยที่สุด

3.สั้นกระชับมีเฉพาะขั้นตอนที่จำเป็น

4.ใช้หน่อยความจำน้อย

5.มีความยือหยุ่นน้อย

6.ใช้เวลาในการพัฒนาน้อย

7.ง่ายต่อความเข้าใจ

สิ่งที่ฉันปรารถนา

VDO สิ่งที่อยากบอก

DTS02-23/06/2009

สรุปบทเรียน

การบ้าน

#include <stdio.h>

#include <string.h>

void main()

{

struct computer {

char name[50];

char model[50];

char processor[30];

float speed;

int hard;

char Graphic[50];

char Operating[20];

float weight;

char price[20];

};

struct computer notebook;

strcpy(notebook.name,"Apple");

strcpy(notebook.model,"MacBook Air");

strcpy(notebook.processor,"intel core 2 duo");

notebook.speed=2.13;

notebook.hard=128;

strcpy(notebook.Graphic,"nVidia GeForce 9400M GS");

strcpy(notebook.Operating,"Mac OS 10.5");

notebook.weight=1.36;

strcpy(notebook.price,"65007");

printf("**********NoteBook********\n\n");

printf(" Name:%s\n",notebook.name);

printf(" model:%s\n",notebook.model);

printf(" processor:%s\n",notebook.processor);

printf(" speed:%f GHz \n",notebook.speed);

printf(" hard disk:%d gb\n",notebook.hard);

printf(" Graphic system:%s\n",notebook.Graphic);

printf(" Operating System:%s\n",notebook.Operating);

printf(" weight:%f kg \n",notebook.weight);

printf(" price:%s\n",notebook.price);

}

ประวัติ

ชื่อ จิรวัฒน์ ภูวสวัสดิ์ รหัสนักศึกษา 50132792049

Mr. Jirawat Powasawat

หลักสูตร การบริหารธุรกิจ(คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัดการ

มหาวิทยาลัยราชภัฏสวนดุสิต

E-Mail : u50132792049@gmail.com