หน่วยที่ 1 พื้นฐานการจัดการข้อมูล

หน่ วยท่ี 1 พื้นฐานการจดั การข้อมลู

2 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู จดุ ประสงคท์ ว่ั ไป 1.บอกความหมายของรปู แบบของขอ้ มูล ระดบั ขอ้ มูล การ จดั การขอ้ มูลได ้ 1.ยกตวั อย่างโครงสรา้ งขอ้ มลู ของระบบคอมพวิ เตอรไ์ ด ้ 2.บอกความหมายของอลั กอรทิ มึ ได ้ 3.ยกตวั อยา่ งวธิ กี ารวดั ประสทิ ธภิ าพของอลั กอรทิ มึ ได ้

3 หน่ วยท่ี 1 พ้ืนฐานการจัดการข้อมูล 1.1 ขอ้ มูล และรูปแบบของขอ้ มูล เ ค รื่อ ง ค อ ม พิว เ ต อ ร เ์ ป็ น อุป ก ร ณ์ท า ง อิเ ล็ ก ท ร อ นิ ก ส ท์ ี่ ประมวลผลดว้ ยสญั ญาณดิจติ อล สญั ญาณนีจ้ ะมีแรง ดนั ไฟฟ้ าสอง ระดบั โดยแทนดว้ ยลอจกิ สูง หรอื “1” และแทนดว้ ยลอจกิ ตํ่าหรอื “0” ขอ้ มูลลอจกิ แตล่ ะคา่ นี้ เรยี กวา่ บติ การทจี่ ะใหค้ อมพวิ เตอรเ์ ขา้ ใจขอ้ มูล ต่างๆ ไดน้ ้ันจะตอ้ งนําขอ้ มูลหลายๆ บิตมาต่อรวมกนั ใหเ้ ป็ น ขอ้ มูลที่ คอมพวิ เตอรส์ ามารถรบั รแู ้ ละเขา้ ใจได ้ เรยี กวา่ รหสั (code)

4 หน่ วยท่ี 1 พ้ืนฐานการจัดการข้อมูล 1.2 ระดบั ของขอ้ มูล และการจดั การขอ้ มูล บติ (Bit : Binary Digit) เป็ นหน่วยทเี่ ล็กทสี่ ดุ ของขอ้ มูล จะแทนดว้ ยสญั ญาณ “0” หรอื “1” ตวั อกั ขระ (Characters) เป็ นกลมุ่ ของบติ ขอ้ มูลทใี่ ชแ้ ทน ตวั อกั ขระทคี่ อมพวิ เตอรส์ ามารถเขา้ ใจได ้ ฟิ ลด ์ (Field) เป็ นกลมุ่ ของไบตข์ อ้ มูลทนี่ ํามาเรยี งตอ่ กนั ใหม้ ี ความหมายเป็ นอยา่ งใดอยา่ งหนึ่ง

5 หน่ วยท่ี 1 พ้ืนฐานการจัดการข้อมูล 1.2 ระดบั ของขอ้ มูล และการจดั การขอ้ มูล เรคอรด์ (Record) เป็ นกลมุ่ ของฟิ ลดข์ อ้ มูลทมี่ ี ความสมั พนั ธก์ นั มารวมกนั ไฟล ์ (File) หรอื แฟ้ มขอ้ มูล เป็ นกลมุ่ ของเรคอรด์ ทนี่ ํามา รวมกนั ใหอ้ ยใู่ นโครงสรา้ งเดยี วกนั

6 หน่วยท่ี 1 พ้ืนฐานการจดั การข้อมลู

