การบ้าน iostream.h & stdio.h

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



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

DTS 22-07-52

stack
สแตกเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียว คือ ส่วนบนของสแตกหรือ เรียกว่า ท๊อปของสแตก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list) หรือ พูชดาวน์ลิสต์ (Pushdown List) คือสมาชิกที่เข้าลิสต์ที่หลังสุดจะได้ออกจากลิสต์ก่อน หรือ เข้าหลังออกก่อน การเพิ่มข้อมูลเข้าสแตกจะเรียกว่าพูชชิ่ง (pushing) การนำข้อมูลจากสแตกเรียกว่า ป๊อปปิ้ง (poping) การเพิ่มหรือลบข้อมูลในสแตกทำที่ท๊อปของสแตก ท๊อปของสแตกนี้เองเป็นตัวชี้สมาชิกตัวท้ายสุดของสแตก



ส่วนประกอบของสแตก
การนำสแตกไปใช้งานนั้น ไม่ว่าจะเป็นโครงสร้างสแตกแบบแถวลำดับ(array)หรือ แบบลิงค์ลิสต์ (link list) เราจะมีตัวแปรตัวหนึ่งที่ใช้เป็นตัวชี้สแตก(stack pointer ) เพื่อเป็นตัวชี้ข้อมูลที่อยู่บนสุดของสแตก ซึ่งจะทำให้สามารถจัดการข้อมูล ที่จะเก็บในสแตกได้ง่าย ดังนั้นโครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น 2 ส่วนที่สำคัญ คือ
ตัวชี้สแตก ( Stack Pointer ) ซึ่งมีหน้าที่ชี้ไปยังข้อมูลที่อยู่บนสุดของ สแตก ( Top stack )
สมาชิกของสแตก ( Stack Element ) เป็นข้อมูลที่จะเก็บลงไปในสแตก ซึ่งจะต้องเป็นข้อมูลชนิด
เดียวกัน เช่น ข้อมูลชนิดจำนวนเต็ม เป็นต้น

การจัดการ กับสแตก
ในการทำงานของสแตก ประกอบด้วย 2 กระบวนการ คือ
1. การเพิ่มข้อมูลในสแตก (pushing stack) เป็นการนำข้อมูลเข้าสู่สแตก ซึ่งการกระทำเช่นนี้ เราเรียกว่า push ซึ่งโดยปกติก่อนที่จะนำข้อมูลเก็บลงในสแตกจะต้องมีการตรวจสอบพื้นที่ในสแตกก่อน ว่ามีที่เหลือว่างให้เก็บข้อมูลได้อีกหรือไม่
2. การดึงข้อมูลจากสแตก (Popping Stack) หมายถึงการเอาข้อมูลที่อยู่บนสุดในสแตก หรือที่ชี้ด้วย ท๊อปออกจากสแตก เรียกว่าการ pop ในการpop นั้นเราจะสามารถ pop ข้อมูลจากสแตกได้เรื่อย ๆ จนกว่า ข้อมูลจะหมดสแตก หรือ เป็นสแตกว่าง โดยก่อนที่จะนำข้อมูลออกจากสแตก จะต้องมีการตรวจสอบว่าใน สแตกมีข้อมูลเก็บ อยู่หรือไม่


ปัญหาที่เกิดขึ้นกับสแตก
1.สแตกเต็ม (Full Stack) การ push สแตกทุกครั้งจะมีการตรวจสอบที่ว่างในสแตกว่ามีที่ว่างเหลือหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ push สแตกได้ ในกรณีเช่นนี้เราเรียกว่าเกิดสถานะล้นเต็ม (Stack Overflow) โดย การตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของ สแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูล อีก
2. สแตกว่าง (Empty Stack) นิยาม empty(S) ถ้า S เป็นสแตก ขบวนการ empty(S) จะส่งผลเป็นจริง (true) เมื่อสแตกว่าง และส่งผลเป็นเท็จ (false) เมื่อสแตกไม่ว่างหรือสแตกเต็ม
การ pop สแตกทุกครั้งจะมีการตรวจสอบข้อมูลในสแตกว่ามีข้อมูลในสแตกหรือไม่ ถ้าไม่มีข้อมูลในสแตก เหลืออยู่ เราก็ไม่สามารถทำการ pop สแตกได้ ในกรณีเช่นนี้เรียกว่าเกิดสถานะ สแตกจม (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่า สแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้


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



การเข้าทีหลังออกก่อน
ตัวอย่างเช่น เก้าอี้ที่วางซ้อนกัน

DTS 21-07-52

สรุปบทเรียน Linked list

โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)
โครงสร้างข้อมูลแบบนี้ จะให้ความสะดวกแก่การจัดการข้อมูลมาก อย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่อง เมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวก เนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้ นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือ ในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มาก ในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใด ลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง



