โครงสร้างข้อมูลชนิดต่าง

รูปภาพของ BVS05022

โครงสร้างข้อมูลแบบสแตก (Stack)

            สแตกเป็นโครงสร้างข้อมูลที่ถูกกล่าวถึงมากโครงสร้างหนึ่งซึ่งมักจะใช้เป็นประโยชน์ในการอินเตอร์รัพต์  การกระโดดไปมาระหว่างโปรแกรมย่อย การเขียนโปรแกรมแบบเรียกใช้ตัวเอง (recursive) นอกจากนั้นแล้วโครงสร้างข้อมูลชนิดนี้มักจะใช้ช่วยในการเข้าไปในโครงสร้างแบบพิเศษ เช่น เครือข่าย หรือต้นไม้ โดยจะช่วยในการจำเส้นทาง และงานที่เรานำโครงสร้างแบบสแตกแล้วเราพบเห็นบ่อยๆ คือ การยกเลิกคำสั่ง (Undo) ในไมโครซอฟท์เวิร์ด

            สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion) และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last  In  First  Out) 

            สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ

           1.ตัวชี้สแตก หรือ Stack Pointer   ซึ่งเป็นตัวควบคุมการนำสมาชิกเข้า  หรือออกจากสแตก  เป็นตัวใช้บอกว่าสแตกนั้นเต็มหรือยัง

           2.ส่วนสมาชิกของสแตก หรือจะเรียกอีกอย่างว่า Stack Element สมาชิกของสแตกนี้จะเป็นข้อมูลชนิดเดียวกันทั้งหมด

 การสร้างสแตก

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

ใช้จริงๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer แต่ในที่นี้จะกำหนดให้ตัวสแตกเป็นแบบอาร์เรย์

            นอกจากตัวสแตกเองแล้วในการทำงานกับสแตกยังต้องกำหนดตัวแปรเพิ่มอีกหนึ่งตัวเพื่อเก็บตัวชี้สแตก (Stack Pointer) โดยเริ่มแรกในขณะที่สแตกยังไม่มีข้อมูล ตัวชี้สแตกก็จะชี้ที่ 0 (ยังไม่ได้ชี้ที่ช่องใดๆ ในสแตก)

การดำเนินงาน

      ทำงานกับโครงสร้างข้อมูลแบบสแตกได้แก่ การ PUSH และการ POP

      PUSH

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

            ในกรณีที่ PUSH ข้อมูลลงสู่สแตก จนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว จะไม่สามารถทำการ PUSH ข้อมูลลงสแตกได้อีก เนื่องจากตัวชี้สแตกไม่สามารถที่จะขยับไปยังช่องต่อไปได้ จะเกิด Error ที่เรียกว่า  Stack Overflow

ALGORITHM  PUSH  

เพื่อใช้ในการแทรกข้อมูล  x  เข้า Stack โดยที่

      TOP    แทน     ตัวชี้สแตก

      N        แทน     จำนวนช่องของสแตก

      X         แทน     ข้อมูล

      ST       แทน     สแตก

1.   [ ตรวจสอบ Overflow  ]

      IF  TOP   >=   N   THEN

            PRINT  “ STACK OVERFLOW “

            EXIT

      ENDIF

2.   [ เพิ่มค่า Stack Pointer  ]

      TOP  =  TOP  +  1

3.   [  แทรกข้อมูลเข้า Stack  ]

      ST (TOP)    =   X

4.   [  จบการทำงาน  ]

      EXIT

การ  POP

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

     การ POP ข้อมูลนี้จะทำการนำข้อมูลในส่วนบนสุดของสแตกออกไปทำงานตามต้องการ แต่การ POP ข้อมูลนี้จะไม่สามารถ POP ข้อมูลออกจากสแตกที่ว่างเปล่าหรือไม่มีข้อมูลได้ ถ้าเราพยายาม POP ข้อมูลออกจากสแตกที่ว่างเปล่า จะเกิด Error ที่เรียกว่า  Stack Underflow

 

ALGORITHM  POP  

เพื่อใช้ในการลบข้อมูล  x  จาก Stack โดยที่

      TOP     แทน      ตัวชี้สแตก

      N          แทน      จำนวนช่องของสแตก

      Y          แทน      ข้อมูล

      ST        แทน      สแตก

 

1.   [ ตรวจสอบ Underflow  ]

      IF  TOP   <=   0   THEN

            PRINT  “ STACK UNDERFLOW “

            EXIT

      ENDIF

2.   [  นำข้อมูลที่ต้องการออกจาก Stack  เก็บไว้ที่  Y ]

      Y   =   ST (TOP)

3.   [ ลดค่า Stack Pointer  ]

      TOP  =  TOP  -  1

4.   [  จบการทำงาน  ]

      EXIT

เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์

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

 

การประยุกต์ใช้งานของสแตก

         สแตกเป็นโครงสร้างที่มีประโยชน์มาก ถูกนำไปประยุกต์ใช้ในหลายๆ ด้าน เช่น

 

1.  การจัดการหน่วยความจำ

         โดยทั่วไปการจัดการหน่วยความจำจะเป็นดังนี้

Reserved

By

System

Programs

And

procedures

Dynamic

Varible

Heap

Local

Variable

stack

Operating

system

Low Memory

Available space

High Memory

                                              

                                   

 

 

โครงสร้างข้อมูลแบบคิว (Queue)

 

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

            โครงสร้างข้อมูลแบบนี้เป็นโครงสร้างที่ปรากฏอยู่โดยทั่วๆไปโดยเฉพาะอย่างยิ่งในระบบปฏิบัติการคอมพิวเตอร์  ในระบบคมนาคม รวมทั้งในระบบการทดลองดาวเทียมด้วย

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

            การนำข้อมูลสู่คิว จะเหมือนกับการยืนต่อแถวคอยอยู่

 

 

5

4

8

9

1

2

3

6

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

154

254

854

621

854

265

168

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

