สรุปครั้งที่ 10

สรุปครั้งที่ 9 เรื่อง Sorting

การเรียงลำดับ (Sorting)  

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

วิธีการเรียงลำดับสามารถแบ่งออกเป็น 2 ประเภท คือ

               การเรียงลำดับแบบภายใน

(Internal sorting) เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก

              การเรียงลำดับแบบภายนอก

(External Sorting) เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง

ประสิทธิภาพในการทำงานสูงสุด

>>> เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม

>>> เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน

>>> จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่

สรุปครั้งที่ 8 เรื่อง Tree

ทรี (Tree)

         

              เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้งานต่างๆอย่างแพร่หลาย ส่วนมากจะใช้สำหรับแสดงความสัมพันธ์ระหว่างข้อมูล

>>>  ความสัมพันธ์กับโหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลายๆโหนดเรียก

-โหนดดังกล่าวว่า โหนดแม่ (Parent or Mother Node)Child or sun Node)Root Node)
    เรียกว่า โหนดพี่น้อง (Sibilings)

-โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับ เรียกว่า โหนดลูก (

-โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหนดราก (

-โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน

-โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)

-เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนด เรียกว่า กิ่ง (Branch)

สรุปครั้งที่ 7 เรื่อง Queue

คิว (Queue)

เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่งเรียกว่าส่วนท้ายหรือเรียร์ (rear) และนำข้อมูลออกจะกระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์(Front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อนออกก่อนหรือที่เรียกว่า FIFO
(First In First Out)

>>> การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะเรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว
>>> การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะเรียกว่า
แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว

การแทนที่ข้อมูลคิว สามารถทำได้ 2 วิธี
 >>>การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
 >>>การแทนที่ข้อมูลของคิวแบบอะเรย์

 

สรุปครั้งที่ 6 เรื่อง Stack

Stack (ต่อ)

        1.Create Stack จัดสรรหน่วยความจำให้แก่ Head Node

        2. Push Stack   การเพิ่มข้อมูลลงในสแตก

3. Pop Stack   การนำข้อมูลออกจากสแตก

4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก

5. Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาด

6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาด

7.Stack Count เป็นการนับจำนวนสมาชิกในสแตก

8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

การประยุกต์ใช้สแตก

>>จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บ

ข่าวสารอันดับแรกสุดไว้ใช้หลังสุด

สรุปครั้งที่ 5 เรื่อง Stack

          สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ 
>>การดำเนินงานพื้นฐานของสแตก  จะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น 
>>การทำงานของสแตกจะประกอบด้วย 3 กระบวนการที่สำคัญ
   
    1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
    2.Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
    3.Stack Top คือ การคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูล
      นั้นออกจากสแตก


>>Stack Empty คือ ไม่มีสมาชิกอยู่ในสแตกเลย
>>แต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop จะทำให้เกิดความผิดพลาดที่เรียกว่า
Stack Underflow

สรุปครั้งที่ 4

        บทที่ 4  

เรื่อง  Linked List

      ลิงค์ลิสต์ ( Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่างๆ 

โดยมีพอยเตอร์เป็นตัวเชื่อม

      แต่ละอิลิเมนต์ เรียกว่าโนด (Node) ในแต่ละโนดจะประกอบด้วย 2 ส่วน 

คือ Data จะเก็บข้อมูลของอิลิเมนต์ และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่ง

ของโนดต่อไปในลิสต์

>> ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหมดแรกของลิสต์จะเป็น Null

      โครงสร้างข้อมูลแบบ ลิงค์ลิสต์

แบ่งเป็น 2 ส่วน คือ

      1. Head Structure จะประกอบด้วย 3 ส่วน ได้แก่ Count , Pos , Head

      2. Data Node Structure  จะประกอบด้วยข้อมูล Data และพอยเตอร์
ที่ชี้ไปยังข้อมูลตัวถัดไป

สรุปครั้งที่ 3 บทที่ 3-4

 Array >> เป็นโครงสร้างข้อมูลที่เรียกว่า Linear List มีลักษณะคล้ายเซ็ตในคณิตศาสตร์ คือ อะเรย์จะประกอบด้วยสมาชิกที่มีจำนวนคงที่
ข้อกำหนดของการกำหนดค่าต่ำสุดและค่าสูงสุดของ subscript คือ
          1. ค่าต่ำสุดต้องมีค่าน้อยกว่าหรือเท่ากับค่าสูงสุดเสมอ
          2. ค่าต่ำสุด เรียกว่า ขอบเขตล่าง (lower bound)
          3.ค่าสูงสุด เรียกว่า ขอบเขตบน (upper bound)
ขนาดของอะเรย์ = ผลคูณของขนาดของ subscript แต่ละตัว
Initialization คือ การกำหนดค่าเริ่มต้นให้กับอะเรย์ การกำหนดค่าให้กับตัวแปรชุดที่มีค่าเป็นตัวเลข
Record or Structure >> เป็นโครงสร้างข้อมูลที่ประกอบขึ้นมาจากข้อมูลพื้นฐานต่างประเภทกัน
รวมเป็น 1 ชุดข้อมูล คือจะประกอบด้วย data element หรือ field
ในภาษา C ก็คือการกำหนดข้อมูลเป็นรูปแบบของ Structure
Structure คือโครงสร้างที่สมาชิกแต่ละตัวมีประเภทข้อมูลแตกต่างกัน อาจมีสมาชิกเป็นจำนวนเต็ม
ทศนิยม อักขระ อะเรย์ หรือพอยเตอร์
  เรื่อง Set and String
โครงสร้างข้อมูลแบบเซ็ต
      เป็นโครงสร้างข้อมูลที่แต่ละตัวไม่มีความสัมพันธ์กัน
สตริง หรือ สตริงของอักขระ เป็นข้อมูลที่ประกอบด้วย ตัวอักษร ตัวเลขหรือเครื่องหมาย
เรียงติดต่อกัน รวมทั้งช่องว่าง
ความยาวของสตริง จะถูกกำหนดโดย ขนาดของสตริง

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

การแทนที่ข้อมูลในหน่วยความจำหลัก มีการแทนที่ข้อมูล 2 วิธี
      
       1.การแทนที่ข้อมูลแบบ สแตติก (Static Memory Representation)
       2.การแทนที่ข้อมูลแบบ ไดนามิก (Dynamic Memory Representation )

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

+ ขั้นตอนวิธี (Algorithm)
    เป็นวิธีการแก้ปัญหาต่างๆ อย่างมีระบบมีลำดับขั้นตอนตั้งแต่ต้นจนกระทั่งได้ผลลัพธ์
+ การแสดงขั้นตอนวิธี เช่น การเขียนด้วยผังงาน (Flowchart)
+ ภาษาขั้นตอนวิธี เป็นภาษาสำหรับเขียนขั้นตอนวิธี มีรูปแบบสั้น กระชับรัดกุม

คำถาม
     การแทนที่ข้อมูลแบบสแตติกและการแทนที่ข้อมูลแบบไดนามิกมีความสำคัญกันอย่างไร
   

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

โครงสร้างข้อมูลและขั้นตอนวิธี

        ข้อมูล คือ ข้อเท็จจริงต่างๆ ซึ่งอาจจะเป็นตัวเลขหรือไม่เป็นตัวเลขก็ได้

        โครงสร้าง คือ ความสัมพันธ์ของสมาชิกในกลุ่ม

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

โครงสร้างข้อมูลในภาษาคอมพิวเตอร์ที่ใช้กันอยู่ในปัจจุบัน มีอยู่ 2 ประเภท

1. โครงสร้างข้อมูลทางกายภาพ

2.โครงสร้างข้อมูลทางตรรกะ

     1. โครงสร้างข้อมูลทางกายภาพ

มีข้อมูลเบี้ยงต้นและข้อมูลโครงสร้าง

ข้อมูลเบี้ยงต้น >> จำนวนเต็ม จำนวนจริง ตัวอักขระ

ข้อมูลโครงสร้าง >> แถวลำดับ ระเบียบข้อมูล แฟ้มข้อมูล

     

     2. โครงสร้างข้อมูลทางตรรกะ

มีข้อมูลแบบเชิงเส้นและข้อมูลแบบไม่เชิงเส้น

ข้อมูลแบบเชิงเส้น >> ลิสต์ แสตก คิว สตริง

ข้อมูลแบบไม่เชิงเส้น >> ทรี กราฟ

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

ได้อย่างสมบูรณ์


คำถาม
      โครงสร้างข้อมูลมีความสัมพันธ์อย่างไร