DTS 08-26-08-2552

ทรี (Tree)

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงานต่างๆ อย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมู

- โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่ เรียกว่า โหนดราก Root Node จากรูป คือ โหนด A
- โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่ระดับหนึ่ง เรียกว่า Child Node หรือ โหนดลูก จากรูป B , C , D และ E เป็น โหนดลูกของ A
- โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลายๆ โหนด เรียกโหนดดังกล่าวว่า Parent Node หรือโหนดพ่อแม่ โหนด B ที่เป็นโหนดลูกของโหนด A ก็สามารถแตกออกเป็นโหนดย่อยๆ ได้แก่ F และ G ดังนั้น B จึงเป็นโหนดพ่อแม่ของ F และ G ในทำนองเดียวกัน A ก็เป็นโหนด พ่อแม่ของ B , C , D และ E
- เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง (Branch or Edge) เป็นเส้นที่เชื่อมต่อระหว่างโหนดพ่อแม่กับโหนดลูก
- โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน เรียกว่า Siblings หรือโหนดพี่น้อง คือ โหนดที่มีพ่อแม่เดียวกัน เช่น B , C , D , E เป็นโหนดพี่น้องกันเพราะมีโหนดพ่อแม่เดียวกัน คือ โหนด A และ F และ G เป็นโหนดพี่น้องกันโดยมี B เป็นโหนดพ่อแม่
- โหนดที่ไม่มีลูก เรียกว่า Leaf Node จากรูปโหนดที่ไม่มีโหนดลูก ได้แก่ F G H I J K L M

นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด loop ในโครงสร้าง โหนดสองโหนดใดๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรี ประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ เรียกว่านัลทรี (Null Tree) และถ้ามีโหนหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)

นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออก หรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่างๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน เช่น ไปทางขวา ไปทางซ้าย เป็นต้น
3. ทรีคล้าย (Similar Tree) คือ ทรที่มีโครงสร้าเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนดนั้นๆ
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหน ดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง หรือความ ลึก

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

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์การแปลงทรีทั่วไปให้เป็นไบนารีทรีขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดั้งต่อไปนี้

1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จบให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆโหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้น ตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)
ทรีย่อยทางซ้าย (แทนด้วย L)
ทรีย่อยทางขวา (แทนด้วย R)

วิธีการท่องไปในทรีมี 6 วิธี แต่นิยมใช้กันมากคือ NLR , LNR , LRN

1. วิธี NLR ในลักษณะการเข้าถึงจะเริ่มต้นจากจุดแรกคือ N จากนั้นจึงเข้าไปทรีย่อยด้านซ้ายและเข้าถึงทรีย่อยด้านขวา
2. วิธี LNR สำหรับการเข้าถึงแบบอินออร์เดอร์จะดำเนินการเข้าเยี่ยมทรีย่อยด้านซ้ายก่อน จากนั้นจึงเข้าเยี่ยม N และสิ้นสุดการเข้าเยี่ยมที่ทรีย่อยด้านขวา
3. วิธี LRN การประมวลผลของโพสออร์เดอร์ จะเริ่มต้นด้วยทรีย่อยด้านซ้ายจานั้นมาประมวลผลต่อที่ทรีย่อยด้านขวาและสิ้น สุดการประมวลผลที่ N

DTS 07-05-08-2552

Queue

คิวเป็นโครงสร้างข้อมูลแบบลำดับ (Sequential) ลักษณะของคิวเราสามารถพบได้ในชีวิตประจำวัน เช่น การเข้าแถวตามคิวเพื่อรอรับบริการต่างๆ ลำดับการสั่งพิมพ์งาน เป็นต้น ซึ่งจะเห็นได้ว่าลักษณะของการทำงานจะเป็นแบบใครมาเข้าคิวก่อน จะได้รับบริการก่อน เรียกได้ว่าเป็นลักษณะการทำงานแบบ FIFO (First In , First Out)

ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT

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

การเพิ่มข้อมูลเข้าไปในคิว

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

การนำข้อมูลออกจากคิว

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

คิวแบบวงกลม (Circular Queue)

