DTS09-01-09-2552

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

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

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

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

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

DTS08-25-08-2552

Unit 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-28-07-2552

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 มีหน้าที่ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์ ผลลัพธ์ที่ได้ จะเป็นค่าจริงถ้าพบข้อมูล และจะเป็นค่าเท็จถ้าไม่พบข้อมูล

การบ้าน 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;
}

DTS04-14/07/2009

สรุป Set and String

โครงสร้างข้อมูลแบบเซต (Set) เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย

ตัวดำเนินการของเซ็ต

-Set intersection การซ้ำกัน

-Set union การรวมกัน

-Set difference ความแตกต่าง

เช่น สมาชิกในห้อง 323 เป็น union กัน เพราะมีตอนเรียน A และตอนเรียน Bแต่ไม่เป็น intersection กัน เพราะคนๆหนึ่งไม่สามารถอยู่ในอีกห้องหนึ่งได้

สตริง String) หรือ สตริงของอักขระ เป็นข้อมูลที่ประกอบด้วยตัวอักษร ตัวเลข หรือเครื่องหมายสตริงในภาษา C ก็คือ อาร์เรย์ของตัวอักษร ที่มีข้อมูลชนิดตัวอักษรเรียงกันไป แต่จะต้องมีจุดสิ้นสุดด้วย โดยจะใช้ตัวอักษรวางหรือ Null Character เป็นจุดสิ้นสุดของสตริง ซึ่งจะต่างจากอาร์เรย์ปกติที่ไม่ต้องมีจุดสิ้นสุดของอาร์เรย์

การเก็บข้อมูลของสตริง

การเก็บข้อมูลของสตริงนั้น จะมีการเก็บข้อมูลอยู่ 2 ส่วน ส่วนแรกจะเป็นข้อมูลตัวอักษรโดยเก็บเรียงกันไป แบะส่วนที่ 2 จะเก็บจุดสิ้นสุดของสตริง ซึ่งจุสิ้นสุดของสตริงจะใช้ Null Characterหรือ ‘\0’ตัวอักษรที่เก็บอยู่ในหน่วยความจำ ข้อมูลชนิด

ตัวอักษรต้องการหน่วยความจำเพียง 1 ส่วน ส่วนข้อมูลชนิดสตริงตัวอักษร 1 ตัว ต้องการหน่วยความจำ 2 ส่วน ส่วนแรกใช้เก็บข้อมูล และส่วนที่สองใช้เก็บจะสิ้นสุดของสตริง

char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};

char a[ ]=“HELLO”;

จะรู้ได้อย่างไรว่าตัวไหนเป็น Character ตัวไหนเป็น String ดูได้จาก Single quote กับ double quote = “”double quote หรือฟันหนู หรืออัญประกาศ หรือเขาคู่ หรือเครื่องหมายคำพูดsingle quote หรือ apostrophe หรือฝนทอง หรือเขาเดี่ยว(ความยาวของสตริงจพถูกกำหนดโดยขนาดของสตริง)

การกำหนดตัวแปรสตริง

ในการกำหนดตัวแปรของสตริง อาศัยหลักการของอะเรย์ เพราะ สตริงก็คืออะเรย์ของอักขระที่ปิดท้ายด้วย null character (\0) และมีฟังก์ชันพิเศษสำหรับทำงานกับสตริงโดยเฉพาะ

ฟังก์ชัน getch() ใช้รับตัวอักขระ 1 ตัวจากแป้นพิมพ์ แต่ขณะรับไม่แสดงทางจอภาพ

ฟังก์ชัน gets() เป็นฟังก์ชันใช้สำหรับรับข้อมูลชนิด Stringหรือข้อความซึ่งป้อนทางแป้นพิมพ์รับข้อมูลที่เป็นข้อความจากเป็นฟังก์ชันที่ใช้ในการแป้นพิมพ์เข้ามาเก็บไว้ในตัวแปรแบบอาเรย์ การใช้ฟังก์ชัน gets(); จะต้องมีการประกาศตัวแปรแบบอาเรย์ และกำหนดจำนวนตัวอักษร ที่ต้องการป้อน โดยคอมพิวเตอร์จะจองพื้นที่ไว้ตามจำนวนตัวอักษร แต่จะป้อนได้น้อยกว่าที่จองไว้ 1 ตัว เพื่อให้ตัวแปรเก็บ 0 อีก 1รูปแบบการใช้งานฟังก์ชัน