ประเภทของ Linked list
1. แบบทิศทางเดียว
2. แบบสองทิศทาง
3. แบบวงกลม
4. แบบหลายทิศทาง


โครงสร้างของ Linked list มี 2 ส่วนใหญ่ๆ คือ
1. โครงสร้าง Head Node
2. โครงสร้าง Data Node


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

NODE(P) หมายถึง โหนดที่ระบุ(ถูกชี้) โดยพอยน์เตอร์ P
INFO(P) หมายถึง ส่วนข่าวสารของโหนดที่ถูกชี้โดย P
LINK(P) หมายถึง ส่วนแอดเดรสของโหนดที่ถูกชี้ P

ลิงค์ลิสต์คู่ (Doubly Linked List)
ลิงค์ลิสต์คู่ (Doubly Linked List) ลิงค์ลิสต์แบบนี้เป็นลิงค์ลิสต์ที่แต่ละโหนดมีสองพอยน์เตอร์คือ LLINK และ RLINK ซึ่งจะชี้ไปยังโหนดข้างซ้ายและข้างขวาของโหนดนั้นตามลำดับ ตัวอย่างเช่น ถ้าต้องการจะเก็บค่า A,B,C,D ในลิงค์ลิสต์ชนิดนี้จะได้โครงสร้างซึ่งปลายทั้งสองข้างของลิงค์ลิสต์ชนิดนี้จะมีพอยน์เตอร์ F และ R แสดงถึงโหนดแรกในทิศนั้น ถ้าใช้อาร์เรย์สร้างลิงค์ลิสต์ตามรูปที่ 19 จะต้องใช้อาร์เรย์ 3 ชุดคือ อาร์เรย์สำหรับช่องข่าวสาร (INFO) , อาร์เรย์สำหรับพอยน์เตอร์ทางซ้าย (LLINK) และอาร์เรย์สำหรับพอยน์เตอร์ทางขวา (RLINK)
เมื่อเปรียบเทียบลิงค์ลิสต์คู่กับลิงค์ลิสต์เดี่ยว จะเห็นได้ชัดว่าลิงค์ลิสต์คู่ต้องใช้เนื้อที่มากกว่า เนื่องจากต้องใช้ 2 พอยน์เตอรืสำหรับแต่ละโหนดแน่นอน ที่เสียไปนั้นก็เพื่อที่จะได้สิ่งบางอย่างเพิ่มเติม นั่นคือ ความสะดวกในการนำข่าวสารเข้าหรือออกจากลิงค์ลิสต์ ในกรณีลิงค์ลิสต์คู่ เราสามารถนำโหนดใหม่เข้าทาง ด้านหน้า หรือ ด้านหลังโหนด H1 ในลิงค์ลิสต์นั้นได้ นอกจากนี้เรายังสามารถคืนโหนด H1 ไปสู่ storage pool โดยตรงได้อีกด้วย อย่าลืมว่าเราไม่สามารถคืนโหนด H1 ไปสู่ storage pool ในกรณีลิงค์ลิสต์เดี่ยว

DTS 12-07-52

สรุปบทเรียน Pointer , Set and String

Pointer
คือ ตัวแปรที่เก็บตำแหน่งของหน่วยความจำ (memory address) ซึ่งตำแหน่งของหน่วยความจำนี้จะเป็นที่อยู่ของสิ่งอื่น ๆ (โดยทั่วไปจะเป็นตัวแปรอื่น) ในหน่วยความจำ เช่น ถ้าตัวแปรตัวหนึ่งเก็บตำแหน่งของตัวแปรอีกตัว เราอาจกล่าวได้ว่าตัวแปรตัวแรกนั้นชี้ไปยัง (point to) ตัวแปรที่สอง จะเก็บ Address ของตัวแปร แทนที่จะเก็บข้อมูลต่างๆ เหมือนตัวแปรชนิดอื่นๆ จากคุณสมบุติของ ตัวแปรชนิด Pointer จึงมองดูเหมือนกับ ตัวชี้ หรือพอยน์เตอร์ ซึ่งชี้ไปที่ Address ของตัวแปร


