DTS 05-22/7/52

สรุปบทเรียน สแตก
สแตกเป็นโครงสร้างข้อมูลชนิดหนึ่งซึ่งมีการจัดการข้อมูลแบบ LIFO ( Last In First Out ) คือ ลำดับของข้อมูลที่ถูกนำมาเก็บก่อนจะถูกนำไปใช้ทีหลัง เหมือนกับวาง จานซ้อนกัน เวลาเราจะหยิบจานไปใช้ เราต้องหยิบใบบนสุดก่อน ซึ่งเป็นจานที่ถูกวางเก็บเป็นอันดับ สุดท้าย ส่วนจานที่ถูกวางเก็บเป็นใบแรกจะนำไปใช้ได้ก็ต่อเมื่อนำจานที่วางทับมันอยู่ออกไปใช้เสียก่อน
การทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1. การนำข้อมูลเข้าสู่สแตก ( Insertion ) คือการนำข้อมูลเข้าไปเก็บไว้ในสแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า PUSH โดยก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ว่างในสแตกก่อน ว่ามีที่เหลือให้เก็บหรือไม่
2. การนำข้อมูลออกจากสแตก ( Deletion ) คือการนำข้อมูลที่อยู่บนสุดออกจากสแตก โดยการกระทำ เช่นนี้เราเรียกว่า POP โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าในสแตกมีข้อมูลเก็บ อยู่หรือไม่
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้น
ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้น เราจะใช้ในรูปแบบของพอยน์เตอร์ ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย โครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วน คือ
1. ตัวชี้สแตก ( Stack Pointer ) หรือ SP ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของสแตก ( Top stack ) หรือชี้ไปยังช่องว่างข้อมูลในสแตกที่อยู่บนข้อมูลที่บนสุด
2. สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิดเดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม
นอกจากนี้ยังต้องมีตัวกำหนดค่าสูงสุดของสแตก ( Max Stack ) ซึ่งจะเป็นตัวบอกว่าสแตกนี้สามารถเก็บ จำนวนข้อมูลได้มากที่สุดเท่าไร
เราจะเปรียบเทียบส่วนประกอบของสแตกได้ดังนี้ คือ สแตกเป็นกระป๋องเก็บลูกเทนนิส ส่วน Stack Element คือ ลูกเทนนิส ส่วนตัวชี้สแตกเป็นตัวบอกว่าขณะนี้มีลูกเทนนิสอยู่ในกระป๋องกี่ลูก ส่วน Max 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
เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การทำงานของสแตก
สแตกมีการใช้แสดงลำดับการประมวลผลของข้อมูล เมื่อต้องการข้ามขั้นตอน บางขั้นตอนไปกระทำขั้นตอนอื่น ให้จบก่อน แล้วจึงกลับมาทำซ้ำขั้นตอนเดิม ดังตัวอย่าง
สมมติเมื่อเรากำลังประมวลผลข้อมูล A อยู่ เราต้องการข้ามไปประมวลผลข้อมูล B ให้เสร็จก่อน แล้วนำ ข้อมูลที่ได้มาใช้งานกับข้อมูล A เราจะต้องเก็บข้อมูล A ลงในสแตกก่อน (Push A) จากนั้นจึงข้ามไปทำ การประมวลผลข้อมูล B
ในขณะที่ประมวลผลข้อมูล B อยู่เราต้องข้ามไปทำข้อมูล C เพื่อนำผลที่ได้มาทำงานกับข้อมูล B เราก็จะต้อง ทำการเก็บ B ลงในสแตก (Push B) แล้วจึงจะข้ามไปทำข้อมูล C
มื่อทำข้อมูล C เสร็จเราก็จะดึงข้อมูล B ออกจากสแตก (Pop B) เพื่อทำการประมวลผล
เมื่อเราประมวลผลข้อมูล B เสร็จ เราก็จะดึงข้อมูล A ออกจากสแตก (Pop A) เพื่อทำการประมวลผล เป็นอันสิ้นสุดการประมวลผล