78

48

54

68

11

99

14

67

89

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

การสร้างคิว (Queue)

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

            ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์  และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer)  ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง F

 

 

 

5

4

8

9

1

2

3

6

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

154

254

854

621

854

265

168

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

78

48

54

68

11

99

14

67

89

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

            F (Front Pointer)                                                R (Rear Pointer)

            เมื่อเริ่มต้นสร้างคิว คิวนั้นไม่มีค่าใดๆ ยังว่างเปล่า F และ R จะมีค่าเป็น 0 ทั้งคู่ คือไม่ได้ชี้ไปที่สมาชิกตัวใด การนำข้อมูลเข้าสู่คิวเรียกว่า การ Insertion ส่วนการนำข้อมูลออกจากคิวเรียกว่า การ Deletion

 

การ Insertion

            เป็นการนำข้อมูลเข้าสู่คิว โดยการที่จะนำข้อมูลเข้าสู่คิวนั้นจะแบ่งออกเป็น 2 กรณี คือ

            1. การนำข้อมูลเข้าไปในคิวว่าง โดยจะต้องดำเนินการให้พอยน์เตอร์ทั้ง 2 คือ F และ R ชี้ไปยังช่องแรกหรือตำแหน่งที่จะเก็บข้อมูลแรก

            2. การนำข้อมูลเข้าไปในคิวต่อจากข้อมูลเดิม จะต้องจัดการให้พอยน์เตอร์ R ชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไป ส่วนพอยน์เตอร์ F ยังคงชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไปเป็นข้อมูลแรก

            จากการ Insertion ข้อมูลเข้าไปในคิวแล้ว ถ้าหากทำการ Insertion ข้อมูลจนพอยน์เตอร์ R อยู่ที่ช่องสุดท้ายแล้ว จะไม่สามารถทำการ Insertion ข้อมูลลงคิวได้อีก เนื่องจากตัวที่เก็บข้อมูลคิวเต็มทำให้ไม่สามารถที่จะรับข้อมูลอื่นๆ อีกได้ ฉะนั้นจะเกิด Error ขึ้น ซึ่ง Error นี้เรียกว่า Overflow ขึ้น เช่น ถ้าจอง Array ขนาด 3 ช่องชื่อ Q

           

1.         เมื่อคิวว่าง (Empty Queue)

0    1          2         3

                                               

 

 

 

                                    F = 0      R = 0

0    1          2         3

            2.   INSERT (Q , A)

                                                   

A

 

 

                            F = 1   R = 1

            3.   INSERT (Q , A)

0    1          2         3

                                                   

A

B

 

                     F = 1    R = 2

0    1          2         3

            4.   INSERT (Q , C)

                                                   

A

B

C

                              F = 1              R = 3

            หลังจากนี้จะเพิ่มข้อมูลเข้าคิวอีกไม่ได้ เนื่องจากคิวเต็มคือ R = 3

 

ALGORITHM QINSERT

ใช้ในการแทรกข้อมูลเข้าคิว โดยที่

            F          แทน      ตัวชี้ต้นคิว

            R          แทน      ตัวชี้ท้ายคิว

            N          แทน      ขนาดของคิว

            X          แทน      ข้อมูลที่จะแทรก

1.   [  ตรวจสอบ Overflow ]

      IF  R  =  N   THEN

            PRINT “QUEUE  OVERFLOW”

            EXIT

      ENDIF

2.   [  เพิ่มค่า R ]

      R  =  R + 1

3.   [  แทรกข้อมูลเข้าคิว ]

      Q( R )  =  X

4.   [ กรณีเป็นสมาชิกตัวแรก  ]

      IF   F = 0   THEN

            F  =  1

      ENDIF

5.   [ จบการทำงาน ]    EXIT

 

การ Deletion

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

            การ Deletion ข้อมูลนี้จะทำการนำข้อมูลในส่วนของข้อมูลตัวแรกสุดที่เข้าสู่คิวออกไปทำงานตามต้องการ แต่การ Deletion ข้อมูลนี้จะไม่สามารถ Deletion ข้อมูลออกจากคิวที่ว่างเปล่าหรือไม่มีข้อมูลได้ (F = 0) ถ้าเกิดกรณีเช่นนี้จะเกิด Error ที่เรียกว่า Underflow ขึ้น ฉะนั้นก่อนที่จะทำการ Deletion ควรที่จะต้องมีการตรวจสอบว่าคิวว่างหรือไม่ เพื่อไม่ให้เกิด Error นี้ขึ้น

            จากตัวอย่างข้างบน เมื่อทำการ Deletion

            5.   DELETE (Q)

0    1          2         3

                                                 

 

B

C

                                             F = 2    R = 3

            6.   DELETE (Q)                                              

0    1          2         3

 

 

 

 

C

                                          F = 3    R = 3

            7.   DELETE (Q)

0    1          2         3

                                                 

 

 

 

                                    F = 0     R = 0

            หลังจากนี้จะทำ DELETE (Q) อีกไม่ได้ เนื่องจาก Q ว่าง  คือ F = 0 พิจารณาจากขั้นตอนทั้ง 7 ขั้นต้น สรุปได้ว่า

1.   การเพิ่มข้อมูลเข้า ซึ่งต้องเข้าที่ REAR ของคิว ต้องเพิ่มค่า R ที่เป็นตัวชี้สมาชิกตัวสุดท้ายของคิวอีก 1 เพื่อให้ชี้เนื้อที่ถัดไป สำหรับเตรียมให้นำข้อมูลมาใช้

2.   การนำข้อมูลออกจากคิว ทำที่  FRONT ของคิว ซึ่ง F ชี้สมาชิกตัวแรกของคิวอยู่แล้ว ดังนั้น จึงนำข้อมูลที่  F  ชี้อยู่ออกได้เลย หลังจากนั้นเปลี่ยนให้ F ไปชี้สมาชิกตัวถัดไป โดยเพิ่มค่า F  อีก 1

      จากข้อสรุป 2 ข้อนี้ เป็นเพียงข้อสรุปที่เป็นกรณีทั่ว ๆ ไป ยังมีกรณีพิเศษอีก 2 กรณี คือ