7 หน่วยท่ี 1 พื้นฐานการจดั การข้อมลู การดาํ เนินการกบั ขอ้ มูลในโครงสรา้ งลกั ษณะตา่ งๆ นั้น มกั จะมกี าร จดั การ ดว้ ยวธิ กี ารตา่ งๆ ดงั นี้ • การเขา้ ถงึ เรคอรด์ (Traversing) เป็ นการตดิ ตอ่ ไปยงั เรคอรด์ ของขอ้ มลู ทตี่ อ้ งการ เพอื่ แกไ้ ขเปลยี่ นแปลงขอ้ มูลในเรคอรด์ น้ัน • การคน้ หา (Searching) เป็ นการคน้ หาขอ้ มูลหรอื เรคอรด์ ที่ ตอ้ งการ เพอื่ กระทําการใดๆ กบั ขอ้ มูลตามเงอื่ นไขทกี่ าํ หนดขนึ้ • การเรยี งขอ้ มูล (Sorting) เป็ นการจดั เรยี งขอ้ มูลหรอื เรคอรด์ ตามคา่ ทกี่ าํ หนด เชน่ เรยี งจากมากไปนอ้ ย จากนอ้ ยไปมาก

8 หน่วยที่ 1 พื้นฐานการจดั การข้อมูล การดาํ เนินการกบั ขอ้ มูลในโครงสรา้ งลกั ษณะตา่ งๆ นั้น มกั จะมกี าร จดั การ ดว้ ยวธิ กี ารตา่ งๆ ดงั นี้ • การเพมิ่ (Inserting) เป็ นการเพมิ่ หรอื แทรกขอ้ มูลหรอื เรคอรด์ ใหม่ • การลบ (Deleting) เป็ นการลบขอ้ มูลหรอื เรคอรด์ ออกไป • การรวบรวมขอ้ มูล (Merging) เป็ นการนําขอ้ มูลหรอื เรคอรด์ หลายๆ ตวั ทมี่ คี วามสมั พนั ธก์ นั มารวมกลมุ่ ใหอ้ ยใู่ นไฟลเ์ ดยี วกนั

9 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมูล 1.3 ตวั อย่างโครงสร้างข้อมลู อารเ์ รย์ (Arrays) อาร์เรย์เป็นโครงสรา้ งขอ้ มูลแบบง่ายทส่ี ุด โดยนําขอ้ มูลท่ีศกึ ษามาเรยี ง ต่อกนั เป็นลําดบั แล้วใช้ตวั เลข ในการอ้างถึงข้อมูลลําดบั นัน้ ๆ การเก็บข้อมูลใน หน่วยความจาํ จะใชต้ าํ แหน่งหน่วยความจาํ ทต่ี ดิ ๆ กนั ไป ตวั อย่างเชน่ ถา้ ให้ A เป็น ช่อื ของอาร์เรย์ ซ่ึงเก็บขอ้ มูลต่างๆ ต่อเน่ืองกนั ไป การอ้างถงึ ขอ้ มูลแต่ละส่วนจะ เขยี น เป็น A[O], A[1], A[2], A[3], ..., A[n]

10 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมูล 1.3 ตวั อย่างโครงสร้างข้อมลู โดยตวั เลขทใ่ี ชอ้ า้ งถงึ เรยี กวา่ ซบั สครปิ ต์ (subscript) หรอื อนิ เดก็ ซ์ (Index) ตวั อยา่ งเชน่ ถา้ หากเกบ็ ชอ่ื ของนกั เรยี น 5 คน จะเกบ็ ไดด้ งั น้ี

11 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู 1.3 ตวั อย่างโครงสรา้ งข้อมลู ตวั อย่างอารเ์ รย์ (Arrays)

12 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู ลิงกล์ ิสต์ (Linked Lists) เป็นโครงสรา้ งขอ้ มลู ประเภทหน่ึงทข่ี อ้ มลู ไมไ่ ดเ้ กบ็ แบบเรยี งลาํ ดบั เชน่ เดยี วกบั อารเ์ รย์ แต่ขอ้ มลู จะมี ความสมั พนั ธก์ นั ดงั ตวั อย่างตอ่ ไปน้ี ถา้ หากบริษัทขายประกนั บริษัทหน่ึงมีการเก็บขอ้ มลู เป็ นเรคอรด์ ซ่ึง ประกอบด้วยช่ือลูกค้าและช่ือผู้ขาย ประกัน ในลักษณะของตารางท่ี มี 2 คอลมั น์ แต่ละคอลมั นม์ ี 9 ช่ือ ดงั ตารางต่อไปนี้ จะพบวา่ มีรายช่ือท่ีซํา้ กนั ดว้ ย ซง่ึ การเก็บขอ้ มลู แบบนีไ้ มถ่ ือวา่ เป็นการเก็บขอ้ มลู ท่ีดที ่ีสดุ

