โครงสร้างข้อมูล และอัลกอริทึม
โครงสร้างข้อมูล และอัลกอริทึม
โครงสร้างข้อมูล จัดเป็นวิชาที่สำคัญมากวิชาหนึ่งในสาขาวิชาคอมพิวเตอร์ เพราะการได้เข้าใจถึงโครงสร้างข้อมูลแต่ละชนิด ย่อมทำให้เราเข้าใจถึงตรรกะเกี่ยวกับวิธีการสร้าง การดึงข้อมูลออกมาใช้งาน และการเข้าถึงข้อมูลอย่างรวดเร็ว เพื่อนำขั้นตอนวิธีดังกล่าวมาแก้ไขปัญหที่ยุ่งยากซับซ้อนโดยเฉพาะอย่างยิ่ง การพัฒนาโปรแกรมให้มีประสิทธิภาพ [3]p.ปกหลัง
คลิ๊ปสอนโครงสร้างข้อมูล โดย รศ.ดร.สมชาย ประสิทธิ์จูตระกูล
หัวข้อ (Topics)
+ การโปรแกรม (Programming)
+ อาร์เรย์ (Array)
+ สแตก (Stack)
+ คิว (Queue)
+ ลิงค์ลิสต์ (Linked List)
+ ทรี (Tree)
+ กราฟ (Graph)
+ การค้นหา (Searching)
+ การจัดเรียง (Sorting)
ความหมายของโครงสร้างข้อมูล
โครงสร้างข้อมูล (Data Structure) คืออะไร
คือ รูปแบบของการจัดระเบียบของข้อมูล ซึ่งมีอยู่หลายรูปแบบ เช่น เขตข้อมูล(Field), แถวลำดับ(Array), ระเบียน(Record), ต้นไม้(Tree), ลิงค์ลิสต์(Link List) เป็นต้น (ทักษิณา สวนานนท์, 2544, หน้า 161) [4]p.12
คือ รูปแบบวิธีการจัดระเบียบของข้อมูลที่ได้จากการดำเนินการทางคณิตศาสตร์(Operations) เพื่อให้สามารถจัดการกับข้อมูลที่ใช้กับระบบคอมพิวเตอร์ได้ [4]p.12
คือ การรวบรวมข้อมูลเป็นกลุ่มอย่างมีรูปแบบ เพื่อให้การนำข้อมูลกลับมาใช้ หรือประมวลผลอย่างมีประสิทธิภาพ ด้วยขั้นตอนวิธีที่หลากหลาย แล้วนำเสนอได้อย่างถูกต้องรวดเร็วตามลักษณะงานที่ต้องการ
คือ การนำกลุ่มของข้อมูลขนาดใหญ่มาจัดรูปแบบ เพื่อให้เครื่องประมวลผลและแสดงผลอย่างมีขั้นตอน โดยเริ่มจากการรวบรวม เพิ่ม ลบ หรือเข้าถึงข้อมูลแต่ละรายการ
หน่วยของข้อมูลที่ถูกจัดรูปแบบตามแนวคิด "โครงสร้างข้อมูล (Data Structure)"
- บิท (Bit) คือ ข้อมูลที่มีขนาดเล็กที่สุด เป็นข้อมูลที่เครื่องคอมพิวเตอร์เข้าใจ และใช้งานได้ ได้แก่ 0 หรือ 1
- ไบท์ (Byte) หรือ อักขระ (Character) คือ ตัวเลข หรือ ตัวอักษร หรือ สัญลักษณ์พิเศษ จำนวน 1 ตัว
- ฟิลด์ (Field) หรือ เขตข้อมูล คือ ไบท์ หรือ อักขระตั้งแต่ 1 ตัวขึ้นไปรวมกันเป็นฟิลด์ เช่น เลขประจำตัว หรือ ชื่อพนักงาน
- เรคคอร์ด (Record) หรือระเบียน คือ ฟิลด์ตั้งแต่ 1 ฟิลด์ขึ้นไป ที่มีความสัมพันธ์เกี่ยวข้องกันมารวมกัน
- ไฟล์ (File) หรือ แฟ้มข้อมูล คือ หลายเรคคอร์ดมารวมกัน เช่น ข้อมูลที่อยู่นักเรียนมารวมกัน
- ฐานข้อมูล (Database) คือ หลายไฟล์ข้อมูลมารวมกัน เช่น ไฟล์ข้อมูลนักเรียนมารวมกันในงานทะเบียน แล้วรวมกับไฟล์การเงิน
เว็บเพจที่เกี่ยวข้อง
+ แนะนำหนังสือ
+ ซูโดโค้ด (Pseudocode)
+ การเขียนโปรแกรม เช่น การเรียงเลข 3 ตัว
ตัวอย่างข้อมูล
ภาษาปาสคาล
r : real;
i : integer;
c : char;
s : string;
s20 : array[1..20] of char;
ภาษาซี
bool b; b = true;
char c; c = 'a';
int ar1[30]; ar1[0]=555;
int ar2[3]={55,66,77};
ภาษาจาวา
// boolean, char
// byte, short, int, long
// float, double
ภาษาวีบี
' 17 type : boolean, byte, char, date
' decimal, double, integer, long, object
' sbyte, short, single, string, uinteger
' ulong, user-defined, ushort
' s คือ signed และ u คือ unsigned
ภาษาจาวาสคริปต์

ศัพท์เทคนิค (Technical Terms)
  1. สำนวน (phrase) : a picture is worth a thousand words [2]p.1
  2. โครงสร้างข้อมูลพื้นฐาน ประกอบด้วยแบบของข้อมูลเบื้องต้น คือ 1)บิท(Binary) 2)อักขระ(Character) 3)ฟิลด์(Field) 4)เรคคอร์ด(Record) 5)ไฟล์(File) 6)ฐานข้อมูล(Database) [4]p.12
  3. วิเคราะห์ปัญหา (Problem Analysis) คือ การแยกปัญหาใหญ่ออกเป็นส่วน เพื่อนำไปสู่การแก้ปัญหาแต่ละส่วน
  4. อัลกอริทึม (Algorithm) (มีความเป็นนามธรรมอยู่ในตัวเป็นธรรมชาติ)
    คือ กลุ่มของขั้นตอนหรือกฎเกณฑ์ที่จะนำพาไปสู่การแก้ปัญหา [3]p.37
    คือ ขั้นตอนวิธีที่ประกอบด้วยชุดคำสั่งเป็นขั้นเป็นตอนที่ชัดเจน และรับประกันว่าเมื่อได้ปฏิบัติถูกต้องตามขั้นตอนจนครบก็จะได้ผลลัพธ์ที่ถูกต้องตามต้องการ [3]p.37
    คือ รูปแบบของการกำหนดการทำงานอย่างเป็นขั้นตอน ซึ่งผ่านการวิเคราะห์และแยกแยะ เพื่อการแก้ปัญหาต่าง ๆ ตามลำดับขั้น อาจเลือกใช้ภาษาไทยหรือภาษาอังกฤษตามความถนัด เพื่อนำเสนอขั้นตอนของกิจกรรมก็ได้ [4]p.17
  5. รหัสเทียม หรือซูโดโค้ด (Pseudo Code)
    รหัสเทียม คือ รหัสจำลองที่ใช้เป็นตัวแทนของอัลกอริทึม โดยมีถ้อยคำหรือประโยคคำสั่งที่เขียนอยู่ในรูปแบบของภาษาอังกฤษที่ไม่ขึ้นกับภาษาคอมพิวเตอร์ใดภาษาหนึ่ง [3]p.37
    รหัสเทียม คือ การแสดงขั้นตอนวิธีการที่ใช้ภาษาเขียนที่เข้าใจได้ง่าย อาจใช้ภาษาไทยหรือภาษาอังกฤษก็ได้ขึ้นอยู่กับความสะดวกของผู้เขียนและกิจกรรมที่จะนำเสนอ มักใช้รูปแบบคล้ายประโยคภาษาอังกฤษเพื่ออธิบายรายละเอียดของอัลกอริทึม
  6. ผังงาน (Flowchart)
    ผังงาน คือ การแสดงขั้นตอนวิธีการที่ใช้สัญลักษณ์ที่เข้าใจได้ง่าย แต่ให้รายละเอียดได้น้อยกว่า
    ผังงาน คือ รูปภาพ (Image) หรือสัญลักษณ์(Symbol) ที่ใช้เขียนแทนขั้นตอน คำอธิบาย ข้อความ หรือคำพูด ที่ใช้ในอัลกอริทึม (Algorithm) เพราะการนำเสนอขั้นตอนของงานให้เข้าใจตรงกัน ระหว่างผู้เกี่ยวข้อง ด้วยคำพูด หรือข้อความ ทำได้ยากกว่า [#]
  7. การโปรแกรมโครงสร้าง (Structured Programming) คือ การกำหนดขั้นตอนให้เครื่องคอมพิวเตอร์ทำงานโดยมีโครงสร้างการควบคุมพื้นฐาน 3 หลักการ ได้แก่ 1)การทำงานแบบตามลำดับ(Sequence) 2)การเลือกกระทำตามเงื่อนไข(Decision หรือ Selection) และ 3)การทำงานแบบทำงานซ้ำ (Repetition หรือ Iteration หรือ Loop) #
  8. โอเปอเรชั่น (Operation) คือ การกระทำที่สามารถทำกับโครงสร้างนั้น เช่น โอเปอเรชั่นของอาร์เรย์ ได้แก่ 1)การท่องเข้าไป (Traversal) 2)การค้นหาข้อมูลที่ต้องการ(Searching) 3)การแทรกข้อมูลใหม่(Insertion) 4)การลบข้อมูล (Deletion) 5)การเรียงกลับหลัง(Reversing) 6)การเรียงลำดับ(Sorting) [1]p.14
  9. นามธรรม (Abstract) คือ เป็นแนวทางพื้นฐานของมนุษย์ที่ใช้จัดการกับความซับซ้อน (Grady Booch) [3]p.41 โดยเรื่องราวของนวนิยายเป็นจินตนาการในหัวของผู้เขียนถือเป็นนามธรรม เมื่อถ่ายทอดผ่านตัวแทน (Representation) ทางหนังสือด้วยภาษาต่าง ๆ ก็จะออกมาเป็นรูปธรรม ดังนั้นการเขียนโปรแกรมต้องเริ่มต้นด้วยนามธรรม หรือจินตนาการจัดการความซับซ้อนก่อนนำเสนอเป็นรูปธรรม เพื่อประมวลผล
  10. ชนิดข้อมูลนามธรรม (Abstract Data Type) คือ เครื่องมือกำหนดโครงสร้างข้อมูลที่ประกอบด้วยชนิดของโครงสร้างข้อมูล รูปแบบการดำเนินการ หรือแยกได้ 3 ส่วนคือ รูปแบบข้อมูล (Element) โครงสร้าง (Structure) และ การดำเนินการ (Operations) [4]p.25
  11. โปรแกรม (Program) คือ ตัวแทนของอัลกอริทึม
  12. โปรเซส (Process) คือ กิจกรรมที่ประมวลผลตามขั้นตอนของอัลกอริทึม
  13. วากยสัมพันธ์ (Syntax) คือ โครงสร้างทางไวยกรณ์ (Grammar) หรือ กฎเกณฑ์ของภาษา
  14. รวมนิยามศัพท์จาก Glossary : http://www.thefreedictionary.com
    array : A group of memory elements accessed by one or more indices.
    set : determine the arrangement of (data) for storage and display
    hash function : which assigns a data item distinguished by some "key" into one of a number of possible "hash buckets" in a hash table.
    linked list : computing a list in which each item contains both data and a pointer to one or both neighbouring items, thus eliminating the need for the data items to be ordered in memory.
    stack : A section of memory and its associated registers used for temporary storage of information in which the item most recently stored is the first to be retrieved.
    queue : A data structure from which the first item that can be retrieved is the one stored earliest.
    tree : A structure for organizing or classifying data in which every item can be traced to a single origin through a unique path.
    graph : A diagram representing a system of connections or interrelations among two or more things, as by a number of distinctive dots or lines.
    search : To move around in, go through, or look through in an effort to find something.
    sort : An operation that arranges data in a specified way: did an alphabetic sort on the columns of data.

