โครงสร้างของอาร์เรย์
การเก็บอาร์เรย์ในคอมพิวเตอร์
เมตริกซ์สามเหลี่ยม

โครงสร้างอาร์เรย์         

           เป็นแบบหนึ่งของโครงสร้างที่เรียกว่า linear list
               ลักษณะของอาร์เรย์            คือตารางที่เป็นช่อง ๆ แต่ละช่องต้องเก็บข้อมูลแบบเดียวกัน เป็นตัวอักษรล้วนหรือเป็นตัวเลขล้วน ขนาดของแต่ละช่องต้องเท่ากันหมด อาร์เรย์เป็นโครงสร้างที่เกือบกล่าวได้ว่าเป็นที่คุ้นเคยมากที่สุดและเข้าใจง่ายที่สุด ทั้งนี้เนื่องจากโครงสร้างของอาร์เรย์ตรงกับความเป็นจริงตามธรรมชาติของข่าวสารข้อมูลหลายประการ เช่น บัญชีการเงิน คะแนนนักเรียนในชั้น บัญชีพนักงานของบริษัท ข้อมูลที่แบ่งเป็นพวกหรือหมวดหมู่ ฯลฯ นอกจากนี้โปรแกรมที่เขียนคำนวณงานเมตริกซ์ (matrix) หรือพีชคณิตเชิงเส้น ก็ต้องใช้อาร์เรย์เป็นที่เก็บตัวเลข นอกจากนี้อาร์เรย์ยังเป็นโครงสร้างพื้นฐานของโรงสร้างที่สำคัญอื่น ๆ อีก เช่น สแตก,คิว,ต้นไม้ เป็นต้น

 

             โดยสรุปเรานิยามได้ว่าอาร์เรย์คือกลุ่มของค่า ชนิดเดียวกัน ที่เรียงกันตามลำดับอย่างมีแบบแผน เราสามารถใช้ค่า (Access) ต่าง ๆ ในอาร์เรย์โดยอาศัยตัวห้อยหรือsubscript เช่น อาร์เรย์ A มีขนาด 100 ตำแหน่ง A(5)จะหมายถึงค่าของอาร์เรย์ตำแหน่งที่ 5 ในอาร์เรย์นั้น เลข5ในวงเล็บเรียกว่าตัวห้อยหรือ subscript จำนวน subscript ที่ต้องใช้ในการใช้ค่าในอาร์เรย์เรียกว่า มิติ หรือ ไดเมนชั่น (dimension) ของอาร์เรย์นั้น

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

ถ้า lower bound = 1 จะเขียนอาร์เรย์ A เป็น A(u) เช่น DIMENSION NUM(5)ในภาษาฟอร์แทรนจะหมายถึงกำหนดใช้อาร์เรย์ชื่อ NUM ขนาด 5 ช่อง ดังนี้

ถ้าเราเขียนคำสั่ง NUM (3 ) = 75 ค่า 75 จะไปปรากฏหรือเก็บอยู่ในช่องที่ 3 ดังนี้

การเก็บอาร์เรย์ในคอมพิวเตอร์

1.อาร์เรย์ 1 มิติ
               ในการใช้อาร์เรย์ ผู้ใช้(นักเขียนโปรแกรม) สามารถอ้างถึงหรือใช้อาร์เรย์ โดยระบุถึงชื่อของอาร์เรย์นั้น และสามารถใช้ค่าใด ๆ ในอาร์เรย์นั้นได้โดยใช้ชื่อกับตัวห้อยหรือ subscript อาร์เรย์ A(N)หมายถึง อาร์เรย์ที่ชื่อ A ที่สามารถเก็บค่าได้ N ค่าหรือเป็นตารางแถวเดียวที่มีช่องอยู่ N ช่อง แต่ละช่องมีชื่อ A(1),A(2),...,A(N) ตามลำดับ ในระดับที่ลึกเข้าไปในระบบคอมพิวเตอร์อีก 1 ระดับ (ระดับ system programming)ชื่อ A จะเป็นแอดเดรสของอาร์เรย์ในพื้นที่ความจำ ถ้าแต่ละช่องอาร์เรย์กินเนื้อที่ C เวิร์ด (word) ตำแหน่งหรือแอดเดรสของค่าตัวที่ i ในอาร์เรย์ [ หรือ A(i)] หาได้โดยการนำแอดเดรสตั้งต้นของอาร์เรย์นั้น (นั่นคือตำแหน่งของ A) บวกเข้ากับระยะทางจากจุดตั้งต้นนั้นไปถึงตำแหน่งที่ i ดังรูป

