สรุปครั้งที่ 10 โครงสร้างข้อมูลเเละขั้นตอนวิธี

Graph
- Vertex
Edge คือทางเชื่อมระหว่าง vertex 2 vertex ซึ่งมักจะแสดงถึงความสัมพันธ์ของทั้งสองเวอร์เท็กนั้น เช่น เส้นทางเดินรถจากเมือง A ไป B หรือ ราคาค่าตั๋วจาก A ไป B เป็นต้น
- Directed Edge
คือ edge ที่ระบุทิศทางไว้ด้วย ซึ่ง edge พวกนี้ ใช้ในการแทนข้อมูลที่ระบุทิศทางนั่นเอง เช่น เที่ยวบินจาก จาก A ไป B เป็นต้น (ซึ่งจะเป็น คนละเที่ยวบินจาก B ไป A เป็นต้น)
- Undirected edge
edge ที่ไม่ได้ระบุทิศทาง เรียกว่า Undirected edge ซึ่ง edge พวกนี้ ใช้ในการแทนข้อมูลที่ไม่มีทิศทางนั่นเอง เช่น ราคาค่าตั๋วจาก A ไป B เป็นต้น (ซึ่งเป็นราคาเดียวกันกับ ราคาค่าตั๋วจาก B ไป A)
- Path
path ทางเดินระหว่าง 2 node (อาจผ่านหลาย node)
- Simple Path
คือ Path ที่ไม่มีการเดินไปซ้ำที่ จุดเดิมเลย
- Cycle
คือ Path ที่มีจุดเริ่มต้น และ จุดปลายเป็นจุดเดียวกัน
- Simple Cycle
คือ Path ที่ไม่มีการเดินไปซ้ำที่ จุดเดิมเลย (คล้ายๆกับคำว่า simple path แต่มีจุดเริ่มและจุดจบ เป็นจุดเดียวกัน)

สรุปครั้งที่ 9 โครงสร้างข้อมูลเเละขั้นตอนวิธี

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

การเรียงข้อมูล สามารถแบ่งได้เป็น 2 ประเภทด้วยกันคือ
- การเรียงข้อมูลแบบภายใน (Internal Sorting) คือ การเรียงลำดับข้อมูล โดยทั้งหมดต้องจัดเก็บอยู่ในหน่วยความจำหลัก (main memory) ที่มีการเข้าถึงข้อมูลได้เร็ว โดยไม่จำเป็นต้องใช้หน่วยความจำสำรอง เช่น ดิสค์ หรือเทปสำหรับการจัดเก็บชั่วคราว ใช้ในกรณีที่ข้อมูลไม่มากเกินกว่าพื้นที่ความจำที่กำหนดให้กับผู้ใช้แต่ละราย
- การเรียงข้อมูลแบบภายนอก (External Sorting) คือ การ เรียงลำดับข้อมูลที่มีขนาดใหญ่เกินกว่าที่จะสามารถเก็บไว้ใน พื้นที่ความจำหลักที่กำหนดให้ได้ในคราวเดียว ดังนั้นข้อมูล ส่วนมากต้องเก็บไว้ในไฟล์ข้อมูลที่อยู่บนดิสค์ เทป เป็นต้น สำหรับการเรียงข้อมูลแบบภายนอกจะต้องคิดถึงเวลาที่ใช้ใน การถ่ายเทข้อมูลจากหน่วยความจำชั่วคราวกับหน่วยความจำหลัก ด้วยเช่นกัน

สรุปครั้งที่ 8 โครงสร้างข้อมูลและขั้นตอนวิธี

Tree
เป็นโครงสร้างที่มีความสัมพันธ์กันระหว่างโหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น
 นิยามของทรี
1.นิยามของกราฟ
2. นิยามแบบrecursive
 นิยามที่เกี่ยวข้องกับทรี
1.Forest
2.Ordered Tree
3.Similar Tree
4.Equivalent Tree
5.Degree
6.Level of Node
Tree replacement in main memory
1. แต่ละโหนดเก็บ pt ชี้ไปยังโหนดลูกทุกโหนด
2. แทนที่ด้วย Binary Tree เป็นวิธีการลดการสิ้นเปลืองเนื้อที่ในหน่วยความจำ
การแปลงทรีเป็น Binary Tree
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโตแล้วลบความสัมพันธ์ ระหว่างโหนดแม่กับโหนดลูกคนอื่นๆ
2.ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3.จับทรีย่อยขวาเอียงลงมา 45 องศา 

สรุปครั้งที่ 7 โครงสร้างข้อมูลเเละขั้นตอนวิธี

คิว Queue
เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่าส่วนท้ายหรือ เรียร์ (Rear) และ การนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า (Front) ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือเรียกว่า FIFO (First In First Out)

การทำงานของคิว
การใส่ข้อมูลเรียกว่า En queue
การนำสมาชิกออกจากคิวเรียกว่า Dequeue
การแสดงข้อมูลตอนต้นเรียกว่า Queue Front
การแสดงข้อมูลส้วนท้ายเรียกว่า Queue Rear

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

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

การดำเนินการเกี่ยวกับคิว

1. Create Queue
2. Enqueue
3. Dequeue
4. Queue Front
5. Queue Rear
6. Empty Queue
7. Full Queue
8. Queue Count
9. Destroy Queue

สรุปครั้งที่ 6 โครงสร้างข้อมูลเเละขั้นตอนวิธี

Stack (cont.)
การดำเนินการเกี่ยวกับ Stack
Create stack
Push stack
Pop stack
stack top
empty stack

Full stack
Stack count
Destroy stack

  การคำนวณนิพจน์ทางคณิตศาสตร์
1.นิพจน์ intfix จะมี operator อยู่ตรงกลางระหว่างoperand 2 ตัว
2.นิพจน์ Postfix จะต้องเขียน operand ตัวที่1และ2 ก่อนแล้วตามด้วย operator
3.นิพจน์ Prefix ต้องเขียน operator ก่อน แล้วตามด้วย operand ตัวที่ 1 และ 2
  การแปลง intfix ไป postfix
1.อ่านcharในนิพจน์intfix เข้ามาทีละตัว
2.ถ้าเป็นoperandจะถูกย้ายเป็นcharในนิพจน์ postfix
3.ถ้าเป็นoperator จะนำค่าลำดับความสำคํญของตัว นำมาเทียบค่ากับoperator ที่อยู่ในstack top
4.operator ที่เป็น ) จะไม่push ลงใน stack แต่จะให้operand อื่น popก่อน จนกว่าจะเจอ (
5.เมื่ออ่านchar ทุกตัวในintfixหมดแล้วให้ทำการpop operator ทุกตัวในstack นำมาเรียงต่อในนิพจน์ postfix

สรุปครั้งที่ 5 โครงสร้างข้อมูลเเละขั้นตอนวิธี

Stack    
 Stack เป็น data structure แบบ linear list มีคุณสมบัติการเพิ่มหรือลบข้อมูลในstack จะกระทำที่ปลายข้างเดียวกัน เรียก Top of stack การเรียงลำดับ ข้อมูลหลังสุดจะถูกนำออกมา จาก stack เป็นลำดับแรกสุด เรียก Last in First Out

• การดำเนินงานพื้นฐานมี 3 ขั้น Push Pop Top
• Overflow ข้อมูลในstack มีอยู่เต็มแล้ว ไม่สามารถเพิ่มเข้าไปได้
• Underflow ข้อมูลไม่มีในstack แล้วทำการ pop จะ error
• empty ถ้าstack มีสมาชิก 1ตัว แล้วpop ออก