3.   (ให้พิจาณาขั้นตอนที่ 1 และ 2) คือเมื่อเพิ่มข้อมูลเข้าคิวที่ว่างอยู่ต้องเซตค่า FRONT ที่แต่เดิมชี้ที่ศูนย์ ให้ชี้ที่ 1 ด้วย เพื่อให้ F ชี้ที่สมาชิกแรกของคิว

4.   (ให้พิจาณาขั้นตอนที่ 6 และ 7) คือเมื่อทำการนำข้อมูลออกจากคิวในขณะที่ในคิวนั้นมีสมาชิกเดียว หลังจากนำข้อมูลออกแล้วก็หมายความว่าคิวต้องว่าง ดังนั้นจึงต้องเซตค่า   F ให้ไปชี้ที่ศูนย์

 

ALGORITHM QDELETE

ใช้ในการลบข้อมูลออกจากคิว โดยที่

      F    แทน      ตัวชี้ต้นคิว

      R    แทน      ตัวชี้ท้ายคิว

      Y    แทน      เก็บค่าข้อมูลที่จะลบออกจากคิว

1.   [  ตรวจสอบ Underflow ]

      IF  F  =  0   THEN

            PRINT “QUEUE  UNDERFLOW”

            EXIT

      ENDIF

2.   [  เก็บข้อมูลตัวที่จะลบไว้ที่ Y ]

      Y  =  Q(F)

3.   [  ปรับค่า  F หรือ  R ]

      IF   F = R   THEN

            F  =  R  =  0

      ELSE

            F  =  F + 1

      ENDIF

4.   [ จบการทำงาน ]

        EXIT

                                                 

                                       โครงสร้างข้อมูลต้นไม้ Tree

ความหมาย  โครงสร้างข้อมูลแบบต้นไม้ (Tree) เป็นโครงสร้างที่ไม่เป็นแบบรายการเชิงเส้น (Non-linear) มีลักษณะโครงสร้างข้อมูลเหมือนต้นไม้ตามธรรมชาติ  คือ ลักษณะคล้ายกิ่งก้านของต้นไม้

                ประกอบด้วยจุดยอดของต้นไม้เรียกว่า ราก (Root)  , จุดที่มีการแตกกิ่งก้านสาขาออกไปเรียกว่า โหนด(Node) และกิ่งก้านสาขาที่ต่อระหว่างโหนดว่า ลิงค์ (Link)

 

                                       ลักษณะของโครงสร้างข้อมูลแบบต้นไม้

 

 โครงสร้างข้อมูลแบบต้นไม้  แบ่งออกมาได้ 3 แบบ คือ

1. ต้นไม้อิสระ (Free Tree) คือ กราฟอย่างง่าย (Simple Graph) มีทางเดินเพียงชุดเดียวระหว่างจุดยอดคู่ใด ๆ

2. ต้นไม้ที่มีราก (Rooted Tree) คือ ต้นไม้ที่มีการกำหนดจุดยอดจุดหนึ่งให้เป็นราก (Root)

3. ต้นไม้ที่มีลำดับ (Ordered Tree) คือ ต้นไม้ที่มีการจัดลำดับของสาขาแต่ละสาขา

 

โครงสร้างต้นไม้แบบทวิภาค (Binary Tree)

  โครงสร้างต้นไม้ทวิภาค (Binary Tree) คือ ต้นไม้ที่มีโหนดราก (Root) และทุกจุดยอดอาจมีลูก (Child) ทางซ้าย, ลูกทางขวา, ลูกทางซ้ายและลูกทางขวา หรือไม่มีลูกเลย

  โครงสร้างต้นไม้ทวิภาคแบบสมบูรณ์ (Complete Binary Tree) คือ  โครงสร้างต้นไม้ทวิภาคที่ทุกจุดยอดมีลูกทั้งสองด้านหรือไม่มีลูกเลย

 

โครงสร้างต้นไม้ทั่วไป (General Trees)

โครงสร้างต้นไม้ทั่วไป คือ เซตจำกัด T ที่มีสมาชิกเรียกว่าโหนด ซึ่งประกอบด้วยคุณลักษณะดังนี้

1. T เป็นต้นไม้ว่าง (Null Tree หรือ Empty Tree) หรือ

2. T มีสมาชิกพิเศษ คือ โหนด R อยู่หนึ่งโหนดที่เรียกว่า Root Node

3. สมาชิกที่เหลือของ T อาจประกอบด้วยต้นไม้ย่อยที่มีจำนวนสมาชิกเป็นศูนย์หรือมากกว่า ได้แก่  T1, T2  , …, T

 

การแทนโครงสร้างต้นไม้

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

                1. การแทนโครงสร้างต้นไม้ด้วยโครงสร้างอาร์เรย์ (Array)

                2. การแทนโครงสร้างต้นไม้ด้วยโครงสร้างรายการเชื่อมโยง (Linked  List)

 

การแทนโครงสร้างต้นไม้ด้วยโครงสร้างอาร์เรย์

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

 ความสัมพันธ์ของโครงสร้างต้นไม้

** ราก (Root) เป็นโหนดบนสุด

** ใต้โหนดรากและในระดับเดียวกันจะใส่จุดยอดซึ่งทางเดินห่างจากราก (Root) เป็นระยะทาง 1 หน่วย

** ใต้จุดยอดเหล่านี้และในระดับเดียวกันจะใส่จุดยอดที่ทางเดินห่างจากราก (Root) เป็นระยะทาง 2 หน่วย

** ทำเช่นนี้เรื่อยไปจนหมดโครงสร้าง

**ระดับ (Level) ของจุดยอด v คือ ระยะทางตามแนวดิ่งของโหนดนั้น (Vn)ว่าอยู่ห่างจากโหนดราก (Root) เท่าไร

