DTS07-06-08-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Queue

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

เรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO) มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียง ด้านเดียว เรียกว่า ส่วนหลัง ( Rear ) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่า ส่วนหน้า ( Front )

การดำเนินการพื้นฐานของ Queue ได้แก่
- การนำข้อมูลเข้าสู่ Queue เรียกว่า enqueue
- การนำข้อมูลออกจาก Queue เรียกว่า dequeue
- การนำข้อมูลที่อยู่ตอนต้นของ Queue มาแสดง เรียกว่า queue front

- การนำข้อมูลที่อยู่ตอนท้ายของ Queue มาแสดง เรียกว่า queue rear

การนำข้อมูลเข้าสู่โครงสร้างคิว (enqueue)

เป็น กระบวนการอ่านข้อมูลจากภายนอกเข้าสู่โครงสร้างคิวทางด้านปลายที่พอยน์เตอร์ R ชี้อยู่ โดยพอยน์เตอร์ R จะเปลี่ยนตำแหน่ง ชี้ไปยังตำแหน่งที่ว่างตำแหน่งถัดไป ก่อนนำข้อมูลเข้าสู่โครงสร้างคิว
ข้อควรคำนึงถึง คือ ในขณะที่คิวเต็ม (Full Queues) หรือไม่มีช่องว่างเหลืออยู่ จะไม่สามารถนำข้อมูลเข้าไปเก็บในโครงสร้างคิวได้อีก ซึ่งจะทำให้เกิดปัญหา “Overflow” ขึ้น

"ขั้นตอนการนำข้อมูลเข้าสู่โครงสร้างคิว" มีดังนี้
1. เมื่อมีข้อมูลเข้าสู่คิว ให้ตรวจสอบว่าคิวเต็มหรือไม่ ถ้าคิวเต็มไม่ให้มีการรับข้อมูล
2. ถ้าคิวไม่เต็มให้เลื่อนตำแหน่งพอยน์เตอร์ R แล้วนำข้อมูลเข้าสู่คิว
3. ตรวจสอบเงื่อนไขว่าถ้าเป็นข้อมูลตัวแรกในคิว ให้เปลี่ยนพอยน์เตอร์ F ให้ชี้ค่าแรก

การนำข้อมูลออกจากโครงสร้างคิว (dequeue)
เป็นการลบ ข้อมูลออกจากโครงสร้างคิวทางด้านหน้า ของโครงสร้างคิว โดยมีพอยน์เตอร์ F เป็นพอยน์เตอร์ชี้บอกตำแหน่งที่ข้อมูลอยู่ เมื่อมีการลบข้อมูล ออกจากโครงสร้างคิวเรียบร้อยแล้ว พอยน์เตอร์ F จะเลื่อนตำแหน่ง ไปยังตำแหน่งถัดไป
ข้อควรคำนึงถึง คือ เมื่อคิวว่าง (Empty queue) หรือไม่มีข้อมูลเหลืออยู่ จะไม่สามารถนำข้อมูลออกจากคิวได้อีก ซึ่ง จะทำให้เกิดปัญหา “underflow” ขึ้น

"ขั้นตอนการนำข้อมูลออกจากโครงสร้างคิว" มีดังนี้
1. ตรวจสอบว่าเป็นคิวว่าง (Empty Queues) หรือไม่
2. ถ้าคิวไม่ว่างให้นำข้อข้อมูลออกจากคิว ณ ตำแหน่งที่ F ชี้อยู่ จากนั้นก็ทำการเลื่อนตำแหน่งพอยน์เตอร์ F ไปยังตำแหน่งถัดไป
3. ถ้ามีข้อมูลอยู่เพียงตัวเดียว ให้กำหนดให้พอยน์เตอร์ F และ R เป็นศูนย์ (0)

ตัวอย่างการนำข้อมูลออกจากคิว (dequeue)