ตัวอย่าง โปรแกรม

#include”stdio.h”

main()

{char message[50];

printf(“ Enter a message(less than 49 characters)\n”);

gets(message);

printf(“ The message you entered is %s\n”,message);

}

ผลลัพธ์

Enter a message

(less than 49 characters)

Kiss and say good-byThe message you entered is Kiss and say good-bye

อะเรย์ของสตริง

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

ฟังก์ชันอื่นที่ใช้กับสตริง

การใช้สตริงนั้น จะมีฟังก์ชันในการกระทำกับสตริงอีกมาก จะช่วยให้การทำงานนั้นสะดวดมากยิ่งขึ้น ซึ่งการใช้ฟังก์ชันต่าง ๆ ที่เกี่ยวกับสตริงนั้นจะต้องนำเข้าไลบรารีไฟล์ strintg.h ด้วยเสมอ ซึ่งมีฟังก์ชันต่าง ๆ ดังนี้

ฟังก์ชั่นStrlen

เป็นฟังก์ชั่นที่ใช้ในการหาขนาดความยาวของข้อความนั้นว่ามีความยาวของข้อมูลกี่ตัวอักษรรูปแบบการใช้ฟังก์ชั่นint strlen (const char *string);ตัวอย่างด้านล่างนี้เป็นการใช้ฟังก์ชัน strlenx = strlen(“Sorapong”);หรือchar str[] = “Good Morning”;x = strlen(str);

คัดลอกสตริง ( strcpy, strncpy )

ในภาษา C จะมีฟังก์ชันในการคะดลอกสตริงหนึ่งไปใส่ในอีกสตริงหนึ่ง อยู่ 2 ฟังก์ชัน คือ strcpy และ strncpy ทั้ง 2 ฟังก์ชันนี้ จะเป็นฟังก์ชันในการคัดลอกสตริง แต่ในฟังก์ชันที่ 2 สามารถกำหนดความยาวของสตริงที่ต้องการจะคัดลอกได้ strcpy ฟังก์ชัน strcpy เป็นฟังก์ชันในการคัดลอกสตริงพื้นฐาน การทำงาน คือ จะทำการคัดลอกสตริงต้นทั้งหมด ซึ่งจะรวมไปถึง Null Character ด้วย ไปใส่ในสตริงปลายทาง

โดยการประกาศฟังก์ชัน strcpy เป็นดังนี้char*strcpy (char *to_string, const char *from_string);ตัวอย่างด้านล่างนี้เป็นตัวอย่างการใช้ฟังก์ชัน strcpy strcpy(s1,s2);

เปรียบเทียบสตริง (strcmp,strncmp)ฟังก์ชันในการเปรียบเทียบสตริงในภาษา c จะมีอยู่ 2 ฟังก์ชัน คือ ฟังก์ชัน strcmp และฟังก์ชัน strncmp ซึ่งฟังก์ชันทั้งสองจะทำการเปรียบเทียบเหมือนกัน แต่ฟังก์ชัน strncmp จะกำหนดความยาวในการเปรียบเทียบได้ ซึ่งผลของฟังก์ชันที่จะส่งกลับมาให้จะมีดังนี้

1. ถ้าทั้ง 2 สตริงเท่ากันจะส่งค่ากลับมาเป็น 0 โดยที่สตริงจะเท่ากัน ได้จะต้องมีความยาวที่เท่ากัน แบะมีตัวอักษรเหมือนกันทุกตัว

2. ถ้าสตริงตัวแรกน้อยกว่าสตริงตัวที่สอง จะส่งค่ากลับเป็นค่าที่น้อยกว่า 0 โดยสตริง s1 จะน้อยกว่า s2 ก็เมื่อทำการเปรียบเทียบไปที่ละตัวอักษร แล้วพบว่าตัวอักษรใน s1 มีค่าน้อยกว่าตัวอักษรของ s2 (โดยเทียบจากรหัส ACSII) หรือจุดสิ้นสุดของ s1 อยู่ก่อน s2

3. ถ้าสตริงตัวแรกมากกว่าสตริงตัวที่สอง จะส่งค่ากลับเป็นค่าที่มากกว่า 0 สตริง s1 จะน้อยกว่า s2 ก็เมื่อทำการเปรียบเทียบไปที่ละตัวอักษรแล้วพบว่าตัวอักษรใน s1 มีค่ามากกว่าตัวอักษรของ s2 (โดยเทียบจากรหัส ACSII)