โครงสร้างข้อมูลและขั้นตอนวิธีทางธุรกิจ: อาร์เรย์

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

                สมาชิกทุกตัวในอาร์เรย์ต้องเป็นข้อมูลชิดเดียวกันการเข้าถึงข้อมูลในอาร์เรย์แต่ละตำ
แหน่งใช้เวลาในการเข้าถึงข้อมูลเท่าๆกัน

การจัดเก็บข้อมูลใน อาร์เรย์ มี 3 แบบคือ

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

ArrayName[L:U]
โดยที่    ArrayName คือชื่อของอาร์เรย์
           L   คือขอบเขตล่างสุด (Lower Bound)
           U   คือขอบเขตบนสุด (Upper Bound)

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

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

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

กำหนดให้ : แอดเดรสเริ่มต้น (Base Address) = 1000
                                                              W      = 1

                อยากทราบว่าอาร์เรย์ a[10] ถูกจัดเก็บไว้ในหน่วยความจำแอดเดรสใด ก็สามารถ
คำนวณได้จากสูตรดังต่อไปนี้

LOC (a[i]   = B + w(i – L)
LOC (a[10] = 1000 + 1(10 – 0)
                    = 1010

ดังนั้นตำแหน่งอาร์เรย์ a[10] จะถูกเก็บไว้ในหน่วยความจำแอดเดรสที่ 1010 นั่นเอง



          รูปที่ 2.3 แสดงอาร์เรย์ number ที่จัดเก็บอยู่ภายในหน่วยความจำ
                       คอมพิวเตอร์
                  2. อาร์เรย์สองมิติ(Two Dimension Array)โครงสร้างอาร์เรย์สองมิติจะมีรูปแบบ
ตารางที่ประกอบด้วยแถว (Row) และคอลัมน์ (Column) ในเชิงคณิตศาสตร์ก็คือแมทริกซ์
(Matrix)การอ้างอิงข้อมูลในอาร์เรย์สองมิติจึงต้องระบุตำแหน่งแถวและคอลัมน์อาร์เรย์สองมิติมัก
จะถูกนำมาใช้งานอย่างแพร่หลาย อันเนื่องมาจากการจัดเก็บข้อมูลโดยทั่วไปนั้นมักอยู่ในรูปแบบ
ของตารางสองมิตินั่นเอง สำหรับรูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์สองมิติคือ

                                                   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];

ซึ่งแสดงได้ดังรูป



                 รูปที่ 2.4 รูปแสดงอาร์เรย์สองมิติชื่อ K ที่มีขนาดมิติ 4 x 3

                อย่างไรก็ตาม การจัดเก็บอาร์เรย์สองมิติในหน่วยความจำยังสามารถจัดเก็บได้ 2 วิธี
ด้วยกันคือ

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

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

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

รูปที่ 2.5 ข้อมูลของอาร์เรย์สองมิติชื่อ K ที่จัดเก็บอยู่ในหน่วยความจำ
หลักในรูปแบบเรียงแถวเป็นหลัก (Row Major Order)

                 3. อาร์เรย์สามมิติ(Three Dimension Array) หากพิจารณาให้ดี จะเห็นว่าอาร์เรย์
สามมิตินั้นก็คือการนำอาร์เรย์สองมิติมาเรียงซ้อนกันหลายๆ ชั้น (Page) ทำให้อาร์เรย์สามมิติ
นอกจากจะมีแถวและคอลัมน์แล้วก็จะมีความลึกเพิ่มขึ้นอีก ซึ่งความลึกนี้เองเกิดขึ้นจากการนำ
อาร์เรย์สองมิติมาเรียงซ้อนกัน

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

ArrayName [L1 : U1 , L2 : U2 , L3 : U3]
โดยที่ ArrayName คือชื่อของอาร์เรย์

L1     คือขอบเขตล่างสุด (Lower Bound) ของชั้น
U1    คือขอบเขตบนสุด (Upper Bound) ของชั้น
L2     คือขอบเขตล่างสุด (Lower Bound) ของแถว
U2    คือขอบเขตบนสุด (Upper Bound) ของแถว
L3     คือขอบเขตล่างสุด (Lower Bound) ของคอลัมน์
U3    คือขอบเขตบนสุด (Upper Bound) ของคอลัมน์

โดยสมมติว่าได้มีการกำหนดให้ S[3,4,5] หรือ S[0:2, 0:3, 0:4] ด้วยภาษา C ดังนี้

Int S [3] [4] [5] ;

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

S [0, 0, 0], S [0, 0 1], S [i, j, k], … , S [2, 3, 4]

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

LOC (S[i, j, k] ) = B + [w X R X C (i-L1) ] + [w X C (j-L2) ] + [w(k- L3) ]

                 และจากรูป คืออาร์เรย์สามมิติชื่อ S ที่จัดเก็บภายในหน่วยความจำในรูปแบบแถวเป็น
หลักในที่นี้ต้องการทราบตำแหน่งแอดเดรสที่เก็บข้อมูลอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4
จากรูปแบบของอาร์เรย์สามมิติ         S[L1 : U1 , L2 : U2 , L3 :U3]

ได้มีการประกาศอาร์เรย์ด้วยภาษา C ดังนี้ S [3] [4] [5]

ผลที่ได้ อาร์เรย์ K จะมีขอบเขตระหว่าง     K [0:2, 0:3, 0:4]

LOC (S[i, j, k] )    = B + [w X R X C (i-L1) ]+ [w X C (j-L2) ]+ [w(k- L3) ]

LOC (S[0, 3, 4] ) = 500 + [4 X 4 X 5 (0-0) ]+ [4 X 5 (3-0) ]+ [4(4- 0) ]

                             = 500 + 0 + 60 +16

                             = 576
ดังนั้นอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4 จะจัดเก็บอยู่ในตำแหน่งแอดเดรสที่ 576

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

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

Month [1] แทนเดือนที่ 1     คือเดือนมกราคม
Month [2]   แทนเดือนที่ 2     คือเดือนกุมภาพันธ์
:
Month [12] แทนเดือนที่12    คือเดือนธันวาคม

              อย่างไรก็ตาม ในภาษาคอมพิวเตอร์อย่างภาษา C หรือ JAVA หมายเลขลำดับของ
อาร์เรย์จะเริ่มต้นด้วยหมายเลข0 ในขณะที่ภาษา FORTRAN จะเริ่มต้นด้วยหมายเลข 1ดัง
นั้นหากมีการประกาศตัวแปรอาร์เรย์ด้วยภาษา C หรือ JAVA ก็อาจทำให้การใช้งานเพื่ออ้าง
อิงลำดับสมาชิกในอาร์เรย์เกิดความสับสนได้ จึงจำเป็นต้องใช้อย่างระมัดระวัง

2.2 ขอบเขตของอาร์เรย์ (Bounds)

        เลขดรรชนีในอาร์เรย์ประกอบด้วยช่วงขอบเขตของค่า ซึ่งประกอบด้วยขอบเขตล่างสุด
(Lower Bound)และขอบเขตบนสุด (Upper Bound) แต่อย่างไรก็ตาม ในภาษาคอมพิว
เตอร์บางภาษาจะกำหนดขอบเขตค่าดังกล่าวได้เพียงขอบเขตบนสุดเท่านั้นโดยขอบเขตล่าง
สุดจะถูกกำหนดคงที่เตรียมไว้อยู่แล้ว เช่น ภาษาC, C++, C# และ JAVAจะถูกกำหนดขอบ
เขตล่างสุดเท่ากับ 0 ในขณะที่ภาษาFORTRANจะถูกกำหนดขอบเขตล่างสุดเท่ากับ 1

ตัวอย่าง การกำหนดตัวแปรอาร์เรย์ในภาษา FORTRAN ซึ่งขอบเขตล่างสุดของภาษา
FORTRAN

จะเท่ากับ 1 (L = 1)

INTEGER a (5)

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



                                         รูปที่ 2.1รายละเอียดของอาร์เรย์ a

สำหรับการคำนวณหาจำนวนสมาชิกของอาร์เรย์หนึ่งมิติ สามารถคำนวณได้จากสูตรดังนี้

จำนวนสมาชิก = U – L + 1
โดยที่      U = ขอบเขตบนสุด (Upper Bound)
               L = ขอบเขตล่างสุด (Lower Bound)

สำหรับการคำนวณหาจำนวนสมาชิกของอาร์เรย์ a ก็จะเป็นไปตามสูตรดังนี้

จำนวนสมาชิก = U – L + 1
                      = 5 – 1 + 1
                      = 5
สำหรับในกรณีเดียวกัน แต่หากกำหนดตัวแปรอาร์เรย์ด้วยภาษา C ซึ่งขอบเขตล่างสุดของภาษา C
จะเท่ากับ 0 (L = 0)

Int b[5];



                                  รูปที่ 2.2 รายละเอียดของอาร์เรย์ b

สำหรับการคำนวณหาจำนวนสมาชิกของอาร์เรย์ a ก็จะเป็นไปตามสูตรดังนี้

จำนวนสมาชิก = U – L + 1

                      = 4 – 0 + 1

                      = 5

ในกรณีที่ อาร์เรย์มีมากกว่า 1 มิติ

U1    ขอบเขตบนสุด (Upper Bounds) ของแถว
L1    ขอบเขตล่างสุด (Lower Bounds) ของแถว
U2    ขอบเขตบนสุด (Upper Bounds) ของคอลัมน์
L2    ขอบเขตล่างสุด (Lower Bounds) ของคอลัมน์

จำนวนสมาชิก = (U1 – L1 + 1) x (U2 – L2 + 1)

โครงสร้างข้อมูลและขั้นตอนวิธีทางธุรกิจ

วันอังคารที่ 8 มีนาคม พ.ศ. 2559

อาร์เรย์

ไม่มีความคิดเห็น:

แสดงความคิดเห็น