การแสดงข้อมูลตอนต้นของคิว (Queue Front)เป็น การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง แต่จะไม่มีการเอาข้อมูลออกจากคิว ซึ่งประโยชน์ของมันก็คือ สามารถทำให้เรารู้ว่า คิวถัดไป (next queue)

การดำเนินการเกี่ยวกับคิว ได้แก่

1.) Create Queue เป็นการจัดสรรหน่วยความจำให้กับ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าป็น null และจำนวนสมาชิกเป็นศูนย์

2.) Enqueue เป็นการเพิ่มข้อมูลเข้าไปในคิว ซึ่ง pointer rear จะเปลี่ยน

3.) Dequeue เป็นการนำข้อมูลออกจากคิว ซึ่ง pointer front จะเปลี่ยน

4.) Queue Front เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง

5.) Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง

6.) Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่

7.) Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8.) Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9.) Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว วิธีการคือ ต้องทำการ Dequeue ทีละตัว แล้วจึงจะ Destroy

2. การแทนที่ข้อมูลของคิวแบบอะเรย์

จาก การดำเนินการกับโครงสร้างคิวจะเห็นได้ว่า โครงสร้างคิวยังไม่มีประสิทธิภาพเพียงใดนัก เนื่องจากเมื่อมีการเพิ่มข้อมูลจนเต็ม (Full Queue) และมีการลบข้อมูลออกจากโครงสร้างคิวแล้ว พอยน์เตอร์ F จะยังคงอยู่ที่ตำแหน่งเดิม ไม่สามารถเปลี่ยนไปที่ตำแหน่งเริ่มต้นใหม่ได้จนกว่าจะมีการลบข้อมูลออกจาก คิวหมดแล้ว (Empty Queue) จึงจะสามารถกำหนดพอยน์เตอร์ข้อมูล F และ R ให้กลับไปยังตำแหน่งเริ่มต้นใหม่ได้ ทำให้เสียพื้นที่ของโครงสร้างคิวในตำแหน่งที่พอยน์เตอร์ F ผ่านมา ไปเนื่องจากต้องรอให้ตำแหน่งของพอยน์เตอร์ F ไปยังตำแหน่งสุดท้ายก่อน (เมื่อคิวว่าง) จึงจะสามารถใช้พื้นที่ดังกล่าวได้

ในกรณีที่เป็นคิวแบบวงกลม คิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆ จนกระทั่ง rear มีค่าน้อยกว่า front อยู่ 1 ค่า คือ rear = front - 1

DTS06-29-07-2552

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

