Slice_Napasakoen

data structure and algorithm

1.0x

Slice_Napasakoen

Created 2 years ago

Duration 0:13:42
lesson view count 108
data structure and algorithm
Select the file type you wish to download
Slide Content
  1. Chapter 3  Linked list

    Slide 1 - Chapter 3 Linked list

    • Napasakorn Sukjay,Ph.d. cand’.
    • 1
  2. คำชี้แจงบทเรียน

    Slide 2 - คำชี้แจงบทเรียน

    • 2
    • ศึกษาชนิดข้อมูลนามธรรม (Abstract Data Types: ADTs) ลักษณะโครงสร้างข้อมูลเชิงเส้นและโครงสร้างข้อมูลไม่เป็นเชิงเส้น ตัวแปรชุด การจัดโครงสร้างข้อมูลภายใน ลิงก์ลิสต์ และการประยุกต์ใช้งาน
  3. จุดประสงค์การเรียนรู้

    Slide 3 - จุดประสงค์การเรียนรู้

    • 3
    • เพื่อให้นักศึกษาเรียนรู้ถึงชนิดข้อมูลแบบต่าง ๆ และเข้าใจโครงสร้างข้อมูลประเภทต่างๆ ที่เป็นพื้นฐานที่จำเป็นสำหรับการเรียนในวิชาอื่น ๆ ที่สูงขึ้นไป
    • นักศึกษาสามารถเขียนโปรแกรมเพื่อ insert update delete linked list ได้
    • นักศึกษาสามารถประยุกต์ใช้ความรู้ที่เรียนมาเพื่อการเขียนโปรแกรมในงานธุรกิจได้
  4. 4

    Slide 4 - 4

    • Pretest
  5. 5

    Slide 5 - 5

  6. 6

    Slide 6 - 6

  7. 7

    Slide 7 - 7

  8. 8

    Slide 8 - 8

  9. 9

    Slide 9 - 9

  10. 10

    Slide 10 - 10

  11. 11

    Slide 11 - 11

  12. 12

    Slide 12 - 12

  13. 13

    Slide 13 - 13

  14. 14

    Slide 14 - 14

  15. Pointer ในภาษาซี

    Slide 15 - Pointer ในภาษาซี

    • Pointer Type เป็นชนิดข้อมูลอย่างหนึ่งในภาษาซีที่ทำให้สามารถใช้เนื้อที่ในหน่วยความจำแบบDynamicได้สัญลักษณ์ที่ใช้แทนPointer คือ* ใช้นำหน้าสิ่งที่ชี้ไป
    • 15
  16. คำสั่งที่ใช้กับPointer

    Slide 16 - คำสั่งที่ใช้กับPointer

    • Malloc(Parameter : Pointer) ทำหน้าที่กําหนดNode ว่างและให้ชี้ด้วยPointer ที่เป็นParameter เช่นmalloc(sizeof(Node))
    • Free(Parameter : Pointer) ทำหน้าที่นำพื้นที่Node ที่ชี้ด้วยParameter นั้นคืนหน่วยความจำเช่นFree(P)
    • Null เป็นPointer ในภาษาซีที่แสดงว่าไม่ได้ชี้ไปที่ใด
    • 16
  17. Linked-List

    Slide 17 - Linked-List

    • Linked-List คือโครงสร้างข้อมูลที่มีลักษณะไม่เป็นเชิงเส้นเนื่องจากใช้การเชื่อโยง(list) ด้วย Addressที่เก็บไว้ในแต่ละ record
    • Linked-List เชื่อมโยงมีโครงสร้างพื้นฐานเป็น record หรือเรียกว่าเป็นโหนด(node) โดยโหนดจะต้องร้องขอให้ระบบจัดสรรเนื้อที่ว่างในหน่วยความจำนำมาทำเป็นโหนด
    • 17
  18. โครงสร้างข้อมูลแบบLinked List

    Slide 18 - โครงสร้างข้อมูลแบบLinked List

    • ลิงค์ลิสต์เป็นชนิดข้อมูลที่สามารถเพิ่มและลดขนาดในการเก็บข้อมูลได้แบบอัตโนมัติ ทำให้ไม่ต้องจองพื้นที่ในหน่วยความจำก่อนใช้งาน
    • โครงสร้างแบบลิงค์ลิสต์ที่ใช้สำหรับเก็บข้อมูลเรียกว่า โหนด (Node) ภายในโหนดมีส่วนประกอบอย่างน้อยสองส่วนคือ
    • ส่วนเก็บข้อมูล (item) ทำหน้าที่เก็บข้อมูลภายในโหนด
    • ส่วนเชื่อมโยง (next) ทำหน้าที่เชื่องโยงโหนดภายในลิงค์ลิสต์
    • 18
  19. Single Linked-List

    Slide 19 - Single Linked-List

    • Single Linked-List หรือ ลิงก์ลิสเชื่องโยงทางเดียว ซึ่งโครงสร้างข้อมูลของลิงก์ลิสจะมีเพียงหนึ่งเซตข้อมูลที่เป็นพอยน์เตอร์เสมอ กรณีตัวสุดท้ายจะใส่ค่า null
    • Data
    • Link
    • ใช้เก็บข้อมูล
    • ใช้เก็บ Address หรือ Pointer
    • Data
    • Null
    • struct Node
    • {
    • int item;
    • struct Node * next
    • }
    • 19
  20. Single Linked List

    Slide 20 - Single Linked List

    • 20
  21. การสร้างและใช้งานลิงค์ลิสต์ทิศทางเดียวในภาษา C

    Slide 21 - การสร้างและใช้งานลิงค์ลิสต์ทิศทางเดียวในภาษา C

    • ภาษา C จะใช้พอร์ตเตอร์ทำหน้าที่อ้างอิงไปยังโหนถัดไป
    • ใช้ฟังก์ชัน malloc( ) เป็นฟังก์ชันในการจัดการบล็อกหน่วยความจำ
    • ใช้ตัวแปรแบบพอยเตอร์อ้างอิงบล็อกหน่วยความจำใหม่ที่สร้างขึ้น
    • 21
  22. การสร้างและใช้งานลิงค์ลิสต์ทิศทางเดียวในภาษา C

    Slide 22 - การสร้างและใช้งานลิงค์ลิสต์ทิศทางเดียวในภาษา C

    • ฟังก์ชันเรียกฟังก์ชัน Node มาใช้งานในภาษา C
    • สร้างโหนดใหม่อ้างอิงด้วย n
    • สร้างโหนดใหม่อ้างอิงด้วย first และ
    • เชื่อมโยงไปยังโหนด n อ้างอิง
    • 22
  23. การจัดการลิงค์ลิสต์ทิศทางเดียว

    Slide 23 - การจัดการลิงค์ลิสต์ทิศทางเดียว

    • การสร้างส่วนหัวของลิงค์ลิสต์ทิศทางเดียว
    • จุดเริ่มต้นในการเข้าถึงข้อมูลในลิงค์ลิสต์ จะถูกเรียกว่า ส่วนหัว (head)
    • ขั้นตอนวิธีการสร้างส่วนหัวและการเพิ่มโหนดในลิงค์ลิสต์ทิศทางเดียว
    • 23
  24. การจัดการลิงค์ลิสต์ทิศทางเดียวการสร้างส่วนหัวของลิงค์ลิสต์ทิศทางเดียว

    Slide 24 - การจัดการลิงค์ลิสต์ทิศทางเดียวการสร้างส่วนหัวของลิงค์ลิสต์ทิศทางเดียว

    • ขั้นตอนวิธีการสร้างส่วนหัวและการเพิ่มโหนดในลิงค์ลิสต์ทิศทางเดียว
    • 24
  25. Operations ที่กระทำกับโครงสร้างข้อมูลแบบLinked List

    Slide 25 - Operations ที่กระทำกับโครงสร้างข้อมูลแบบLinked List

    • การInsertสามารถInsert ข้อมูลเข้าไปในLinked List ได้ในทุกๆตำแหน่ง
    • การDeleteสามารถDelete ข้อมูลจากLinked List ได้ในทุกๆตำแหน่ง
    • 25
  26. การค้นหาตำแหน่งโหนดที่ต้องลบหรือแทรกโหนดในลิงค์ลิสต์ทิศทางเดียว

    Slide 26 - การค้นหาตำแหน่งโหนดที่ต้องลบหรือแทรกโหนดในลิงค์ลิสต์ทิศทางเดียว

    • ตัวแปรที่เกี่ยวข้องการค้นหาตำแหน่งโหนดมีอยู่ 2 ตัว
    • ตัวแปร curr ทำหน้าที่ค้นหาตำแหน่งโหนดที่ต้องการลบหรือแทรกโหนด
    • ตัวแปร prev ทำหน้าที่อ้างอิงตำแหน่งโหนดก่อนหน้าที่ต้องการลบหรือแทรกโหนด
    • 26
  27. Slide 27

    • การเพิ่มโหนดระหว่างข้อมูลที่มีอยู่ในลิงค์ลิสต์ทิศทางเดียว
    • curr อ้างอิงตำแหน่งโหนดก่อนหน้าโหนดที่จะแทรก
    • prev อ้างอิงตำแหน่งโหนดหลังโหนดที่จะแทรก
    • การจัดการลิงค์ลิสต์ทิศทางเดียว
    • การเพิ่มโหนดในลิงค์ลิสต์ทิศทางเดียว
    • 27
  28. การเพิ่มโหนดระหว่างข้อมูลที่มีอยู่ในลิงค์ลิสต์ทิศทางเดียว

    Slide 28 - การเพิ่มโหนดระหว่างข้อมูลที่มีอยู่ในลิงค์ลิสต์ทิศทางเดียว

    • 28
  29. การเพิ่มโหนดในตำแหน่งที่เป็นส่วนหัวลิงค์ลิสต์ทิศทางเดียว

    Slide 29 - การเพิ่มโหนดในตำแหน่งที่เป็นส่วนหัวลิงค์ลิสต์ทิศทางเดียว

    • curr อ้างอิงตำแหน่งโหนดที่ต้องการแทรกและเป็นตำแหน่งโหนดที่เป็นส่วนหัว
    • prev ไม่อ้างอิงตำแหน่งโหนดใดๆ โดยมีค่าเท่ากับ null
    • 29
  30. การเพิ่มโหนดในตำแหน่งสุดท้ายของลิงค์ลิสต์ทิศทางเดียว

    Slide 30 - การเพิ่มโหนดในตำแหน่งสุดท้ายของลิงค์ลิสต์ทิศทางเดียว

    • curr ไม่อ้างอิงตำแหน่งโหนดใดๆ โดยมีค่าเท่ากับ null
    • prev อ้างอิงตำแหน่งโหนดสุดท้ายในลิงค์ลิสต์
    • 30
  31. การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    Slide 31 - การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    • ก่อนที่จะลบโหนดในลิงค์ลิสต์ได้ต้องค้นหาโหนดที่ต้องการลบเสียก่อน โดยที่ตัวแปร curr และ prev จะทำหน้าที่อ้างอิงตำแหน่งโหนดในลิงค์ลิสต์
    • curr อ้างอิงตำแหน่งโหนดที่ต้องการลบ
    • prev อ้างอิงตำแหน่งโหนดก่อนหน้าที่ต้องการลบ
    • 31
  32. การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    Slide 32 - การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    • การลบโหนดระหว่างข้อมูลที่มีอยู่ในลิงค์ลิสต์ทิศทางเดียว
    • เพื่อให้เข้าใจมากขึ้นในขั้นตอนในการลบโหนดในลิงค์ลิสต์ ได้แสดงการนำตัวแปร buff มาทำหน้าที่อ้างอิงในตำแหน่งโหนดก่อนหน้าที่ต้องการลบ
    • 32
  33. การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    Slide 33 - การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    • การลบโหนดที่เป็นส่วนหัวในลิงค์ลิสต์ทิศทางเดียว
    • curr อ้างอิงตำแหน่งโหนดที่ต้องการลบ
    • prev มีค่าเท่ากับ null คือไม่อ้างอิงโหนดใดๆ
    • 33
  34. การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    Slide 34 - การลบโหนดในลิงค์ลิสต์ทิศทางเดียว

    • การลบโหนดตำแหน่งสุดท้ายของลิงค์ลิสต์ทิศทางเดียว
    • curr อ้างอิงตำแหน่งโหนดที่ต้องการลบและเป็นตำแหน่งโหนดสุดท้ายในลิงค์ลิสต์
    • prev อ้างอิงตำแหน่งโหนดก่อนหน้าที่ต้องการลบ
    • 34
  35. 35

    Slide 35 - 35

    • Postest
  36. 36

    Slide 36 - 36

  37. 37

    Slide 37 - 37

  38. 38

    Slide 38 - 38

  39. 39

    Slide 39 - 39

  40. 40

    Slide 40 - 40

  41. 41

    Slide 41 - 41

  42. 42

    Slide 42 - 42

  43. 43

    Slide 43 - 43

  44. 44

    Slide 44 - 44

  45. 45

    Slide 45 - 45