เตรียมตัวสอบปลายภาคกันได้แล้ว

ข้อสอบปลายภาควิชาโครงสร้างข้อมูล เป็นปรนัย 60 ข้อ มีดังนี้
อาเรย์ สแตก คิว รวมประมาณ 10 ข้อ (เป็นความรู้ทั่วไปไม่มีคำนวณ)

ที่เหลืออีก 50 ข้อ คือ
ลิงค์ลิสต์ (singly linked lsit,doubly linked list)
ทรี (ศัพท์,Binary tree, การเข้าถึงข้อมูลในทรี, Binary Search Tree)
Searhcing (การค้นหา 5 วิธี)
Sorting (การเรียงลำดับ 5 วิธี :
bubble sort,selection sort,insertion sort,quick sort, shell sort)

Close your eyes you will see

Pachelbel Canon in D Original Instruments



iPhone Guitar App - Canon in D



ดูนี่ อาจช่วยให้กำลังใจสำหรับคนสู้ชีวิตได้นะ

ใกล้ชิดกับน้องอาเรย์ ..อีกนิด

มาทำความรู้จักกับอาเรย์ 3 พี่น้องกัน น้องเล็กสุดคือ อาเรย์ 1 มิติ เป็นอาเรย์ที่มีสมาชิกหลายตัวเรียงติดต่อกันไปในแนวนอน หรืออาจเรียงในแนวตั้งก็ได้ ดังภาพ a) ส่วนอาเรย์ 2 มิติ เป็นอาเรย์ที่มีลักษณะเป็นตาราง เปรียบเสมือนนำอาเรย์ 1 มิติที่มีขนาดเท่ากันมาเรียงแถวซ้อนต่อกันเป็นชั้น ดังภาพ b) ส่วนพี่ใหญ่ อาเรย์ 3 มิติ ก็ซับซ้อนไปอีกนั่นคือเหมือนการนำเอาตารางอาเรย์ 2 มิติมาเรียงซ้อนทับกันเป็นชั้น ๆ ดังภาพ c) จากภาพที่เห็นนั้นเราจะสนใจเฉพาะดัชนีที่เรียงรายกันอยู่กรอบนอกของอาเรย์แต่ละประเภท
เวลาเราเรียกชุดอาเรย์ 1 มิติ ก็ใช้รูปทั่วไปได้ว่า A(L:U) โดยที่ A คือชื่อของอาเรย์ ซึ่งเรากำหนดเองได้ แต่ขอยกตัวอย่างว่าชื่อ A ก็แล้วกัน ส่วน L คือ ดัชนีต่ำสุดของอาเรย์ และ U คือ ดัชนีสูงสุดของอาเรย์ แต่โดยปกติมักไม่ค่อยสนใจ L เท่าไร คืออาจไม่เขียนไว้ในรูปทั่วไปของชุดอาเรย์ เพราะถือว่าเริ่มที่ 0 (ศูนย์)จึงอาจเขียนรูปทั่วไปเพียง A(U) มีตำราหลายเล่มก็บอกเริ่มที่ 1 เพื่อจะได้ง่ายกับการคำนวณ ดังนั้นจากภาพ a) ก็เรียกว่าเป็นชุดอาเรย์ A(9) ซึ่งมีสมาชิกคือ A[0],A[1],A[2],A[3],A[4],A[5],A[6],A[7],A[8],A[9] มีสมาชิก 10 ตัว (เพราะนับจากสมาชิกตัวที่ศูนย์ด้วย)สังเกตด้วยนะว่าถ้าเป็นสมาชิก จะใช้วงเล็บ []เรียกว่า Square Brackets ส่วนชุดอาเรย์ใช้วงเล็บ ()ที่เรียกว่า parentheses ตัวอย่างจากภาพ a) ข้อมูลของ A[2] คือ -5 ข้อมูลของ A[7] คือ 56
ส่วนชุดอาเรย์ 2 มิติ ใช้รูปทั่วไปคือ A(L1:U1,L2:U2) ซึ่งจะเห็นว่าต้องระบุดัชนีต่ำสุดของแถวกับดัชนีสูงสุดของแถว (L1:U1) และระบุดัชนีต่ำสุดของคอลัมน์กับดัชนีสูงสุดของคอลัมน์ (L2:U2) ซึ่งซับซ้อนขึ้นกว่า 1 มิติ แต่อาจละ L1 และ L2 ไว้ก็ได้ เขียนเพียง A(U1,U2) จากภาพ b) จึงสามารถเขียนเป็นรูปทั่วไปได้ว่า A(0:9,0:9) หรือเขียนเพียง A(9,9)มีสมาชิก 100 ตัว คือ
A[0,0],A[0,1],A[0,2],A[0,3],...,A[0,9],
A[1,0],A[1,1],A[1,2],A[1,3],...,A[1,9],
A[2,0],A[2,1],A[2,2],A[2,3],...,A[2,9],
...
...
A[9,0],A[9,1],A[9,2],A[9,3],...,A[9,9]
การเขียนสมาชิกของอาเรย์ 2 มิติ จะต้องเขียนเป็นคู่ลำดับอย่างที่เห็น โดยระบุ ชื่ออาเรย์[แถว,คอลัมน์] หากระบุว่า A[3,5] ก็หมายความว่าเรากำลังจะสนใจกับสมาชิกของอาเรย์ A แถวที่ 3 คอลัมน์ที่ 5 ซึ่งเมื่อดูจากภาพจะเห็นได้ว่า A[3,5] นั้นเก็บข้อมูล 55 นั่นเอง
 