** ความสูง (Height) ของโครงสร้างต้นไม้ คือ ระดับสูงสุด (Heightest Level) ที่เกิดขึ้น

**  ดีกรีของโหนด (Level Degree) คือ จำนวนของต้นไม้ย่อย ในแต่ละโหนดว่า มีจำนวนเท่าไร

 

 กำหนดให้โหนดราก (Root) คือ จุดยอด Vและ x, y, z  เป็นจุดยอดในต้นไม้ และ (V0 , V1 , ….,Vn )  เป็นทางเดินในต้นไม้จะกล่าวว่า

1)  Vn-1 เป็น บิดามารดา (Parent) ของ Vn

2)  V0,…,Vn-1 เป็น บรรพบุรุษ (Ancestor) ของ Vn

3)  Vn เป็น ลูก (Child) ของ Vn-1

4)   ถ้า x เป็นบรรพบุรุษของ y จะได้ว่า y เป็น ผู้มาทีหลัง (Descendant)  x

5)  ถ้า x และ y เป็นลูกของ z จะได้ x และ y เป็น พี่น้องกัน (Siblings)

6)  ถ้า x ไม่มีลูก x จะเป็น จุดยอดที่สิ้นสุด (Leaf  Node) หรือใบไม้  

7)  ถ้า x ไม่ใช่จุดยอดที่สิ้นสุด x จะเป็น จุดยอดภายใน (Internal vertex) หรือ กิ่ง

8)  กราฟย่อยของ T ประกอบด้วยจุดยอด x และโหนดที่มาทีหลังนับจากบรรพบุรุษของมันทั้งหมด โดยมีโหนด  x เป็นราก และเรียกว่า ต้นไม้ย่อยของ ต้นไม้ที่มีราก x

 

การแทนโครงสร้างต้นไม้ด้วย Linked List

คือ การใช้โครงสร้างข้อมูล Linked List มาแทนต้นไม้ โดยแต่ละโหนดจะประกอบด้วย 3 ส่วน คือ Left , Info ,Right โดย ส่วน Left จะเป็นตัวเชื่อมไปยังต้นไม้ย่อยในระดับถัดไปที่อยู่ทางซ้าย , Right จะชี้ไปยังต้นไม้ย่อยในระดับถัดไปทางด้านขวา Info จะเก็บข้อมูลของโหนด  และต้นไม้ย่อยที่ว่าง (ไม่มีต้นไม้ย่อยต่ออยู่) แสดงด้วย X สำหรับค่า NULL

การเข้าถึงข้อมูลในโครงสร้างต้นไม้ทวิภาค

การเข้าถึงข้อมูลในโครงสร้างต้นไม้ทวิภาคมีหลายวิธีด้วยกัน   แต่วิธีหลักๆ  ที่สำคัญมี 3 วิธี ดังนี้

                                 1. การเข้าถึงข้อมูลแบบพรีออร์เดอร์ (Preorder)

                                 2. การเข้าถึงข้อมูลแบบอินออร์เดอร์ (Inorder)

                                 3. การเข้าถึงข้อมูลแบบโพสท์ออร์เดอร์ (Preorder)

การเข้าถึงข้อมูลในโครงสร้างต้นไม้ทวิภาค

สังเกตว่า แต่ละวิธีจะประกอบด้วยขั้นตอนที่เหมือนกัน และต้นไม้ย่อยทางซ้ายของ Root ของถูกประมวลผลก่อนต้นไม้ย่อยทางขวามือ วิธีการทั้ง 3 บางครั้งเรียกว่า โหนด-ซ้าย-ขวา (Node-Left-Right : NLR) ,ซ้าย-โหนด-ขวา (Left-Node-Right : LNR) และ ซ้าย-ขวา-โหนด (Left-Right-Node : LRN) แต่ละวิธีการเป็นการกำหนดแบบ เรียกตัวเอง (Recursive) เนื่องจากอัลกอริทึมมีการค้นหาต้นไม้ย่อยในลำดับที่กำหนด ซึ่งต้องใช้โครงสร้างสแตกเมื่อมีการทำงานด้วยคอมพิวเตอร์

โครงสร้างต้นไม้แบบ THREADED TREE

 คือ การนำไบนารีทรีมีการปรับปรุงแก้ไขโดยวิธีการดำเนินการแบบรายการเชื่อมโยง โดยมีการเพิ่มโหนดพิเศษที่เรียกว่า โหนดนำ (Header Node) ไว้ที่จุดเริ่มต้นของ T และกำหนดให้ HEAD เป็นพอยน์เตอร์ที่ชี้ไปยัง Header  Node  และพอยน์เตอร์ทางซ้ายของ Header Node จะชี้ไปยัง Root ของทรี

 

 

รูปแบบโครงสร้างต้นไม้แบบ THREADED TREE

แบ่งออกเป็น 3 แบบ ดังนี้

1. การเชื่อมโยงทางเดียว (One-Way Threading)

2. การเชื่อมโยง 2 ทาง (Two-Way Threading)

3. การเชื่อมโยง 2 ทาง ที่มีโหนดนำ (Two-Way Threading with header node)

      โครงสร้างข้อมูลแบบ กราฟ (Graph)

กราฟ (Graph)  เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นอีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น การวางข่ายงานคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น \

 

ศัพท์ที่เกี่ยวข้อง

1. เวอร์เทก (Vertex)  หมายถึง  โหนด

2. เอดจ (Edge)    หมายถึง  เส้นเชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Undirected Graph

3. Arc หมายถึง เส้นที่เชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Directed Graph

4. ดีกรี (Degree)หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

5. แอดจาเซนท์โหนด (Adjacent Node)    หมายถึง โหนดที่มีการเชื่อมโยงกัน

สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบมีทิศทาง  =  N * (N –1)

จากภาพที่ (ข) ซึ่งเป็นกราฟแบบมีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมดเท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

