เรื่อง Queue
คิว Queue เป็นโครงสร้างข้อมูลแบบเชิงเส้นซึ่งการเพิ่มข้อมุลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่า
ส่วนท้ายหรือเรียร์ (rear)และการนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
การใส่สมาชิกใหม่ลงในคิวเรียกว่า Enqueue ซึ่งมีรูปแบบคือ
enqueue หมายถึง การใส่ข้อมูล newElementลงไปที่ส่วนเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่า Dequeue หมายถึง การนำข้อมูลออกจากส่วนหน้าของคิวและให้ ข้อมุลนั้นกับ element
การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะเรียกว่า Queue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของคิว
การแทนที่ข้อมูลของคิวสามารถทำได้ 2 วิธี คือ
1.การแทนที่ข้อมุลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ
1.Head Node
จะประกอบไปด้วย 3 ส่วนคือพอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
2.Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว
การดำเนินการเกี่ยวกับคิว ได้แก่
1.Create Queue คือ จัดสรรหน่อยความจำให้แก่ Head Node และให้ค่า ponter ทั้ง 2 ตัวมีค่าเป็น null
และจำนวนสมาชิกเป็น 0
2.Enqueue คือ การเพื่มข้อมูลเข้าไปในคิว
3.Dequeue คือ การนำข้อมุลออกจากคิว
4.Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5.Queue Rear คือ เป็นการนำข้อมุลที่อยุ่ส่วนท้ายของคิวมาแสดง
6.Empty Queue คือ เป็นการตรวจสอบว่าคิวว่างหรือไม่
7.Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8.Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9.Destroy Queue คือ เป็นการลบข้อมุลทั้งหมดที่อยู่ในคิว
การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายามนำเข้าจะให้เกิด
ความผิดพลาดที่เรียกว่า Overflow
การนำข้อมุลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ ถ้าพยายามจะทำให้เกิด
ความผิดพลาดที่เรียกว่า underflow
วันอาทิตย์ที่ 23 สิงหาคม พ.ศ. 2552
วันพุธที่ 5 สิงหาคม พ.ศ. 2552
iostream
การนับจำนวนตัวอักษร
#include "iostream"
#include "conio.h"
using namespace std;
int main(){
char chr;
int count = 0;
cin>>chr;
while(true){
if(chr == '#')
break;
count++;
cin>>chr;
}
cout<<"total characher is : "<"count<"endl;
getch();
return 0;}
#include "iostream"
#include "conio.h"
using namespace std;
int main(){
char chr;
int count = 0;
cin>>chr;
while(true){
if(chr == '#')
break;
count++;
cin>>chr;
}
cout<<"total characher is : "<"count<"endl;
getch();
return 0;}
DTS06-04-08-2552
(Stack)
โครงสร้างสแตก (stack structure)
สแตก เป็นโครงสร้างข้อมูลอีกรูปแบบหนึ่งที่มีลักษณะของการจัดเก็บข้อมูลที่สามารถจัดเก็บได้แบบทั้งเรคอร์ด อาร์เรย์ หรือการจัดเก็บในลักษณะลิงค์ลิสต์ แต่โดยรูปแบบของการทำงานนั้นจะเป็นเหมือนการจัดเก็บหรือบันทึกสมาชิกในลักษณะของการพักไว้ สแตก เป็นโครงสร้างที่ถูกออกแบบมาให้มีลักษณะเป็นเชิงเส้น (linear list) สามารถที่จะทำการลบหรือเพิ่มจำนวนสมาชิกเข้ามาในโครงสร้างได้
Last In First Out : LIFO หมายถึงข้อมูลที่เข้ามาในลิสต์เป็นลำดับสุดท้าย จะถูกนำออกจากลิสต์เป็นอันดับแรก ตัวอย่างได้แก่การนำชั้นของปิ่นโตเข้าและออกจากเถาปิ่นโต พื้นฐานการดำเนินการกับสแตก
1.Push หรือการนำเข้าข้อมูล เป็นการดำเนินการในลักษณะของการเพิ่มข้อมูลในสแตกกรณีที่ไม่มีข้อมูลใดอยู่ก็จะ push เข้าไปตำแหน่งแรก ซึ่งถือว่าเป็นตำแหน่ง top แต่ถ้าหากนำข้อมูล push เข้ามาอีกก็จะดำเนินการจัดลงในตำแหน่งต่อจาก top และปรับค่า top มาอยู่ที่ตำแหน่งข้อมูลที่ push เข้ามาใหม่ จะต้องระวังปัญหา stack over flow คือไม่มีพื้นที่ว่างสำหรับการเพิ่มข้อมูลเข้าไปใน สแตก หรือ สแตก เต็ม
2.Pop หรือการดึงข้อมูลออก การดึงออกข้อมูล คือการนำเอาข้อมูลออกจากสแตก ซึ่งการดำเนินการก็จะต้องดำเนินการในตำแหน่ง top กรณีของการ pop ก็จะต้องตวรจสอบด้วยว่า หากไม่มีข้อมูลภายในสแตกแล้วยังมีการเรียก pop ข้อมูลอีกจะทำให้เกิดข้อผิพลาดที่เรียกว่า stack under flow
3. Top หรือตำแหน่งบนสุด ตำแหน่งบนสุดนั้นใช้ top เป็นตัวกำกับ ซึ่งบอกให้ทราบว่าหากต้องการ pop หรือ push ข้อมูลก็สามารถทำได้ ณ ตำแหน่งนี้ โดยลักษณะการดำเนินการของ top เป็นเพียงสิ่งที่บอกตำแหน่งของข้อมูลท่อยู่บนสุดเท่านั้น หากมีการ push ข้อมูลตำแหน่งของ top ก็จะชี้ไปค่าตำแหน่งสูงสุดใหม่ หรือ หากมีการ pop ข้อมูลออกไป top ก็ไม่ใช่ตัวลบค่า แต่จะเป็นการคืนค่าและลดตำแหน่งลงมา ซึ่งtop จะเกิดความผิดพลาดกรณีเดียวกันกับ pop คือ Underflow เมื่อ สแตกนั้นเกิดการว่าง
โครงสร้างของการแทนสแตกด้วยอาร์เรย์
การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด
Operations พื้นฐานของ Stack ที่สร้างด้วย Linked list
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 ให้ระบบ
>การประยุกต์ใช้งานสแตกในการแปลงรูปนิพจน์ทางคณิตศาสตร์
1.รูปแบบนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
1. นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่กึ่งกลางตัวถูกดำเนินการ (operand)
2. นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหลังตัวถูกดำเนินการ (operand)
3. นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหน้าตัวถูกดำเนินการ (operand)
เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^
ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C D ….. หรือตัวแปรอื่น
รูปแบบนิพจน์ของ infix จะเป็นลักษณะของนิพจน์ที่ใช้งานกันทั่วไป เช่น a + b, A*B ซึ่งมีการนำเครื่องหมายการดำเนินการไว้ตรงกลาง นิพจน์ posfix เป็นนิพจน์ที่มีการจัดรูปแบบของการคำนวณโดยเอาเครื่องหมายดำเนินการไว้หลังตัวถูกดำเนินการเพื่อให้ระบบอ่านตัวถูกดำเนินการก่อนแล้วจึงทราบวิธีการคำนวณ เช่น AB + และนิพจน์ prefix เป็นนิพจน์ที่นำเครื่องหมายสำหรับการดำเนินการ วางไว้ด้านหน้าก่อนตัวถูกดำเนินการ เช่น + AB
Prefix : +AB
Infix : A+B
Posfix : AB+
2.การแปลงนิพจน์ infix เป็น posfix สำหรับการดำเนินการด้านการคำนวณนั้น ในระบบคอมพิวเตอร์ไม่สามารถที่จะจัดลำดับของการคำนวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ infix หรือ prefix เสียก่อน โดยลักษณะของการแปลงนิพจน์จะใช้การเปรียบเทียบความสำคัญของตัวดำเนินการ เครื่องหมายในการคำนวณทั้ง 5 ตัว และหลักการอัลกอริทึมของการแปลงนิพจน์
วิธีการเปลี่ยน Infix เป็น Postfix
•Algorithm การเปลี่ยน Infix เป็น Postfix
• ให้ EXP เป็นสมการคณิตศาสตร์ที่เป็น Infix และ Stack เป็น stack ใด ๆ NEXP เป็นสมการที่เป็น Postfix
•1. ใส่ “(“ เข้าไปใน Stack
•2. อ่าน EXP จากซ้ายไปขวา
2.1 ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ใส่เข้าไปใน NEXP
2.2 ถ้าพบ “(“ ให้ push ใส่ stack
2.3 ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ทำดังนี้ - ให้ pop ตัวดำเนินการ ทุกตัวที่มีลำดับความสำคัญกว่าตัวดำเนินการที่พบใน 2.3 ออกมาใส่ใน NEXP ให้หมด - นำตัวดำเนินการที่พบใน
2.3 push เข้าใน stack แทนที่
2.4 ถ้าพบ “)” ให้ทำดังนี้ • - ให้ push ตัวดำเนินการ ทุกตัวมาใส่ไว้ใน NEXP ให้หมดจนพบ “(“ • - push “(“ ทิ้ง
3. จบการทำงาน
โครงสร้างสแตก (stack structure)
สแตก เป็นโครงสร้างข้อมูลอีกรูปแบบหนึ่งที่มีลักษณะของการจัดเก็บข้อมูลที่สามารถจัดเก็บได้แบบทั้งเรคอร์ด อาร์เรย์ หรือการจัดเก็บในลักษณะลิงค์ลิสต์ แต่โดยรูปแบบของการทำงานนั้นจะเป็นเหมือนการจัดเก็บหรือบันทึกสมาชิกในลักษณะของการพักไว้ สแตก เป็นโครงสร้างที่ถูกออกแบบมาให้มีลักษณะเป็นเชิงเส้น (linear list) สามารถที่จะทำการลบหรือเพิ่มจำนวนสมาชิกเข้ามาในโครงสร้างได้
Last In First Out : LIFO หมายถึงข้อมูลที่เข้ามาในลิสต์เป็นลำดับสุดท้าย จะถูกนำออกจากลิสต์เป็นอันดับแรก ตัวอย่างได้แก่การนำชั้นของปิ่นโตเข้าและออกจากเถาปิ่นโต พื้นฐานการดำเนินการกับสแตก
1.Push หรือการนำเข้าข้อมูล เป็นการดำเนินการในลักษณะของการเพิ่มข้อมูลในสแตกกรณีที่ไม่มีข้อมูลใดอยู่ก็จะ push เข้าไปตำแหน่งแรก ซึ่งถือว่าเป็นตำแหน่ง top แต่ถ้าหากนำข้อมูล push เข้ามาอีกก็จะดำเนินการจัดลงในตำแหน่งต่อจาก top และปรับค่า top มาอยู่ที่ตำแหน่งข้อมูลที่ push เข้ามาใหม่ จะต้องระวังปัญหา stack over flow คือไม่มีพื้นที่ว่างสำหรับการเพิ่มข้อมูลเข้าไปใน สแตก หรือ สแตก เต็ม
2.Pop หรือการดึงข้อมูลออก การดึงออกข้อมูล คือการนำเอาข้อมูลออกจากสแตก ซึ่งการดำเนินการก็จะต้องดำเนินการในตำแหน่ง top กรณีของการ pop ก็จะต้องตวรจสอบด้วยว่า หากไม่มีข้อมูลภายในสแตกแล้วยังมีการเรียก pop ข้อมูลอีกจะทำให้เกิดข้อผิพลาดที่เรียกว่า stack under flow
3. Top หรือตำแหน่งบนสุด ตำแหน่งบนสุดนั้นใช้ top เป็นตัวกำกับ ซึ่งบอกให้ทราบว่าหากต้องการ pop หรือ push ข้อมูลก็สามารถทำได้ ณ ตำแหน่งนี้ โดยลักษณะการดำเนินการของ top เป็นเพียงสิ่งที่บอกตำแหน่งของข้อมูลท่อยู่บนสุดเท่านั้น หากมีการ push ข้อมูลตำแหน่งของ top ก็จะชี้ไปค่าตำแหน่งสูงสุดใหม่ หรือ หากมีการ pop ข้อมูลออกไป top ก็ไม่ใช่ตัวลบค่า แต่จะเป็นการคืนค่าและลดตำแหน่งลงมา ซึ่งtop จะเกิดความผิดพลาดกรณีเดียวกันกับ pop คือ Underflow เมื่อ สแตกนั้นเกิดการว่าง
โครงสร้างของการแทนสแตกด้วยอาร์เรย์
การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด
Operations พื้นฐานของ Stack ที่สร้างด้วย Linked list
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 ให้ระบบ
>การประยุกต์ใช้งานสแตกในการแปลงรูปนิพจน์ทางคณิตศาสตร์
1.รูปแบบนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
1. นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่กึ่งกลางตัวถูกดำเนินการ (operand)
2. นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหลังตัวถูกดำเนินการ (operand)
3. นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหน้าตัวถูกดำเนินการ (operand)
เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^
ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C D ….. หรือตัวแปรอื่น
รูปแบบนิพจน์ของ infix จะเป็นลักษณะของนิพจน์ที่ใช้งานกันทั่วไป เช่น a + b, A*B ซึ่งมีการนำเครื่องหมายการดำเนินการไว้ตรงกลาง นิพจน์ posfix เป็นนิพจน์ที่มีการจัดรูปแบบของการคำนวณโดยเอาเครื่องหมายดำเนินการไว้หลังตัวถูกดำเนินการเพื่อให้ระบบอ่านตัวถูกดำเนินการก่อนแล้วจึงทราบวิธีการคำนวณ เช่น AB + และนิพจน์ prefix เป็นนิพจน์ที่นำเครื่องหมายสำหรับการดำเนินการ วางไว้ด้านหน้าก่อนตัวถูกดำเนินการ เช่น + AB
Prefix : +AB
Infix : A+B
Posfix : AB+
2.การแปลงนิพจน์ infix เป็น posfix สำหรับการดำเนินการด้านการคำนวณนั้น ในระบบคอมพิวเตอร์ไม่สามารถที่จะจัดลำดับของการคำนวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ infix หรือ prefix เสียก่อน โดยลักษณะของการแปลงนิพจน์จะใช้การเปรียบเทียบความสำคัญของตัวดำเนินการ เครื่องหมายในการคำนวณทั้ง 5 ตัว และหลักการอัลกอริทึมของการแปลงนิพจน์
วิธีการเปลี่ยน Infix เป็น Postfix
•Algorithm การเปลี่ยน Infix เป็น Postfix
• ให้ EXP เป็นสมการคณิตศาสตร์ที่เป็น Infix และ Stack เป็น stack ใด ๆ NEXP เป็นสมการที่เป็น Postfix
•1. ใส่ “(“ เข้าไปใน Stack
•2. อ่าน EXP จากซ้ายไปขวา
2.1 ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ใส่เข้าไปใน NEXP
2.2 ถ้าพบ “(“ ให้ push ใส่ stack
2.3 ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ทำดังนี้ - ให้ pop ตัวดำเนินการ ทุกตัวที่มีลำดับความสำคัญกว่าตัวดำเนินการที่พบใน 2.3 ออกมาใส่ใน NEXP ให้หมด - นำตัวดำเนินการที่พบใน
2.3 push เข้าใน stack แทนที่
2.4 ถ้าพบ “)” ให้ทำดังนี้ • - ให้ push ตัวดำเนินการ ทุกตัวมาใส่ไว้ใน NEXP ให้หมดจนพบ “(“ • - push “(“ ทิ้ง
3. จบการทำงาน
วันจันทร์ที่ 3 สิงหาคม พ.ศ. 2552
DTS05-28-07-2552
Linked List
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2ประเภทคือ
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การยกเลิกลิสต์ลบแล้วก็ต้องคืนค่าให้หน่วยความจำเพื่อไปใช้งานอื่นต่อไป
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์
2. Double Linked List ลิงค์ลิสต์คู่ เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูล ก่อนหน้า (backward pointer:B) และตัวชี้ข้อมูลถัดไป (forward pointer :F)
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2ประเภทคือ
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การยกเลิกลิสต์ลบแล้วก็ต้องคืนค่าให้หน่วยความจำเพื่อไปใช้งานอื่นต่อไป
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์
2. Double Linked List ลิงค์ลิสต์คู่ เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูล ก่อนหน้า (backward pointer:B) และตัวชี้ข้อมูลถัดไป (forward pointer :F)
สมัครสมาชิก:
บทความ (Atom)