โครงสร้างข้อมูลแบบอาร์เรย์
  
         อาร์เรย์ เป็นแบบหนึ่งของโครงสร้างที่เรียกว่า Linear List ซึ่งมีจำนวนรายการ ( Element) จำกัด และข้อมูลที่เก็บอยู่ในอาร์เรย์แต่ละช่องจะต้องเป็นข้อมูลชนิดเดียวกัน อยู่ภายใต้ตัวแปรชื่อเดียวกัน   โดยขนาดของแต่ละช่องต้องเท่ากันหมด การอ้างถึงข้อมูลในแต่ละช่องของของอาร์เรย์    ต้องอาศัยตัวห้อย Subscript เช่น กำหนดให้ Array A มีขนาด 100 รายการ A[5]   จะหมายถึง  ค่าของอาร์เรย์ตำแหน่งที่ 5 ในอาร์เรย์นั้น ซึ่ง Subscript ก็คือ เลข 5 จำนวน Subscript ที่ต้องการใช้เวลาเรียกใช้ค่าใน   Array เรียกว่า มิติ   ไดเมนชั่น ( Dimention) ของ Array นั้น

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

การสร้าง Array ขึ้นมาใช้งานนั้น ต้องคำนึงถึง
        1. ชื่อของ Array
        2. ขนาดของ Array แต่ละช่อง และมิติของ Array
        3. ค่าสูงสุด ( Upper Bound) และค่าต่ำสุด (Lower Bound) ในแต่ละมิติ

 

ARRAY 1 มิติ
          คือ Array ที่มีลักษณะเป็นตารางแถวเดียว Array 1 มิติ จะมีลักษณะโดยทั่วไปดังนี้

 

   ถ้า Lower Bound = 1 สามารถเขียน Array เป็น A [u] ก็ได้ เช่น
            Ex1 ถ้าต้องการสร้าง Array N เพื่อเก็บตัวเลขประเภท Integer ให้มีขนาด 5 ช่อง N [1 : 5 ] สามารถเขียนเป็น N [5]

              เนื่องจาก Integer 1 ตัวจะใช้เนื้อที่ในหน่วยความจำ 2 Bytes ดังนั้น Array N จะใช้เนื้อที่ในหน่วยความจำ
ทั้งหมด 10 Bytes

              หมายเหตุ ในภาษาซี ช่องแรกของอาร์เรย์จะเริ่มจาก 0

             การดำเนินงาน : มี 2 การดำเนินงาน คือ การดึงค่าของแถวลำดับมาใช้ ( retrieve) และการกำหนดค่าให้สมาชิก
ของแถวลำดับ( update) ดังนี้
           -  การดึงค่าของแถวลำดับมาใช้ เช่น ประโยค X = A[I]; หมายถึงการดึงค่าของสมาชิกตัวที่ I ของแถวลำดับ A ให้กับตัวแปร X
            ถ้าสั่ง N[3] = 30 หมายถึง ค่า 30 จะถูกนำไปเก็บใน Array N ช่องที่ 3
          - การกำหนดค่าให้กับสมาชิกของแถวลำดับ เช่น ต้องการ กำหนดค่า X ให้กับสมาชิกตัวที่ I ของ แถวลำดับ A นั่นคือให้ A[I] = X;

การหาจำนวนช่องใน Array 1 มิติ
             การคำนวณหาจำนวนช่องของ Array คำนวณจาก

             Ex 1 จงคำนวณหาจำนวนช่องของ Array B [ -3 : 9 ]
                       จำนวนช่องของ B [ -3 : 9 ] = 9 - - 3 + 1
                                                                = 13

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

การคำนวณหาตำแหน่ง ( Address) ของ Array ตัวที่ I ในหน่วยความจำ
              Array 1 ชุด จะเป็นข้อมูลชนิดเดียวกัน จึงทำให้ Array แต่ละตัวใช้เนื้อที่หน่วยความจำเท่ากันทุกตัว และ Address ของหน่วยความจำในคอมพิวเตอร์จะต่อเนื่องกัน เราสามารถเข้าถึงข้อมูลในทุกตำแหน่งได้โดยตรง หากเราทราบ Address เริ่มต้นของ Array ตัวแรก (ช่องแรก)