ตัวอย่างการทำงานแบบ LIFOที่เห็นในชีวิตประจำวันของข้าพเจ้า

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

Linked List

DTS 04-15-07-09
Linked List



ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node)
โนดจะประกอบไปด้วย 2 ส่วนคือ
Data จะเก็บข้อมูลของอิลิเมนท์
ส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์
ในส่วนของdataอาจจะเป็นรายการเดียวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ linkจะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปใน โหนดสุดท้ายจะเก็บคา Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการ สิ้นสุดของลิสตในลิงค์ลิสตจะมีตัวแปรสำหรับชี้ ตำแหน่งลิสต (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต ซึ่งก็ คือโหนดแรกของลิสตนั้นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสตจะเป็น Null
ในส่วนของdataอาจจะเป็นรายการเดียวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ linkจะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไปใน โหนดสุดท้ายจะเก็บคา Null ซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการ สิ้นสุดของลิสตในลิงค์ลิสตจะมีตัวแปรสำหรับชี้ ตำแหน่งลิสต (List pointer variable)ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต ซึ่งก็ คือโหนดแรกของลิสตนั้นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสตจะเป็น Null
โครงสร้างข้อมูลแบบลิงค์ลิสตโครงสร้างข้อมูลแบบลิงค์ลิสตจะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่ จำนวนโหนดในลิสต (Count)พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง(Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อูมลแรกของลิสต (Head)
2. Data Node Structure จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
โครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน
ได้แก่ จำนวนโหนดในลิสต์ (Count) พอยเตอร์ที่ชี้ไปยัง
โหนดที่เข้าถึง (Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูล
แรกของลิสต์ (Head)
2. Data Node Structure จะประกอบไปด้วยข้อมูล
การลบข้อมูล
การลบข้อมูลมีหลายวิธี แต่ล่ะวิธีจะแตกต่างตามตำแหน่งของโนดที่ต้องการลบ วิธีลบโนดในแต่ล่ะตำแหน่งมีดังนี้
ตำแหน่งต้นลิสต์ ทำได้โดยให้โนดพิเศษชี้ไปโนดที่2ของลิสต์
ตำแหน่งท้ายลิสต์ การลบโนด ทำได้โดยให้ตัวชี้ของโนดรองสุดท้ายมีค่าเป็นNULL
ตำแหน่งท้ายลิสต์ กำหนดให้ตัวชี้ prev ชี้ที่โนดก่อนหน้าโนดที่ต้องการลบ และตัวชี้ p ชี้ที่โนดที่ต้องการลบ
ในการลบโนดควรตรวจสอบก่อนว่าในลิสต์นั้นมีสมาชิกกี่จำนวน ถ้าเหลือเพียงจำนวนเดียวก็หมายความว่า หลังจากลบโนดทิ้งแล้วจะกลายเป็นลิสต์ว่างไม่จำเป็นต้องเชื่อมโยงโนดใหม่

แบบฝึกหัดบทที่ 2

1. ให้นักศึกษากำหนดค่าของ Array 1 มิติ และ Array 2 มิติ
ตอบ

อาเรย์ คือชุดของตัวแปร ที่มีชื่อตัวแปรและชนิดตัวแปรเดียวกัน มักใช้กับตัวแปรชนิดเดียวกันหลายๆ ตัว ที่มีการทำงานเหมือนกัน เช่นคะแนนนักศึกษา 40 คน ชื่อทุกกระบวนวิชาที่เปิดสอนภายในภาควิชา (เช่นอาจมี 40 กระบวนวิชา ก็จะมีข้อมูล 40 ชื่อ) เป็นต้น
รูปแบบการประกาศอาเรย์
ชนิดข้อมูล ชื่อตัวแปร [ขนาดข้อมูล];
ตัวอย่าง ต้องการเก็บข้อมูลคะแนนสอบของนักศึกษา 10 คนไว้ในตัวแปร array จะต้องการประกาศตัวแปรอาเรย์ ดังนี้
float score[10];
อาเรย์ 2 มิติ
ข้อมูลในอาเรย์ 2 มิติ จะเป็นลักษณะของตาราง
ซึ่งมีแถวและคอลัมน์
แถว (row)
คอลัมน์ (column)
score[row][column] เช่น score[0][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]
char a[2][3];
col1 col2 col3
row1 a[0][0] =6 a[0][1] =5 a[0][2] =4
row 2 a[1][0] =3 a[1][1] =2 a[1][2] =1

ตอบ ค่าของ a[1][0] = 3
a[0][2] = 4
______________________________
4. ให้นักศึกษากำหนด Structure ที่มีค่าของข้อมูลจากน้อย 6 Records

ตอบ struct student
#include<stdio.h>
struct student
{
char name[30];
char lastname[40];
int age;
char sex;
int day;
int month;
int year;
char address[20];
}data;
void main()
{

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


array m3[ ] จะเก็บข้อมูลอยู่ใน array มีพื้นที่เก็บข้อมูลเป็นของตัวแปรนี้และชื่อ m3 จะมี ค่า address คงที่ไม่สามารถเปลี่ยนค่าได้ใช้ m3 + 1 ได้ แต่ใช้ m3++ ไม่ได้

pointer *m3 จะชี้ไปที่ที่เก็บข้อมูล จากตัวอย่างข้างต้นจะมีพื้นที่ส่วนหนึ่งที่ใช้ในการเก็บ string ชุดนี้ไว้แล้ว m3 จะชี้ไปที่ address ของพื้นที่นั้น ๆ เราสามารถที่จะทำการเปลี่ยนค่าของ m3 ได้โดยใช้ m3++

สรุปการเรียน Set and String

DTS 03-01-07-09


Pointer คือ ตัวแปรชนิดหนึ่งที่อ้างอิงไปยังตำแหน่งของหน่วยความจำ (Address) เป็นการใช้ตัวชี้จะทำให้โปรแกรมรวดเร็วและ มีขนาดเล็ก

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

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

โครงสร้างข้อมูลแบบสตริง
สตริง เป็นข้อมูลประกอบไปด้วย ตัวอักษร ตัวเลขหรือเครื่องหมาย ที่เรียงต่อๆกันไป รวมทั้งช่องว่างด้วยสตริงกับอะเรย์ สตริงคือ อะเรย์ของอักขระ
เช่น Char name[15]
อาจจะเป็นอะเรย์ขนาด 15 ช่องอักขระ หรือเป็นสตริงขนาด 15 อักขระก็ได้ โดยจุดสิ้นสุดขอบ สตริง จะจบด้วย \0 หรือ null character
เช่น char b[] = {'S' ,'A ','W', 'A' ,'S ','D' ,'E' ,'E' ,'\0'};
หรือ char b[] = "SAWASDEE";
การกำหนดตัวแปรสตริง อาศัยหลักการของอะเรย์ เพราะสตริงคืออะเรย์ของอักขระที่เปิดท้ายด้วย (\0) และมีฟังก์ชันพิเศษสำหรับการทำงานของสตริงโดยเฉพาะ

DTS02-24/06/2009

#include<stdio.h>
struct student
{
char name[30];
char lastname[40];
int age;
char sex;
int day;
int month;
int year;
char address[20];
}data;
void main()
{
printf("studen data\n");
printf("name:");
scanf("%s",&data.name);
printf("lastname:");
scanf("%s",&data.lastname);
printf("age:");
scanf("%d",&data.age);
printf("sex:");
scanf("%s",&data.sex);
printf("date of birth (d/m/y):");
scanf("%d/%d/%d",&data.day,&data.month,&data.year);
printf("address:");
scanf("%s",&data.address);
{
printf("\n\n\nDisplay Data of student\n");
printf("Name : %s\n",data.name);
printf("Lastname : %s\n",data.lastname);
printf("Age : %d\n",data.age);
printf("sex : %s\n",data.lastname);
printf("birthday : %d/%d/%d\n",data.day,data.month,data.year);
printf("address : %s\n",data.address);
}
}