+
คำที่น่าสนใจ
+ Decimal คือ เลขฐาน 10 ที่ใช้เลขระหว่าง 0 - 9
+ Binary คือ เลขฐาน 2 ที่ใช้เลขเพียง 2 ตัว คือ 0 กับ 1
+ Metric System คือ มาตราวัดที่ถูกกำหนดโดย International System of Units (SI)
+ IEC คือ คณะกรรมมาธิการระหว่างประเทศว่าด้วยมาตรฐานสาขาอิเล็คทรอเทคนิค
+ JEDEC คือ สภาวิศวกรรมอุปกรณ์อิเล็กตรอนร่วม #

Movie Godzilla 1998 : size does matter
https://www.youtube.com/watch?v=BdVF74zEEfE
การโปรแกรม (Programming)

การพัฒนาโปรแกรมประกอบด้วยขั้นตอนพื้นฐาน 7 ขั้นตอน [3]p.19
1. กำหนดปัญหา (Define the Problem)
2. ร่างรายละเอียดแนวทางแการแก้ไขปัญหา (Outline the Solution)
3. พัฒนาอัลกอริทึม (Develop Algorithm) : Flowchart, DFD, ER หรือ UML
4. ตรวจสอบความถูกต้องของอัลกอริทึม (Test the Algorithm for Correctness)
5. เขียนโปรแกรม (Programming)
6. ทดสอบโปรแกรม (Testing)
7. จัดทำเอกสารและบำรุงรักษาโปรแกรม (Document and Maintain the Program)

กรรมวิธีการออกแบบโปรแกรม (Program Design Methodology) [3]p.21 
- การออกแบบโปรแกรมแบบ Procedure-Driven
   โปรแกรมประกอบด้วย ข้อมูลนำเข้า ส่งออก มีฟังก์ชัน มีโปรแกรมย่อย
- การออกแบบโปรแกรมแบบ Event-Driven
   โปรแกรมประกอบด้วย เหตุการณ์ต่าง ๆ 
   เช่น onChange, onClick, onKeydown, onLoad, onMouseOver, onSubmit, 
- การออกแบบโปรแกรมแบบ Data-Driven
   โปรแกรมประกอบด้วย การกำหนดโครงสร้างข้อมูลเบื้องต้น เช่น ADT


การเขียนโปรแกรมแบบ Procedural และ Object-Oriented [3]p.22
- การเขียนโปรแกรมแบบบนลงล่าง (Top-Down Development)
- การออกแบบโปรแกรมในลักษณะโมดูล (Modular Design)
- การโปรแกรมเชิงวัตถุ (Object-Oriented Programming) 
คือ การโปรแกรมที่ให้ความสำคัญกับการรวมวัตถุ และกระบวนการได้ด้วยกัน 
เพื่อสืบทอด (Inheritance) หรือนำกลับมาใช้ใหม่ได้ (reused)
โดยการนำทั้งวัตถุ และกระบวนการมารวมกัน มักเก็บไว้ใน Class ซึ่งหมายถึง ต้นแบบของวัตถุ
ต.ย. โปรแกรมแบบ Top-Down ด้วยภาษา Pascal
program p01;
begin
Writeln('burin');
Writeln('rujjanapan');
end. 
ลำดับการทำงานของเครื่องหมายทางคณิตศาสตร์
เช่น + - * / ^ ( ) [3]p.164
x = 4 / 2 + 4 ^ 2 - 1 * 2 + 3 [ans=19] 
y = 36 / (2 + 4) ^ 2 - 1 * 2 + 3 [ans=2]
z = 4 / 2 + 4 ^ (2 - 1) * 2 + 3 [ans=13]
ตรวจคำตอบว่าค่าของ x, y, z คืออะไร ด้วยการกด Ctrl + A 
ต.ย. โปรแกรมแบบ Modular ด้วยภาษา Pascal
ตั้งใจจะถามนักศึกษาว่าโปรแกรมนี้เป็นอย่างไร
program mypro;
procedure xName;
begin
  Writeln('burin');
end;
begin
  xName;
end. 

ต.ย. โปรแกรมแบบ OOP ด้วยภาษา Java
class father {
String n;
private void pname () {
  n = "burin"; 
  return n;
}
}

class child extends father {
child() {
  n = "rujjanapan";
  System.out.println(pname()); // nation
}
public static void main(String[] a) {
  new child();
}
private void pname () {
  n = "nation"; 
  return n;
}
}

แสดงความแตกต่างของ
การจัดการหน่วยความจำแบบ Stack กับ Heap
การส่งค่าแบบ pass by value และ pass by reference
แอพสอนเขียนโปรแกรมด้วย Programming hub Programming hub คือ แอพพลิเคชั่นที่สอนเขียนโปรแกรมด้วยภาษาคอมพิวเตอร์ ที่มีทั้งบนแอนดรอย (Android) และไอโอเอส (iOS) และสามารถเรียนผ่านเว็บไซต์ (Learn on Web) ได้ที่ programminghub.io โดยแบ่งเนื้อหาเป็นตัวอย่างโค้ด (Program) และเนื้อหาอ้างอิง (Reference) สำหรับแอพพลิเคชั่นบนสมาร์ทโฟนจะมีบางภาษาที่สามารถทำการทดสอบเขียนโค้ด และประมวลผลได้ทันที (Playground) ปัจจุบันมีภาษาโปรแกรมให้ศึกษา ดังนี้ Python, Assembly, HTML, VB.NET, C, C++, C# (C Sharp), JavaScript, PHP, Ruby, R Programming, CSS, Java programming เป็นต้น
อัลกอริทึม (Algorithm)
อัลกอริทึม (Algorithm) คือ กลุ่มของขั้นตอนหรือกฎเกณฑ์ที่จะนำพาไปสู่การแก้ปัญหา [3]p.37
อัลกอริทึม สร้างได้หลายวิธี ได้แก่ 1) การบรรยาย (Narative Description) 2) การเขียนผังงาน (Flowchart) 3) การเขียนซูโดโค้ด (Pseudo code)

