Stack:
สแตก (Stack) เป็นโครงสร้างข้อมูลที่
ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การ
เพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลาย
ข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top
Of Stack) และ ลักษณะที่สำคัญของสแตก
คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากส
แตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า
LIFO (Last In First Out)
การดำเนินงานพื้นฐานของสแตก
การทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวน
การที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้
push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุด
ของสแตก
เช่น ต้องการนำข้อมูลออกจากสแตก s
ไปไว้ที่ตัวแปร i
จะได้ i = pop (s)
การนำข้อมูลออกจากสแตก ถ้าสแตกมีสมาชิกเพียง 1
ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตก
ว่าง (Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลย
3. Stack Top เป็นการคัดลอกข้อมูลที่
อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น
ออกจากสแตก
การบ้าน
- การหยิบลูกปิงปองออกจากกล่อง
- การหยิบหนังสือที่อยู่ในกล่อง
Set and String , Linked List
อาเรย์ของสตริงนั้นสามารถแบ่งได้เป็น 2 ประเภทคือแบบยาวเท่ากันและยาวไม่เท่ากันกรณียาวไม่เท่ากันนั้นทำได้ดังนี้
char *name[4]={“Thatchapol”, “John”, “Somchai”, “Ratchawee”};
แต่จะทำได้ก็ต่อเมื่อมีการกำหนดค่าเริ่มต้นเท่านั้น
กรณียาวเท่ากันนั้นเราจะทำการกำหนดอาเรย์ของสตริงเป็น 2 มิติ
Linked List
ลิงค์ลิสต์เป็นรูปแบบหนึ่งของโครงสร้างเหมือนกับพอยน์เตอร์คือมีการจัดการข้อมูลแบบไม่ตายตัว (Dynamic Structure) โครงสร้างของลิงค์ลิสต์จะประกอบด้วยโหนดหลาย ๆ โหนดภายใน 1 โหนดจะแบ่งออกเป็น 2 ส่วนคือส่วน data กับ link โดยการเชื่อมโยงไปยังโหนดต่อ ๆ นั้นจะใช้รูปแบบของพอยน์เตอร์เป็นตัวชี้ไปยังโหนดต่อ ๆ ไปประเภทของลิงค์ลิสต์นั้นมีหลายประเภทเช่น
1. ลิงค์ลิสต์แบบทิศทางเดียว
2. ลิงค์ลิสต์แบบวงกลม
3. ลิงค์ลิสต์แบบ 2 ทิศทาง
4. ลิงค์ลิสต์แบบหลายทิศทาง
โดยปกติครงสร้งของลิงค์ลิสต์มี 2 ส่วนใหญ่ ๆ คือ
1.โครงสร้างโหนดต้นลิสต์ หรือ Head node
2. โครงสร้างโหนดข้อมูล หรือ Data node การเพิ่มข้อมูลลงไปในลิงค์ลิสต์นั้น จากที่ Head Structure ในส่วนของ count จะมีค่าเป็น 0 นั้นหมายถึงในลิสต์นั้นยังไม่มีข้อมูลใดเลย ส่วน head จะมีเครื่องหมายกากบาท นั้นหมายถึงในลิสต์นั้นไม่มีการเชื่อมโยงไปยังข้อมูลแรก แต่ถ้าต้องการเพิ่มข้อมูลลงไปในลิสต์ Data Node ในส่วนของข้อมูล (Data)จะมีค่าเก็บอยู่ แล้ว count ก็จะเปลี่ยนค่าจาก 0 เป็น 1 คือ การบ่งบอกถึงจำนวนข้อมูลที่มีอยู่ในลิสต์นั้น แล้ว head ก็จะชี้ไปยังข้อมูล (Data) ตัวแรกของลิสต์ ส่วนพอยเตอร์ที่ชี้ไปโหนดถัดไปจะเป็นเครื่องหมายกากบาทแทนการลบข้อมูลในลิงค์ลิสต์ ถ้าต้องการลบข้อมูลตัวใดในลิสต์สามารถลบได้เลย แต่ต้องเปลี่ยน head เพื่อชี้ไปยังข้อมูลตัวแรกของลิสต์กรณีที่ลบข้อมูลตัวแรกออก แล้ว link คือ เมื่อลบข้อมูลตัวใดออกควรชี้ link ถัดไปให้ถูกต้องด้วย
ทฤษฏีการดำเนินการ
1. การสร้างลิสต์เนื่องจากลิงค์ลิสต์มีโครงสร้างที่ไม่ตายตัวดังนั้นจะต้องมีการจองพื้นที่บนหน่วยความจำให้กับพอยน์เตอร์ด้วยซึ่งก็คือการสร้างลิสต์ขึ้นมาหลักการทำงาน : จองพื้นที่หน่วยความจำให้กับลิงค์ลิสต์ก่อนดำเนินการ : ไม่มีการกำหนดค่าหลังการดำเนินการ : พอยน์เตอร์เริ่มต้นมีการจองพื้นที่บนหน่วยความจำการคืนค่า : เนื่องจากหน่วยความจำไม่มีที่ว่าง
2. การแทรกโหนดกำหนดค่าเริ่มต้น : pList = Head nodeกำหนดค่าเริ่มต้น : pPre = Node pointerกำหนดค่าเริ่มต้น : dataIn = ค่าข้อมูลในโหนดหลักการทำงาน : ทำการแทกรโหนดที่มีค่าข้อมูลลงในลิงค์ลิสต์ก่อนการทำงาน : กำหนดพอยน์เตอร์ของลิสต์ชี้ไปยังโหนดต้นลิสต์หลังการทำงาน : แทรกโหนดที่จัดเก็บข้อมูลเข้าไปยังลิสต์การคืนค่า : จริง คือแทรกโหนดเรียบร้อยการคืนค่า : เท็จ ถ้าหน่วยความจำเต็ม overflow
สรุปเนื้อหาโครงสร้างข้อมูลแบบเซ็ต
เป็นโครงสร้างข้อมูลที่ข้อมูลแต่ละตัวไม่มีความสัมพันธ์กัน ในภาษาซีจะไม่มีประเภทข้อมูลแบบเซ็ตนี้เหมือนกับในภาษาปาสคาล แต่สามารถใช้หลักการของการดำเนินงานแบบเซ็ตมาใช้ได้
ตัวดำเนินการของเซ็ต (Set operators)
ประกอบด้วย
- Set intersection
- Set union
- Set difference เป็นต้น
โครงสร้างข้อมูลแบบสตริง
สตริง (String) หรือสตริงของอักขระ(Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง
ความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง การกำหนดขนาดของสตริงนั้นต้องจองเนื้อที่ในหน่อยความจำให้กับ \0 ด้วย
สตริงกับอะเรย์
สตริง คือ อะเรย์ของอักขระ
การกำหนดสตริง
การกำหนดสตริงทำได้หลายแบบ คือ
1. การกำหนดเป็นสตริงที่มีค่าคงตัว สามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอกฟังก์ชัน ชื่อค่าคงตัวจะเป็นพอยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริงนั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่อยความจำที่เวมันเองก็บตั
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์
การกำหนดตัวแปร name เท่ากับเป็นการกำหนดะเรย์ ขนาด 31 ไบต์ และให้ตัวแปร name ชี้ไปที่ต้นอะเรย์
ในการกำหนดตัวแปร name กำหนดไว้ว่าชื่อจะองไม่ยาวเกิน 30 อักขระ หากผู้ใช้ป้อนไม่ถึง 30 อักขระ เครื่องจะทำการเติม null character ให้จนครบ 31 ช่อง แต่ถ้าผู้ใช้ป้อนเกินจะเกิดข้อผิดพลาดหลุดจากโปรแกรมน้ เพราะฉะนั้นจึงต้องกำหนดความยาวของสตริงให้เพียงพอ
ฟังก์ชัน gets( ) เป็นฟังก์ชันที่อ่านค่าจากแป้นพิมพ์มาเก็บไว้ในหน่วยความจำ ซึ่งก็คืออะเรย์ที่ตัวแปร name ชี้อยู่ รวมทั้งช่องว่าง จนกว่าผู้ใช้จะกด Enter จะเติม null character ให้
ถ้าหากมีสตริจำนวนมาก ก็ควรจะทำให้เป็นอะเรย์ของสตริง เพื่อทีจะเขียนโปรแกรมได้สะดวก การสร้างอะเรย์ของสตริง สามารถสร้างได้ทั้งแบบที่ให้ค่าเริ่มต้นและแบบที่กำหนดเป็นตัวแปร
การกำหนดตัวแปร country จะแตกต่างกับการกำหนดอะเรย์ เพราะเป็นการกำหนดตัวแปรพอยเตอร์ขึ้น 4 โดยที่ contry [0] จะชี้ที่ข้อมูลแรก contry [1] จะชี้ข้อมูลที่สอง contry [2] จะชี้ชี้ข้อมูลที่สาม และ contry [3] จะชี้ข้อมูลตัวสุดท้าย
#include
#include
main(){
struct profile
{
char name [40];
int age; char sex[10];
char address[30];
char work[10];
int weight;
int high;
char future[20];
}profile_1;
strcpy(profile_1.name,"Nathasa");
profile_1.age = 22;strcpy(profile_1.sex,"female");
strcpy(profile_1.address,"123/32 Bangkok");
strcpy(profile_1.work,"Office");
profile_1.weight = 52;profile_1.high = 165;
strcpy(profile_1.future,"Work");
printf("Name %s\n",profile_1.name);
printf("Age %d\n",profile_1.age);
printf("Sex %s\n",profile_1.sex);
printf("Address %s\n",profile_1.address);
printf("Work %s\n",profile_1.work);
printf("Weight %d\n",profile_1.weight);
printf("High %d\n",profile_1.high);
printf("Futur %s\n",profile_1.future);
}
