DTS09-01-09-2552

Graphกราฟ (Graph)


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

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

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

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

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

DTS08-25-08-2552

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

นิยามของทรี

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

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

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

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

5. กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด

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

การแทนที่ทรีในหน่วยความจำหลัก

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

DTS07-11-08-2552

สรุป 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 ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่

DTS05-21/07/2009

เรื่อง Set and String

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

ตัวดำเนินการของเซ็ต (Set operators) ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้น

สมมติว่า ต้องการจัดตารางเรียน 4 วิชา ได้แก่ Math, English,Physics และ Chemistry ให้กับผู้ลงทะเบียนเรียน

วิธีการแก้ปัญหาเบื้องต้น
- จะต้องกำหนดเซ็ตของผู้เรียนที่ลงทะเบียนเรียนในแต่ละวิชา
- นำเซ็ตดังกล่าวที่ได้มาทำการ intersection กัน หากมีเซ็ตใดที่ทำการ intersect กันแล้ว มีข้อมูลสมาชิกในเซ็ตที่ซ้ำกันอยู่ จะไม่สามารถจัดให้วิชาดังกล่าวอยู่ในวันเวลาเดียวกันได้


โครงสร้างข้อมูลแบบสตริง
สตริง (String) หรือ สตริงของอักขระ (CharacterString) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง

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



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

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

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

การกำหนดตัวแปร country จะแตกต่างกับการกำหนดตัวแปรอะเรย์ เพราะเป็นการกำหนดตัวแปรพอย
เตอร์ ขึ้น 4 ตัว โดยให้แต่ละตัวชี้ไปยังค่าคงตัวสตริงทั้ง4 ตัว โดยที่ contry[0] จะชี้ไปที่ข้อมูลแรก contry[1]จะชี้ข้อมูลที่สอง contry[2] จะชี้ข้อมูลที่สาม และcontry[3] จะชี้ข้อมูลตัวสุดท้าย
ในการเขียนค่าเริ่มต้น คือ ค่าคงตัวสตริง เขียนไว้ในเครื่องหมายวงเล็บปีกกา และข้อมูลในเครื่องหมาย
คำพูด คือ ค่าคงตัวสตริง


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

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

เช่น
char fruit [3][7]={“Apple”, “Orange”, “Mango”};

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

สิ่งที่ได้รับจากการเรียน : ได้ทราบถึงการนำ Set และ String สามารถนำมาใช้กับ อะเรย์ ได้

การบ้าน iostream.h

โปรแกรมแสดงสูตรคูณ

#include

int main() {

int x;

cout<<"===***Multiplication table***==="<<'\n'<<'\n';

cout<<"Enter your number(2-25):";

cin>>x;

for(int i=1;i<=12;i++)

cout<<<" t=" ">

return 0;

}