การกำหนดตัวแปร Pointer
จะคล้ายกับการกำหนดตัวแปรชนิดต่างๆ เพียงแต่ต้องมีเครื่องหมาย * หน้าชื่อตัวแปร ดังนี้
int *pt;
ในที่นี้กำหนดให้ pt เป็นตัวแปร Pointer ซึ่งเก็บ Address ของตัวแปรชนิดตัวเลขจำนวนเต็ม ในเรื่อง Pointer มีเครื่องหมาย 2 ชนิด คือ * และ & เครื่องหมาย * จะให้ค่า ของข้อมูล ซึ่งเก็บอยู่ใน Address โดย Address นี้เก็บ อยู่ในตัวแปร Pointer ซึ่งอยู่หลังเครื่องหมาย * สำหรับเครื่องหมาย & จะให้ค่า Address ของตัวแปรซึ่งอยูหลังเครื่องหมาย & ดังตัวอย่าง
ตัวอย่าง
#include "stdio.h"
main()
{
int *pt, a, b;
a = 30;
pt = &a;
b = *pt;
printf("%d\n",b);
}



จะได้ผลลัพท์ = 30



ความสัมพันธ์ของ Pointer และ Array
ใน C++ Pointer และ Array จะมีความสัมพันธ์กันมาก เมื่อใข้ Array โดยไม่ระบุ Index เลย Array จะทำหน้าที่ เสมือนเป็น Pointer ซึ่งชี้ไปที่ ส่วนต้นของ Array (ตัวแปร Array ตัวแรก) ดังเช่นใน Function gets() ซึ่งเราจะเขียนเฉพาะชื่อ Array เท่านั้น Function gets() จะนำตัวอักษรที่ป้อนทางแป้นพิมพ์ ไปเก็นใน Array ซึ่งถูกชี้โดย Pointer การผ่านค่าไป Function ใน C++ จะผ่านในรูปของ Pointer เท่านั้น



String
หมายถึง ชุด(array)ของตัวอักขระ(character) ที่เรียงต่อกัน ตริงจะเป็นคําหรือข้อความที่มีความหมาย ใน C++ ไม่มีชนิดข้อมูลประเภท string การกําหนด string คือการกําหนดเป็นอาร์เรย์ของข้อมูลชนิด char หลาย ๆ ตัวนํามาเชื่อมต่อกันเป็น string เช่น character 'C','o','m','p','u','t','e','r' เก็บไว้ในอาร์เรย์รวมเป็นข้อมูล string ซึ่งจะได้ข้อความ "Computer" ข้อมูล string เป็นได้ทั้งค่าคงที่(constant) และตัวแปร(variable)

การกําหนดค่าคงที่ให้ string
วิธีการกําหนดตัวแปรประเภทchar ให้เป็นอาร์เรย์เพื่อให้เก็บค่าคงที่

1. ประกาศตัวแปรอาร์เรย์ประเภท char ไม่ระบุขนาดของอาร์เรย์และกําหนดค่ามีรูปแบบดังนี้

char string_name[] = "string or text";

โดยที่ char คือ ประเภทข้อมูลของสตริงเป็น character
string_name[] คือ ชื่อของตัวแปรสตริง โดยที่[ ] กําหนดให้เป็นอาร์เรย์ของสตริงไม่ระบุขนาดของอาร์เรย์ C++ Compilerจะตรวจสอบและกําหนดขนาดจากค่าคงที่ด้านขวาของเครื่องหมายเท่ากับ "string or text" คือข้อความหรือสายอักขระที่เป็นค่าคงที่ของสตริงต้องเขียนไว้ในเครื่องหมาย " " เสมอ (ถ้าเป็นค่าคงที่ประเภท char ค่าคงที่เขียนไว้ในเครื่องหมาย ' ') เช่น

char name[] ="Sirichai Namburi";
char str[] = "C++ is OOP language";

เนื่องจากสตริงเป็นอาร์เรย์ของ char จึงสามารถกําหนดค่าคงที่ได้อีกวิธีหนึ่ง คือ

char name[] = {'S','i','r','i','c','h','a', 'i',' ','N','a','m','b','u','r', 'i','\0'};

สําหรับ'\0' หมายถึงเครื่องหมาย null ซึ่งใช้เป็นรหัสจบสตริงในภาษาC++

2. ประกาศตัวแปรอาร์เรย์ประเภทchar โดยระบุขนาดของอาร์เรย์และกําหนดค่า มีรูปแบบดังนี้

char string_name[n] = " string or text";

โดยที่ n คือขนาดของอาร์เรย์ 1 มิติ เช่น

char name[31]; //ตัวแปรname สามารถเก็บอักขระได้30 ตัวตัวที่31ใช้เก็บ'\0'
char location[50]; //ตัวแปรlocation สามารถเก็บอักขระได้49 ตัวตัวที่50 ใช้เก็บ'\0'