สูตรหาจำนวนเอดจ์ของกราฟมีทิศทาง             =  N * (N –1)

                                                                                      = 4 * ( 4 – 1)

                                                                                      = 4 * 3

                                                                                      = 12 เส้น

สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบไม่มีทิศทาง

            = (N * (N – 1)) / 2

            กราฟแบบไม่มีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมด   เท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

                        สูตรหาจำนวนเอดจ์ของกราฟไม่มีทิศทาง  = (N * (N – 1)) / 2

                                                                            = (4 * (4 – 1)) / 2

                                                                            = (4 * 3 ) / 2

                                                                            = 12 / 2

                                                                            = 6 เส้น

Graph Storage Structure

การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้

1.Adjacency Matrix  :   ใช้อาร์เรย์เก็บข้อมูล

2.Adjacency List  :  ใช้ลิงค์ลิสต์เก็บข้อมูล

 

Adjacency Matrix

  • * เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทาง  หรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
  • *Mk เป็นเมทริกซ์ของกราฟใด ๆ  k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง 
  • Graph Traversal

    สามารถทำได้ 2 วิธี

    1.แนวลึก : Depth-first Traversal 

    2.แนวราบ : Breath-first Traversal

     

    Depth-first Traversal

    เป็นลักษณะการท่องเข้าไปยังโหนดเริ่มต้น  แล้วให้โหนดใกล้เคียงเป็นโหนดเริ่มต้น  เข้าเยี่ยมโหนด  ทำต่อไปจนกระทั่งไม่มีโหนดใกล้เคียงจึงย้อนกลับมายังโหนดก่อนหน้า  และเข้าเยี่ยมโหนดอีกด้านด้วยรูปแบบเดียวกันจนครบ เทียบได้กับการท่องเข้าไปในทรีแบบพรีออเดอร์

    1.Push vertex

    2.Pop vertex และประมวลผล

    3.Push adjacent ทั้งหมดของ Vertex ในข้อ 2

    4.ทำซ้ำข้อ 2-3 จนกว่าจะครบทุก Vertex และ Stack ว่าง

    Breath-first Traversal

    เป็นการท่องเข้าไปในกราฟโดยเข้าเยี่ยมโหนดตัวแรก และดำเนินการ  หากมีโหนดใกล้เคียงจะดำเนินการกับโหนดที่อยู่ด้านซ้ายก่อน

    1.Enqueue vertex

    2.Dequeue vertex และประมวลผล

    3.Enqueue adjacent ทั้งหมดของ Vertex ในข้อ 2

    4.ทำซ้ำข้อ 2-3 จนกว่าจะครบทุก Vertex และ Queue ว่าง

  • Network Application

    • * Minimum Spanning Tree เป็นรูปแบบของการค้นหาโดยกำหนดเรียกใช้โหนดทุกโหนดและทุกเส้นการเชื่อมต่อ  มาลำดับความสำคัญของน้ำหนักโดยเริ่มจากค่าน้อยที่สุดในข่ายงาน  ทำการเชื่อมต่อคู่โหนดนั้น  และดำเนินการต่อไปในค่าน้ำหนักที่ต่อกัน  แต่ถ้าโหนดใดมีการเชื่อมต่อคู่โหนดแล้วจะไม่เชื่อมต่ออีก
    • * Shortest Path เป็นอัลกอริทึมที่ใช้ในการหาระยะทางที่สั้นที่สุดเช่นเดียวกับ  MST  แต่จะเปลี่ยนจากการหาเส้นทางจากโหนดแรกไปยังโหนดปลายทางของข่ายงาน  เป็นโหนดที่กำหนดเป็นโหนดต้นทางไปยังโหนดต่าง ๆ โดยหาระยะทางสั้นที่สุดแต่ละเส้นทาง
    •                             โครงสร้างข้อมูลแบบแถวลำดับ  (Array)

                     

                      แถวลำดับ (Array)  เป็นแบบหนึ่งของโครงสร้างข้อมูลแบบเชิงเส้น (linear data structures)  ซึ่งมีจำนวนรายการ  (Element)  จำกัด  และข้อมูลที่เก็บอยู่ในอาร์เรย์แต่ละช่องจะต้องเป็นข้อมูลชนิดเดียวกัน  อยู่ภายใต้ตัวแปรชื่อเดียวกัน  โดยขนาดของแต่ละช่องต้องเท่ากันหมด 

       

      การกำหนดแถวลำดับ 

      ในการกำหนดแถวลำดับขึ้นมาใช้งานนั้น จะต้องคำนึงถึง

      1. ชื่อของแถวลำดับ

      2. ขนาดของแถวลำดับแต่ละช่อง  และมิติของแถวลำดับ

      3. ค่าสูงสุด  (Upper  Bound)  และค่าต่ำสุด  (Lower  Bound)  ในแต่ละมิติ

                      ตัวอย่างต่อไปนี้เป็นการประกาศตัวแปรแถวลำดับมิติต่างๆ ในภาษาคอมพิวเตอร์บางภาษา เช่น

      -  ภาษาซี กำหนดตัวแปรแถวลำดับได้ดังนี้

      float  array[10];

      int  array[5][15];

      - ภาษาปาสคาล  กำหนดตัวแปรแถวลำดับได้ดังนี้

      VAR  A  :  array[1..10] of real;

      VAR  K  :  array[1..5, 1..15]] of integer;

                      จากตัวอย่างอธิบายได้ว่าแถวลำดับ A เป็นแถวลำดับ 1 มิติ ซึ่งในภาษาซีมีค่าต่ำสุดคือ 0 ค่าสูงสุดคือ 9 มีจำนวนสมาชิกทั้งหมด 10 ตัว และในภาษาปาสคาลมีค่าต่ำสุดคือ 1 ค่าสูงสุดคือ 10 มีจำนวนสมาชิกทั้งหมด 10 ตัว เช่นเดียวกัน

      แถวลำดับ K เป็นแถวลำดับ 2 มิติ โดยมิติที่ 1 ในภาษาซีจะมีค่าต่ำสุดคือ 0 ค่าสูงสุดคือ 4 และ มิติที่ 2 มีค่าต่ำสุดคือ 0 ค่าสูงสุดคือ 14 ส่วนภาษาปาสคาลมิติที่ 1 มีค่าต่ำสุดคือ 1 ค่าสูงสุดคือ 5 และ มิติที่ 2 มีค่าต่ำสุดคือ 1 ค่าสูงสุดคือ 15 ดังนั้นแถวลำดับ K มีสมาชิกทั้งหมด 75 ตัว

       

      การอ้างถึงสมาชิกของแถวลำดับ

                      การอ้างถึงหรือการเข้าถึงสมาชิกแต่ละตัวของแถวลำดับ จะต้องอ้างถึงชื่อแถวลำดับพร้อมตัวเลขที่บ่งบอกว่าเปฌนสมาชิกตัวใด ตัวเลขนั้นเรียกว่า ตัวบอกลำดับ (subscript) โดยกำหนดตัวบอกลำดับภายในเครื่องหมายวงเล็บหรือก้ามปูแล้วแต่ข้อกำหนดของภาษาคอมพิวเตอร์นั้น  เช่น

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

                      A[0], A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]

    • K[0][0], K[0][1], K[0][2], …, K[4][14]

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

                      A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9], A[10]

                      K[1,1], K[1, 2], K[1, 3], …, K[5, 15]

       

      การจัดเก็บแถวลำดับในหน่วยความจำ

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

    • การคำนวณหาจำนวนช่องของ  Array  คำนวณจาก

       

      จำนวนช่อง  A  [ l  : u ]  =  u  -  l  +  1

       

      ตัวอย่างเช่น  จงคำนวณหาจำนวนช่องของ  Array  B [ -3 : 9 ]

      จำนวนช่องของ  B [ -3 : 9 ]            =     9 - - 3 + 1

                                                      =     13

      ถ้าแต่ละช่องของ  Array  B  ใช้เนื้อที่  10  Bytes  Array  B  จะใช้เนื้อที่ทั้งหมด

                                                                              = 13   *  10

                                                                                = 130  Bytes

      การคำนวณหาตำแหน่ง  (Address)  ของแถวลำดับตัวที่   i  ในหน่วยความจำ

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

      ตัวอย่างเช่น Array  NA [1  :  5]  ซึ่ง   Address  NA [1]  อยู่ที่  1001  และแต่ละช่องของ  Array  NA  ใช้เนื้อที่  25 Bytes

    • แถวลำดับ  2   มิติ (two – dimensional array)

      แถวลำดับ  2  มิติ  คือ แถวลำดับที่มีลักษณะที่เป็นตารางที่มี  2  ด้าน  คือ  ทางด้านแนวนอน    (ROW)   และแนวตั้ง  (COLUMN)  ในทางคณิตศาสตร์เรียกว่า เมทริกซ์ (matrix)  การกำหนดตัวแปรแถวลำดับ 2 มิติ จะระบุชื่อของแถวลำดับแล้วตามด้วยขอบเขตของมิติแรกที่กำหนดจำนวนแถว และขอบเขตของมิติที่ 2 ที่กำหนดจำนวนคอลัมน์ ดังนี้

      ชื่อของอาร์เรย์   [ l1  :  u1  ,  l2  :  u2 ]

       

      l1 คือ  ขอบเขตล่างของมิติที่  1  u1  คือ   ขอบเขตบนของมิติของที่  1

      l2 คือ  ขอบเขตล่างของมิติที่  2 u2  คือ   ขอบเขตบนของมิติของที่  2

      ตัวอย่างเช่น   ถ้ากำหนด Array A [ 5 : 9 , 30 : 33 ]    จะได้โครงสร้างของอาร์เรย์  

    • การอ้างถึงสมาชิกในแถวลำดับ  2  มิติ  ต้องกำหนดชื่อของแถวลำดับแล้วตามด้วยตัวบอกลำดับตัวแรกและตัวที่สอง เช่น A(5,30)

       

      การคำนวณหาจำนวนสมาชิกของแถวลำดับ 2 มิติ

                      การคำนวณหาจำนวนสมาชิกของแถวลำดับ 2 มิติ สามารถคำนวณได้จาก

       

      จำนวนสมาชิกของ  A [ l1  :  u1,  l2  :  u2 ]  =  r  x  c

       

                      โดยที่      r              หมายถึงจำนวนแถว ซึ่งคำนวณได้จาก

       

      r  =  u1  -  l1  +  1

                     

                                      c              หมายถึงจำนวนคอลัมน์ ซึ่งคำนวณได้จาก

                                                     

      c  =  u2  -  l2  +  1

       

       การจัดเก็บแถวลำดับ 2 มิติ

      การจัดเก็บแถวลำดับ 2 มิติในหน่วยความจำของเครื่องคอมพิวเตอร์ ตำแหน่งของหน่วยความจำจะต่อเนื่องกันไปเช่นเดียวกันกับแถวลำดับมิติเดียว แต่การจัดเรียงในแถวลำดับ 2 มิติ แบ่งออกเป็น 2 แบบ ดังนี้

      การจัดเรียงแบบแถว  (Row  Major  Order)  เป็นการจัดเรียงสมาชิกในหน่วยความจำหลักเรียงกันไปทีละแถว โดยเริ่มตั้งแต่แถวแรกจะจัดเรียงสมาชิกในคอลัมน์แรกตามด้วยสมาชิกในคอลัมน์ที่สองจนถึงสมาชิกในคอลัมน์สุดท้ายของแถวแรก จากนั้นจัดเรียงสมาชิกในแถวที่ 2 เริ่มที่คอลัมน์แรกไปอีกเรื่อยๆ จนกระทั่งถึงสมาชิกในคอลัมน์สุดท้ายของแถวที่ 2 และในแถวต่อๆ ไปจัดเรียงในลักษณะเดียวกันจนกระทั่งถึงแถวสุดท้าย

     

    การคำนวณหาตำแหน่งของสมาชิกใดๆ ในหน่วยความจำของอาร์เรย์  2  มิติ  ที่จัดเก็บแบบแถว

                    เช่นเดียวกันกับแถวลำดับ  1  มิติ  คอมพิวเตอร์จะเก็บเฉพาะตำแหน่งของสมาชิกตัวแรกของแถวลำดับ 2 มิติ  ซึ่งจะสามารถนำไปคำนวณหาค่า  Array  A  ตำแหน่งแถวที่ i  คอลัมน์ที่ j ( A[ i , j ] ) ได้ดังนี้

    การหาแอดเดรส A [ i , j ] ในอาร์เรย์  A [1 : m , 1 : n ] นั้น เริ่มจากขั้นแรกเราต้องข้ามไป  i  -  1  แถว  แต่ละแถวมีจำนวนคอลัมน์  c  ค่า  แต่ละค่าใช้เนื้อที่ขนาด  s  นั่นคือเราจะต้องข้ามไป  (i - 1)cs  จาก  A(1, 1)  ตอนนี้เท่ากับเราอยู่ที่ตำแหน่ง A [ i, 1 ]  

  • ดังนั้นถ้าต้องการหา  Ad  A [ i , j ]  ของอาร์เรย์  2  มิติ    A [ I1  :  u1,  I2  :  u2 ]  ก็ต้องใช้สูตรAd   A [ i , j ] =  B + ( i  -  l1 )cs  +  ( j - I2 )s

    ตัวอย่างเช่น  Array  XY [ 1 : 5 , 3 : 7 ]  แต่ละช่องมีขนาด  10  Bytes  ซึ่งนำไปเก็บในหน่วยความจำแบบ  Row  Major  Order  โดยเริ่มต้นเก็บที่  Address  10000  จงหา  Address  เริ่มต้นของ  XY [4 , 3]

                    c  =  u2  -  I2  +  1

                                    c =  7 – 3 + 1 = 5

                                    Ad  A [ i , j ]      =             Ad  ตัวแรก  + ( i  - 1 )cs  +  ( j  -  I2 )s

                                                                    =  10000  +  ( 4  -  1 )x5x10  +  ( 3  -  3 )x10

                                                                    =  10000  +  150  +0

                                                                    =  10150

    2.  การจัดเรียงแบบคอลัมน์  (Column  Major  Order)  เป็นการจัดเรียงสมาชิกในหน่วยความจำหลักโดยเรียงกันไปทีละคอลัมน์ เริ่มตั้งแต่คอลัมน์แรกจะจัดเรียงสมาชิกในแถวแรก ตามด้วยสมาชิกในแถวที่ 2 ไปจนถึงสมาชิกในแถวสุดท้ายของคอลัมน์แรก จากนั้นจัดเรียงสมาชิกในคอลัมน์ที่ 2 เริ่มที่แถวแรกไปจนถึงแถวสุดท้ายของคอลัมน์ที่ 2 และจัดเรียงสมาชิกในคอลัมน์ต่อไปในลักษณะเดียวกันจนกระทั่งถึงคอมัลมน์สุดท้ายแถวสุดท้าย การเก็บอาร์เรย์  2  มิติในลักษณะนี้มีใช้ในภาษาฟอร์แทรน  (FORTRAN) 

    กำหนดอาร์เรย์  2  มิติ  ชื่อ   A [ 1 : 4 , 1 : 5 ]  ซึ่งจัดเก็บแบบ  Column  Major  Order

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

     

    การประยุกต์ใช้แถวลำดับในเมทริกซ์

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

    เมทริกซ์สมมาตร (Symmetric Matrix)

    เมทริกซ์อีกแบบหนึ่งที่มีลักษณะเดียวกันกับเมทริกซ์สามเหลี่ยมคือเมทริกซ์สมมาตร (symmetric matrix) เป็นเมทริกซ์จัตุรัสที่มีค่าหรือสมาชิกแถวที่ i คอลัมน์ j มีค่าเท่ากับสมาชิกแถวที่ j คอลัมน์ i นั่นคือ ถ้า M เป็นเมทริกซ์จัตุรัสที่ M[i,j] = M[j,i] แล้วจะเรียก M ว่าเป็นเมทริกซ์สมมาตร ดังตัวอย่างในรูปเป็นตัวอย่างเมทริกซ์สมมาตรขนาด 4 x 4 ในการเก็บค่าสมาชิกแต่ละตัวของเมทริกซ์สมมาตร สามารถทำได้ในทำนองเดียวกันกับเมทริกซ์สามเหลี่ยม

     

    เมทริกซ์กระจาย (Sparse matrix)

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

     

    ข้อจำกัด

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

  • โครงสร้างข้อมูลแบบลิงค์ลิสต์ (Linked list)             

                 โครงสร้างข้อมูลแบบนี้จะให้ความสะดวกแก่การจัดการข้อมูลมาก อย่างไรก็ดีในบางครั้งก็ให้ความยุ่งยากแก่ผู้ใช้เนื่องจากจะซับซ้อนกว่าแบบใช้อาร์เรย์ ข้อจำกัดของการใช้อาร์เรย์คืออาร์เรย์มีขนาดคงที่ ถ้าเราจะใช้อาร์เรย์ขนาด 100 ช่อง เมื่อใช้หมด 100 ช่องก็ใช้อาร์เรย์นั้นไม่ได้ ถ้าไม่อนุญาตให้เคลียร์พื้นที่อาร์เาย์เพื่อใช้ซ้ำถึงแม้อนุญาตให้เคลียร์พื้นที่อาร์เรย์เพื่อใช้ซ้ำก็ไม่เป็นการสะดวก เนื่องจากอาจต้องตรวจทุกช่องในอาร์เรย์เพื่อหาว่าช่องไหนสามารถใช้ซ้ำได้ นอกจากนี้การใช้พื้นที่ซ้ำยังต้องเลื่อนข่าวสารทั้งหมดไปอยู่ในส่วนอาร์เรย์อีกประการคือ ในภาวะการทำงานแบบ real - time ที่ต้องมีการนำข้อมูลเข้า (insertion) หรือดึงข้อมูลออก (deletion) อาร์เรย์จะไม่สะดวกแก่การใช้มาก ในภาวะการทำงานแบบนี้โครงสร้างแบบลิงค์ลิสต์จะสะดวกกว่า    การแทนแบบใช้พอยเตอร์นี้เราต้องใช้พื้นที่เพิ่มเติมเป็นส่วนของพอยน์เตอร์ (pointer) หรือลิงค์ (link) เพื่อแสดงให้เห็นขัดว่าโหนดที่ต่อจากโหนดนั้นคือโหนดใด ลักษณะของแต่ละโหนดจึงประกอบด้วยช่อง 2 ช่อง

                  สมมติว่าเราจะแทนชุดข่าวสารที่ประกอบด้วย A,B,C ลักษณะการแทนจะเป็นไปตามรูปซึ่งเป็นภาพแสดงแนวคิดการเก็บแบบหนึ่ง ส่วนการเก็บข่าวสาร A,B,C แท้จริงแล้วจะเป็นในรูปไหนก็ได้ แต่ก็ต้องสอดคล้องกับแนวความคิดนี้ รูปที่ 3 แสดงถึงความเป็นไปได้อีกแบบหนึ่งเมื่อข่าวสาร A,B,C อยู่ในพื้นที่ความจำ

     

    รูปการแทนโครงสร้างแบบลิงค์ลิสต์

                   ข่าวสาร A อยู่ที่ตำแหน่ง 5000 ดูได้จากค่าที่ตำแหน่ง 6000 ผู้ใช้จะต้องรู้ว่า head node ของค่าชุดนี้อยู่ที่แอดเดรส 6000 ส่วนค่า A,B,C ผู้ใช้ไม่ทราบว่าอยู่ที่ใดยกเว้นแต่จะตามพอยน์เตอร์เข้าไป จากตำแหน่ง 6000 เรารู้ว่าค่าที่อยู่ที่ตำแหน่ง 5000 คือค่าแรก (ค่า A ) จากส่วนพอยน์เตอร์ของ A (ที่ตำแหน่ง 5001) เรารู้ว่าค่าถัดไป (ค่าB) อยู่ที่ตำแหน่ง 5600 เราตามพอยน์เตอร์ไปยังตำแหน่ง 5600 พบ B ค่าพอยน์เตอร์ของ B ที่ตำแหน่ง 5601 เป็นแอดเดรสของค่าถัดไป (ค่า C) ซึ่งอยู่ที่ตำแหน่ง 5508 จากค่า C เมื่อพิจารณาค่าพอยน์เตอร์ของ C พบว่าค่า - 1 ซึ่งหมายถึงว่าสิ้นสุดของค่าชุดนี้แล้ว อนึ่งผู้ใช้ไม่สามาร5นำค่า A หรือ B หรือ C มาใช้โดยตรงอย่าในอาร์เรย์ ผู้ใช้ต้องเดิน เข้าไปหาค่าเหล่านี้ ลักษณะการหาค่าแบบนี้คล้าย ๆ กับการหาค่าในเทปซึ่งเรียกว่า การหาค่าแบบลำดับ (sequential access) ซึ่งในทางปฏิบัติสำหรับระบบโปรแกรมภาษาชั้นสูง เราอาจใช้อาร์เรย์เป็นตัวเก็บค่า A,B,C และใช้อีกหนึ่งอาร์เรย์เป็นตัวเก็บพอยน์เตอร์ ดังรูปซึ่งผู้ใช้ต้องทราบว่าค่าแรกของข่าวสารชุดนี้อยู่ที่ตำแหน่งที่ 2 ในอาร์เรย์ INFO (3)