Ex Array NA [1 : 5] ซึ่ง Address NA [1] อยู่ที่ 1001 และแต่ละช่องของ Array NA ใช้เนื้อที่ 25 Bytes

 

             โดยปกติแล้วคอมพิวเตอร์จะเก็บเพียง Address เริ่มต้นของ Array และใช้ Address เริ่มต้นนั้น ร่วมกับลักษณะ
การจัดเก็บข้อมูลในแต่ละช่อง (ซึ่งก็คือ ในแต่ละช่องใช้เนื้อที่หน่วยความจำเท่าไร) ทำให้คอมพิวเตอร์ สามารถคำนวณหา Address ของช่องใดๆ ได้จาก
                    Address ของ A [I] = Address ของ A ตัวแรก + จำนวนช่องที่เก็บมาแล้ว x ขนาดของแต่ละช่อง
เมื่อเขียนเป็นสูตร จะได้เป็น

                                

 

         จาก Array NA ในตัวอย่าง ต้องการหา Address ของ NA [3]
         NA [3] = 1001 + (3 - 1) * 25
                      = 1051

 

อาร์เรย์ 2 มิติ
       
         อ
าร์เรย์ 2 มิติ คือ อาร์เรย์ที่มีลักษณะที่เป็นตารางที่มี 2 ด้าน คือ ทางด้านแนวนอน ( ROW) และแนวตั้ง ( COLUMN) มีจำนวนช่องเท่ากับ จำนวนช่องทางด้านแนวนอน ( ROW) คูณกับจำนวนช่องทางด้านแนวตั้ง ( COLUMN) การอ้างถึง Array 2 มิติ ต้องใช้ Subscript 2 ตัว คือ ROW และ COLUMN การกำหนดอาร์เรย์ 2 มิติทำได้โดย  

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

         l1 คือ lower bound ของมิติที่ 1 u1 คือ upper bound ของมิติของที่ 1
         l2 คือ lower bound ของมิติที่ 1 u2 คือ upper bound ของมิติของที่ 1

          เช่น ARO [ 5 : 20 , 30 : 50 ] คือ    การกำหนดให้ อาร์เรย์ 2 มิติ ชื่อ ARO มีจำนวน 16 ช่องทางด้านแนวนอน ( ROW) เริ่มที่ 5 ถึง 20 และ 21 ช่องทางด้านแนวตั้ง ( COLUMN) เริ่มที่ 30 ถึง 50  เช่นเดียวกับอาร์เรย์ 1 มิติ   คือ
ถ้า l1 หรือ l2 เป็น 1 ก็สามารถกำหนดโดยไม่ใส่ l1 หรือ l2 ก็ได้ เช่น STR [ 20 , 50 ] กำหนดให้ อาร์เรย์ 2 มิติ ชื่อ STR มีจำนวนช่อง 20 ช่องทางด้านแนวนอน ( ROW) โดยเริ่มที่ 1 ถึง 20 และ 50 ช่องทางด้านแนวตั้ง ( Column) เริ่มที่
1 ถึง 50
          หมายเหตุ ในภาษาซี การกำหนดอาร์เรย์ 2 มิติ ต้องประกาศดังนี้ ชื่อของอาร์เรย์ [ u1 ] [ u2 ] เช่น int num[5][10];

การคำนวณหาจำนวนช่องของ ARRAY 2 มิติ
        จำนวนช่องทางด้านแนวนอน ( ROW) หาได้จาก

                    m = u1 - l1 + 1

        จำนวนช่องทางด้านแนวตั้ง ( COLUMN) หาได้จาก

                   n = u2 - l2 + 1

        ดังนั้น   จำนวนช่องทั้งหมดของ A [ l1 : u1, l2 : u2 ] = m x n