ชุดอาเรย์ 3 มิติ ใช้รูปทั่วไปคือ A(L1:U1,L2:U2,L3:U3) ในภาพ c) คือ A(0:9,0:9,0:2)หรือเขียนเพียง A(9,9,2) ซึ่งเมื่อระบุสมาชิกก็จะต้องให้ละเอียดลงไปถึงระดับความลึก เช่น A[1,4,0] หมายถึงสมาชิกแถวที่ 1 คอลัมน์ที่ 4 ชั้นที่ 0 หรือ A[5,8,2] หมายถึงสมาชิกแถวที่ 5 คอลัมน์ที่ 8 ชั้นที่ 2 หวังว่าคงทำความเข้าใจได้ไม่ยากเน้อ
 
ขอบคุณภาพจาก book.mql4.com/variables/arrays

รู้จักกับน้องอาเรย์ (Array) เค้าว่าง่ายนะ

อาเรย์เป็นการจัดเก็บข้อมูลรูปแบบหนึ่งที่ซับซ้อนมากขึ้นกว่าการจัดเก็บแบบตัวแปรธรรมดา เพราะสามารถจัดเก็บข้อมูลได้หลาย ๆ ตัว (เรียกว่าเหล่าสาวกก็ได้)จะเก็บได้กี่ตัวก็ขึ้นอยู่กับโปรแกรมเมอร์นี่ละกำหนดเอง เรียกได้ว่าเป็นการจัดเก็บแบบมีโครงสร้าง (structure) ถือเป็นโครงสร้างข้อมูลที่ง่ายที่สุด ทำความเข้าใจได้ไม่ยาก ลักษณะสำคัญของเจ้าอาเรย์ก็คือ เป็นการจัดเก็บข้อมูลโดยมีสมาชิกเรียงติดต่อกันไปในหน่วยความจำ เหมือนคอนโดที่มีห้องเรียงติด ๆ กันนั่นละ แต่ละช่องสมาชิกก็จัดเก็บข้อมูลได้ 1 ชุด นอกจากนี้สมาชิกของอาเรย์ยังต้องเก็บข้อมูลชนิดเดียวกัน เช่น ถ้าอาเรย์หนึ่ง ๆ ถูกกำหนดให้เก็บตัวเลขจำนวนเต็ม สาวกของอาเรย์นั้น ๆ ก็ต้องเก็บได้เฉพาะเลขจำนวนเต็มเท่านั้น หรือหากกำหนดให้อาเรย์สามารถเก็บได้เฉพาะตัวอักษร เหล่าสาวกของเขาก็สามารถเก็บได้เฉพาะตัวอักษรเหมือนกันทุกช่อง เหมือนคอนโดที่กำหนดให้เช่าเฉพาะผู้หญิง ก็ต้องให้อยู่ได้เฉพาะผู้หญิงเท่านั้น ผู้ชาย ตุ๊ด เกย์ อยู่บ่ได้ เมื่อสมาชิกหรือเหล่าสาวกของอาเรย์ต้องมีชนิดเดียวกัน ก็สืบเนื่องมาได้ว่าสมาชิกเหล่านั้นก็ย่อมต้องมีขนาดที่เท่ากันด้วย ขนาดในที่นี้อย่าคิดเป็นอื่น เพราะมันคือขนาดของการใช้พื้นที่ในหน่วยความจำ ซึ่งมีหน่วยเป็นไบต์ (Byte) ดังนั้นถ้าสมาชิกในอาเรย์มี 10 ช่อง แต่ละช่องใช้พื้นที่ 2 ไบต์ ก็หมายความว่า อาเรย์นี้ใช้พื้นที่ในหน่วยความจำไปทั้งสิ้น 20 ไบต์

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