แอดเดรสของ A(i) เขียนเป็นสูตรได้ว่า

แอดเดรส [A(i)]= แอดเดรส [A(1)] + C(i - 1)

ในกรณีทั่วไปเมื่ออาร์เรย์มี lower bound เป็น 1 และ upper bound เป็น u อาร์เรย์ทั่วไปนี้จะเป็น A(l : u) ค่าในอาร์เรย์ทั่วไปจะเก็บตั้งแต่ A(l) จนถึง A(u) ค่า u ต้องมีค่ามากกว่าค่า l เสมอ ส่วนค่า l จะเป็นค่าจำนวนเต็ม บวกหรือลบก็ได้

จำนวนช่องใน     A(l : u)     =       u - l + 1
             แอดเดรส [A(i)]     =       แอดเดรส [A(l)] + C(i - l)

2. อาร์เรย์ 2 มิต รูปแบบของอาร์เรย์ 2 มิติ จะเป็น A[1 : M,1 : N] อาร์เรย์ 2 มิติ จะมี M แถว (row) และ แต่ละแถวมี N ค่า

ÃÙ»โครงสร้างของอาร์เรย์ 2 มิติ

เมื่อเก็บอาร์เรย์ 2 มิติ แบบซีเควนเชียล อาจเก็บได้ 2 แบบ คือ

1.แบบ row major หรือแบบ lexicographic order
              ลักษณะการเก็บจะเก็บแต่ละแถว ต่อ ๆ กันไปดังนี้
                            A(1,1) A(1,2) ... A(1,N) A(2,1) A(2,2) ... A(2,N)

                            A(3,1) A(M,2) ... A(M,N)

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

แอดเดรส [A(i,j)] = แอดเดรส [A(1,1)] + C(i - 1)N + C(j - 1)
                ในกรณีทั่วไป อาร์เรย์ 2 มิติจะมีรูปร่างเป็น A[l1 : u1 , l2 : u2]
                โดยที่         l1 เป็น lower bound ของมิติที่1
                                u1 เป็น upper bound ของมิติที่1
                                 l2  เป็น lower bound ของมิติที่2
                                u2 เป็น upper bound ของมิติที่2

                การหาแอดเดรสของ A(i,j) สามารถคิดในทำนองเดียวกันดังนี้ ก่อนที่จะถึงแถวที่ i จะต้องข้ามไป i - l1 แถว แต่ละแถวมี u2 - l2 + 1 ค่า แต่ละค่ากินเนื้อที่ C เวิร์ด นั่นคือ ต้องข้าม ไปคิดเป็น   C(u2 - l2 + 1)(i - l1) ตำแหน่ง จากนั้นค่อยข้ามไปอีก j - l2 ค่า (ของแถวที่ i) ก็จะถึงค่า A(i,j) แอดเดรส [A(i,j)] = แอดเดรส [A(l1,l2)] + C (u2 - l2 + 1) (i - l1) + C(j - l2)

