บทที่ 2 Array

                                              บทที่ 2 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)

รูปที่1  แสดงอาร์เรย์  number ที่จัดเก็บอยู่ภายในหน่วยความจำคอมพิวเตอร์

                  อาร์เรย์สองมิติ (Two  Dimension  Array)                                      อาร์เรย์สองมิติจะมีรูปแบบตารางที่ประกอบด้วยแถว (Row) และคอลัมม์ (Column) การอ้าองอิงอาร์เรย์สองมิติจึงต้องระบุบแนวแถวและคอลัมม์  สำหรับรูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์สองมิติ  คือ                                                   ArrayName [L1 : U1 , L2 : U2]                                       โดยที่  ArrayName  คือชื่อของอาร์เรย์                    L1   คือขอบเขตล่างสุด  (Lower Bound)  ของแถว                   U1  คือขอบเขตบนสุด  (Upper Bound)   ของแถว                   L2   คือขอบเขตล่างสุด  (Lower Bound)  ของคอลัมน์                  U2  คือขอบเขตบนสุด  (Upper Bound)   ของคอลัมน์                 โดยสมมติว่าได้มีการกำหนดให้ K[4,3] หรือ K[0:3,0:2] ด้วยภาษา C ดังนี้                  int K[4] [3];                ซึ่งแสดงได้ดังรูป