ขอบคุณภาพจาก http://www.manansaini.co.cc

เรื่องเล่าของ Memory ตอน 2 (ตัวแป๊ร ตัวแปร)

หน้าที่หลัก memory คือจัดเก็บข้อมูลที่ซีพียูจะประมวลผล โปรแกรมใดต้องการใช้พื้นที่ memory ก็ต้องจับจอง (allocate) จู่ ๆ จะเข้าไปถือครองพื้นที่เอง บ่ได้หรอก เหมือนกับจะไปขายของที่ตลาดนัดก็ต้องไปขอจองพื้นที่ทำสัญญาจะขายของ แล้วจึงเอาของไปวางขายในพื้นที่ที่จองไว้ได้ การจองพื้นที่ก็เหมือนกับเราประกาศตัวแปรเตรียมไว้สำหรับข้อมูล ส่วนของที่เราเอาไปวางขายก็เหมือนข้อมูล อย่างเราเขียนโปรแกรมด้วยภาษาซี ง่าย ๆ มีการประกาศตัวแปร เช่น
int i;
float x,y;
แบบนี้ก็เป็นการประกาศขอจองพื้นที่ในหน่วยความจำไง โดยจองพื้นที่ชื่อ i  พื้นที่ชื่อ x และพื้นที่ชื่อ y เพียงแต่ว่ายังไมได้เอาข้อมูลไปเก็บไว้ เป็นการกันท่า (ที่) ไว้ก่อน

เมื่อเราเขียนโปรแกรมต่อไปอีกว่า
i = 22;
x = 98.5;
อย่างนี้ก็แปลว่ามีการเขียนบันทึกข้อมูลลงบนพื้นที่ i กับพื้นที่ x เรียบร้อยแล้ว ส่วนพื้นที่ y ยังบ่ได้ใช้

จริง ๆ แล้วพื้นที่ใน memory เนี่ยมันมีบ้านเลขที่ หมายถึง address นะ เป็นเลขฐานสิบหก เช่น 0x2034AC54, 0xC030C00 เป็นต้น การจับจองพื้นที่ก็ต้องระบุ address ที่ต้องการ แต่คงเป็นการยากที่จะต้องมาบอก มาประกาศขอพื้นที่นี้ถึงพื้นที่นั้น ให้เป็นเลขฐานสิบหก จึงกำหนดให้เป็นการประกาศเป็นชื่อตัวแปรขึ้นมาแทน แล้ว OS จะไปจัดการเบื้องหลังการถ่ายทำให้เองว่า พื้นที่ตรงไหนว่าง ก็จัดสรรให้เป็นตัวแปรตามที่ประกาศขอมาโดยอัตโนมัติ โปรแกรมเมอร์ก็ไม่ต้องเหนื่อย เห็นไม๊ว่าโปรแกรมเมอร์อย่างเรา ๆ ก็ยังไม่ถึงกับลงไปทำงานระดับ physical ซักเท่าไร

เรื่องเล่าของ Memory ตอน 1