การจัดเก็บ Array 2 มิติในหน่วยความจำ
        1. แบบ Row Major Order จะเก็บแต่ละแถวตามแนวนอนต่อๆ กันไป โดยเก็บทีละแถวจนเต็ม แล้วค่อยเริ่มเก็บ
แถวใหม่ เช่น
         กำหนดอาร์เรย์ 2 มิติ ชื่อ A [ 1 : 4 , 1 : 5 ] ซึ่งจัดเก็บแบบ Row Major Order


         การจัดเก็บจะเก็บแต่ละแถวต่อ ๆ กันไป ดังนี้
       A [1 , 1] A [1 , 2] A [1 , 3] A [1 , 4] A [2 , 1] A [2 , 2]
      A [2 , 3] A [2 , 4] A [2 , 5] ………. A [4 , 5]

การคำนวณหา Array ตัวที่ ( i , j ) ตรงกับช่องที่เท่าไร
       เราสามารถคำนวณหาหมายเลขช่องของอาร์เรย์ ได้จากสูตร

                    หมายเลขช่องของ A [ i , j ] = i - I1 + 1, j - I2 + 1

        ตัวอย่าง จาก Array XY [ 1 : 5 , 3 : 7 ] จงหาว่า XY [ 4 , 3 ] ตรงกับ อาร์เรย์ ช่องที่เท่าไรถ้าเริ่มนับอาร์เรย์ช่องแรก
เป็น [ 1 , 1 ]


        XY [ 4 , 3 ] ตรงกับช่องที่ = i - I1 + 1 , j - I2 + 1
                                                = 4 , 1
        ดังนั้น     XY [ 4 , 3 ] ตรงกับแถวที่ 4 คอลัมน์ที่ 1 ของอาร์เรย์ XY

การคำนวณหา ADDRESS ของอาร์เรย์ 2 มิติ ที่จัดเก็บแบบ Row Major Order
         เช่นเดียวกันกับ Array 1 มิติ คอมพิวเตอร์จะเก็บเฉพาะ Address ของ Array ตัวที่ 1 แล้วนำไปคำนวณหาค่า Array A [ i , j ]   ซึ่งเป็นอาร์เรย์ที่มี I1 และ I2 เป็น 1  
          การหาแอดเดรส A [ i , j ] ในอาร์เรย์ A [1 : m , 1 : n ] นั้น เริ่มจากขั้นแรกเราต้องข้ามไป i - 1 แถว แต่ละแถวมีค่า