คิวแบบวงกลมจะมีลักษณะเหมือนคิวธรรมดา คือ มีตัวชี้ FRONT และ REAR ที่แสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ โดย FRONT และ REAR จะมีการเลื่อนลำดับทุกครั้งเมื่อมีการนำข้อมูลเข้าและออกจากคิว แต่จะแตกต่างจากคิวธรรมดาก็คือ คิวธรรมดาเมื่อ REAR ชี้ที่ตำแหน่งสุดท้ายของคิว จะทำให้เพิ่มข้อมูลเข้าในคิวอีกเมื่อไม่ได้ เนื่องจาก ค่า REAR=MAX QUEUE ซึ่งแสดงว่าคิวนั้นเต็ม ไม่สามารถเพิ่มข้อมูลเข้าไปได้อีก ทั้งๆ ที่ยังมีเนื้อที่ของคิวเหลืออยู่ก็ตาม ทำให้การใช้เนื้อที่ของคิวไม่มีประสิทธิภาพ

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

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

DTS 06-29-07-2552

การแทนที่ข้อมูลของสแตกแบบอะเรย์

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ

1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data)และพอยเตอร์ ที่ชี้ไปยังข้อมูล

การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
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 เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก
8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก

การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์

รูปแบบนิพจน์ทางคณิตศาสตร์

• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)
มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้

เครื่องหมายบวก ( + ) , ลบ ( - )
เครื่องหมายคูณ ( * ) , หาร ( / )
เครื่องหมายวงเล็บเปิด (
เครื่องหมายวงเล็บปิด )

ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix

1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix

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

<เขียนโปรแกรมโดยใช้ stdio.h >

#include
void main()
{
char name[20];
char student_id[12];
char subjectiveness[50];
int score;
printf("Input name:");
scanf("%s",&name);
printf("Input sutudent id:");
scanf("%s",&student_id);
printf("Input subjectiveness:");
scanf("%s",&subjectiveness);
printf("Input score:");
scanf("%d",&score);
if(score>=0&&score<=100) { if(score>=80)
printf("score grade 4(A)",score);
else if(score>=75)
printf("score grade 3.5(B+)",score);
else if(score>=70)
printf("score grade 3(B)",score);
else if(score>=65)
printf("score grade 2.5(C+)",score);
else if(score>=60)
printf("score grade 2(C)",score);
else if(score>=55)
printf("score grade 1.5(D+)",score);
else if(score>=50)printf
("score grade 1(D)",score);
elseprintf("score grade 0(F)",score);
}
elseprintf("error!!!",score);
}



<เขียนโปรแกรมโดยใช้ iostream.h >

#include
void main()
{
char name[20];
char student_id[12];
char subjectiveness[50];
int score;
cout<<"Input name:";
cin>>name;
cout<<"Input sutudent id:";
cin>>student_id;
cout<<"Input subjectiveness:";
cin>>subjectiveness;
cout<<"Input score:";
cin>>score;
if(score>=0&&score<=100) { if(score>=80)
cout<<"score grade 4(A)";
else if(score>=75)
cout<<"score grade 3.5(B+)";
else if(score>=70)
cout<<"score grade 3(B)";
else if(score>=65)
cout<<"score grade 2.5(C+)";
else if(score>=60)
cout<<"score grade 2(C)";
else if(score>=55)
cout<<"score grade 1.5(D+)";
else if(score>=50)
cout<<"score grade 1(D)";
elsecout<<"score grade 0(F)";
}
elsecout<<"error!!!";
}

DTS 05-22-07-2552

Linked List แบบซับซ้อน

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

2.Double Linked List หมายถึง ลิงค์ลิสต์ที่ทุกโหนดสามารถวกกลับมาที่โหนดก่อนหน้าของตนเองได้ ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง

สแตค (Stack)

สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้

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

รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค

การเพิ่มข้อมูลลงในสแตค (pushing stack)

การเพิ่มข้อมูลลงในสแตคการเพิ่มข้อมูลลงในสแตค คือ การนำเข้ามูลเข้าสู่สแตคโดยทับข้อมูลที่อยู่บนสุดของสแตค ข้อมูลจะสามารถนำเข้าได้เรื่อยๆ จนกว่าสแตคจะเต็ม สมมติว่าสแตคจองเนื้อที่ไว้ N ตัว ถ้าหากค่า TOP เป็น 0 แสดงว่าสแตคว่าง หากค่า TOP = N แสดงว่าสแตคเต็ม (Stack Overflow) ไม่สามารถเพิ่มข้อมูลลงในสแตคได้อีก