การเขียนอัลกอริทึมมีประเด็นต้องพิจารณาหลายเรื่อง
1)วัตถุประสงค์ 2)เหตุการณ์ก่อนประมวลผล 3)ค่าของพารามิเตอร์ทั้งก่อนและหลังประมวลผล 4)สิ่งที่ได้หลังประมวลผล 5)ลำดับเหตุการณ์ระหว่างประมวลผล
+ http://www.thaiall.com/datastructure/pseudocode.htm

ต.ย. อัลกอริทึมที่ 1 : ต้มมาม่า [3]p.25
1. หามาม่าไว้ 1 ซอง
2. ฉีกซองมาม่าและเทลงถ้วยเปล่า
3. ฉีกซองเครื่องปรุง แล้วเทลงถ้วยเดิม
4. ต้มน้ำให้ร้อนได้ที่ แล้วเทลงถ้วย
5. ปิดฝาไว้ 3 นาที
6. เปิดฝา แล้วรับประทาน
คำถาม : ต้มมาม่า
1. มีขั้นตอนใดสลับกันได้
2. ถ้าเปลี่ยนข้อความ จะเปลี่ยนอย่างไร
3. ถ้าทำหลายถ้วยจะทำอย่างไร

โจทย์ใหม่ : มี 3 คน หาว่าใครอายุมากที่สุด และเป็นเท่าใด
ต.ย. อัลกอริทึมที่ 2 : หาค่าเฉลี่ย ใช้ Pseudo Code 
1. set variable
2. loop
   1. read number into variable
   2. add number to total
   3. increase counter
3. end loop
4. set average = total / counter
5. print average

คำถาม : หาค่าเฉลี่ย
1. เขียนเป็นภาษาไทยอย่างไร
2. แต่ละบรรทัดในจาวาคืออะไร
3. สลับบรรทัดใดในจาวาได้บ้าง
4. ไม่มีตัวแปร avg จะได้หรือไม่

1.


2.



3.
4.
5.
ภาษาจาวา : หาค่าเฉลี่ย
byte x;
int i = 0;
int total = 0;
while (i < 5) {
  x = System.in.read();
  total = total + x;
  i++;
}
double avg = total/i;
System.out.println(avg);
อัลกอริทึมแสดงการใช้เครื่องคิดเลขเพื่อหาผลรวมค่าสินค้า [12]p.19
turn on calculator
clear calculator
repeat the following instructions
   key in baht amount 
   key in decimal point (.)
   key in satang amount
   press addition (+) key
until all prices have been entered
write don total price
turn off calculator
เปิดเครื่องคิดเลข
เคลียร์ค่าเริ่มต้นใหม่
ลูปทำซ้ำ
   กรอกจำนวนเงินบาท
   กรอกจุดทศนิยม
   กรอกจำนวนสตางค์
   กดปุ่มบวกเพื่อรวมค่าตัวเลข
กลับไปจุดเริ่มต้นลูป จนกระทั่งกรอกค่าตัวเลขจนครบ
พิมพ์ยอดรวมราคาสินค้า
ปิดเครื่องคิดเลข
กรณีตัวอย่าง : max ของเลข 2 จำนวน [wichep w.11.4]
โจทย์ 
จงคำนวณหาค่ามากที่สุดระหว่างตัวเลข 2 จำนวน
ที่รับเข้าทางแป้นพิมพ์ และแสดงผลลัพธ์ทางจอภาพ

วิเคราะห์เงื่อนไข
- จำนวนที่หนึ่ง มากกว่า จำนวนที่สอง
- จำนวนที่สอง มากกว่า จำนวนที่หนึ่ง
- ทั้งสองจำนวนเท่ากัน

การออกแบบกระบวนการ
- รับค่า
- เปรียบเทียบทั้ง 3 กรณี
- แสดงผลสำหรับแต่ละกรณี

คำถาม : ถ้าเขียนให้นั้นลงจะเขียนอย่างไร
อ.วิเชพ ใช้ตัวอย่างเป็นภาษาเบสิก บน VB
sub form_load()
dim one, two as integer
one = inputbox("first number",,0)
two = inputbox("second number",,0)
if (one > two) then
msgbox "max is one"
end if
if (one < two) then
msgbox "max is two"
end if
if (one = two) then
msgbox "they are equal"
end if
end sub
' elseif and else InputBox(msg, title, default, xpos, ypos)
ปฏิบัติการพื้นฐานของเครื่องคอมพิวเตอร์ [3]p.37
1. รับข้อมูล (input device)
2. แสดงผล (output device)
3. คำนวณ (limit and sequence)
4. กำหนดค่าตัวแปร (storage)
5. เปรียบเทียบ หรือเลือกทำงาน (compare or decision)
6. ทำซ้ำ (repeation or loop)
ขั้นตอน
1. แจ้งว่ารอรับข้อมูลจากแป้นพิมพ์
2. รับข้อมูลจากแป้นพิมพ์เก็บเข้าตัวแปร
3. นำมาเปรียบเทียบกับค่าคงที่
4. เลือกประมวลผลเมื่อเป็นจริงหรือเป็นเท็จ
Barack Obama พูดเรื่อง CS ในโรงเรียน

GitHub ระบบการควบคุมรุ่นรหัสต้นฉบับ # Git คือ ระบบควบคุมรุ่นของรหัสต้นฉบับ (Source code) มีหน้าที่จัดเก็บการเปลี่ยนแปลงของรหัสต้นฉบับในโครงการ (Project) ของเรา มีการสำรอง (Backup code) และเรียกดูย้อนไปดูรุ่นต่าง ๆ ของโครงการได้ (Previous version) และดูว่าผู้พัฒนา (Developer) แต่ละท่าน ได้เพิ่ม ลบ แก้ไขบรรทัดใด เมื่อใด ผู้พัฒนาสามารถดาวน์โหลดไปติดตั้งในเครื่อง เพื่อใช้พัฒนาโครงการของตนเองได้ โดย Github คือ เครื่องบริการฝากแฟ้ม Git สำหรับการใช้งานบน Linux ติดตั้งด้วย #sudo apt-get install git หรือจะใช้งานบนวินโดว์ สามารถดาวน์โหลดได้ที่ git-scm.com
ต.ย. รับตัวเลข 2 จำนวนมาหาผลบวก แล้วแสดงผล
plus_number_in_javascript.htm
ต.ย. การหาค่า Factorial ที่ใช้ Recursion
factorial_by_javascript.htm
ต.ย. การทำซ้ำซ้อนกัน แล้วนับจำนวนรอบ
for_for_count_round.html

หน่วยความจำ (Memory)
โครงสร้างหน่วยความจำ (Memory Architecture)
การจัดสรรหน่วยความจำ (Memory Allocation)
- แบบคงที่ (Static)
- แบบเปลี่ยนแปลงได้ (Dynamic)
ตารางแฟท (FAT = File Allocatio Table)
- Directory Table
- Memory Pointer
File Attribute
- Archive file
- System file
- Readonly file
- Hidden file

โปรแกรม winhex ใช้สำหรับ FAT และ DIR


