สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การ
เพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack) และ ลักษณะที่สำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การทำงานของสแตกจะประกอบด้วยกระบวนการ 3
กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้
push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
ในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ
ตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็
สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับ
ตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าส
แตกเต็ม (Stack Overflow) ก็จะไม่สามารถ
เพิ่มข้อมูลเข้าไปในสแตกได้อีก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
เช่น ต้องการนำข้อมูลออกจากสแตก sไปไว้ที่ตัวแปร i
จะได้ i = pop (s)การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิก
เพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง
(Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย
แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำ
การ pop สแตก จะทำให้ เกิดความ
ผิดพลาดที่เรียกว่า Stack Underflow
เพราะฉะนั้นก่อนนำข้อมูลออกจากส
แตกจะต้องตรวจสอบ ก่อนว่าสแตกว่าง
หรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้
และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของ
ข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2
ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack 5. Empty Stack
2. Push Stack 6. Full Stack
3. Pop Stack 7. Stack Count
4. Stack Top 8. Destroy Stack
1. Create Stack
จัดสรรหน่วยความจำให้แก่ Head Node
และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack
การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack
การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top
เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการ
ลบข้อมูลออกจากสแตก
5.Empty Stack
เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาด
ในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack
เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความ
ผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count
เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack
เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบ
กับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว
ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรใน
นิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตก
แต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก
นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop
วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก
ตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
วันอังคารที่ 18 สิงหาคม พ.ศ. 2552
วันจันทร์ที่ 3 สิงหาคม พ.ศ. 2552
DTS05-28-07-2552
Linked List
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
1.Head Structrue จะประกอบไปด้วย3ส่วน ได้แก่ จำนวนโหนดในลิสต์(count) พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง(pos) คือ รายการเก็บข้อมูลปัจจุบันที่มีการท่องเข้าไปในลิสต์แทนด้วยpos และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์(head)
2.Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป ประกอบไปด้วย 2 ฟิลด์ ฟิลด์แรกเก็บในส่วนของข็อมูล ฟิลด์ที่ 2 เก็บส่วนของการเชื่อโยง ก็จะใช้พอยเตอร์เป็นตัวเชื่อมไปยังโหนดอื่นๆ
กระบวนงานและฟังชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่างผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Note การแทรกโหนดคือการเพิ่มสมาชิกใหม่ลงในรายการ เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการกระบวนนำเข้า ลิสต์ ข้อมูล และตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Noteหน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ ในการลบโหนดโดยจะทำการลบทั้งโหนดและข็อมูลที่ไมต้องการออกไป หลักง่ายๆ ด้วยการเปลี่ยนลิงค์ของโหนดก่อนหน้าโหนดที่ต้องการลบให้ชี้ไปยังลิงค์ของโหนดที่ต้องการลบ และคืนค่าของโหนดที่ต้องการลบแก่หน่วยความจำไปข้อมูลนำเข้า ข้อมูลและตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search Iist ในการ Search ต้องมี Conditionหน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverseหน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์,คำนวนค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Nodeการแสดงขอมูลในโหนดหน้าที่ หาตำแหน่งของข้อมูลจากลิสต์ข้อมูลนำข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์ หากต้องการนำข้อมูลในโหนดขึ้นมาแสดง เพียงทราบถึงตำแหน่งของลิสต์ที่จัดเก็บข้อมูล ก็สามารถนำข้อมูลนั้นๆ มาแสดงได้
7. ฟังก์ชั่น Emptylistหน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง Count= ถ้าไม่เท่า Count# ตรวจสอบโดยการกำหนดวนลูบค่าหากตรวจสอบว่าไม่มีข้อมูลกำหนดค่าเป็นจริง
8. ฟังก์ชั่น Fulllist การตรวจสอบลิสต์เต็มหน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ ตรวจสอบว่าลิสต์นั้นเต็มหรือไม่ มีพื้นที่ว่างในหน่วยความจำสำหรับลิสต์หรือไม่ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list countการนับจำนวนลิสต์ทำใหทราบว่าในโครงสร้างของลิสต์ปัจจุบันมีจำนวนลิสต์อยู่เท่าใดและสามารถตรวจสอบได้จากหนดต้นลิสต์ เนื่องจากเก็บค่าไว้ที่ countหน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน Destroy listการยกเลิกลิสต์ลบแล้วก็ต้องคืนค่าให้หน่วยความจำเพื่อไปใช้งานอื่นต่อไปหน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
1.Head Structrue จะประกอบไปด้วย3ส่วน ได้แก่ จำนวนโหนดในลิสต์(count) พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง(pos) คือ รายการเก็บข้อมูลปัจจุบันที่มีการท่องเข้าไปในลิสต์แทนด้วยpos และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์(head)
2.Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป ประกอบไปด้วย 2 ฟิลด์ ฟิลด์แรกเก็บในส่วนของข็อมูล ฟิลด์ที่ 2 เก็บส่วนของการเชื่อโยง ก็จะใช้พอยเตอร์เป็นตัวเชื่อมไปยังโหนดอื่นๆ
กระบวนงานและฟังชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create Listหน้าที่ สร้างลิสต์ว่างผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Note การแทรกโหนดคือการเพิ่มสมาชิกใหม่ลงในรายการ เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการกระบวนนำเข้า ลิสต์ ข้อมูล และตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Noteหน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ ในการลบโหนดโดยจะทำการลบทั้งโหนดและข็อมูลที่ไมต้องการออกไป หลักง่ายๆ ด้วยการเปลี่ยนลิงค์ของโหนดก่อนหน้าโหนดที่ต้องการลบให้ชี้ไปยังลิงค์ของโหนดที่ต้องการลบ และคืนค่าของโหนดที่ต้องการลบแก่หน่วยความจำไปข้อมูลนำเข้า ข้อมูลและตำแหน่งผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search Iist ในการ Search ต้องมี Conditionหน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverseหน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์,คำนวนค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Nodeการแสดงขอมูลในโหนดหน้าที่ หาตำแหน่งของข้อมูลจากลิสต์ข้อมูลนำข้าลิสต์ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์ หากต้องการนำข้อมูลในโหนดขึ้นมาแสดง เพียงทราบถึงตำแหน่งของลิสต์ที่จัดเก็บข้อมูล ก็สามารถนำข้อมูลนั้นๆ มาแสดงได้
7. ฟังก์ชั่น Emptylistหน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้าลิสต์ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง Count= ถ้าไม่เท่า Count# ตรวจสอบโดยการกำหนดวนลูบค่าหากตรวจสอบว่าไม่มีข้อมูลกำหนดค่าเป็นจริง
8. ฟังก์ชั่น Fulllist การตรวจสอบลิสต์เต็มหน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ ตรวจสอบว่าลิสต์นั้นเต็มหรือไม่ มีพื้นที่ว่างในหน่วยความจำสำหรับลิสต์หรือไม่ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list countการนับจำนวนลิสต์ทำใหทราบว่าในโครงสร้างของลิสต์ปัจจุบันมีจำนวนลิสต์อยู่เท่าใดและสามารถตรวจสอบได้จากหนดต้นลิสต์ เนื่องจากเก็บค่าไว้ที่ countหน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน Destroy listการยกเลิกลิสต์ลบแล้วก็ต้องคืนค่าให้หน่วยความจำเพื่อไปใช้งานอื่นต่อไปหน้าที่ ทำลายลิสต์ข้อมูลนำเข้า ลิสต์ผลลัพธ์ ไม่มีลิสต์
สมัครสมาชิก:
ความคิดเห็น (Atom)