จากรูปแสดง การ Push ข้อมูล ABC ลงในสแตคที่มีการจองเนื้อที่ไว้ N ตัว โดยมี TOP ชี้ข้อมูลตัวที่เข้ามาล่าสุด โดยค่าของ TOP จะเพิ่มขึ้นทุกครั้งเมื่อมีข้อมูลเข้ามาในสแตค

การดึงข้อมูลออกจากสแตค (popping stack)

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

Stack Top

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

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

DTS 04-15-07-2552

ลิงค์ลิสต์ (Linked List)

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

โครงสร้างข้อมูลแบบลิงค์ลิสต์ประกอบด้วย 2 ส่วน

1.Head Structure แบ่งเป็น 3 ส่วน

-count เป็นการนับจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น

-pos พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง

-head พอยเตอร์ที่ชี้ไปยังโหนดแรกของลิสต์

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

การเพิ่มข้อมูลลงไปในลิงค์ลิสต์

จากที่ Head Structure ในส่วนของ count จะมีค่าเป็น 0 นั้นหมายถึงในลิสต์นั้นยังไม่มีข้อมูลใดเลย ส่วน head จะมีเครื่องหมายกากบาท นั้นหมายถึงในลิสต์นั้นไม่มีการเชื่อมโยงไปยังข้อมูลแรก แต่ถ้าต้องการเพิ่มข้อมูลลงไปในลิสต์ Data Node ในส่วนของข้อมูล (Data)จะมีค่าเก็บอยู่ แล้ว count ก็จะเปลี่ยนค่าจาก 0 เป็น 1 คือ การบ่งบอกถึงจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น แล้ว head ก็จะชี้ไปยังข้อมูล (Data) ตัวแรกของลิสต์ ส่วนพอยเตอร์ที่ชี้ไปโหนดถัดไปจะเป็นเครื่องหมายกากบาทแทน

การลบข้อมูลในลิงค์ลิสต์

ถ้าต้องการลบข้อมูลตัวใดในลิสต์สามารถลบได้เลย แต่ต้องเปลี่ยน head เพื่อชี้ไปยังข้อมูลตัวแรกของลิสต์กรณีที่ลบข้อมูลตัวแรกออก แล้ว link คือ เมื่อลบข้อมูลตัวใดออกควรชี้ link ถัดไปให้ถูกต้องด้วย

กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน

1. กระบวนงาน Create List หน้าที่ สร้างลิสตว่าง ผลลัพธ์ ลิสต์ว่าง

2. กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต์ ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและ ตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

DTS 03-1-07-2552

pointer

ความหมายของพอยน์เตอร์

พอยน์เตอร์ (pointer) เป็นตัวแปรชนิดหนึ่งใช้เก็บตำแหน่งของข้อมูลในหน่วยความจำ โดยการเก็บตำแหน่งจะเก็บเฉพาะตำแหน่งแรกของข้อมูล

พอยน์เตอร์ มี 2 ประเภท คือ

1. direct pointer เป็นตัวแปรที่เก็บตำแหน่ง(address) ในหน่วยความจำ ของข้อมูล ตัวอย่าง เช่น ตัวแปรชื่อ x มีข้อมูลเป็น 120 ซึ่งถูกเก็บไว้ในหน่วยความจำที่ตำแหน่ง 5000 พอยน์เตอร์ ชื่อ ptr มีค่าที่เก็บไว้เป็น 5000

2. indirect pointer เป็นตัวแปรที่เก็บตำแหน่ง (address) ของพอยน์เตอร์ซึ่งเก็บตำแหน่งของข้อมูลของตัวแปร เช่น ตัวแปรชื่อ x มีข้อมูลเป็น 120 ซึ่งถูกเก็บไว้ในหน่วยความจำที่ตำแหน่ง 5000 พอยน์เตอร์ ชื่อ ptr มีค่าที่เก็บไว้เป็น 5000 และ พอยน์เตอร์ ชื่อ pptr เก็บตำแหน่งหน่วยความจำของ ptr ซึ่งมีค่า 3000 พอยน์เตอร์ pptr นี้อาจเรียกว่า pointer to pointer

การประกาศตัวแปรพอยน์เตอร์ (Declaration of Pointer Variables)

type *variable_name ;
หรือ type *variable_name1, *variable_name2,... ,*variable_nameN ;
โดย type คือ ชนิดของตัวแปร เช่น int ,float ,char ฯลฯ โดยต้องเป็นชนิดเดียวกับของตัวแปรหรือข้อมูลที่พอยน์เตอร์นั้นเก็บตำแหน่งที่อยู่