2.แบบ column major
                 การเก็บอาร์เรย์ 2 มิติในลักษณะนี้ใช้ในภาษาฟอร์แทรนเนื่องจากว่า ฟอร์แทรนเป็นภาษาที่ใช้กับเครื่องคอมพิวเตอณืบางรุ่นในยุคแรก ๆ และเครื่องรุ่นนั้นมีโครงสร้างแอดเดรสซึ่งเหมาะกับการเก็บข้อมูลอาร์เรย์ 2 มิติอย่างคอลัมน์เมเจอร์มาก ดังนั้นโปรแกรมแปลภาษาฟอร์แทรนจึงกำหนดให้เก็บอาร์เรย์ 2 มิติ ดังกล่าว
                  ลักษณะการเก็บอาร์เรย์ 2 มิติ A[ 1 : M ,1 : N]แบบซีเควนเชียลแบบนี้จะเป็น A(1,1)A(2,1)A(3,1,)...A(M,1)A(1,2)A(2,2)...A(M,2)...A(1,N)A(2,N)...A(M,N)

                  ส่วนสูตรการหาแอดเดรสของค่า A(i,j)ในอาร์เรย์ 2 มิติ A[l1 : u1 , l2 : u2] จะเก็บไว้เป็นการฝึกหัดสำหรับท่านผู้อ่าน

          3. อาร์เรย์ 3 มิติ      อาร์เรย์ 3 มิติ A[1 : 2, 1: 4 , 1: 4] จะหมายถึงอาร์เรย์ที่มี lower bound และ upper bound ของมิติต่าง ๆ ดังนี้
                  lower bound ของมิติที่ 1 คือ 1 upper bound ของมิติที่ 1 คือ 2
                  lower bound ของมิติที่ 2 คือ 1 upper bound ของมิติที่ 2 คือ 4
                  lower bound ของมิติที่ 3 คือ 1 upper bound ของมิติที่ 3 คือ 4

                  อาร์เรย์ 3 มิติ เมื่อเก็บแบบซีเควนเชียลก็สามารถเก็บได้ 2 แบบคือแบบ row major หรือ column major เมื่อเก็บแบบ row major จะมีลำดับการเก็บค่าต่าง ๆ ดังนี้

                  A(1,1,1) A(1,1,2) A(1,1,3) A(1,1,4) A(1,2,1) A(1,2,2) A(1,2,3)
                  A(1,2,4) A(1,3,1) A(1,3,2) A(1,3,3) A(1,3,4) A(1,4,1) A(1,4,2)
                  A(1,4,3) A(1,4,4) A(2,1,1) A(2,1,2) A(2,1,3) ... A(2,4,3) A(2,4,4)

                  จะเห็นได้ว่าการเก็บแบบ row major นี้อินเด็กซ์หรือซับสคริปต์ของมิติที่ 3 จะแปรค่าเร็ซที่สุด รองลงมาก็ของมิติที่ 2 ส่วนมิติที่ 1 จะแปรค่าซับสคริปต์ช้าที่สุด เมื่อพิจารณาอาร์เรย์ A[1 : L , 1 : M , 1 : N] เราจะกล่าวได้ว่าอาร์เรย์ 3 มิตินี้ก็คืออาร์เรย์ 2 มิติ ขนาด M x N จำนวน L นั่นเอง เมื่อเก็บอาร์เรย์นี้อย่าง row major

                  ในการหาแอดเดรสของ A(i,j,k)เราต้องข้ามแผ่น 2 มิติขนาด M x N ไปเป็นจำนวน (i - 1) แผ่น นั่นคือข้ามไป C(i - 1) MN เวิร์ด เมื่อเทียบกับระยะจุดตั้งต้น A(1,1,1) แล้วจะเป็นแผ่นที่ i ถ้าเราต้องการไปอยู่แถวที่ j ของแผ่นที่ i นี้ เราต้องข้ามไปอีก (j - 1 )แถว ขนาดของแต่ละแถว คือ N นั่นคือข้ามจำนวนค่าไป (j - 1)N ค่า คิดเป้นระยะทาง (จำนวนเวิร์ด) ได้เป็น (k - 1) ค่า ก็ถึงแอดเดรสของ A(i,j,k)

                   จะเป็น แอดเดรส [A(i,j,k)] = แอดเดรส [A(1,1,1)] + C(i-1)MN+C(j - 1)N+C(k - 1)

                   กรณีทั่วไปอาร์เรย์ 3 มิติ จะมีรูปร่าง เป็น A[l1 : u1, l2 : u2 , l3 : u3] เมื่อเก็บแบบ row major เราสามารถหาแอดเดรสของ A(i,j,k) โดยการคิดในทำนองเดียวกัน เมื่อเทียบกับที่หามาแล้วจะได้ความสอดคล้องดังนี้
                                       L -- > u1 - l1 + 1
                                      M -- > u2 - l2 + 1
                                      N -- > u3 - l3 + 1
                                   i - 1 -- > i - l1
                                   j - 1 -- > j - l2
                                  k - 1 -- > k - l3
                   ซึ่งสูตรหาแอดเดรสของ A(i,j,k) ก็สามาร¶หาได้ในแบบเดียวกันกับที่กล่าวมาแล้ว ปกติแล้วเราจะใช้อาร์เรย์แค่ 3 มิติเท่านั้น ในภาษาโปรแกรมบางภาษาก็ยอมให้ใช้มิติได้มากกว่า 3 มิติ เช่น ภาษา PL/1 ในภาษาฟอร์แทรนก็เช่นกัน คอมไพเลอร์บางรุ่นก็ให้ใช้ได้แค่ 3 มิติ บางรุ่นยอมให้ใช้ได้ถึง 31 มิติ เป็นต้น

