LECTURE6

DTS:06-07-2552

เรื่อง Stack


การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ

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


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


การประยุกต์ใช้สแตก

จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรย่อยการคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)


การคำนวณนิพจน์ทางคณิตศาสตร์

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

1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2

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

1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว

2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix

3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัอักษรในนิพจน์ Postfix

4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไเรียงต่อ

5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix

ตัวอย่างการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix

ในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน ขั้นตอนในการคำนวณ

1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร

2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา

3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดย ตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่1
ตามลำดับ

4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3

5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก

6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

การเขียนโปรแกรมแบบ iostream.h และ stdio.h

DTS:05-22-07-2552

โปรแกรมสำหรับคำนวณพื้นที่วงกลมตามที่เรากำหนดโดยเขียนออกมาในรูปแบบ iostream.h และ stdio.h


"iostream.h"



















"stdio.h"

ยกตัวอย่างสิ่งที่เจอในชีวิตประจำวันแบบ(LAST IN FIRST OUT)

DTS:05-22-07-2552

ยกตัวอย่างสิ่งที่เจอในชีวิตประจำวันแบบ(LAST IN FIRST OUT)

-ตั๋วรถเมล์

-ด้ายเย็บผ้า

- การถ่ายเอกสาร

-การหยิบหนังสือจากกองหนังสือ

-แก้วน้ำพลาสติกใน 7-11

- แก้วพลาสติกตามร้านขายชาไข่มุกที่วางซ้อนกัน

LECTURE5

DTS:05-22-07-2552

เรื่อง Linked List และ เรื่อง Stack

กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน(ต่อจากสัปดาห์ที่แล้ว)
-กระบวนงาน Traverse
หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์
ผลลัพธ์ ขึ้นกับการประมวลผล เช่นเปลี่ยนแปลงค่าในnode,รวมฟิลด์ในลิสต์

-กระบวนงาน Retrieve Node
หน้าที่ หาตำแหน่งข้อมูลจากลิสต์ข้อมูลนำเข้าลิสต์
ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์

-ฟังก์ชั่น EmptyList
หน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์
ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่างเป็นเท็จ ถ้าลิสต์ไม่ว่าง

-ฟังก์ชั่น FullList

หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์

ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็มเป็นเท็จ ถ้าสามารถมีโหนดอื่น

-ฟังก์ชั่น list count

หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์ข้อมูลนำเข้าลิสต์

ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์

-กระบวนงาน destroy list

หน้าที่ ทำลายลิสต์

ข้อมูลนำเข้า ลิสต์

ผลลัพธ์ ไม่มีลิสต์

Exam.

Algorithm destroyList (ref pList )

Pre pList is a pointer to a valid list head structure
Post All data and head structure deleted
Return null head pointer
1. Loop (pList->count not zero)
1 dltPtr = pList->head
2 pList->head = dltPtr->link
3 pList->count = pList->count-1
4 release (dltPrt)
2. release (pList)
3. Return null pointer
End destroyList


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

1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม

2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทางในลิงค์ลิสต์แบบ 2ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูลก่อนหน้า (backward pointer)และตัวชี้ข้อมูลถัดไป(forward pointer)

เรื่อง Stack

สแตก(Stack)เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตกจะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียคุณสมบัตินี้ว่าLIFO(Last In First Out)

การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญ คือ

1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก sต้องการใส่ข้อมูล i ในสแตก จะได้push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตกเช่นต้องการนำข้อมูลออกจากสแตก sไปไว้ที่ตัวแปร iจะได้ i = pop (s) แต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3.Stack Topเป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

LECTURE4

DTS:15-22-07-2552

เรื่อง Linked List

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

ส่วนของ data อาจจะเป็นรายการเดี่ยวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ link จะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไป ในโหนดสุดท้ายจะเก็บค่า Nullซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการสิ้นสุดของลิสต์


โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2 ส่วน คือ

1. Head Structure จะประกอบไปด้วย 3 ส่วนได้แก่ จำนวนโหนดในลิสต์ (Count)
พอยเตอร์ที่ชี้ไปยัง โหนดที่เข้าถึง (Pos) และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)

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


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

-กระบวนงาน Create List

หน้าที่ สร้างลิสต์ว่าง

ผลลัพธ์ ลิสต์ว่าง


-กระบวนงาน Insert Node

หน้าที่เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ

ข้อมูลนำเข้า ลิสต์ ข้อมูล และตำแหน่ง

ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง


-กระบวนงาน Delete Node

หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ

ข้อมูลนำเข้า ข้อมูลและตำแหน่ง

ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง


-กระบวนงาน Search list

หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้าลิสต์

ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล

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

DTS 03-01-07-52

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

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

ตอบ Array 1 มิติ คือ float nettotal[4];

Array 2 มิติ คือ int name[5][6];


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

ตอบ A[2] คือ 16A[6] คือ 3


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

ตอบ a[1][0] คือ 3a[0][2] คือ 4