13 หน่วยที่ 1 พื้นฐานการจดั การข้อมูล

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

15 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู หากในการพฒั นาโปรแกรมแลว้ ต้องการทราบว่า ผขู้ ายคนหน่ึงขาย ประกนั ให้กบั ลูกค้าคนใดบ้าง โปรแกรมจะต้องทําการค้นช่อื ลูกค้าแล้วหาช่อื ผูข้ าย โดยจะต้องคน้ ทุกรายการจงึ จะไดข้ ้อมูลครบ หากจดั โครงสร้างขอ้ มูล ใหมโ่ ดยใหต้ ารางชอ่ื ผขู้ ายมพี อยน์เตอรช์ ไ้ี ปทช่ี ่อื ลูกคา้ แต่ละราย สามารถเขยี น ตารางไดด้ งั น้ี

16 หน่วยท่ี 1 พื้นฐานการจดั การข้อมลู ดงั ตารางต่อไป น้ี การจดั โครงสรา้ งแบบน้ีเรยี กว่าลงิ กล์ ิสต์ ซ่งึ จะทํา ใหก้ ารคน้ หาทาํ ไดง้ า่ ยมาก

17 หน่วยที่ 1 พื้นฐานการจดั การข้อมลู ทรี (Tree) โครงสรา้ งขอ้ มลู แบบทรี เป็นโครงสรา้ งทข่ี อ้ มลู หน่ึงตวั มคี วามสมั พนั ธ์ กบั ขอ้ มลู อ่นื อกี หลายๆ ตวั ความ สมั พนั ธน์ ้ีอาจเรยี กอกี ชอ่ื หน่ึงวา่ กราฟรากไม้ (rooted tree graph)

18 Our process is easy สแตก็ (stack) เป็นโครงสรา้ งทเ่ี กบ็ ขอ้ มูลในลกั ษณะกองซอ้ นกนั เป็นระบบเขา้ ที หลงั ออกก่อน (last-in first-out LIFO) เม่อื ขอ้ มลู แรกวางลงไปแลว้ จงึ วาง ขอ้ มูลต่อไป ขอ้ มูลนนั้ จะทบั ขอ้ มูลแรก แลว้ วางทบั ไปเร่อื ยๆ สาํ หรบั การนํา ขอ้ มูลออกจะตอ้ งนําขอ้ มูลท่อี ยู่ดา้ นบนออกมาก่อน ซ่งึ จะพบว่าการสดหรอื เพมิ่ ขอ้ มลู จะกระทาํ กบั ขอ้ มลู ทอ่ี ยู่ บนสดุ เท่านนั้

19 หน่วยท่ี 1 พ้ืนฐานการจดั การข้อมลู คิว (Queue) เป็นโครงสรา้ งคลา้ ยสแตก แตจ่ ะเป็นระบบเขา้ ก่อนออกกอ่ น (First-in First-Out FIFO) ขอ้ มลู จะถูกเรยี ง ลาํ ดบั กนั คลา้ ยกบั การเขา้ ควิ ซอ้ื ของ โดยคน แรกจะไดซ้ อ้ื ก่อนแลว้ ตามดว้ ยคนตอ่ ๆ มา

20 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู กราฟ (Graph) ขอ้ มลู แบบกราฟจะเป็นการเชอ่ื มโยงความสมั พนั ธข์ องขอ้ มลู เป็นคๆู่ ตวั อยา่ งเชน่ เสน้ ทางการบนิ ระหวา่ ง เมอื ง

