DTS 05-22/07/52

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

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

DTS 04-15/07/52

สรุป

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

โหนด (Node)







โครงสร้างแบบ Linked list แบ่งได้หลายแบบตามวิธีการชี้ไปยังโหนดต่างๆ เช่น Singly Linked list , Doubly Linked list , Multi-Linked list






การสร้าง Linked listวิธีสร้าง Linked list คือการนำข้อมูลที่จะจัดเก็บเข้า Linked list เพิ่มตรงโหนดตำแหน่งสุดท้ายของลิสต์ ฉะนั้นจึงต้องมี External พอยน์เตอร์ที่คอยชี้โหนดสุดท้ายของลิสต์ ในที่นี้ใช้ L (Last) ตัวอย่างการสร้าง Linked list จากลิสต์ L = 21 , 5 เริ่มจากการให้ H ชี้ทิ่โหนดตำแหน่งแรก และ L ชี้ทิ่โหนดตำแหน่งสุดท้าย






เพิ่มข้อมูล 5 เข้าไปใน list , L ชี้ไปยังโหนดที่เก็บข้อมูล 5







การเพิ่มข้อมูลโดยแทรกลงในลิสต์การเพิ่มข้อมูลจะทำการแทรกโหนด NEW หลังโหนด P ตัวอย่าง ทำการเพิ่มข้อมูลโหนด 16 ระหว่างโหนด 21 และ 5



















การลบข้อมูลใน Linked listการลบข้อมูลที่ต้น list เนื่องจากขั้นตอนของการลบข้อมูลที่ header นั้นจะมีปัญหาที่ยุ่งยากกว่าเมื่อ design ด้วย oop(java) เราสามารถที่จะแก้ปัญหานี้ได้โดยการใส่ header node ที่ว่าง ๆ ไว้ข้างหน้าของ linked list เพื่อที่จะทำหน้าที่เป็นชี้ว่าเป็นหัวโหนดโดยที่ไม่ต้องมี pointer คอยชี้ที่ header และเมื่อเราต้องการที่จะเปลี่ยนแปลงข้อมูลใด ๆ บนหัวสามารถที่จะทำได้โดยการแทรก node เข้าไปดังตัวอย่างของการแทรกข้อมูลข้างล่างการแทรกข้อมูลลงในโหนดที่ต้องการ











จากรูปมีขั้นตอนดังนี้

tmp.next = tmp.next.next;


ฟังก์ชัน iostream.h กับ stdio.h

เป็นการกำหนดค่าให้กับตัวแปรแล้วมีการนำค่าของตัวแปรมาบวกกันตามที่กำหนดไว้

iostream.h

#include
int main()
{ float a = 15.9,b = 11.5;
float *p,*q;
p = &a;
q = &b;
cout << "*p = " << *p << q =" ">
*p = *p + 5.5;
*q = *q + 10.5;
cout << " a = " <<>
cout << " b = " <<>
return 0;
}

stdio.h

#include
int main()
{
float a = 15.9,b = 11.5;
float *p,*q;
p = &a;
q = &b;
printf(">printf("*q = %f \n",*q);
*p = *p + 5.5;
*q = *q + 10.5;
printf(" a = %f \n",a);
printf(" b = %f\n",b);
return 0;
}

DTS 03-01/07/52

สรุป
Pointer เป็นตัวแปรชนิดหนึ่งที่ทำหน้าที่เก็บตำแหน่งที่อยู่(Address ) ของตัวแปรที่อยู่ในหน่วยความจำรูปแบบเช่นการกำหนด address ของตัวแปร structure ให้กับตัวแปรพอยน์เตอร์จะใช้ ptvar = &struct_variable;
ตัวอย่าง
typedef struct
{
int acct_no;
char name[20];
}account;
Account customer,*p;
จากตัวอย่าง customer เป็นตัวแปร structure ประเภท account และ p เป็นพอยน์เตอร์ที่ชี้ตำแหน่งที่อยู่ของตัวแปรแบบ structure จะกำหนดเลขที่อยู่เริ่มต้นของ customer
ให้กับ p ได้โดย P= &customer;


แบบฝึกหัด

1.ให้นักศึกษากำหนดค่าของ Array 1 มิติ และ Array 2 มิติ
ตอบ Array 1 มิติ คือ float score[3];
และ Array 2 มิติ คือ int student[5][4];

2.ให้นักศึกษาหาค่าของ A[2] , A[6]
จากค่าA={2,8,16,24,9,7,3,8,}
ตอบ A[2] คือ 16
A[6] คือ 3

3.จากค่าของ int a [2][3] = {{6,5,4},{3,2,1}};
ให้นักศึกษาหาค่าของ a[1][0]และa[0][2]
ตอบ a[1][0] คือ 3
a[0][2] คือ 4

4.ให้นักศึกษากำหนด structure ที่มีค่าของข้อมูลจากน้อย 6 Records
ตอบ struct student
{
char code[11];
char name[15];
char lastname[15];
int mid;
int final;
float score;
float grade;
}stud;

5. ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวชนิด Array กับตัวแปร Pointer ในสภาพของการกำหนดที่อยู่ของข้อมูล
ตอบ array หมายถึง ตัวแปรชุดที่ใช้เก็บตัวแปรชนิดเดียวกันไว้ด้วยกัน เช่น เก็บ ข้อมูล charไว้กับ char เก็บ int ไว้กับ int
ไม่สามารถเก็บข้อมูลต่างชนิดกันได้ เช่น char กับ int เรียก array อีกอย่างว่าหน่วยความจำแบ่งเป็นช่อง การกำหนดสมาชิกของ array จะเขียนภายในเครื่องหมาย [ ]
pointer หมายถึง ตัวเก็บตำแหน่งที่อยู่ของหน่วยความจำ (Address) หรือเรียกว่า ตัวชี้ตำแหน่งที่อยู่ สัญลักษณ์ของ pointer จะแทนด้วยเครื่องหมาย *