เมตริกซ์สามเหลี่ยม Trianglar Matrix      

                             ถึงแม้ว่านักเขียนโปรแกรมไม่จำเป็นต้องยุ่งเกี่ยวกับการแปลงค่าที่อยู่ของข้อมูลในอาร์เรย์ให้เป็นค่าที่อยู่จริงในคอมพิวเตอร์ ในบางครั้งความรู้ที่ว่านี้ก็สามารถนำมาใช้ในการออกแบบโครงสร้างข้อมูลที่ประหยัดพี้นที่ความจำได้ ดังเห็นได้จากการแทนเมตริกซ์แบบสามเหลี่ยม ปกติแล้วเมตริกซ์จะถูกใช้เพื่อแทนความสัมพันธ์หระหว่างสิ่งของสองสิ่ง ถ้า M(i,j) คือ เมตริกซ์ที่ว่านี้ เราสามารถเก็บค่าต่าง ๆ ใน M(i,j) โดยใช้อาร์เรย์แบบ 2 มิติ ได้ ถ้าM(i,j) เป็นเมตริกซ์จัตุรัส ขนาด N x N เราก็สามารถใช้อาร์เรย์ 2 มิติ M(N,N) แทนเมตริกซ์นี้ได้ เมตริกซ์แบบสามเหลี่ยมที่จะกล่าวถึงนี้คือครึ่งหนึ่งของเมตริกซ์จัตุรัส

;โครงสร้างของเมตริกซ์จัตุรัส กับเมตริกซ์สามเหลี่ยม

ตัวอย่าง     สมมติว่ามีคน 5 คน แทนด้วยตัวเลข 1,2,3,4,5 โดยแบ่งเป็นกลุ่มที่หนึ่ง [1,3,5] และกลุ่มที่ สอง [2,4] และกำหนดให้คนภายในกลุ่มเป็นญาติกัน ความสัมพันธ์ที่ว่านี้แทนด้วยเมตริกซ์จัตุรัสได้ดังนี้ ค่าในแต่ละช่อง M(i,j) จะเป็น 1 ถ้า i และ j เป็นญาติกัน นอกจากนี้กำหนดให้ M(i,j) = 0 สำหรับค่า i ตั้งแต่ 1 ถึง 5 จะเห็นได้ว่าสามเหลี่ยมล่างและบนเหมือนกัน ดังั้นเมตริกซ์จัตุรัสนี้จึงสามารถถูกแทนด้วยเมตริกซ์สามเหลี่ยมดังรูปที่ 2.7 (ข)
                   ปัญหาที่ตามมาคือ เราจะเก็บเมตริกซ์สามเหลี่ยมในคอมพิวเตอร์อย่างไร คำตอบที่ง่ายที่สุดคือเก็บโดยใช้อาร์เรย์ 2 มิติ ซึ่งจะใช้เนื้อที่ 25 ตำแหน่งโดยจะเสียที่ว่างที่ไม่ใช้ (เพราะซ้ำซ้อน) 15 ช่อง หรือตำแหน่ง แต่วิธีที่ดีกว่านี้คือเก็บเมตริกซ์สามเหลี่ยมนี้โดยใช้อาร์เรย์ 1 มิติ ที่มี 10 ช่อง ดังรูปที่ 2.8

เมตริกซ์จัตุรัสกับเมตริกซ์สามเหลี่ยมที่สามารถใช้แทนเมตริกซ์จัตุรัสตามรูป(ก) ได้

 

รูปอาร์เรย์ที่ใช้แทนเมตริกซ์สามเหลี่ยมในรูป (ข) การแทนแบบนี้เราต้องการฟังก์ชันความสัมพันธ์ระหว่างข้อมูล (mapping function) เพื่อที่จะหาว่า M(4,2) มีค่า 1 ซึ่งตรงกับ T (5)

จำนวนช่องก่อนถึงแถว i = 1 + 2 + 3 ... + ( i - 2 ) = (i - 2) ( i - 1) 2 T(k) ซึ่งก็คือ M(i,j) สามารถหาได้ในอาร์เรย์ T โดยคำนวณค่า k ดังนี้
  k คือ จำนวนช่องก่อนถึงแถว i + จำนวนช่องถึงคอลัมน์ j ในแถว i = ( i - 2)(i - 1) + j ; 2 <= i <=5 ; 1 <= j <= 4 2 ตามตัวอย่างที่ 2.6 จะเห็นได้ว่า M(4,2) ตรงกับ T(5) ดังนี้ k = (4 - 2)(4 - 1) + 2 = 3 + 2 = 5 2

การใช้สูตรความสัมพันธ์ระหว่างข้อมูลนี้ เราต้องกำหนดว่า M(i,j) = 0