ต.ย. แฟ้ม adisinit.exe มีขนาด 35.1 KB ใช้พื้นที่ 9 Block ๆ ละ 4 KB
เพราะเครื่องนี้แบ่ง 1 Cluster มีขนาด 8 Sectors
ชนิดข้อมูลนามธรรม (Abstract Data Type : ADT)
ชนิดข้อมูลนามธรรม (Abstract Data Type) คือ เครื่องมือกำหนดโครงสร้างข้อมูลที่ประกอบด้วยชนิดของโครงสร้างข้อมูล รูปแบบการดำเนินการ หรือแยกได้ 3 ส่วนคือ รูปแบบข้อมูล (Element) โครงสร้าง (Structure) และ การดำเนินการ (Operations) [4]p.25
แบบประเภทข้อมูลตามลักษณะความสัมพันธ์ในข้อมูล
1. ข้อมูลเชิงเดี่ยว (Atomic Data)
2. ข้อมูลเชิงประกอบ (Composite Data)
ชนิดข้อมูลนามธรรม (ADT) มิใช้โครงสร้างข้อมูล [3]p.50
แต่เป็นรูปแบบระดับแนวคิดหรือรูปแบบข้อมูลเชิงลอจิคอล
1. รูปแบบข้อมูลเชิงลอจิคอล (Logical Form) เป็นการนิยามด้วย ADT
2. รูปแบบข้อมูลเชิงฟิสิคัล (Psysical Form) เป็นการนำ ADT มาใช้
ประสิทธิภาพของอัลกอริทึม (Algorithm Efficiency)
ประเด็นที่ใช้วัดประสิทธิภาพ [3]p.58
1. เวลาที่ใช้ประมวลผล (Running Time)
2. หน่วยความจำที่ใช้ (Memory Requirement)
3. เวลาที่ใช้แปลโปรแกรม (Compile Time)
4. เวลาที่ใช้ติดต่อสื่อสาร (Communication Time)
ปัจจัยที่ส่งผลต่อความเร็วในการประมวลผล
1. ความเร็วของเครื่องคอมพิวเตอร์ (CPU, Main Board)
2. อัลกอริทึมที่ออกแบบเพื่อใช้งาน
3. ประสิทธิภาพของตัวแปลภาษา
4. ชุดคำสั่งที่สั่งประมวลผลเครื่องคอมพิวเตอร์
5. ขนาดของหน่วยความจำในเครื่องคอมพิวเตอร์
6. ขนาดของข้อมูลนำเข้า และผลลัพธ์จากการประมวลผล
- การวัดประสิทธิภาพของอัลกอริทึม (Efficiency Algorihm)
คือ การวัดจากพื้นที่ทำงาน และเวลา แต่กับคอมพิวเตอร์ในปัจจุบันที่มีศักยภาพสูง การวัดประสิทธิภาพจากเวลาอาจไม่เห็นความแตกต่าง
- การวิเคราะห์บิ๊กโอ (Big-O Analysis)
คือ การวัดประสิทธิภาพของอัลกอริทึมจากความเร็วในการทำงาน โดยพิจารณาไปที่จำนวนรอบ และเวลา
ปัจจุบันมีการเปลี่ยนจาก f() มาเป็น Big-O notaion เพื่อใช้ Big-O วัดประสิทธิภาพของอัลกอริทึม
- ขั้นตอนการเปลี่ยน f() เป็น Big-O Notation [4]p.23
1. ปรับฟังก์ชันให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย คือ ตัดตัวประกอบออก ให้เหลือเพียงค่าของโพลิโนเมียน (คือ n ยกกำลัง)
f(n) = n( (n + 1) / 2 )
= ((1/2)(n ^ 2)) + (1/2(n))
= (n ^ 2) + n
2. ตัดค่าของตัวประกอบออก
= n ^ 2
3. นำฟังก์ชันมาตรฐานมาเขียนในรูปของ Big-O Notation
O(f(n)) = O(n ^ 2)
ความหมายของลอการิทึม
- ลอการิทึม (อังกฤษ: logarithm) เป็นการดำเนินการทางคณิตศาสตร์ที่เป็นฟังก์ชันผกผันของฟังก์ชันเลขชี้กำลัง
- ค่าลอการิทึมของจำนวนหนึ่งโดยกำหนดฐานไว้ให้ จะมีค่าเทียบเท่ากับ การเอาฐานมายกกำลังค่าลอการิทึม ซึ่งจะให้คำตอบเป็นจำนวนนั้น

ลูปแบบเพิ่ม 2 เท่า
for(i=1;i<1000;i*=2){ echo i; }
เช่น 1 2 4 8 16 32 64

ลูปแบบลด 2 เท่า
for(i=1;i<1000;i/=2){ echo i; }
เช่น 1000 500 250 125 62.5 31.25
ตัวอย่าง Big-O Notation

ต.ย.1 จงหาผลบวกของการบวกจำนวนที่เริ่มต้นตั้งแต่ 1 - 10
ฟังก์ชัน คือ f(n) = n( (n + 1) / 2 )
= ((1/2)(n ^ 2)) + (1/2(n))
= (n ^ 2) + n
= n ^ 2
O(f(n)) = O(n ^ 2)