21 หน่วยท่ี 1 พื้นฐานการจดั การข้อมลู 1.4 อลั กอริทึม (Algorithms) - ขนั้ ตอนการแกป้ ัญหาต่างๆ เรยี กว่าอลั กอรทิ มึ การแก้ปัญหาหน่ึงๆ สามารถใชอ้ ลั กอรทิ มึ ไดห้ ลายวธิ ี แต่ละวธิ จี ะใชเ้ วลาในการดําเนินการแตกต่าง กนั อัลกอริทึมมีหลายวิธีและไม่สามารถบอกได้ว่าวิธีใดดีท่ีสุด ทัง้ น้ีข้ึนกับ ลกั ษณะของงานทต่ี อ้ งการแกป้ ัญหา อลั กอรทิ มึ บางอย่างใชก้ บั งานหน่ึงได้ แต่ก็ ไมส่ ามารถใชก้ บั งานอกี ประเภทหน่ึงได้

22 หน่วยท่ี 1 พ้ืนฐานการจดั การข้อมลู 1.4 อลั กอริทึม (Algorithms) - ในการเขยี นโปรแกรมคอมพวิ เตอรม์ กั จะประกอบดว้ ยรปู แบบการ ทาํ งาน หลกั 3 ประเภทดงั ต่อไปน้ี 1. การทาํ งานแบบเรยี งลาํ ดบั 2. การทาํ งานแบบมเี งอ่ื นไข 3. การทาํ งานแบบทาํ ซํา้

23 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู การทาํ งานแบบเรียงลาํ ดบั ลกั ษณะการทํางานของโปรแกรมแบบน้ีจะกระทําตามลําดบั กจิ กรรม ก่อนหลัง โดยไม่มีการเปล่ียนแปลง ทิศทางการทํางานในลักษณะอ่ืน ประกอบด้วยพ้นื ฐานคําสงั่ ทวั่ ไป ไม่มกี ารตดั สนิ ใจ ไม่มกี ารทําซํ้า ดงั ลกั ษณะ การทาํ งานตอ่ ไปน้ี

24 หน่วยท่ี 1 พื้นฐานการจดั การข้อมูล การทาํ งานแบบมีเง่ือนไข เป็นการทาํ งานทม่ี กี ารเลอื กทาํ งาน เมอ่ื เงอ่ื นไขเป็นจรงิ จะทํางานหน่ึง เม่อื เง่อื นไขเป็นเทจ็ จะทําอกี งาน หน่ึง การทํางานแบบมเี ง่อื นไขน้ีแบ่งได้เป็น การทํางานแบบมที างเลอื กเดยี ว (Single Selection) การทํางาน แบบสอง ทางเลอื ก (Double Selection) และการทํางานแบบหลายทางเลอื ก (Multiple Selection)

25 หน่วยที่ 1 พื้นฐานการจดั การข้อมูล การทาํ งานแบบทาํ ซ้ํา การทาํ ซํา้ หรอื การทาํ ลปู จะตอ้ งมกี ารตรวจสอบเงอ่ื นไขอยภู่ ายในลปู ของการทาํ ซํา้ ดว้ ย งานบางประเภท มจี าํ นวนครงั้ ในการทาํ ซํา้ ทแ่ี น่นอน

26 หน่วยที่ 1 พื้นฐานการจดั การข้อมูล การทาํ งานแบบทาํ ซ้ํา การทาํ ซํา้ หรอื การทาํ ลปู จะตอ้ งมกี ารตรวจสอบเงอ่ื นไขอยภู่ ายในลปู ของการทาํ ซํา้ ดว้ ย งานบางประเภท มจี าํ นวนครงั้ ในการทาํ ซํา้ ทแ่ี น่นอน

27 หน่วยที่ 1 พื้นฐานการจดั การข้อมลู การทาํ งานแบบทาํ ซํ้า การทาํ ซํา้ ไมว่ า่ จะเป็นแบบใดนนั้ จะตอ้ งมกี ารตรวจสอบเงอ่ื นไขทาง ลอจกิ อยภู่ ายในดว้ ย ถา้ หากเป็นการ ทาํ ซํา้ แบบตรวจสอบเงอ่ื นไขกอ่ นและหลงั การทาํ ซํา้ จะมโี ครงสรา้ งการทาํ งานดงั ตอ่ ไปน้ี