รูปภาพของ ssspoonsak

เนื่องจากมีข้อมูลบางส่วนหรือทั้งหมดได้ทำการคัดลอกมาแล้วไม่อ้างอิงแหล่งที่มาของข้อมูล

กรุณาอ้างอิงแหล่งที่มาของข้อมูลให้ชัดเจนด้วย ดูรูปแบบการทำเอกสารอ้างอิงได้ที่

http://www.thaigoodview.com/node/99177 

มิฉะนั้นทางเว็บ thaigoodview.com จำเป็นต้องลบข้อมูลทั้งหมดออก

อ่านรายละเอียด http://www.thaigoodview.com/node/159116

ขอขอบคุณ

ครูพูนศักดิ์ สักกทัตติยกุล

ผู้ดูแลเว็บไซต์ไทยกู๊ดวิว

 


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

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ ไม่ถูกปิดเสียก่อน
ขอขอบคุณในความร่วมมือครับ

มหาวิทยาลัยศรีปทุม ผู้ใหญ่ใจดี
 
 

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

ช่วยกันนะครับ 
ไทยกู๊ดวิวจะได้อยู่นานๆ 
ไม่ถูกปิดเสียก่อน

ขอขอบคุณในความร่วมมือครับ

อ่านรายละเอียด

ด่วน...... ขณะนี้
พระราชบัญญัติลิขสิทธิ์ (ฉบับที่ 2) พ.ศ. 2558 
มีผลบังคับใช้แล้ว 
ขอให้นักเรียนและคุณครูที่ใช้งาน
เว็บ thaigoodview ในการส่งการบ้าน
ระมัดระวังการละเมิดลิขสิทธิ์ด้วย
อ่านรายละเอียดที่นี่ครับ

 

สมาชิกที่ออนไลน์

ขณะนี้มี สมาชิก 0 คน และ ผู้เยี่ยมชม 40 คน กำลังออนไลน์