* เป็นเครื่องหมายที่ระบุว่าเป็นตัวแปรพอยน์เตอร์
variable_name1, variable_name2,..., variable_nameN ชื่อตัวแปรพอยน์ตัวที่ 1 ถึง ตัวสุดท้ายที่ประกาศในการประกาศครั้งนี้

ตัวอย่าง int *ptr1, *prt2; char *word, *str1;

การกำหนดตำแหน่งของข้อมูลให้ตัวแปรพอยน์เตอร์

การกำหนดตำแหน่งที่เก็บข้อมูลในหน่วยความจำของตัวแปรทำได้โดยใช้เครื่องหมาย & (ampersand) นำหน้าชื่อตัวแปร นำมากำหนดให้เป็นค่าของพอยน์เตอร์เช่น

int num1 = 120; /* ประกาศและกำหนดค่าให้แก่ตัวแปร ในที่นี้เป็นตัวแปร ชื่อ num1 เป็นประเภท int โดยมีค่า เป็น 120 */
int *ptr1; /* ประกาศตัวแปรพอยน์เตอร์ ในที่นี้เป็นประเภท int เพราะใช้เก็บตำแหน่งของตัวแปรประเภท int */
ptr1 = &num1; /* กำหนดค่าตำแหน่งของตัวแปรให้เป็นค่าของพอยน์เตอร์ */

พอยน์เตอร์และอาร์เรย์

พอยเตอร์สามารถกำหนดให้เป็นอารฺเรย์ได้ โดยในอาร์เรย์จะมีตัวแปร พอยเตอร์เหมือนตัวแปรอาเรย์ทั่วไป อาเรย์พอยเตอร์จะเก็บแอดเดรสของตัวแปรตามชนิดข้อมูลของตัวแปร ในการกำหนดอาเรย์ของ พอยเตอร์มีรูปแบบดังนี้
data type *pointer name[size];

พอยน์เตอร์ของพอยเตอร์

ตัวแปรพอยน์เตอร์อาจใช้เก็บค่าแอดเดรสของตัว แปรพอยเตอร์อื่น ซึ่งเก็บค่าแอดเดรสของตัวแปรหรือพอยเตอร์ตัวที่ 1 ชี้ไป แอดเดรสของพอยเตอร์ตัวที่ 2 ซึ่งพอยเตอร์ตัวที่ 2 ชี้ไปแอดเดรสตัวแปร

Set

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

1.set intersection

2.set union

3.set difference String

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

Dts 02-24-06-2552

สรุปบทเรียน

Array and Record

Array

ตัวแปรอาเรย์สามารถเก็บข้อมูลหลายๆข้อมูลไว้ได้โดยไม่ต้องใช้ตัวแปรหลายตัว เช่นถ้าต้องการเก็บอายุของเพื่อนทั้ง 20 คน ถ้าเราใช้ตัวแปรแบบ int เราจะต้องประกาศตัวแปร age1, age2, age3,.....,age20 ให้เป็นแบบ int ซึ่งเป็นการประกาศตัวแปรถึง 20 ตัวด้วยกัน แต่ถ้าใช้อาเรย์เราประกาศตัวแปร age ให้เป็นอาเรย์แบบ int เพียงตัวเดียวก็สามารถเก็บค่าทั้ง 20 ค่าได้แล้ว