28 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู 1.5 ประสิทธิภาพของอลั กอริทึม จากทก่ี ลา่ วไวแ้ ลว้ วา่ การประมวลผลงานหน่ึงอาจทําไดห้ ลายวธิ ี แต่ละ วิธีจะมีประสทิ ธิภาพแตกต่างกนั ซ่ึงจะใช้เวลาในการประมวลผลต่างกัน ใช้ หน่วยความจําในการทํางานต่างกนั ในการเขยี นโปรแกรมเบ้อื งต้น นัน้ ผู้เขยี น โปรแกรมจะตอ้ งเขยี นโปรแกรมใหท้ าํ งานไดเ้ รว็ ทส่ี ดุ ใชห้ น่วยความจาํ น้อยทส่ี ดุ

29 หน่วยที่ 1 พ้ืนฐานการจดั การข้อมลู 1.5 ประสิทธิภาพของอลั กอริทึม ซง่ึ เป็นปรมิ าณขอ้ มูลหรอื จาํ นวนครงั้ ในการทํางาน ซ่งึ โดยทวั่ ไปแลว้ การวเิ คราะหอ์ ลั กอรทิ มึ จะอยใู่ นรปู แบบฟังกช์ นั่ มาตรฐานต่อไปน้ี 1. ฟังกช์ นั คา่ คงท่ี (Constant) O(c) 2. ฟังกช์ นั ลอการทิ มึ (Logarithmic) O(log, n) 3. ฟังกช์ นั ลอการทิ มึ กาํ ลงั สอง (Log - Squared) O(logy n) 4. ฟังกช์ นั เสน้ ตรง (Linear) O(n) 5. ฟังกช์ นั กาํ ลงั สอง (Quadratic) O(n) 6. ฟังกช์ นั กาํ ลงั สาม (Cubic) O(n) 7. ฟังกช์ นั เอกซโ์ พเนนเชยี ล (Exponential) O(27)

30 หน่วยท่ี 1 พ้ืนฐานการจดั การข้อมลู โดยลาํ ดบั ทเ่ี ขยี นมาน้ีเรยี งตามอลั กอรทิ มึ ทเ่ี รว็ ทส่ี ุดไปจนถงึ อลั กอรทิ มึ ทช่ี า้ ทส่ี ดุ อลั กอรทิ มึ O(c) หมาย ถงึ อลั กอรทิ มึ นนั้ มคี า่ คงทไ่ี มข่ น้ึ กบั จาํ นวน ขอ้ มลู สาํ หรบั อลั กอรทิ มึ อ่นื ๆ ถา้ หากจาํ นวนขอ้ มลู หรอื จาํ นวนครงั้ มคี า่ มาก จะ ทาํ ใหเ้ วลาการทาํ งานมคี า่ มากขน้ึ ไปดว้ ย

31 กจิ กรรมทา้ ยบทที่ 1 1. เหตใุ ดจึงตอ้ งศึกษาเรอื่ งโครงสรา้ งข้อมลู หากไม่ศึกษาเรอื่ งน้ี ทา่ นเขียนโปรแกรมไดห้ รอื ไม่ 2. ทําไมจึงต้องมกี ารวเิ คราะห์ประสิทธภิ าพของอลั กอริทึม 3. บ๊กิ โอ (Big-O) คืออะไร 4. จงเขียนบ๊ิกโอ ของการหาผลรวมของเลขจํานวนเตม็ บวกยก กาํ ลังสาม 5. จากฟังกช์ นั ท่กี ําหนด จงเปล่ียนให้อยใู่ นรูปแบบของบ๊กิ โอ 5.1 5n + 7 5.2 2n2 + 3 5.3 5n9 + 2n

32 Thanks! Any questions?