DTS 06-29-07-2552

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

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

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

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


การแปลงนิพจน์ Infix เป็นนิพจน์ Postfix นิพจน์ A-B/C+D*Eตัวที่อ่านเข้ามา ผลลัพธ์ในสแตก นิพจน์ Postfix
A ว่าง A
- - A
B - AB
/ -/ AB
C -/ ABC
+ + ABC/-
D + ABC/-D
* +* ABC/-D
E +* ABC/-DE
ABC /- DE*+

นิพจน์ A*(B+C-D)/E

การบ้าน iostream.h และ stdio.h

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

#include
main()
{
int price,amount,pay;
printf("Enter Amount :");
scanf("%d",&amount);
while(amount!=0)
{
printf("Enter Price : ");
scanf("%d",&price);
pay=price*amount;
printf("You must pay %d baht\n",pay);
printf("* * * * * * * * * * * * * * *\n");
printf("Enter Amount : ");
scanf("%d",&amount);
}
printf("* * * * * * * * * * * * * * *\n");
printf("Thank you");
}



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

#include
main()
{
int price,amount,pay;
cout<<"Enter Amount :"; cin>>amount;
while(amount!=0)
{
cout<<"Enter Price : "; cin>>price;
pay=price*amount;
cout<<"You must pay "<<<" baht\n"; cout<<"* * * * * * * * * * * * * * *\n"; cout<<"Enter Amount : "; cin>>amount;
}
cout<<"* * * * * * * * * * * * * * *\n"; cout<<"Thank you"; }

DTS 05-22-07-2552

Linked List (ต่อ)

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

Traverse การท่องเข้าไปในลิสต์ คือ การท่องไปในทุกโหนดของลิงค์ลิสต์ เข้าถึงโครงสร้างทีละโครงสร้างที่อยู่ในลิสต์นั้น

** สมมติว่ามีลิงค์ลิสต์ H อยู่แล้ว ถ้าจะหาว่า X อยู่ในลิสต์นี้หรือไม่ เราจะสามารถรู้ได้โดยการค้นหาแบบลำดับ (sequential search) ตามลำดับ

Retrieve Node คือ การหาตำแหน่งข้อมูลในลิสต์ ว่าข้อมูลที่ต้องการนั้นอยู่ตำแหน่งที่เท่าไหร่ในลิสต์นั้น

EmptyList คือ ลิงค์ลิสต์ที่ไม่มี node อยุ่ภายใน หรือเป็นการทดสอบว่าลิสต์ว่างหรือไม่

list count คือ การนับจำนวนข้อมูลที่มีอยู่ในลิสต์ทั้งหมด ซึ่งสามารถดูค่าของจำนวนข้อมูลได้จาก Count

destroy list คือ การทำลายลิสต์ทิ้ง

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

1.Circular Linked Listหมายถึง ลิงค์ลิสต์ที่โหนดสุดท้ายสามารถวกกลับมาที่โหนดแรกได้

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

2.Double Linked List หมายถึง ลิงค์ลิสต์ที่ทุกโหนดสามารถวกกลับมาที่โหนดก่อนหน้าของตนเองได้ ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง

สแตก(Stack)

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

การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก โดยการเพิ่มข้อมูลลงในสแตก จะต้องทำการตรวจสอบว่า
สแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่
ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่สามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก

2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก โดยการนำข้อมูลออกจากสแตก ถ้าสแตก
มีสมาชิก เพียง 1ตัว แล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง (Stack Empty)
คือ ไม่มีสมาชิก อยู่ในสแตกเลย แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิด
ความผิดพลาดที่เรียกว่า Stack Underflowเพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้อง
ตรวจสอบ ก่อนว่าสแตกว่างหรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้และ ปรับตัวชี้ตำแหน่งให้ไปชี้
ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป

3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

**ตัวอย่างของสแตก = สก๊อกเทป ก็คือ การม้วนของเทป เวลาม้วนเข้าไปก่อน แต่เวลาใช้ จะใช้ตรงปลายที่ถูกม้วนเข้าไปทีหลังสุดก่อน

DTS 04-15-07-2552

ลิงค์ลิสต์ (Linked List)

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

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

กระบวนงานและฟังกชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List หน้าที่ สร้างลิสตว่าง ผลลัพธ์ ลิสตว่าง
2.กระบวนงาน Insert Nodeหน้าที่เพิ่มข้อมูลลงไปในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าลิสต ข้อมูล และตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Node หน้าที่ลบสมาชิกในลิสตบริเวณตำแหน่งที่ต้องการข้อมูลนำเข้าข้อมูลและตำแหน่งผลลัพธ์ ลิสตที่มีการเปลี่ยนแปลง

DTS 03-1-07-2552

pointer

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


การกำหนดตัวแปร Pointer
การกำหนดตัวแปร Pointer จะคล้ายกับการกำหนดตัวแปรชนิดต่างๆ เพียงแต่ต้องมีเครื่องหมาย * หน้าชื่อตัวแปร ตัวอย่างเช่น int *pt;ในที่นี้กำหนดให้ pt เป็นตัวแปร Pointer ซึ่งเก็บAddressของตัวแปรชนิดตัวเลขจำนวนเต็มในเรื่อง Pointer มีเครื่องหมาย 2 ชนิด คือ * และ & เครื่องหมาย * จะให้ค่า ของข้อมูล ซึ่งเก็บอยู่ใน Address โดย Address นี้เก็บ อยู่ในตัวแปร Pointer ซึ่งอยู่หลังเครื่องหมาย * สำหรับเครื่องหมาย & จะให้ค่า Address ของตัวแปรซึ่งอยูหลังเครื่องหมาย &


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

data type *pointer name[size];

พอยน์เตอร์ของพอยเตอร์
ตัวแปรพอยน์เตอร์อาจใช้เก็บค่าแอดเดรสของตัว แปรพอยเตอร์อื่น ซึ่งเก็บค่าแอดเดรสของตัวแปรหรือพอยเตอร์ตัวที่ 1 ชี้ไป แอดเดรสของพอยเตอร์ตัวที่ 2 ซึ่งพอยเตอร์ตัวที่ 2 ชี้ไปแอดเดรสตัวแปรดังรูป

พอยเตอร์ >>> พอยเตอร์ >>> ตัวแปร

ในการกำหนดพอยเตอร์ของพอยน์เตอร์จะต้องเพิ่มเครื่อหมาย * อีก 1 ตัวหน้าพอยเตอร์เช่น int **pt;

Set

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

1.set intersection
2.set union
3.set difference

String

เป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลข หรือเครื่องหมายที่เรียงติดต่อกันความยาวของสตริงจะถูกกำหนดโดยขนาดของสตริง ในการจองเนื้อที่นั้น ต้องทำการจองเนื้อที่ให้กับ \0 ด้วย