อาเรย์ 1 มิติ(One-Dimensional Array)
เราสามารถสร้างตัวแปรอาเรย์ของข้อมูลชนิดต่างๆได้ไม่ว่าจะเป็นอาเรย์แบบ int, char, float ดังตัวอย่างต่อไปนี้void main(){int age [5];double grade [5];char s [5];....}จากตัวอย่างเป็นการประกาศตัวแปรชื่อ age ให้เป็นอาเรย์ของข้อมูลชนิด int ที่มีขนาดเท่ากับ 5 ดังนั้นตัวแปร age จะสามารถเก็บเลขจำนวนเต็มได้ถึง 5 จำนวน สำหรับตัวแปร grade ถูกประกาศเป็นอาเรย์ของข้อมูลชนิด double และมีขนาดเท่ากับ 5 เช่นเดียวกัน เราจึงสามารถเก็บเลขทศนิยมไว้ในตัวแปร grade ได้ 5 จำนวน และการประกาศตัวแปร s ให้เป็นอาเรย์ของข้อมูลชนิด char ที่มีขนาด 5 ตัวอักษร จึงเก็บตัวอักษรได้ 5 ตัวเมื่อเราประกาศตัวแปรอาเรย์ทั้ง 3 ตัวคือ age, grade และ s แล้ว ในหน่วยความจำจะมีการจองพื้นที่เอาไว้ตามจำนวนที่กำหนด โดยตัวแปร age และ grade นั้นจะมีการเตรียมพื้นที่ว่างในหน่วยความจำสำหรับเก็บค่าตัวแปรละ 5 ค่า และตัวแปร s ก็มีการเตรียมพื้นที่เอาไว้เก็บตัวอักษร 5 ตัวการนำค่าใส่ลงไปในตัวแปรอาเรย์ตัวแปรอาเรย์นั้นสามารถเก็บค่าได้หลายๆค่า โดยแต่ละค่าก็จะเหมือนกับเป็นตัวแปร 1 ตัว เช่นถ้าเราประกาศตัวแปร int age [5] ก็เหมือนกับว่าเรามีตัวแปร age ถึง 5 ตัว ซึ่งแต่ละตัวนี้เราเรียกว่าสมาชิกของอาเรย์ การอ้างถึงสมาชิกของอาเรย์จะต้องใช้หมายเลขลำดับ โดยเริ่มจาก 0,1,2,...ไปเรื่อยๆจนถึง” ขนาดของอาเรย์ลบด้วย 1” เช่นถ้าเราสร้างอาเรย์ int age [5] การอ้างถึงสมาชิกของอาเรย์จะใช้หมายเลข 0 ถึง 4 ถ้าเรานำเอาค่า 20, 21, 23, และ 26 มากำหนดให้กับสมาชิกลำดับที่ 0, 1, 2 และ 3 ของอาเรย์ age ตามลำดับ เราจะเขียนโปรแกรมดังนี้int age [5];age [0] = 20;age [1] = 21;age [2] = 23;age [3] = 26;จะเห็นว่าตัวแปร age เป็นอาเรย์แบบ int ซึ่งเก็บเลขจำนวนเต็มได้ 5 ค่า แต่จากตัวอย่างเรากำหนดค่าให้กับสมาชิกลำดับที่ 0 ถึง 3 โดยไม่ได้กำหนดค่าให้กับสมาชิกลำดับที่ 4 เพราะว่าการใส่ข้อมูลลงในอาเรย์นั้นไม่จำเป็นจะต้องใส่ทุกๆช่องให้ครบจึงจะ ใช้งานได้ ช่องใดไม่ได้ใส่ค่าลงไป มันก็ไม่เก็บค่าอะไรไว้จะเป็นช่องว่างๆไปโดยอัตโนมัติอาเรย์ของข้อมูลชนิด char คือตัวแปรสตริงตัวแปรอาเรย์ของข้อมูลชนิด char อีกนัยหนึ่งก็คือตัวแปรแบบข้อความหรือตัวแปรสตริง(String) ตัวแปรสตริงคือการนำเอาตัวแปรแบบ char มาเรียงต่อๆกัน ซึ่งตัวแปร char ที่เรียงต่อกันก็เรียกได้ว่าเป็นตัวแปรอาเรย์ของข้อมูลชนิด char นั่นเอง จึงสรุปได้ว่า ”สตริง” กับ “อาเรย์ของ ข้อมูลชนิด char” คือสิ่งเดียวกันตัวแปรอาเรย์ของข้อมูลชนิด char จะแตกต่างจากอาเรย์ของ int, double หรือแบบอื่นๆ เพราะว่าสมาชิกตัวสุดท้ายของอาเรย์แบบ char จะใช้เก็บรหัสสิ้นสุดข้อความ ด้วยเหตุนี้ถ้าเราประกาศตัวแปรอาเรย์แบบ char เพื่อเก็บข้อความ เราจะต้องประกาศอาเรย์ให้มีขนาดมากกว่าจำนวนตัวอักษรของข้อความที่ต้องการ เก็บอย่างน้อย 1 ตัวอักษรสมมติว่าเราประกาศตัวแปรอาเรย์แบบ char เพื่อที่จะเก็บคำว่า “Computer” ซึ่งมีทั้งหมด 8 ตัวอักษร เราจะต้องประกาศตัวแปรอาเรย์แบบ char ที่มีขนาด 9 ตัวอักษร นอกจากนี้การกำหนดค่าให้กับตัวแปรอาเรย์แบบ char หรือตัวแปรสตริงนี้ยังสามารถทำไปพร้อมกับการประกาศตัวแปรได้เลย ดังนี้char s[5] = “GIRL”;หรือchar s[5] = { ‘G’, ‘I’, ‘R’, ‘L’ }