ต.ย.2 จงแปลง f(n) = a*n^k + a*n^k-1 + .. a*n^0 เป็น Big-O Notation
ฟังก์ชัน คือ f(n) = a*n^k + a*n^k-1 + .. a*n^0
= n^k + n^k-1 + .. n^0 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= n^k (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(n ^ k) (เขียนในรูปของ Big-O Notation)

ต.ย.3 จงแปลง f(n) = 4n + 7 เป็น Big-O Notation [6]p.50
ฟังก์ชัน คือ f(n) = 4n + 7
= n + 7 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= n (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(n) (เขียนในรูปของ Big-O Notation)

ต.ย.4 จงแปลง f(n) = 1009 เป็น Big-O Notation [6]p.51
ฟังก์ชัน คือ f(n) = 1009
= 1009 (ปรับให้อยู่ในรูปสัมประสิทธิ์อย่างง่าย)
= 1 (ตัดค่าของตัวประกอบออก)
O(f(n)) = O(1) (เขียนในรูปของ Big-O Notation)


ดร.บุญญฤทธิ์  อุยยานนวาระ
เปรียบเทียมประสิทธิภาพของ Big-O กับความเร็วของยวดยาน ดังนี้
+ O(1) เหมือน เครื่องว๊าบ หรือเครื่องย้ายมวลสาร ไกลใกล้เท่ากัน
+ O(log n) เหมือน เครื่องบินโดยสาร 
+ O(n) - เหมือน รถฟอร์มูล่าวัน ระยะทางไกลขึ้น ก็ขับนานขึ้น
+ O(n log n) - เหมือน รถยนตทั่วไป ยิ่งไกลยิ่งช้า
+ O(n^2) - เหมือน มอร์เตอร์ไซด์ 
+ O(n^3) - เหมือน จักรยาน 
+ O(2^n) - เหมือน คนเดิน


การทำซ้ำ หรือลูป มีหลายแบบ
- ลูปแบบเชิงเส้น (Linear Loops)
- ลูปแบบลอการิธมิค (Logarithmic Loops)
- ลูปแบบซ้อน (Nested Loops)

1. ลูปแบบเชิงเส้น (Linear Loops) [3]p.59 f(n) = n for (i=0; i< n; i++)    application code f(n) = n / 2 for (i=0; i< n; i+=2)    application code 2. ลูปแบบลอการิทึม (Logarithmic Loops) f(n) = log n for (i=0; i< n; i*=2)    application code    เช่น 1 2 4 8 16 32 64 f(n) = log2n for (i=0; i< n; i/=2)    application code    เช่น 1000 500 250 125 62.5 31.25 3. ลูปแบบซ้อน (Nest Loops) 3.1 ลูปแบบซ้อนชนิดกำลังสอง (Quadratic) f(n) = n^2 for (i=0; i< n; i++) for (j=0; j< n; j++)    application code 3.2 ลูปแบบซ้อนชนิดลอการิทึมเชิงเส้น (Linear Logarithmic) f(n) = n log n for (i=0; i< n; i++) for (j=0; j< n; j*=2)    application code 3.3 ลูปแบบซ้อนกำลังสองชนิดขึ้นต่อกัน (Dependent Quadratic) f(n) = n( (n + 1) / 2 ) for (i=0; i< n; i++) for (j=0; j< i; j++)    application code
มีคำถามในโจทย์ข้อ 4 เรื่อง for ซ้อน for ที่น่าตอบ
อาร์เรย์ (Array)

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

อาร์เรย์ คือ ชุดของข้อมูลที่มีค่าเป็นแบบใดแบบหนึ่ง มีการจัดเรียงอย่างมีลำดับก่อนหลัง (Order Set) เหมือนตารางข้อมูล ประกอบด้วยช่องสำหรับเก็บข้อมูลที่เรียงต่อกัน และเรียกข้อมูลมาใช้ผ่านดัชนี (Index) ที่กำกับแต่ละช่องข้อมูล

อาร์เรย์ คือ การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวกันแทนข้อมูลสมาชิกได้หลาย ๆ ตัวในคราวเดียวกัน ด้วยการใช้เลขดรรชนี (Index) หรือซับสคริปต์ (Subscript) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนแถวลำดับนั้น ๆ [3]p.80

อาร์เรย์หนึ่งมิติ (One Dimension Array)
รูปแบบของอาร์เรย์ คือ arrayname[L:U]
arrayname คือ ชื่อของตัวแปรอาร์เรย์ เช่น x[5]
L คือ ขอบเขตล่างสุด (Lower Bound)
U คือ ขอบเขตบนสุด (Upper Bound)
จำนวนสมาชิก = U - L + 1
เช่น สมาชิกของ x[100:150] = 150 - 100 + 1 = 51 สมาชิก

อาร์เรย์สองมิติ (Two Dimension Array)
จำนวนสมาชิก = (U1 - L1 + 1) * (U2 - L2 + 1)
เช่น สมาชิกของ x[10:24,1:7] = (24 - 10 + 1) * (7 - 1 + 1) = 105 สมาชิก
ตัวอย่างอารย์เรย์ ภาษาเบสิก เช่น Dim x(7, 24) As Byte
ตัวอย่างอารย์เรย์ ภาษาซี เช่น int a[][] = new int[4][3];
ตัวแรกมักหมายถึง แถว (rows) ตัวที่สองหมายถึง หลัก (columns)
  - เมทริกซ์ คล้ายกับอาร์เรย์ 2 มิติ
  - ตำแหน่งในหน่วยความจำ
B คือ ตำแหน่ง หรือแอดเดรสเริ่มต้น (Base Address)
w คือ จำนวนช่องของหน่วยความจำที่จัดเก็บข้อมูลต่อหนึ่งสมาชิก
ตำแหน่งในหน่วยความจำ LOC(a[i]) คือ B + w (i - L)
เช่น อาร์เรย์หนึ่ง มีตำแหน่งเริ่มต้นที่ 100 ใช้จำนวนช่องต่อสมาชิก 2 ช่อง มี 30 สมาชิก
ดังนั้น LOCation = 100 + 2 (30 - 0) = 160


+ Javascript : data-structures-the-string-object
+ Javascript : data-structures-the-array-object

อาร์เรย์สามมิติ
Microsoft Developer Network
เซต (set) เซต (set) คือ ชุดของข้อมูลในแบบที่ไม่อนุญาตให้ซ้ำกัน และไม่เรียงลำดับ จึงมีการใช้เซตมาช่วยในการตรวจสอบการซ้ำของข้อมูล
ตัวอย่างของเซต
วันในสัปดาห์ เดือนในหนึ่งปี ปีนักษัตร เพศ ตำแหน่งทางวิชาการ รายชื่ออำเภอในจังหวัด อาชีพ เชื้อชาติ สัญชาติ
// Set in Java Language
Set<Integer> numbers = new TreeSet<Integer>();
numbers.add(2);
numbers.add(5);
System.out.println(numbers); // "[2, 5]"
System.out.println(numbers.contains(7)); // "false"
System.out.println(numbers.contains(5)); // "true"
System.out.println(numbers.add(5)); // "false"
System.out.println(numbers.size()); // "2"
int sum = 0;
for (int n : numbers) { sum += n; }
System.out.println("Sum = " + sum); // "Sum = 7"
numbers.addAll(Arrays.asList(1,2,3,4,5));
System.out.println(numbers); // "[1, 2, 3, 4, 5]"
numbers.removeAll(Arrays.asList(4,5,6,7));
System.out.println(numbers); // "[1, 2, 3]"
numbers.retainAll(Arrays.asList(2,3,4,5));
System.out.println(numbers); // "[2, 3]"

+ https://th.wikipedia.org
เรคคอร์ด (Record)
ระเบียนข้อมูล หรือเรคคอร์ด คือ ชุดของข้อมูลที่รวมเอาหลายเขตข้อมูล
ที่สัมพันธ์กันไว้ด้วยกัน และแบ่งออกเป็นแถวอย่างชัดเจน


ตารางข้อมูลในฐานข้อมูล NorthWind ประกอบด้วย 8 ตาราง คือ Categories, Customers, Shippers, Products, Orders, Order Details, Employees, Suppliers แบบฝึกหัด : จงเขียนความสัมพันธ์ระหว่างตารางทั้ง 8 ตาราง

สแตก (Stack) สแตก (Stack) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าทีหลังและนำออกก่อน มักเรียกว่าไลโฟ (LIFO = Last in First out) อาจมองว่าข้อมูลเข้าใหม่จะมาเรียงต่ออยู่ด้านบน หากเรียกใช้ก็นำด้านบนสุดออกไปก่อน ดังนั้นข้อมูลที่เข้ามานานที่สุด จะอยู่ล่างสุด และจะอยู่ในสแตกนานที่สุด
- Push คือ เพิ่มข้อมูลลงสแตก [3]p.137
- Pop คือ นำข้อมูลบนสุดไปใช้ และลบออกจากสแตก
- Stack Top คือ นำข้อมูลบนสุดไปใช้ แต่ไม่ลบออกจากสแตก
- Infix คือ นิพจน์ทางคณิตศาสตร์ทั่วไปที่เราใช้กัน [3]p.159
- Postfix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หลังโอเปอแรนต์ เช่น AB+
- Prefix คือ นิพจน์ที่โอเปอเรเตอร์อยู่หน้าโอเปอแรนต์ เช่น +AB

javascript/1674-javascript-data-structures-stacks-queues-and-deques.html

อาจกล่าวอีกอย่างได้ว่า
- ตัวดำเนินการ คือ เครื่องหมายทางคณิตศาสตร์ (Operator)
- ตัวถูกดำเนินการ คือ สัญลักษณ์หรือตัวแปร (Operand)
- Infix คือ ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ
- Postfix คือ ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ
- Prefix คือ ตัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ

กฎเกณฑ์สำหรับการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix [3]p.160
ขั้น 1. ใส่เครื่องหมายวงเล็บให้ทุกนิพจน์ แยกลำดับการคำนวณ เช่น คูณหาร มาก่อน บวกลบ
ขั้น 2. เปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้เป็น Postfix เริ่มจากวงเล็บในสุดก่อน
ขั้น 3. ถอดวงเล็บออก
ฟังก์ชันที่เกี่ยวกับสแตก [3]p.143
1. Create Stack คือ สร้างหัวสแตก
2. Push Stack คือ เพิ่ม
3. Pop Stack คือ ดึงออก
4. Stack Top คือ อ่านบนสุด
5. Empty Stack คือ ตรวจการว่าง
6. Full Stack คือ ตรวจการเต็ม
7. Stack Count คือ นับสมาชิก
8. Destroy Stack คือ ลบข้อมูลและหัวสแตก
infixpostfixprefix ?
A * B + C / D A B * C D / + + * A B / C D
A * (B + C) / D A B C + * D / / * A + B C D
A * (B + C / D) A B C D / + * * A + B / C D
การเปลี่ยนจาก postfix เป็น prefix
1. มองหาคู่ operand
2. ย้าย operator จากด้านหลังมาอยู่ด้านหน้า
3. ย้ายจนกว่าจะครบทุกคู่
กฎเกี่ยวกับการแปลง infix เป็น postfix
1. ถ้า input เป็น operand ให้ออกเป็น postfix
2. ถ้า input เป็น operator แล้ว stack ว่างให้ลง stack
3. ถ้า input มีลำดับสำคัญกว่าใน stack ให้ลง stack
4. ถ้า input สำคัญน้อยกว่าใน stack ย้าย operator ใน stack ไปต่อท้าย postfix

ลำดับการประมวลผล
ความสำคัญอันดับแรก : วงเล็บ
ความสำคัญอันดับที่สอง : ยกกำลัง
ตวามสำคัญอันดับที่สาม : คูณ หาร
ความสำคัญอันดับที่สี่ : บวก ลบ
ต.ย. 1 แปลง A - B / C เป็น Postfix
ขั้นตอนที่ 1 :
A - (B / C)
ขั้นตอนที่ 2 :
A - (BC /)
A(BC/)-
ขั้นตอนที่ 3 :
ABC/-
โจทย์ให้ฝึกแปลงจาก infix เป็น postfix
1. a + b - c * d / e - f + g * h
2. a * b - c * d + e - f + g * h
3. a + b * c * d / (e * f) * g + h
4. a + b - (c * d) - e - f + g - h
5. a + (b + c) * d / e + f / g * h
6. a / b * c * d * (e - f) + g ^ h
7. (a ^ b) / c * d / e - f + g + h
8. a * b ^ c * ((d - e) - f) * g - h
9. a + b - c ^ ((d - e) - f) * (g - h)
10. a / (b + c) * (d + (e + f)) ^ g + h
+ stack_cal_postfix.xls
คิว (Queue) : #
คิว (Queue) คือ โครงสร้างข้อมูลเชิงเส้น มีลักษณะเป็นแถวเรียงต่อกัน ซึ่งมีลักษณะแบบเข้าก่อนออกก่อน (FIFO : First In First Out)
คิว (Queue) คือ ชุดของข้อมูลที่เรียงต่อกัน และจัดลำดับการเก็บข้อมูลแบบเข้าก่อนและนำออกก่อน มักเรียกว่าไลโฟ (FIFO = First in First out) อาจมองว่าข้อมูลเข้าใหม่จะมาเรียงต่อท้าย หากเรียกใช้ก็นำข้อมูลที่เคยเข้ามาก่อนออกไปใช้ก่อน ดังนั้นข้อมูลที่เข้ามาก่อน จะอยู่หน้าสุด และพร้อมจะออกเร็วที่สุด
- ตัวอย่างของคิวที่พบได้ในปัจจุบัน เช่น แถวซื้ออาหาร รอฝากเงิน คิวรอพริ้น เป็นต้น
+ pushpop.xlsx (function pushStack, popStack, enqueue, dequeue)
ฟังก์ชันที่เกี่ยวกับคิว ประกอบด้วย enqueue, dequeue, queue front, queue rear
ลิงค์ลิสต์ (Linked List) [3]p.101
ลิงค์ลิสต์ (Linked List) หรือรายการ (List) คือ ชุดของข้อมูลที่มีการจัดเก็บข้อมูลแบบเชื่อมต่อกันเป็นเชิงเส้น แต่ละข้อมูลเรียกว่า อีลิเมนต์ (Element) หรือสมาชิก (Member) ซึ่งสมาชิกประกอบด้วย ข้อมูล (Data) และลิงค์ (Link) โดยลิงค์ของข้อมูลหนึ่งจะเชื่อมไปยังอีกข้อมูลหนึ่ง ทำให้เกิดสายการเชื่อมโยงข้อมูลที่เรียงต่อกันแบบรายการ และข้อมูลอาจประกอบด้วยหลายเขตข้อมูล
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List)
1. การแทรก (Insertion)
2. การลบ (Deletion)
3. การปรับปรุง (Updation)
4. การท่องเข้าไปในลิสต์ (Traversal)
ตัวชี้ข้อมูลด้วยภาษาปาสคาล [2]p.220
Binary Tree
type
nodeptr = ^trnode;
trnode = record
data : integer;
leftptr : nodeptr;
rightptr : nodeptr;
end;

ตัวชี้ข้อมูลด้วยภาษาซี [3]p.193
Abstract Data Type ของ คิว
typedef struct node {
void* dataptr;
struct node* next;
} QUEUE_NODE;

typedef struct {
QUEUE_NODE* front;
QUEUE_NODE* rear;
int count;
} QUEUE;

QUEUE* createQueue (void);
bool enqueue (QUEUE* q, void* itemptr);
สร้างคิว [2]p.221
var root : nodeptr;
begin
maket(root);

procedure maket(var t:nodeptr);
begin
new(t);
t^.data := 123;
t^.leftptr := nil;
t^.rightptr := nil;
end;
สร้างคิว
QUEUE* createQueue (void) {
QUEUE* q;
q = (QUEUE*) malloc (sizeof (QUEUE));
if (q) {
q->front = NULL;
// node ชี้ตัวแรก
q->rear = NULL;
// node ชี้ตัวสุดท้าย
q->count = 0;
}
}
เพิ่มข้อมูลในคิว [2]p.224
new(n);
inserted := false;
o := t;
while not inserted do begin
if num <= o^.data then
if o^.leftptr <> nil then
o := o^.leftptr;
else begin
o^.leftptr := n;
inserted := true;
end
else
if o^.rightptr <> nil then
o := o^.rightptr;
else begin
o^.rightptr := n;
inserted := true;
end;
end;
n^.data := num;
n^.leftptr := nil;
n^.rightptr := nil;
เพิ่มข้อมูลในคิว
bool enqueue (QUEUE* q, void* itemptr) {
QUEUE_NODE* newptr;
if (!(newptr = (QUEUE*) malloc (sizeof(QUEUE))))
return false;
newptr->dataptr = itemptr;
newptr->next = NULL;
if (q->count == 0)
q->front = newptr;
else
q->rear->next = newptr;
(q->count)++;
q->rear = newptr;
return true;
}
// Test of Linked List #1/2
class BlankNode {
  public Object data;
  public BlankNode next;
  public BlankNode(Object data) {
    this.data = data;
    this.next = null;
  }
  public String toString() { 
    return data.toString(); 
  }
}
ทรี (Tree)
ทรี 3 ชนิด
1. ไบนารีเสิร์ชทรี (Binary Search Tree)
คือ ทรีที่มีโหนดในซับทรีด้านซ้ายน้อยกว่ารูทโหนด และโหนดในซับทรีด้านขวามีค่ามากกว่าหรือเท่ากับรูทโหนด และซับทรีต้องมีคุณสมบัติเป็นไบนารีเสิร์ชทรี
2. เอวีแอลเสิร์ชทรี (AVL Search Tree)
คือ ทรีที่คิดค้นโดย G.M.Adelson-Velskii และ E.M.Landis โดยทรีแบบนี้จะมี ความสูงของซับทรี มาหักลบกันแล้วต้องมีค่าไม่มากกว่า 1
3. ฮีพทรี (Heap Tree)
คือ ไบนารีทรีแบบสมบูรณ์หรือเกือบสมบูรณ์ ซึ่งโหนดพ่อจะมีค่ามากกว่าหรือเท่ากบับซับทรีด้านซ้าย และด้านขวา
แนวคิดพื้นฐานของทรี [3]p.211
- โหนดราก (Root Node) คือ โหนดแรก เริ่มต้นที่อยู่บนสุด
- โหนดพ่อ (Parents) คือ โหนดที่มีลูก
- โหนดลูก (Children) คือ โหนดที่มีพ่อ
- โหนดพี่น้อง (Siblings) คือ โหนดเป็นพี่น้อง และนับแยกครอบครัว
- โหนดใบ (Leaf Node) คือ โหนดที่อยู่ปลายสุด
- ดีกรีทั้หมดของทรี คือ ที่มีฐานะเป็นลูกทั้งหมด
- ดีกรีทั้หมดของพ่อ A คือ ที่มีฐานะเป็นลูกทั้งหมดของ A
- ระดับความสูง (Level) คือ จำนวนชั้นของทรี

Binary Search Tree


Heap Tree
กรณีตัวอย่างของทรี (Tree application)
กราฟ (Graph) กราฟ (Graph) คือ ชุดของข้อมูลที่มีการจัดเก็บข้อมูลแบบไม่ใช่เชิงเส้น ข้อมูลจะมีความสัมพันธ์กันแบบเชื่อมโยง (Network) โดยแทนหน่วยข้อมูลด้วยโหนด (Node) และเชื่อมโยงโหนดด้วยเอดจ์ (Edge)
การจัดเก็บข้อมูลในกราฟ
1. เมทริกซ์ประชิด (Adjacency Matrix)
2. ลิสต์ประชิด (Adjacency List)

- ดีกรี (Degree) คือ จำนวนของเวอร์เท็กซ์ประชิด
- เอาต์ดีกรี คือ เส้นที่ออกจากเวอร์เท็กซ์
- อินดีกรี คือ เส้นที่เข้ามายังเวอร์เท็กซ์
- เส้นทาง (Path) คือลำดับของเวอร์เท็กซ์ที่ประชิดต่อกันไปยังตัวถัดไป
- เอดจ์ (Edges) คือ เส้นที่เชื่อมระหว่างเวอร์เท็กซ์ แบบไม่มีทิศทาง
- อาร์ค (Arcs) คือ เส้นที่เชื่อมระหว่างเวอร์เท็กซ์ แบบมีทิศทาง
- เวอร์เท็กซ์ (Vertex) คือ โหนด
V = {A,B,C,D,E}

+ http://www.chanthaburi.buu.ac.th/~thararat/
+ http://piyapan-aod.blogspot.com/2009/03/graph.html
กรณีตัวอย่างของกราฟ (Graph application)
การค้นหา (Searching) การค้นหา (Searching) คือ การดำเนินการที่มีการใช้คำค้น (Keyword) หรือวัตถุหนึ่ง (Object) ที่อาจอยู่ในรูปแบบใด ๆ เข้าไปค้นในกลุ่มข้อมูล (Data) หรือกลุ่มวัตถุที่อาจอยู่ในรูปแบบใด ๆ อาทิ ข้อความ รูปภาพ ภาพเคลื่อนไหว เสียง หรือโปรแกรม เพื่อให้ได้ข้อมูลที่เกี่ยวข้อง หรือตำแหน่งข้อมูลที่ต้องการ
ปัจจัยที่ทำให้ค้นหาข้อมูลได้เร็ว
1. โครงสร้างข้อมูลที่เก็บข้อมูล
2. รูปแบบการเก็บข้อมูล
3. การทำงานกับข้อมูล ทั้ง Insert, Delete และ Update
+ http://www.bus.rmutt.ac.th/~suwat/DataStructure/Searching.ppt [expire]
+ http://www.thaiall.com/search.htm
การเรียงลำดับข้อมูล (Sorting) การเรียงลำดับข้อมูล (Sorting) คือ การนำชุดข้อมูลมาดำเนินการประมวลผลให้ได้ชุดข้อมูลใหม่ที่มีการจัดเรียงใหม่ ซึ่งผลการจัดเรียงอาจเรียงข้อมูลจากน้อยไปมาก (Ascending) หรือมากไปน้อย (Descending)
สำหรับอธิบายการจัดเรียงแบบน้อยไปมาก เป็นการเริ่มต้น
- แบบเลือก (Selection Sort) O(n2)
คือ การสแกนหาค่าน้อยที่สุด แล้วสลับตำแหน่งกับตัวแรก [javascript]
- แบบฟองสบู่ (Bubble Sort) [javascript]
คือ เริ่มโหนดสุดท้าย แล้วลอยขึ้นเป็นตัวแรก หากพบตัวใดน้อยกว่าก็จะสลับหน้าที่ในการลอยขึ้นมา
- แบบแทรก (Insertion Sort)
คือ การเปรียบเทียบค่ากับตำแหน่งถัดไป หากพบค่าใหม่ก็จะนำมาแทรกในตำแหน่งที่เหมาะสม เหมือนการเรียงไพ่
- แบบฮิพ (Heap Sort)
คือ การย้าย root note ไปอยู่ตำแหน่งสุดท้าย แล้วทำการ reheap ใหม่
- แบบควิค (Quick Sort)
คือ การจัดเรียงคล้าย Bubble Sort ที่มีการ exchange แต่แบบนี้จะแบ่งส่วนเป็น Partition โดยข้อมูลแบ่งได้ 3 ส่วนคือ 1)ค่า pivot สำหรับแบ่งส่วน 2)ค่าที่น้อยกว่า pivot 3)ค่าที่มากกว่า pivot
1)ก่อนดำเนินการจะนำค่า Pivot Key ตัวแรก และค่าแรก และค่าสุดท้ายมาเรียกให้ถูกต้องก่อน
2)หลังจากนั้น จะย้าย Pivot Key ตัวแรก สลับกับค่าแรก และให้ตัวที่อยู่ถัดค่าแรกเรียกว่า sort left และตัวสุดท้ายเรียกว่า sort right
3)ย้าย sort left ไปทางขวา แล้วย้าย sort right มาทางซ้าย จะหยุดเมื่อ sort left มากกว่า pivot key และ sort right น้อยกว่า pivot key แล้วสลับทั้ง 2 ค่า พร้อมเลื่อนต่อด้วยหลักการเดิม
4)ก่อนเสร็จสิ้นการแบ่ง ให้ย้ายค่าที่เคยเป็นค่าแรก กับ pivot key
5)การดำเนินการหลังแบ่งส่วนแล้ว ให้เริ่มจากด้านซ้าย แล้วค่อยทำทางขวา ในขณะจัดเรียงทางซ้ายก็จะแบ่งส่วนด้วย pivot key ของด้านซ้าย และแบ่งย่อยลงไปอีก ในขณะจัดเรียงทางขวาก็จะแบ่งส่วนด้วย pivot key ของด้านขวา และแบ่งย่อยลงไปอีก ทำเรื่อยไปจนแบ่งส่วนไม่ได้ ก็จะได้ผลการจัดเรียง
การเรียงแบบนี้ปรับปรุงโดย R.C.Singleton ปีค.ศ.1969 ให้เลือกค่า Pivot Key จากค่ากลาง Median Value คือตำแหน่งที่อยู่ตรงกลาง (ตำแหน่งแรก + ตำแหน่งสุดท้าย/2 แล้วปัดเศษทิ้ง)
- แบบผสาน (Merge Sort)
คือ การจัดเรียงที่นิยมใช้กับข้อมูลปริมาณมาก ที่ต้องแบ่งข้อมูลออกไปเก็บในหน่วยความจำสำรอง และนำแต่ละส่วนมาจัดเรียงในหน่วยความจำหลัก เช่น ข้อมูล 2 ล้าน 5 แสนระเบียน อาจแบ่งเป็น 3 ส่วน คือ 2 ส่วนแรกส่วนละ 1 ล้านระเบียน ส่วนสุดท้าย 5 แสนระเบียน เพราะข้อจำกัดของหน่วยความจำหลักที่ไม่อาจรับข้อมูลทั้ง 2 ล้าน 5 แสนระเบียนในคราวเดียวกัน เมื่อเรียงแต่ละส่วนจนครบทั้ง 3 ส่วนแล้ว ก็จะนำผลการจัดเรียงมารวมกัน
สำหรับการจัดเรียงจะทำการแบ่งข้อมูลจนเหลือเพียง 2 ส่วน แล้วจัดเรียงกลุ่มเล็กทุกกลุ่มจนหมด แล้วนำทั้งหมดมารวมกัน ก็จะได้ผลการจัดเรียง
S e l e c t i o n s o r t : One of the simplest sorting algorithms works as follows: First, find the smallest item in the array and exchange it with the first entry (itself if the first entry is already the smallest). Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted. This method is called selection sort because it works by repeatedly selecting the smallest remaining item. [11]p.248
ทางเลือกในการเก็บข้อมูลปริมาณมาก [blog]
[1] Solid State Drive : SSD
Apacer AS330
SATA III 6Gb/s
ขนาด 120 GB
Read Up to 495 MB/s Write Up to 385 MB/s
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 1720/120GB = 14.33 บาทต่อ GB
ราคา 1720 บาท
+ https://www.advice.co.th
14.33 บาทต่อ GB
[2] เทป backup ของ imation รุ่น LTO-6
เป็น Backup Cartridge Ultrium
เก็บธรรมดา ได้ 2.5TB บีบอัดได้ 6.25 TB
ราคาเก็บปกติต่อ 1 GB คือ 2.5TB * 1024= 2560 GB คิดต่อหน่วยได้ 4200 / 2560 = 1.64 บาทต่อ GB
ราคาเก็บบีบอัด ต่อ 1 GB คือ 6.25TB * 1024= 6400 GB คิดต่อหน่วยได้ 4200 / 6400 = 0.65 บาทต่อ GB
ราคา 4,200 บาท
ความเร็วในการอ่าน 400MB/sec (บีบอัด)
+ http://www.scts.co.th
1.64 บาทต่อ GB
[3] แผ่น DVD 4.7
เป็นแผ่น DVD-R 16x
ความจุ 4.7 GB * 50 แผ่น = 235 GB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 160/235GB = 0.68 บาทต่อ GB
ราคา 160 บาท
+ http://www.buyprinco.com
0.68 บาทต่อ GB
[4] Flash drive
ขนาด 32 GB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 320/32GB = 10 บาทต่อ GB
ราคา 320 บาท
+ https://www.advice.co.th
10 บาทต่อ GB
[5] Internal Harddisk
Toshiba รุ่น DT01ACA100
Buffer size 32 MByte
ขนาด 1TB = 1024GB ขนาด 3.5 นิ้ว
interface SATA 6.0 GB/S
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 1570/1024GB = 1.53 บาทต่อ GB
ราคา 1570 บาท
+ https://www.advice.co.th
1.53 บาทต่อ GB
[6] External Harddisk
HDD SEAGATE BACKUP PLUS
USB 3.0 ขนาด 3.5นิ้ว
ขนาด 4TB = 4096GB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 5590/4096GB = 1.36 บาทต่อ GB
ราคา 5590 บาท
+ https://www.jib.co.th
1.36 บาทต่อ GB
[8] FreeNAS Mini และ My Cloud EX4
ขนาด 8 TB = 1024 * 8 = 8192 GB
$2,249 for 24TB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 21,000/8192GB = 2.56 บาทต่อ GB
$700 for 8TB
ราคา $700 = 21,000 บาท
+ https://www.ixsystems.com
+ http://www.wdc.com
2.56 บาทต่อ GB
[7] Dropbox for business
ขนาด 1TB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 3,000/1024GB = 2.92 บาทต่อ GB ต่อปี
ราคา $99 = 3,000 บาท
+ https://www.dropbox.com
2.92 บาทต่อ GB ต่อปี
[9] Big Query กับ google cloud
ใช้เยอะก็จ่ายเยอะ
เก็บ 1 TB = 1024GB
1 TB for a full month, you pay $20
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 600/1024GB = 0.5 บาทต่อ GB ต่อเดือน
ราคา $20 = 600 บาทต่อเดือน
+ https://cloud.google.com
0.5 บาทต่อ GB ต่อเดือน
[10] Big Data Cloud Service – Starter Pack
Oracle Cloud
6 nodes with 32 OCPUs per node
256 GB RAM and 48 TB storage per node
ความจุ 6 node * 48TB = 288TB * 1024 = 294912 GB
ราคาเก็บต่อ 1 GB คิดต่อหน่วยได้ 864000/294912GB = 2.93 บาทต่อ GB ต่อเดือน
ราคา $28,800 ต่อเดือน = 864,000 บาทต่อเดือน
—
ซื้อเพิ่ม $4800 ต่อ node ต่อเดือน แต่ต้องซื้อครั้งละ 6 nodes
+ https://cloud.oracle.com/bigdata
2.93 บาทต่อ GB ต่อเดือน
งานที่มอบหมาย รายงานประกอบด้วย ปกนอก ปกใน คำนำ สารบัญ เนื้อหา สรุปเนื้อหาท้ายบท สรุปภาพรวม
1. ออกแบบคำถามคำตอบบทละ 20 ข้อ โดยเขียนคำตอบไม่น้อยกว่าข้อละ 3 บรรทัด
2. งานครอบคลุมเนื้อหาจำนวน 5 + 5 = 10 บท ซึ่งถัวเฉลี่ยได้ (กลางภาค + ปลายภาค)
3. สรุปเนื้อหาบทละ 1 หน้า รวมทั้งหมด 5 + 5 = 10 บท
4. สรุปภาพรวมเกี่ยวกับโครงสร้างข้อมูล ทั้งหมดใน 1 หน้า แล้วนำเสนอหน้าชั้น
5. เขียนด้วยมือทั้งหมด ตั้งแต่ปกนอกไปจนถึงสรุปภาพรวม
6. แนะนำหนังสือโครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์ [3] ของ โอภาส เอี่ยมสิริวงศ์
หนังสืออีกเล่มที่แนะนำ สำหรับนักศึกษาที่สนใจ เรื่อง การออกแบบอัลกอริทึม (Algorithm Design) มีหนังสือที่หัวหน้าแชร์มาในไลน์ ว่าน่าอ่าน เป็นอีกเล่มที่น่าโหลดเก็บไว้ คือ หนังสือ "การออกแบบอัลกอริทึม" ของ รศ.ดร.สมชาย ประสิทธิ์จูตระกูล ภาควิชาวิศวกรรมคอมพิวเตอร์ จุฬาลงกรณ์มหาวิทยาลัย มีจำนวน 504 หน้า ฉบับวันที่ 9 เมษายน 2553 เนื้อหาบทเรียนวิชาโครงสร้างนี้ได้รับการสนับสนุนการผลิตจาก โครงการมหาวิทยาลัยไซเบอร์ไทย สำนักงานคณะกรรมการการอุดมศึกษา กระทรวงศึกษาธิการ สงวนลิขสิทธิ์ 2553 ตามพ.ร.บ.ลิขสิทธิ์ 2537/2540 ดาวน์โหลดได้จาก ALGO-ALL-A5.pdf แต่ถ้าเป็นหนังสือ "โครงสร้างข้อมูลด้วยภาษาจาวา" [9] ท่านเขียนไว้อีกเล่มเมื่อ 2549.
ประเด็นในเครือข่ายสังคม
ในเครือข่ายสังคม มีประเด็น เป็นเรื่อง .. มากมาย
#sizeขนาด เป็น เรื่องจากภาพยนตร์เรื่อง Godzilla 1998
#speedความเร็ว เป็น เรื่องจากภาพยนตร์เรื่อง The Flash
#truthศรัทธา เป็น เรื่องข่าว วัดธรรมกาย เห็นได้ชัดว่ามีคน 2 กลุ่มคิดเห็นต่างกัน คือ เคารพกฎหมาย กับอีกกลุ่ม
#believeความเชื่อ เป็น เรื่องติดตาม วิทยา ตาสว่าง แถลงเรื่องที่สังคมมักถูกหลอก
#angryโทสะ เป็น เรื่องข่าว เหนียวไก่ ของน้องล่า หรือ เรื่องนี้ถึงครูอังคณาแน่
#sexเซ็ก เป็น เรื่องข่าว ข่าวที่ถูกแชร์กว้างขวาง อ.ปริญญา เล่าให้ฟังตอนประชุมวิชาการ
#lifeชีวิต เป็น เรื่องข่าว รายงานสด และอ่านเอกสารของดอกเตอร์ที่ยิงอีก 2 ท่าน
#loveประชดรัก เป็น เรื่องข่าว แตงโมประชดโตโน่โชคดีรอด แต่สิงห์ มุสิกพงศ์ไม่รอด
#natureธรรมชาติ เป็น เรื่องดูคลิ๊ป กระแสปลูกป่าน่าน ฟัง มาโนช ชัดเจนดีครับ (แก้กฎเพื่อมนุษย์)
#rightสิทธิ์ เป็น เรื่องข่าว กด F5 ทำ DDoS เพื่อแสดงการต่อต้าน
#topท๊อป เป็น เรื่องเรามักสนใจข่าว ข้อมูล เหตุการณ์อันเป็นที่สุด
#careerอาชีพ เป็น เรื่องเกี่ยวข้องกับอาชีพ องค์กรที่เราเกี่ยวข้อง
#meตัวเรา เป็น เรื่องเรามักกดแชร์ กดไลค์ กดเม้นเรื่องเกี่ยวกับตัวเรา หรือครอบครัว เช่น birthday
Special lecture by Prof. Dr.-Ing. habil. Herwig Unger Faculty of Mathematics and Informatics, FernUniversitat in Hagen, Germany
Topic: Pattern generation in decentralized communities