n ค่า แต่ละค่าใช้เนื้อที่ขนาด S นั่นคือเราจะต้องข้ามไป ( i - 1)nS จาก A(1 , 1) ตอนนี้เท่ากับเราอยู่ที่ตำแหน่ง A [ i , 1 ] ต่อไปจะต้องข้ามไปอีก j - 1 ค่าในแถวที่ i แต่ละค่าใช้เนื้อที่ S ก็คือ ( j - 1)S ก็จะถึงตัวที่ j ในแถวที่ i ซึ่งก็คือตัวที่ A [ i , j ] ซึ่งสูตรที่ใช้ก็คือ
                      Ad A [ i , j ] = Ad ตัวแรก + ( i - 1 )nS + ( j - 1 ) S

          ในกรณีทั่วไป อาร์เรย์ 2 มิติจะมีรูปร่างเป็น A [ l1 : u1 , l2 : u2 ]
          โดยที่ l1 เป็น lower bound ของมิติที่ 1
                  u1 เป็น upper bound ของมิติที่ 1
                  l2 เป็น   lower bound   ของมิติที่ 2
                  u2 เป็น upper bound ของมิติที่ 2

       ดังนั้นถ้าต้องการหา Ad A [ i , j ] ของอาร์เรย์ 2 มิติ A [ I1 : u1, I2 : u2 ] ก็ต้องใช้สูตร

                               Ad A [ i , j ] = Ad ตัวแรก + ( i - l1 )nS + ( j - I2 )S

        Ex Array XY [ 1 : 5 , 3 : 7 ] แต่ละช่องมีขนาด 10 Bytes ซึ่งนำไปเก็บในหน่วยความจำแบบ Row Major Order โดยเริ่มต้นเก็บที่ Address 10000 จงหา Address เริ่มต้นของ XY [4 , 3]
             m = u1 - I1 + 1
             m = 5 - 1 + 1 = 5
             Ad A [ i , j ] = Ad ตัวแรก + ( i - 1 )nS + ( j - I2 ) S
                                  = 10000 + ( 4 - 1 )5x10 + ( 3 - 3 )10
                                  = 10000 + 150 +0
                                  = 10150

          2. แบบ Column Major Order การเก็บอาร์เรย์ 2 มิติในลักษณะนี้มีใช้ในภาษาฟอร์แทรน ( FORTRAN) ซึ่งจะเก็บให้เต็มทีละคอลัมน์ แล้วจึงไปเริ่มคอลัมน์ใหม่ดังนี้
           กำหนดอาร์เรย์ 2 มิติ ชื่อ A [ 1 : 4 , 1 : 5 ] ซึ่งจัดเก็บแบบ Column Major Order

             การจัดเก็บจะเก็บค่าแต่ละคอลัมน์แถวต่อๆ กันไป ดังนี้
           A [1 , 1] A [2 , 1] A [3 , 1] A [4 , 1] A [1 , 2] A [2 , 2]
           A [3 , 2] A [4 , 2] A [1 , 3] ………. A [4 , 5]

การคำนวณหา ADDRESS ของอาร์เรย์ 2 มิติ ที่จัดเก็บแบบ Column Major Order
           คล้ายๆ กับการคำนวณหา Address ของอาร์เรย์ที่มีการจัดเก็บแบบ Row Major Order การจะคำนวณหา Address ของ Array A [ i , j ] ซึ่งเป็นอาร์เรย์ที่มี I1 และ I2 เป็น 1 จะเริ่มจาก เราต้องข้ามไป j - 1 คอลัมน์ แต่ละคอลัมน์มีค่า m ค่า แต่ละค่าใช้เนื้อที่ขนาด S นั่นคือจะต้องข้ามไป ( j - 1) mS จาก A [ 1,1 ] ตอนนี้เท่ากับเราข้ามมาอยู่ที่ A [ i , j ] ต่อไปจะต้องข้ามไปอีก i - 1 ค่าในคอลัมน์ที่ j แต่ละค่าใช้เนื้อที่ S ก็คือ ( i - 1) S ก็จะถึงตัวที่ j ในแถวที่ i ซึ่งก็คือตัวที่ A [ i , j ] ซึ่งสูตรที่ใช้ก็คือ

                               Ad A [ i , j ] = Ad ตัวแรก + ( j - 1) mS + (i - 1)S  

           ดังนั้นถ้าต้องการหา Ad A [ i , j ] ของอาร์เรย์ 2 มิติ A [ I1 : u1 , I2 : u2 ] ก็ต้องใช้สูตร

 

