การบ้าน stdio.h และ iostream.h

05-22-07-2552

สรุปบทเรียน Linked List,Stack
สแตค (Stack)สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก

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

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

Empty Stackเป็นการตรวจสอบการว่างของสแตกเพื่อไม่ให้เกิดการผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack UnderflowFull

Stackเป็นการตรวจสอบว่าสแตกเต็มหรือไม่เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลสแตกที่เรียกว่า Stack Overflow

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

ตัวอย่างของสแตก คือ "หลอดด้าย" หลอดด้ายที่เป็นม้วนจะมีการพันด้ายเส้นแรกจากด้านใน แล้วเวลาใช้จะต้องใช้เส้นที่อยู่หน้าสุดคือเส้นที่ม้วนเข้าไปที่หลังออกมาใช้ก่อน

04-15-07-2552

Linked List
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ
ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้นตรง (linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้
ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node)
ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ
เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link)
หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป
ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือสัญลักษณ์ ^


โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ1. Head Structure จะประกอบไปด้วย 3 ส่วน

ได้แก่ จำนวนโหนดในลิสต์ (Count)
พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง (Pos)
และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูล แรกของลิสต์ (Head)

2. Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

dts01-07-52

pointer

เป็นตัวแปรชนิดหนึ่งที่ทำหน้าที่เก็บตำแหน่งที่อยู่ (Address) ของตัวแปรที่อยู่ในหน่วยความจำ

การประกาศตัวแปรชนิดของตัวแปรพอยน์เตอร์

รูปแบบ

type *variable-name

type หมายถึง ชนิดของตัวแปร

* หมายถึง เป็นเครื่องหมายที่แสดงว่า ตัวแปรที่ตามหลังเครื่องหมายนี้เป็นตัวแปรพอยน์เตอร์

variable-name เป็นชื่อของตัวแปรที่ต้องการประกาศว่าเป็นชนิดของพอยน์เตอร์

เครื่องหมายที่ใช้ทำงานกับตัวแปรพอยน์เตอร์

1. เครื่องหมาย & เป็นเครื่องมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ชองตัวแปรที่เก็บไว้ในหน่วยความจำออกมาใช้

2. เครื่องหมาย * มีการใช้งาน 2 ลักษณะคือ

- ใช้ในการประกาศ parameter ว่าเป็นตัวแปรแบบพอยน์เตอร์ ว่าเป็นตัวแปรพอยน์เตอร์

- ใช้เป็น dereferencing operator จะใช้เมื่อต้องการนำค่าที

อยู่ในตำแหน่งทีตัวแปรพอยน์เตอร์นั้นชี้อยู่ออกมาแสดง

การใช้ตัวแปรพอยน์เตอร์กับอะเรย์

ตัวแปรพอยน์เตอร์จะใช้อ้างถึงค่าที่เก็บไว้ในตัวแปรชุดได้ ดังนี้

char str[80],*pl;

pl=str;

บรรทัดที่1 เป็นการประกาศว่า str เป็นตัวแปรชุด ชนิด charater 1 มิติ มีขนาดสมาชิก 80 สมาชิกและ pl เป็นตัวพอยน์เตอร์

บรรทัดที่2 เป้นการอ้างอิงถึงข้อมูลที่เก็บในตัวแปรชุด str โดยการนำตำแหน่งที่อยู่ของตัวแปร str[0] ซึ่งเป็นสมาชิกตัวแรกไปเก็บไว้ใน ตัวแปรพอยน์เตอร์ pl