อาเรย์ 2 มิติ (Two-Dimensional Array)
อาเรย์ 2 มิติจะเก็บข้อมูลไว้ในลักษณะของตาราง การสร้างอาเรย์ 2 มิตินั้นเราจะเขียนโค้ดภาษาซีดังนี้int a[3][3];int b[2][3];การนำค่าที่ต้องการเก็บในอาเรย์เราจะต้องอ้างถึงลำดับของสมาชิกช่องนั้นๆ ทั้งลำดับในแนวนอนและลำดับในแนวตั้ง หรือจะมองในลักษณะของคู่ลำดับก็ได้ดังรูปต่อไปนี้int a[3][3];a[0][0] a[1][0] a[2][0]a[0][1] a[1][1] a[2][1]a[0][2] a[1][2] a[2][2]จะเห็นว่าหมายเลขลำดับของอาเรย์ในแต่ละแนวเริ่มต้นจาก 0 จนถึง “ขนาดในแนวนั้นลบด้วย 1” เช่น ถ้าประกาศอาเรย์ 2 มิติขนาด 3x3 ลำดับในแนวนอนก็จะเริ่มจาก 0 ถึง 2 รวมทั้งหมด 3 ช่อง และในแนวตั้งก็จะเริ่มจาก 0 ถึง 2 รวมทั้งหมด 3 ช่องเช่นกัน

Structure

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

เราสามารถประกาศ Structure หนึ่งเป็นสมาชิกของอีก Structure ก็ได้แต่ต้องประกาศตัวที่จะนำไปใส่ไปไว้อีก Structure ก่อน

การบ้าน

#include
struct date{
int day;
int month;
int year;
};
struct ticket{
char name[20];
char last_name[20];
char telephone[15];
char place[30];
int seat;
float time[5];
float price;
struct date date1;
}ticket1;
void input_data()
{
printf("ticket data\n");
printf("day dd=");
scanf("%d",&ticket1.date1.day);
printf("month mm=");
scanf("%d",&ticket1.date1.month);
printf("year yyyy=");
scanf("%d",&ticket1.date1.year);
printf("Name =");
scanf("%s",&ticket1.name);
printf("Last name =");
scanf("%s",&ticket1.last_name);
printf("telephone=");
scanf("%s",&ticket1.telephone);
printf("place =");
scanf("%s",&ticket1.place);
printf("seat=");
scanf("%d",&ticket1.seat);
printf("time =");
scanf("%f",&ticket1.time);
printf("Price =");
scanf("%f",&ticket1.price);
}
void show_data()
{
printf("Display Data of ticket\n");
printf("Day=%d-%d-%d\n",ticket1.date1.day,ticket1.date1.month,ticket1.date1.year);
printf("name= %s Last Name= %s\n",ticket1.name,ticket1.last_name);
printf("telephone=%s\n",ticket1.telephone);
printf("place= %s\n",ticket1.place);
printf("seat=%d\n",ticket1.seat);
printf("time= %f\n",ticket1.time);
printf("price=%f\n",ticket1.price);
}
main()
{
input_data();
show_data();
}

VDO แนะนำตัว

ประวัติ

นางสาว จาริยา พิมพ์สอาด

Miss Jariya Pimsa-art

รหัสประจำตัว 50152792030

ชื่อเล่น น้ำ

งานอดิเรก : เล่น Internet , ฟังเพลง , ดูหนัง

วันเดือนปีเกิด : 11 พฤศจิกายน 2531

สถานภาพ : โสด

ศาสนา : พุทธ

ภูมิลำเนา : จังหวัดประจวบคีรีขันธ์

คติประจำใจ : อย่าคิดว่าทำไม่ได้ ถ้ายังไม่ได้ลองทำ

หลักสูตร การบริหารธุรกิจ (คอมพิวเตอร์ธุรกิจ) คณะวิทยาการจัดการ มหาวิทยาลัยราชภัฎสวนดุสิต

e-mail address : u50152792030@gmail.com