4.ให้นักศึกษากำหนด structure ที่มีค่าของข้อมูลจากน้อย 6 Records

ตอบ struct student {


char name[30];


char surname[40];


int age;


char sex[10];


char address[50];


int month;


int year;


5. ให้นักศึกษาบอกความแตกต่างของการกำหนดตัวชนิด Array กับตัวแปร Pointer ในสภาพของการกำหนดที่อยู่ของข้อมูล

ตอบ array หมายถึง ตัวแปรชุดที่ใช้เก็บตัวแปรชนิดเดียวกันไว้ด้วยกัน เช่น เก็บ ข้อมูล char ไว้กับ char เก็บ int ไว้กับ int ไม่สามารถเก็บข้อมูลต่างชนิดกันได้ เช่น char กับ int เรียก array อีกอย่างว่าหน่วยความจำแบ่งเป็นช่อง การกำหนดสมาชิกชิกของ array จะเขียนภายในเครื่องหมาย [ ]

pointer หมายถึง ตัวเก็บตำแหน่งที่อยู่ของหน่วยความจำ(Address) หรือเรียกว่า ตัวชี้ ตำแหน่งที่อยู่ สัญลักษณ์ของ pointer จะแทนด้วยเครื่องหมาย *

สรุป LECTURE3

DTS: 03-01-07-2552

เรื่อง Pointer

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

การประกาศชนิดของตัวแปรพอยน์เตอร์
รูปแบบ
type *variable-name
type หมายถึง ชนิดของตัวแปร
* หมายถึง เป็นเครื่องหมายที่แสดงว่า ตัวแปรที่ตามหลังเครื่องหมายนี้เป็น ตัวแปรพอยน์เตอร์
variable-name เป็นชื่อของตัวแปรที่ต้องการประกาศว่าเป็นชนิดพอยน์เตอร์

ตัวอย่าง
char *prt หมายความว่า ประกาศว่าตัวแปร prt เป็นตัวแปรพอยน์เตอร์
ที่ใช้เก็บตำแหน่งเริ่มต้นที่จะเก็บ char

เครื่องหมายที่ใช้ทำงานกับตัวแปรพอยน์เตอร์

1. เครื่องหมาย & เป็นเครื่องหมายที่ใช้เมื่อต้องการให้เอาค่าตำแหน่งที่อยู่ของตัวแปรที่เก็บไว้ในหน่วยความจำออกมาใช้
2. เครื่องหมาย * มีการใช้งาน 2 ลักษณะ คือ
- ใช้ในการประกาศ parameter ว่าเป็นตัวแปรแบบพอยน์เตอร์
- ใช้เป็น dereferencing operator จะใช้เมื่อต้องการนำค่าที่อยู่ในตำแหน่งที่ตัวแปรพอยน์เตอร์นั้นชี้อยู่ออกมาแสดง


เรื่อง Set and String

โครงสร้างข้อมูลแบบเซ็ต

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

โครงสร้างข้อมูลแบบสตริง

สตริง (String) หรือ สตริงของอักขระ (Character String) เป็นข้อมูลที่ประกอบไปด้วย ตัวอักษร ตัวเลขหรือ เครื่องหมายเรียงติดต่อกันไป รวมทั้งช่องว่าง

สตริงกับอะเรย์

สตริง คือ อะเรย์ของอักขระ
เช่น char a[6] อาจจะเป็นอะเรย์ขนาด 6 ช่องอักขระ หรือ เป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character
เช่น
char a[ ]={‘H’, ‘E’, ‘L’, ‘L’, ‘O’, ‘\0’};
char a[ ]=“HELLO”;

การกำหนดสตริง

การกำหนดสตริงทำได้หลายแบบ คือ
1. กำหนดเป็นสตริงที่มีค่าคงตัว (String Constants)
2. กำหนดโดยใช้ตัวแปรอะเรย์หรือพอยเตอร์

การกำหนดค่าคงตัวสตริง

สามารถกำหนดได้ทั้งนอกและในฟังก์ชัน เมื่อกำหนดไว้นอก ฟังก์ชัน ชื่อค่าคงตัวจะเป็นพอยเตอร์ชี้ไปยังหน่วยความจำที่เก็บสตริง
นั้น เมื่อกำหนดไว้ในฟังก์ชัน จะเป็นพอยเตอร์ไปยังหน่วยความจำที่ เก็บตัวมันเอง การกำหนดค่าให้กับสตริงนั้น
เราจะใช้เครื่องหมายdouble quote (“ ”) เช่น “abc”
คือ ชุดของอักขระที่มีขนาด 4 (รวม \0 ด้วย)


Example

#define NME “Semi”
main ( ){
char *cpntr;
cpntr=NME;
printf(“con\n”);
printf(“%s, %u, %c\n”, “con”, “duc”,*“tor”);
printf(““%s, %u, %c\n”, NME, NME,*NME);
printf(““%s, %u, %c\n”, cpntr, cpntr,*cpntr);
}

ผลการรันโปรแกรม
con
con, 37, t
Semi, 16, S
Semi, 16, S