การดำเนินการเกี่ยวกับสแตก
1. Create stack จัดสรรหน่วยความจำให้แก่ head node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push stack โดยทั่วไปจะกระทำที่ต้นลิสต์ซึ่งถือว่าเป็นตำแหน่งโหนดบนสุดของสแตกหรือเป็นตำแหน่งที่พุชโหนดเข้าไปในสแตกหลังสุด เมื่อมีการพุชโหนดใหม่ลงในสแตกก็จะต้องปรับค่าพอยน์เตอร์ของโหนดใหม่ชี้ไปที่โหนดบนสุดในขณะนั้น และถ้า top เป็นพอยน์เตอร์ชี้ที่ตำแหน่งโหนดบนสุดในสแตก ให้ทำการปรับพอยน์เตอร์ top ชี้ไปที่โหนดใหม่ที่ทำการพุชลงไปแทน
3. Pop stack โหนดแรกที่จะถูกพ็อปออกมาคือโหนดที่อยู่บนสุดหรือโหนดแรกของลิงค์ลิสต์นั่นเอง ก่อนที่จะทำการพ็อปโหนดต้องตรวจสอบก่อนว่าสแตกว่างหรือไม่ โดยตรวจสอบจากค่าพอยน์เตอร์ที่ชี้ตำแหน่งโหนดบนสุดของสแตก ถ้ามีค่าเป็นนัลแสดงว่า สแตกว่าง และถ้าสแตกไม่ว่างก็สามารถทำการพ็อปโหนดออกจากสแตกได้
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack (เป็นการคัดลอกโดยไม่มีการลบข้อมูลออกจากสแตก)
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่ ถ้าไม่มีข้อมูลสแตกเหลืออยู่ เราก็ไม่สามารถทำการ Pop สแตกได้ ในกรณีเช่นนี้เรียกว่า "สแตกว่าง" (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่าสแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ Push สแตกได้ ในกรณีเช่นนี้เราเรียกว่า "สแตกเต็ม" (Stack Overflow) โดยการตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของสแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูลอีก
7. Stack count ส่งค่าจำนวนรายการในสแตก หรือเป็นการนับจำนวนสมาชิกในสแตก
8. Destroy stack คืนหน่วยความจำของทุก node ในสแตกให้ระบบ หรือเป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การแทนที่ข้อมูลของสแตกแบบอะเรย์ เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการ นำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกัน ไปตามพื้นที่ที่กำหนด

การดำเนินการเกี่ยวกับสแตก
1. Create stack สร้าง stack head node
2. Push stack เพิ่มรายการใน stack
3. Pop stack ลบรายการใน stack
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่
7. Stack count ส่งค่าจำนวนรายการใน stack
8. Destroy stack คืนหน่วยความจำของทุก node ใน stack ให้ระบบ

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

1. การทำงานของโปรแกรมที่มีโปรแกรมย่อย
การทำงานของโปแกรมหลักที่เรียกใช้โปรแกรมย่อย และในแต่ละโปรแกรมย่อยมีการเรียกใช้โปรแกรมย่อยต่อไปอีก ลักษณะของปฏิบัติการแบบนี้ โครงสร้างข้อมูลแบบสแตกสามารถช่วยทำงานได้ โดยที่แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยนั้นแล้ว จะทำการ popค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อยนั้น จนกระทั่งโหนดในสแตกว่าง
2. การคำนวณนิพจน์ทางคณิตศาสตร์การเขียนนิพจน์คณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์คณิตศาสตร์สามารถเขียนได้ 3 รูปแบบดังนี้
1. นิพจน์อินฟิกซ์ (infix expression) การเขียนนิพจน์ด้วยรูปแบบนี้ ตัวดำเนินการ (operator) อยู่ตรงกลางระหว่างตัวถูกดำเนินการ (operand) 2 ตัว
2. นิพจน์โพสฟิกซ์ (postfix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ก่อน ตามด้วยตัวดำเนินการ
3. นิพจน์พรีฟิกซ์ (prefix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวดำเนินการก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ตามลำดับ

DTS05-22-07-52

สรุปสิ่งที่ได้จากการเรียน เรื่อง Linked List

- โครงสร้างข้อมลแบบลิงค์ลิสต์
- กระบวนงานและฟังกชันทที่ใช้ดำเนินงานพื้นฐาน
- การสร้างลิงค์ลิสต์
- ลิงค์ลิสต์แบบซับซ้อน

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

การดำเนินการเกี่ยวกับสตริง จะใช้คำสั่ง #include ในการเรียกใช้ เช่น
- ฟังก์ชัน strlen(str) ใช้หาความยาว
- ฟังก์ชัน strcpy(str1, str2) ใช้คัดลอกข้อมูล จากตัวที่ 2 ไปให้ตัวที่ 1
- ฟังก์ชัน strcat(str1, str2) ใช้เชื่อมต่อข้อความ เช่น ตัวแปร 1 เก็บ ชื่อ ตัวแปร 2 เก็บ นามสกุล แล้วนำตัวแปรทั้ง2 มาต่อกัน
- ฟังก์ชัน stecmp(str1, str2) ใช้ปรียบเทียบข้อความ 2 ข้อความว่ามีค่าเท่ากันหรือไม่ ยึดตามหลักพจนานุกรม

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

5. Traverse ทำหน้าที่ท่องหรือเยือนไปในลิสต์เพื่อเข้าถึงและประมวลผลนำเข้า ผลลัพธ์ที่ได้จะขึ้นอยู่กับการประมวลผล อย่างเช่น การรวมฟิลด์ในลิสต์ การเปลี่ยนแปลงค่าในโนด การคำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น

6. Retrieve Node ทำหน้าที่หาตำแหน่งของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้ก็คือ ตำแหน่งข้อมูลที่อยู่ในลิสต์ และเมื่อรู้ตำแหน่งก็ดึงค่าที่ได้มาแสดงในโปรแกรม

7. EmptyList ทำหน้าที่ทดสอบดูว่า ลิสต์ว่างหรือไม่ ผลลัพธ์ที่ได้คือ เป็นจริงและเป็นเท็จ กล่าวคือ จะเป็นจริงก็ต่อเมื่อลิสต์ว่าง และจะเป็นเท็จก็ต่อเมื่อลิสต์ไม่ว่าง

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

9. List Count ทำหน้าที่นับจำนวนของข้อมูลที่อยู่ในลิสต์ ผลลัพธ์ที่ได้คือ จำนวนข้อมูลที่อยู่ในลิสต์นั้นๆ ซึ่งจะใช้ค่า count ที่อยู่ใน Head Node ออกมาแสดง

10. Destroy List ทำหน้าที่ในการลำลายลิสต์ หรือหยุดใช้ลิสต์นี้แล้ว

Linked List แบบซับซ้อน มี 2 แบบ

สแตก stack

สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทําที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สําคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนําออกมา จากสแตกเป็นลําดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)

การดําเนินงานพื้นฐานของสแตกการทํางานต่าง ๆ ของสแตกจะกระทําที่ปลายข้างหนึ่งของ สแตกเท่านั้น ดังนั้นจะต้องมีตัวชี้ตําแหน่งข้อมูลบนสุดของสแตกด้วยการทํางานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สําคัญ

คือ1.Push คือ การนําข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก

ในการเพิ่มข้อมูลลงในสแตก จะต้องทําการตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตําแหน่งให้ไปชี้ที่ตําแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม้สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก

2. Pop คือ การนําข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องการนําข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนําข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1 ตัว แล้วนําสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทําการ pop สแตก จะทําให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow เพราะฉะนั้นก่อนนําข้อมูลออกจากสแตกจะต้องตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนําข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตําแหน่งให้ไปชี้ตําแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนํา ออกไป

3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นําเอาข้อมูลนั้นออกจากสแตก

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

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

DTS04-15-07-52

สรุปบทเรียนเรื่อง เซ็ตและสตริง


เซ็ตเป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้ตัวดำเนินการของเซ็ต (Set operators)ประกอบด้วย
- set intersection
- set union
- set difference เป็นต้นสตริง (String) หรือ สตริงของอักขระ (Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง การประยุกต์ใช้คอมพิวเตอร์ที่เกี่ยวกับข้อมูลที่เป็นสตริง มีการนําไปใช้สร้างโปรแกรมประเภทบรรณาธิการข้อความ(text editor) หรือโปรแกรมประเภทประมวลผลคํา (wordprocessing) ซึ่งมีการทํางานที่อํานวยความสะดวกหลายอย่าง เช่น การตรวจสอบข้อความ การจัดแนวข้อความในแต่ละย่อหน้าและการค้นหาคํา เป็นต้นสตริงกับอะเรย์สตริง คือ อะเรย์ของอักขระ เช่น char a[6]อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character เช่นchar a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};char a[ ]=“HELLO”;

ความยาวของสตริง จะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่วยความจำให้กับ \0ด้วย เช่น“This is String !”
จะเป็นข้อมูลแบบสตริงยาว 16 อักขระ
การกำหนดสตริงการกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว(String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
การกำหนดค่าคงตัวสตริงสามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอกฟังก์ชัน ชื่อค่าคงตัวจะเป็นพอยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริงนั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่วยความจำที่เก็บตัวมันเองการกำหนดค่าให้กับสตริงนั้น เราจะใช้เครื่องหมาย double quote (“ ”) เช่น “abc” คือ ชุดของอักขระที่มีขนาด 4(รวม \0 ด้วย)

DTS03-01-07-2552

Data Structure

เรื่อง Set and String
Pointer ตัวแปร pointer เป็นตัวแปรที่ทำหน้าที่เก็บตำแหน่งที่อยู่ของตัวแปร
สามารถอ้างอิงกลับไปกลับมาได้ มีขนาด 2 ไบต์เท่ากันหมด ไม่ว่าจะเป็น
char,int,floatหรืออื่นๆในการประกาศตัวแปร pointer จะต้องนำหน้าด้วย
เครื่องหมาย * เช่น int*x เป็นตัวแปร pointer

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

ตัวอย่าง
int *ptr,count เป็นการประกาศตัวแปร ptr เป็นตัวแปร pointer
และประกาศตัวแปร count
count = 100 เป็นการกำหนดค่าให้กับ count มีค่าเท่ากับ 1
00ptr = &count เป็นการกำหนดค่าให้กับ ptr มีค่าเท่ากับตำแหน่งที่อยู่ของ count


ถ้าต้องการทราบว่า *ptr มีค่าเท่าไหร่หาได้จาก ณ ตำแหน่งที่ ptr เก็บอยู่
คือตำแหน่งที่เท่าไหร่แล้วดูว่าที่ตำแหน่งนั้นมีค่าเท่ากับเท่าไหร่


Set
เป็นโครงสร้างที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กันเลย ตัวดำเนินการของเซ็ต ประกอบด้วย
1.set intersection
2.set union
3.set difference


String
เป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกัน
ความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้น ต้องทำการจองเนื้อที่ให้กับ \0 ด้วย

DTS02-24-06-2552

สรุป
เรื่อง Array and Record

-การดําเนินการเกี่ยวข้องกับอะเรย์ 1 มิติ หลายมิติ
-การส่งค่าของอะเรย์ ในโปรแกรม และฟังก์ชัน
-การดําเนินการที่เกี่ยวข้องกับ เรคคอร์ด
-ความสัมพันธ์ระหว่าง เรคคอร์ด กับอะเรย์ และอะเรย์ชนิดโครงสร้าง

อะเรย์เป็นโครงสร้างข้อมูลที่เรียกว่า Linear List มีลักษณะคล้ายเซ็ตในคณิตศาสตร์ คือ อะเรย์จะประกอบด้วยสมาชิกที่มีจํานวนคงที่ มีรูปแบบข้อมูลเป็นแบบเดียวกัน สมาชิกแต่ละตัวใช้เนื้อที่จัดเก็บที่มีขนาดเท่ากัน เรียงต่อเนื่องในหน่วยความจําหลัก

การกำหนด Array

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

ข้อกําหนดของการกําหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ

1.ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
2.ค่าต่ำสุด เรียกว่า ขอบเขตล่าง (lower bound)
3.ค่าสูงสุด เรียกว่า ขอบเขตบน (upper bound)

ขนาดของ index แต่ละตัว ของ Array หาได้จาก
(ขนาดของ subscript = upper bound – lower bound + 1)
จํานวนสมาชิกหรือขนาดของอะเรย์ n มิติ หาได้จาก
(ขนาดของอะเรย์ = ผลคูณของขนาดของsubscript แต่ละตัว)

อะเรย์ 1 มิติ
อะเรย์ 2 มิติ

รูปแบบของอะเรย์ 1มิติ
data-type array-name[expression]

data-type คือ ประเภทของข้อมูลอะเรย์ เช่น inchar float
array-name คือ ชื่อของอะเรย์
expression คือ นิพจน์จำนวนเต็มซึ่งระบุจำนวนสมาชิกของอะเรย์

ตัวอย่าง char a[4]; int num[10];

การประกาศอาร์กิวเมนต์ในฟังก์ชันเป็นอะเรย์

1. มีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

2. ไม่ต้องมีการประกาศขนาดของอะเรย์ที่ทำหน้าที่ในการรับค่า

3. ตัวแปรที่ทำหน้าที่รับค่าถูกกำหนดเป็นพอยน์เตอร์

รูปแบบของอะเรย์ 2 มิติ

type array-name[n] [m];

type หมายถึง ชนิดของตัวแปรที่ต้องการประกาศเป็นอะเรย์

array-name หมายถึง ชื่อของตัวแปรที่ต้องการประกาศเป็นอะเรย์

n หมายถึง ตัวเลขที่แสดงตำแหน่งของแถว

m หมายถึง ตัวเลขที่แสดงตำแหน่งของคอลัมน์

ตัวอย่าง

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

ตัวอย่าง

กำหนดค่าเริ่มต้นให้ int a[2][3]

int a[2][3] = {1,2,3,4,5,6}; หรือ

int a[2][3] = {{1,2,3},{4,5,6}}; หรือ

int a[][3] = {{1,2,3},{4,5,6}};

Record or Structure

Structure คือ โครงสร้างที่สมาชิกแต่ละตัวมีประเภทข้อมูลแตกต่างกันได้ โดยที่ใน structure อาจมีสมาชิกเป็นจํานวนเต็ม ทศนิยม อักขระ อะเรย์หรือพอยเตอร์ หรือแม้แต่ structure ด้วยกันก็ได้

struct เป็นคําหลักที่ต้องมีเสมอ

struc-nameชื่อกลุ่ม structure

type ชนิดของตัวแปรที่อยู่ในกลุ่ม structure

name-n ชื่อของตัวแปรที่อยู่ในกลุ่ม structure

struc-variable ชื่อตัวแปรชนิดโครงสร้าง

คือ ตัวแปรที่มีโครงสร้าง เหมือนกับที่ประกาศไว้ในชื่อของกลุ่ม structure อาจมีหรือไม่มีก็ได้ถ้ามีมากกว่า 1 ชื่อ แยกกันด้วยเครื่องหมายคอมม่า (,)

การผ่าน structure ให้ฟังก์ชัน ประเภทของการส่งผ่าน structure ให้ฟังก์ชันนั้น มี่ 2 ประเภท คือ

1. ส่งสมาชิกแต่ละตัวของ structure
2. ส่งทั้ง structure

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

2. ส่งผ่านทั้ง structure ให้กับฟังก์ชันจะส่งผ่านในลักษณะของพอยน์เตอร์ไปยัง structure โดยหลักการจะเหมือนกับการส่งผ่านอะเรย์ไปให้ฟังก์ชัน ซึ่งเป็นลักษณะที่เรียกว่า Pass by reference

ส่งงาน

struct notebook
{

char brand[30];

char series[20];

int price;

char cpu[30];

char ram[30];

float lcd;

int hdd;

char cd[10];

}product={"Acer","4935G-742G32Mn/C011",27900, "CORE 2 Duo 2.13 GHz.","2048/667",14.1,320,"DVD-RW"};

จากด้านบนกำหนดให้ notebook เป็นชื่อ structureโดยมีตัวแปร char brand[30] , char series[20] , int price , char cpu[30] , char ram[30] , float lcd , int hdd , char cd[10] โดยมี product เป็นตัวแปรชนิดโครงสร้างข้อมูล ชนิดเดียวกับ notebook

brand[30] = Acer

series[20] = 4935G-742G32Mn/C011

price = 27900

cpu[30] = CORE 2 Duo 2.13 GHz .

ram[30] = 2048/667

lcd = 14.1

hdd = 320

cd[10] = DVD-RW

ประวัติ

นาวสาว ขนิษฐา คล้ายมณี รหัส 50172792026 Miss Khanitta Klaimanee หลักสูตร บริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัการ หมาวิทยาลัยราชภัฏสวนดุสิต Email: u50172792026@gmail.com