บทที่ 3 Array

บทที่ 3 Array

Array โครงสร้างข้อมูลแบ่งออกเป็น 2 ประเภท คือ

1.โครงสร้างข้อมูลแบบเชิงเส้น ( Linear Lists )

เช่น อาร์เรย์( Array ), สแต็ก ( Stack ) และ คิว ( Queues )

2.โครงสร้างข้อมูลแบบไม่เป็นเชิงเส้น ( Non-Linear Lists )           
เช่น ทรี ( Trees ) และกราฟ ( Graphs )

โครงสร้างข้อมูลแบบอาร์เรย์

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

คุณสมบัติสำคัญของอาร์เรย์

1.อาร์เรย์เป็นตัวแทนของกลุ่มที่มีความสัมพันธ์กัน

2.มีชนิดข้อมูลเหมือนกันทั้งหมด

3.อาร์เรย์มีขนาดคงที่

4.ผู้ใช้สามารถอ้างอิงเพื่อเข้าถึงข้อมูลที่ต้องการได้ทันที

การอ้างอิงตำแหน่งสมาชิกในอาร์เรย์

ต้องเริ่มต้นด้วยชื่ออาร์เรย์และตามด้วยเลขลำดับกำกับไว้ 

ด้วย สามารถเรียกได้หลายชื่อด้วยกัน เช่น เลขลำดับ เรียกอีกชื่อ ซัป

สคริปต์ หรือเลขดรรชนี

 

ขอบเขตของอาร์เรย์ (Bounds)         เลขดรรชนีในอาร์เรย์ประกอบด้วยช่วงขอบเขตของค่าซึ่งประกอบด้วยขอบเขตล่างสุดและขอบเขตบนสุด
การคำนวณหาจำนวนสมาชิก                                            

โดยที่  U  = ขอบเขตบนสุด  , L = ขอบเขตล่างสุด
อาร์เรย์ 1 มิติ  ใช้สูตร         U – L + 1                                  

อาร์เรย์ 2 มิติ  ใช้สูตร  ( U₁ – L₁ + 1) * ( U₂ – L₂ + 1)

การจัดเก็บอาร์เรย์ในหน่วยความจำ

-อาร์เรย์จัดเก็บอยู่ในหน่วยความจำคอมพิวเตอร์จะมีลักษณะเป็นลำดับต่อเนื่องกัน

-ใช้เนื้อที่ในการจัดเก็บข้อมูลสมาชิกของแต่ละตัวในขนาดเท่าๆกัน

-สมาชิกทุกตัวในต้องเป็นข้อมูลชนิดเดียวกัน

 

รูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์

                                                         อาร์เรย์ 1 มิติ ใช้สูตร ArrayName [ L:U ]

 a[1:10] = a[10] 

    
อาร์เรย์ 2 มิติ ใช้สูตร ArrayName [ L₁:U₁,L₂:U₂ ]  
          

 a[4,5] = a[0:3,0:4] 

อาร์เรย์ 3 มิติ ใช้สูตร ArrayName [ L₁:U₁,L₂:U₂ ,L₃:U₃ ]  

 

a[6,5,4] = a[0:5,0:4,0:3] 

 

การคำนวณหาตำแหน่งแอดเดรสในหน่วยความจำอาร์เรย์ 1 มิติ

ใช้สูตร LOC(a[i]) = B + w(i – L)

โดยที่                                                                                  
LOC(a[i]) คือ ตำแหน่งแอดเดรสที่เก็บ a[i] ในหน่วยความจำ                       
B คือ แอดเดรสเริ่มต้นของ a                                                 
w  คือ ขนาดของข้อมูลในการจัดเก็บ                                    
 i คือ ตำแหน่งของสมาชิกในอาร์เรย์                                     
 L คือ ขอบเขตล่างสุด                                                             
 

ตัวอย่าง

อยากทราบอาร์เรย์ a[10] (ภาษา C ) ถูกจัดเก็บในหน่วยความจพเดรสใด กำหนดให้ : 

 แอดเดรสเริ่มต้น = 1000      w =  1 ไบต์
LOC(a[i]) = B + w(i – L)                  
                  = 1000 + 1(10-0)
                  = 1000 + 10
                  = 1010
อาร์เรย์ 2 มิติ                                                                        การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก   
ใช้สูตร      LOC(a[i]) = B + w[C(i – L₁) + ( j – L₂)] 

 

โดยที่ C  คือตำแหน่งคอลัมน์ของแถวลำดับ ( R*C )            
ตัวอย่าง  ต้องการทราบตำแหน่งที่เก็บข้อมูลอาร์เรย์ K แถวที่ 2 คอลัมน์ 1 กำหนด B = 500, w = 4 ( ภาษา C )
LOC(K[i,j]     = B + w[C(i – L₁) + ( j – L₂)] 
LOC(K[2,1])  = 500 + 4[3(2– 0) + ( 1 – 0)]
                        = 500 + 4[6 +1]
                        = 500 +28
                        = 528
อาร์เรย์ 3 มิติ                                                                            
การจัดเก็บด้วยการเรียงแถวเป็นหลัก       ใช้สูตร
      LOC(s[i,j,k])  = B + [ w * R * C( i - L₁)                  
                                     + [w * C( j – L₂ )] + [w(k-L₃)]
ตัวอย่าง      

ต้องการทราบตำแหน่งที่เก็บข้อมูลอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4 กำหนดให้ B = 500, w =4 (ภาษา C S[3][4][5] )
LOC(s[i,j,k])  = B + [ w * R * C( i - L₁)                  
                               + [w * C( j – L₂ )] + [w(k-L₃)]
LOC(s[0,3,4])  = 500 + [ 4 * 4 * 5( 0 - 0)                  
                                     + [4 * 5( 3– 0 )] + [4(4-0)]
                           = 500 + 0 + 60 + 16
                          = 576
อาร์เรย์ 3 มิติ 

-การนำเอาอาร์เรย์ 2 มิติ มาเรียงซ้อนกันหลายๆ ชั้น

-มีแถว (row) และคอลัมน์ (column) และความลึก(deap)

                                      

การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก      

 

ใช้สูตร
LOC( S[i,j,k]) = B + [w * K * R * C(j – L₂) ]
                                + [ w * K * R(i – L₁ )]  + [k – L₃]

การคำนวณหาตำแหน่งแอดแดรสในหน่วยความจำของอาร์เรย์ 3 มิติ

สามารสจัดเก็บได้ 2 วิธี

1. การจัดเก็บด้วยการเรียงแถวเป็นหลัก (Row Major Order)

2. การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก (Column Major Order)