สรุปครั้งที่ 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 ออก

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

Linked List

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

     Data             จะเก็บข้อมูลของอิลิเมนท์

      Link Field    จะทำหน้าที่เก็บตำแหน่งของโหนดต่อไปในลิสต์

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

     1. กระบวนงาน Create  List

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

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

     2. กระบวนงาน   Insert  Node

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

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

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

Array and Record

Array  เป็นโครงสร้างข้อมูลที่เรียกว่า linear Iist มีลักษณะคล้ายเซ็ตในคณิตศาสตร์ คือ อะเรย์จะประกอบด้วยสมาชิกที่มีจำนวนคงที่ มีรูปแบบข้อมูลเป็นแบบเดียวกัน สมาชิกแต่ละตัวใช้เนื้อที่จัดเก็บที่มีขนาดเท่ากัน เรียงต่อเนื่องในหน่วยความจำหลัก

การกำหนด Array

การกำหนดอะเรย์จะต้องกำหนดชื่ออะเรย์ พร้อม subscript ซึ่งเป็นตัวกำหนดขอบเขตของอะเรย์ มีได้มากกว่า 1 จำนวน subscript จะเป็นตัวบอกมิติของอะเรย์นั้น อะเรย์ที่มี subscript มากกว่า 1 ตัวขึ้นไป จะเรียกว่าอะเรย์หลายมิติ

อะเรย์1 มิติ

รูปแบบ :  data – type  array – name[expression]

 data – type  คือ ประเภทของข้อมูลอะเรย์ เช่น int char float

อะเรย์ 2 มิติ

Char  a[2][3];

หมายถึง คอมพิวเตอร์ จะจองเนื้อที่ในหน่วยความจำ จำนวน 6 ที่ สำหรับตัวแปร a

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

สตริง คือ อะเรย์ของอักขระ

เช่น char a[6]   อาจจะเป็นอะเรย์ขนาด  6 ช่องอักขระ หรือเป็นสตริงขนาด 5 อักขระก็ได้ โดยจุดสิ้นสุดของ string จะจบด้วย \0 หรือ null character

 

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

“This is String ! “ จะเป็นข้อมูลแบบสตริงยาว16 อักขระ

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

การแทนที่ข้อมูลในหน่วยความจำ
การแทนที่ข้อมูลในหน่วยความจำหลัก ในการเขียนโปรแกรมคอมพิวเตอร์มี 2 วิธี คือ
1) การแทนที่ข้อมูลแบบสแตติก (Static  Memory  Representation) เป็นการจองเนื้อที่แบบคงที่แน่นอน
2) การแทนที่ข้อมูลแบบ (Dynamic Memory Representation) เป็นการแทนที่ข้อมูล  แบบไม่ต้องจองเนื้อที่

อัลกอริทึม (Algorithm)                                                                                                                                

อัลกอริทึม คือ วิธี หรือ ขั้นตอนการแก้ปัญหาอย่างเป็นขั้นตอน มีระบบ ช่วยให้การแก้ปัญหานั้น ๆ อย่างมีประสิทธิภาพ

องค์ประกอบของการจัดทำอัลกอริทึม

1) การวิเคราะห์ (Analysis)

2) การออกแบบ (Design)

3) การเขียนโปรแกรม (Coding/Programming)      

4) การทดสอบและแก้ไขข้อผิดพลาดของโปรแกรม (Testing  and  Debugging)

5) การจัดทำเอกสารและบำรุงรักษา (Documentation  and  Maintenance)

ขั้นตอนที่ดีควรมีคุณสมบัติดังนี้
1) มีความถูกต้อง
2) ใช้เวลาในการปฏิบัติงานน้อยที่สุด
3) สั้น กระชับ
4) ใช้หน่วยความจำน้อยที่สุด
5) มีความยืดหยุ่นในการใช้งาน
6) ใช้เวลาในการพัฒนาน้อยที่สุด
7) ง่ายต่อการทำความเข้าใจ

สรุป บทที่1 ความหมายของโครงสร้างข้อมูล

ข้อมูล คือ ข้อเท็จจริง สามารถเป็นตัวเลขหรือไม่เป็นตัวเลขก็ได้
โครงสร้าง คือ ความสัมพันธ์ของสมาชิกในกลุ่ม

โครงสร้างข้อมูล คือ ความสัมพันธ์ของข้อมูลรวมไปถึงกระบวนการในการจัดข้อมูล เช่น แถวลำดับ สตริง ลิสต์ สแตก

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

วิธิการเลือกโครงสร้างข้อมูล
- มีความสัมพันธ์มากที่สุด
- มีความถูกต้องเเละผ่านการตรวจสอบ

คำถาม เราสามารถนำโครงสร้างข้อมูลมาใช้ให้เกิดประโยชน์ในสถานศึกษาได้อย่างไร?

My suggestion

I think that. Should increases desks for reading a book and doing homework after class.