อาร์เรย์ 3  มิติ

          อาร์เรย์ 3 มิติ คือ อาร์เรย์ที่มีลักษณะเป็นตารางที่มี 3 ด้าน คือ ทางด้านแนวนอน ( ROW) และแนวตั้ง (COLUMN) และแนวลึก    มีจำนวนช่องเท่ากับ จำนวนช่องทางด้านแนวนอน ( ROW) คูณกับจำนวนช่องทางด้านแนวตั้ง ( COLUMN) คูณกับจำนวนช่องทางด้านแนวลึก  ( DEEP) การอ้างถึง Array 3 มิติ ต้องใช้ Subscript 3 ตัว คือ ROW, COLUMN และ DEEP การกำหนดอาร์เรย์ 3 มิติทำได้โดย

                                                ชื่อของอาร์เรย์ [ I1 : u1 , I2 : u2 , I3 : u3 ]

                 I1 คือ lower bound ของมิติที่ 1 u1 คือ upper bound ของมิติของที่ 1
                 I2 คือ lower bound ของมิติที่ 2 u2 คือ upper bound ของมิติของที่ 2
                 I3 คือ lower bound ของมิติที่ 3 u3 คือ upper bound ของมิติของที่ 3
              เช่น B [1 : 2 , 1 : 4 , 1 : 3 ] ( หรือเขียนเป็น B [2 , 4 , 3] ก็ได้) คือการกำหนดให้ อาร์เรย์ 3 มิติ ชื่อ B มีจำนวน 2 ช่องทางด้านแนวนอน  ( ROW) เริ่มที่ 1 ถึง 2 และ 4 ช่องทางด้านแนวตั้ง ( COLUMN) เริ่มที่ 1 ถึง 4 และ 3 ช่องทางด้าน
  แนวลึก ( DEEP) เริ่มที่ 1 ถึง 3

  การคำนวณหาจำนวนช่องของ ARRAY 3 มิติ
             จำนวนช่องทางด้านแนวนอน ( ROW) หาได้จาก

                         m = u1 - I1 + 1

             จำนวนช่องทางด้านแนวตั้ง ( COLUMN) หาได้จาก

                         n = u2 - I2 + 1

             จำนวนช่องทางด้านแนวลึก ( DEEP) หาได้จาก

                         d = u3 - I3 + 1
  ดังนั้น   จำนวนช่องทั้งหมดของ   A [ I1 : u1 , I2 : u2 , I3 : u3 ] = m x n x d

  การจัดเก็บ Array 3 มิติในหน่วยความจำ
          1. แบบ Row Major Order จะเก็บแต่ละแถวตามแนวนอนต่อๆ กันไป โดยเก็บทีละแถวจนเต็ม แล้วค่อยเริ่มเก็บแถว
  ใหม่ เช่น
           กำหนดอาร์เรย์ 3 มิติ ชื่อ B [1 : 2 , 1 : 4 , 1 : 3] ซึ่งจัดเก็บแบบ Row Major Order

   การจัดเก็บจะเก็บแต่ละแถวต่อๆ กันไป โดยเก็บให้หมดแต่ละแถวก่อน จึงจะขึ้นแถวใหม่ดังนี้
B[1 ,1 , 1] B[1 , 1 , 2] B[1 ,1 , 3] B[1 , 2 ,1] B[1 , 2 , 2] B[1 ,2 ,3]
B[1 ,3 , 1] B[1 , 3 , 2] B[1 ,3 , 3] B[1 , 4 ,1] B[1 , 4 , 2] B[1 ,4 ,3]
B[2 ,1 , 1] B[2 , 1 ,2] B[2 ,1 , 3] B[2 , 2 ,1] B[2 , 2 , 2] B[2 ,2 ,3]
B[2 ,3 , 1] B[2 , 3 ,2] B[2 ,3 , 3] B[2 , 4 ,1] B[2 , 4 , 2] B[2 ,4 ,3]

        ดังนั้นถ้าต้องการหา Ad A [ i , j , k ] ของอาร์เรย์ 3 มิติ A [ I1 : u1 , I2 : u2 , I3 : u3 ] ที่มีการเก็บแบบ Row Major Order   ก็ต้องใช้สูตร

                           Ad A [ i , j , k ] = Ad ตัวแรก + ( i - I1 )nds + ( j - I2 )dS + ( k - I3 )S

         2. แบบ Column Major Order จะเก็บแต่ละแถวตามแนวตั้งต่อๆ กันไป โดยเก็บทีละคอลัมน์จนเต็ม แล้วค่อยเริ่มเก็บ
  คอลัมน์ใหม่ เช่น
          กำหนดอาร์เรย์ 3 มิติ ชื่อ [ 1 : 2 , 1 : 4 , 1 : 3] ซึ่งจัดเก็บแบบ Column Major Order