ข่าวภูทับเบิก รัฐใช้อำนาจจัดระเบียบ รื้อ 60 resort เกี่ยวข้องกับผู้ประกอบการ ลูกจ้าง และนักเที่ยว และภูเขา ซึ่งผมก็ไม่เคยไปเที่ยวนะ
เพื่อนที่เคยไปเที่ยวมาครั้งหนึ่ง บอกว่า ถ้าไม่ปลูกกะหล่ำปลีก็จะเป็นแต่เขาหัวโล้น พอโล้นก็นึกถึง ข้าวโพดที่น่าน
การจัดการข้อมูลนั้น มี 3 แบบ คือ ปล่อยตามธรรมชาติ นำมาจัดใหม่ตามกฎเกณฑ์ หรือ จัด ๆ เลิก ๆ
แหล่งอ้างอิง (Reference)
โครงสร้างข้อมูลฉบับภาษาจาวา โดย อ.สมชาย ประสิทธิ์จูตระกูล http://www.cp.eng.chula.ac.th/~somchai/ULearn/DataStructures
Source Code by Mark Allen Weiss http://users.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/
DS. with JAVA by William H. Ford & William R. Topp http://www1.pacific.edu/~wford/fordtopp/javabook/java_index.html
DS & Algo with OOP by Bruno R. Preiss, P.Eng. All http://www.brpreiss.com/books/opus5/html/book.html
Dictionary of Data Structure https://xlinux.nist.gov/dads/
โครงสร้างข้อมูลฉบับภาษาจาวา : อ.สมชาย ประสิทธิ์จูตระกูล http://www.cp.eng.chula.ac.th/~somchai/ # # # # # # # # # # # # # #
เอกสารฉบับเต็ม (Full Text)