การจัดการกับโครงสร้างข้อมูลนี่เกี่ยวข้องตรง ๆ กับ Memory เลยนะ  และ Memory ที่จะเล่าให้ฟัง (อ่าน) ต่อไปนี้ก็คือเจ้า RAM (Random Access Memory) เป็นการ์ดเล็ก ๆ ยาวไม่ถึงคืบ เสียบอยู่บนเมนบอร์ด สามารถถอดเปลี่ยนเพื่อ upgrade ได้ไม่ยาก หน้าที่ของเจ้า RAM มีไว้สำหรับจัดเก็บข้อมูลที่ถูกซีพียูเรียกมาประมวลผล ณ เวลานั้น ๆ  หากมองเข้าไปในพื้นที่ของ RAM ที่แฝงอยู่ในการ์ดแล้วต้องบอกว่าไร้รูปทรงจริง ๆ เพราะมีการจับจองพื้นที่และคืนพื้นที่ภายในนั้นอยู่ตลอดเวลา อย่างน้อย ๆ ผู้ที่จับจองพื้นที่อยู่ตลอดเวลาก็เห็นจะเป็น พี่เบิ้ม OS (windows, linux ฯลฯ) นอกจากนี้ก็เป็นพวกโปรแกรมต่าง ๆ ที่เราเปิดขึ้นมาใช้งาน อาจจะเป็นโปรแกรม office โปรแกรมเกม เปิด Browser เปิดโปรแกรมฆ่าไวรัส และเมื่อเราปิดการใช้งานส่วนใดก็จะมีการคืนพื้นที่การจับจอง memory ส่วนนั้น ๆ ให้เป็นอิสระ ในอดีต RAM มีราคาสูงมาก OS จะต้องบริหารจัดการ memory โดยหากข้อมูลใน memory ส่วนใดยังไม่ถูกเรียกใช้ทันทีก็จะนำไปฝากไว้ที่หน่วยความจำถาวรก่อน (ฮาร์ดดิสก์) ที่เรียกว่าการทำ Virtual memory ไง พอจะใช้งานก็ไปอ่านออกมาจากฮาร์ดดิสก์ ก็เขียน ๆ อ่าน ๆ กันอยู่อย่างนี้ ดังนั้นจึงมีการอ่านเขียนฮาร์ดดิสก์อยู่ตลอดเวลา (swap file) ทั้ง ๆ ที่เราก็ไม่ได้ไปทำอะไรซักหน่อย แต่นี่ก็เป็นวิธีบริหารหน่วยความจำนะจ๊ะ

ขอบคุณภาพจาก 168hours.wordpress.com

เรียนอะไรบ้าง

เรื่องที่อยู่ในขอบข่ายจะต้องศึกษาประกอบด้วยหัวข้อใหญ่ ๆ 7 หัวข้อ ตามลำดับดังนี้
1. อาร์เรย์ (Array) หรือแถวลำดับ
2. สแตก (Stack)
3. คิว (Queue)
4. ลิงค์ลิสต์ (Linked list) หรือ ลิสต์เชื่อมโยง
5. ต้นไม้ (Tree)
6. กราฟ (graph)
7. การค้นหาข้อมูล (Searching)
8. การเรียงลำดับข้อมูล (Sorting)

สิ่งที่จะต้องเรียนข้างต้น ถ้าดูรายละเอียดตามเนื้อหาแล้วจะพบว่าเป็นทฤษฏีทั้งหมด จริง ๆ แล้วลำพังเรียนแต่ทฤษฏีเวลาเรียนก็ไม่ค่อยจะพอ แต่จำเป็นต้องทำให้เห็นจริงมากกว่าจะจินตนาการ จึงต้องนำมาประยุกต์กับการเขียนโปรแกรมในภาษาใดภาษาหนึ่งก็ตามแต่ผู้เรียน อาจเป็นภาษา C, C++, Pascal ฯลฯ ขอให้เป็นภาษาระดับสูงเป็นใช้ได้ ซึ่งหากผู้เรียนเคยเรียนภาษา C มา ก็ใช้ภาษา C มาทดลองเขียนโปรแกรมแล้วยกเอาแบบโครงสร้างแต่ละชนิดมาออกแบบกันไป แต่ผู้สอนเคยพบกรณีที่นักศึกษาไม่เคยเรียนภาษาคอมพิวเตอร์ใดมาเลย ก็จำเป็นต้องสอนภาษาคอมพิวเตอร์ปนเข้าไปด้วย แล้วยกตัวอย่างให้เห็นจริง นักศึกษาที่ต้องการจะหาซื้อหนังสือตำราที่ใช้ประกอบการเรียนวิชานี้ก็ให้ดูหัวข้อไปตามนี้ ในหน้าสารบัญ แล้วดูลักษณะการเขียนว่าน่าอ่านไม๊ เห็นแล้วรู้สึกอยากอ่านก็เอาเล่มนั้นละ

ความสำคัญของวิชาโครงสร้างข้อมูล

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