การจัดเก็บจะเก็บแต่ละคอลัมน์ต่อๆ กันไป โดยเก็บให้หมดแต่ละคอลัมน์ก่อน จึงจะขึ้นคอลัมน์ใหม่ ดังนี้
B[1, 1, 1] B[2, 1, 1] B[1, 2, 1] B[2, 2, 1] B[1, 3, 1] B[2, 3, 1]
B[1, 4, 1] B[2, 4, 1] B[1, 1, 2] B[2, 1, 2] B[1, 2 ,2] B[2, 2, 2]
B[1, 3, 2] B[2, 3, 2] B[1, 4, 2] B[2, 4, 2] B[1, 1, 3] B[2, 1, 3]
B[1, 2, 3] B[2, 2, 3] B[1, 3, 3] B[2, 3, 3] B[2, , 3] B[2, 4, 3]

           ดังนั้นถ้าต้องการหา Ad A [ i , j , k ] ของอาร์เรย์ 3 มิติ A [ I1 : u1 , I2 : u2 , I3 : u3 ] ที่มีการจัดเก็บแบบ Column Major Order   ก็ต้องใช้สูตร

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

  เมตริกซ์สามเหลี่ยม ( Triangular Matrix)
             เมตริกซ์สามเหลี่ยม    เป็นลักษณะของเมตริกซ์สี่เหลี่ยม (Square matrix) ที่มีข้อมูลเฉพาะ   ตอนบนหรือตอนล่างของ
  เส้นแทยงมุมหลัก มี 2 แบบคือ
           1. Lower Triangular Matrix เป็นเมตริกซ์ที่มีสมาชิกอยู่เหนือเส้นแทยงมุมหลักมีค่าเป็นศูนย์ทั้งหมด
               ตัวอย่าง   การนำ Lower Triangular Matrix มาเก็บในตัวแปรอาร์เรย์ 1 มิติ จะกระทำได้ 2 แบบ ดังนี้
      1. แบบ Row Major Order


        2. แบบ Column Major Order


            การคำนวณหาตำแหน่งของ a [ i , j ] แบบ Row Major Order ของ Lower Triangular Matrix
            พิจารณาข้อมูล
แถวที่ 1 มีสมาชิก 1 ตัวที่ไม่เป็น 0
แถวที่ 2 มีสมาชิก 2 ตัวที่ไม่เป็น 0
แถวที่ 3 มีสมาชิก 3 ตัวที่ไม่เป็น 0
แถวที่ 4 มีสมาชิก 4 ตัวที่ไม่เป็น 0
แถวที่ i มีสมาชิก i ตัวที่ไม่เป็น 0
โดยที่ i คือ แถว
ถ้าให้ L0 คือ Ad เริ่มต้น และสมาชิกแต่ละตัวใช้หน่วยความจำเท่ากับ S ดังนั้น
ad a[1 , 1] = L0
ad a[2 , 1] = L0 + 1S
ad a[3 , 1] = L0 + (1+2)S
ad a[4 , 1] = L0 + (1+2+3)S
ad a[ i , 1 ] = L0 + (1+2+3+…+ i -1)S
ad a[ i , j ] = L0 + (1+2+3+…+ i -1)S + ( j - 1 )S
จาก 1 + 2 + 3 + … + n = (n(n+1))/2

ดังนั้น 1 + 2 + 3 + … + n - 1 = ((n - 1)(n - 1 + 1))/2= ((n - 1)n)/2
ad a[ i , j ] = Ad เริ่มต้น + (( i( i - 1 ))/2)S + (j - 1)S

ตัวอย่าง จงคำนวณหาตำแหน่งของ Lower Triangle a [3 , 2] โดย a [1 , 1] อยู่ที่ตำแหน่ง 2000 และ แต่ละช่องใช้เนื้อที่ 10 bytes
สูตร ad a[ i , j ] = Ad เริ่มต้น + (( i( i - 1 ))/2)S + (j - 1)S
       ad a [3 , 2] = 2000 + ((3(3-1)/2)*10 + (2-1)10
                            = 2000 + 30 + 10
                            = 2040