รศ.ดร.สมชาย ประสิทธิ์จูตระกูล

Bruno R. Preiss

Mark Allen Weiss

William H. Ford

DB: พัฒณืรพี

Michael Mcmillan
เอกสารอ้างอิง
[1] นิรุธ อำนวยศิลป์, "โครงสร้างข้อมูล : การเขียนโปรแกรมและการประยุกต์", บริษัท ดวงกมลสมัย จำกัด., กรุงเทพฯ, 2548.
[2] Guy J.Hale, Richard J.Easton, "Applied Daa Structures Using Pascal", D.C.Heath and Company. Canada. 2530.
[3] โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures) เพื่อการออกแบบโปรแกรมคอมพิวเตอร์", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549.
[4] วิวัฒน์ อภิสิทธิ์ภิญโญ, อมร มุสิกสาร, "โครงสร้างข้อมูล (Data Structures)", บริษัท เอ-บุ๊ค ดิสทริบิวชั่น จำกัด., กรุงเทพฯ, 2548.
[5] เนรมิต ชุมสาย ณ อยุธยา, "เรียนรู้โครงสร้างข้อมูลและอัลกอริทึมด้วย Java", บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2550.
[6] ขนิษฐา นามี, "โครงสร้างข้อมูลและอัลกอริทึม", บริษัท ไอดีซี อินโฟ ดิสทริบิวเตอร์ เซ็นเตอร์ จำกัด., กรุงเทพฯ, 2548.
[7] ปิยทัสน์ ฉัตรวรวิทย์, "โครงสร้างข้อมูลด้วย Java", บริษัท โปรวิชั่น จำกัด., กรุงเทพฯ, 2552.
[8] Michael McMillan, "Data Structures and Algorithms with JavaScript", O’Reilly Media, Inc., USA., 2014.
[9] รศ.ดร.สมชาย ประสิทธิ์จูตระกูล, "โครงสร้างข้อมูลด้วยภาษาจาวา", ภาควิชาวิศวกรรมคอมพิวเตอร์, จุฬาลงกรณ์มหาวิทยาลัย, 2549.
[10] Loiane Groner, "Learning JavaScript Data Structures and Algorithms", Packt Publishing, 2014.
[11] วิษณุ ช้างเนียม, "คู่มือเรียนโครงสร้างข้อมูล และอัลกอริทึม", บริษัทไอดีซี พรีเมียร์, 2556.
[12] โอภาส เอี่ยมสิริวงศ์, "อัลกอริทึม และการเขียนโปรแกรมภาษา C", บริษัท ซีเอ็ดยูเคชั่น จำกัด (มหาชน), 2557.


"Imagination is more important than knowledge" - Albert Einstein
http://goo.gl/72BPC