บทที่ 2 อาร์เรย (Array )
อาร์เรย์ (Array)
คือ การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวแทนสมาชิกได้หลายๆตัวในคราวเดียวกัน ด้วยการใช้อเลขดรรชนี (Index) หรือชับสคริปต์ (Subscrip) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนตัวแปรนั้นๆ
ตัวแปรอาร์เรย์ (Array) หรือเรียกอีกชื่อหนึ่งว่า ตัวแปรชุด เป็นการจองพื้นที่ในหน่วยความ จำให้กับตัวแปร เพื่อให้ตัวแปรนั้นสามารถรับข้อมูลหรือเก็บข้อมูลได้มากกว่า 1 ค่า โดยค่าแต่ละค่านั้น จะถูกเก็บลงยังพื้นที่ของหน่วยความจำที่แตกต่างกัน พื้นที่ในหน่วยความจำจะใช้หมายเลขลำดับเป็นตัว จำแนกความแตกต่างของค่าตัวแปรแต่ละพื้นที่ด้วยการระบุหมายเลขลำดับที่เรียกว่า ดัชนี (Index) กำกับตามหลังชื่อตัวแปร โดยใช้หมายเลขลำดับตั้งแต่ 0, 1, 2, … เป็นต้นไป
ตัวแปรอาร์เรย์ (Array) หรือเรียกอีกชื่อหนึ่งว่า ตัวแปรชุด เป็นการจองพื้นที่ในหน่วยความ จำให้กับตัวแปร เพื่อให้ตัวแปรนั้นสามารถรับข้อมูลหรือเก็บข้อมูลได้มากกว่า 1 ค่า โดยค่าแต่ละค่านั้น จะถูกเก็บลงยังพื้นที่ของหน่วยความจำที่แตกต่างกัน พื้นที่ในหน่วยความจำจะใช้หมายเลขลำดับเป็นตัว จำแนกความแตกต่างของค่าตัวแปรแต่ละพื้นที่ด้วยการระบุหมายเลขลำดับที่เรียกว่า ดัชนี (Index) กำกับตามหลังชื่อตัวแปร โดยใช้หมายเลขลำดับตั้งแต่ 0, 1, 2, … เป็นต้นไป
คุณสมบัติสำคัญของอาร์เรย์มีดังนี้
1. อาร์เรย์เป็นตัวแทนกลุ่มข้อมูลที่มีความสัมพันธ์กัน
2. สมาชิกในอาร์เรย์จะมีคุณสมบัติเหมือนๆกัน กล่าวคือต้องมีชนิดข้อมูลเหมือนกันทั้งหมด
3. ขนาดของอาร์เรย์จะมีขนาดดคงที่เมื่อได้ถูกสร้างขึ้น
4. อาร์เรย์เป็นข้อมูลที่ผู้ใช้สามารถอ้างอิงเพื่อเข้าถึงข้อมูลที่ต้องการได้ทันที
การอ้างอิงตำแหน่งสมาชิกในอาร์เรย์
สำหรับการอ้างอิงตำแหน่งสมาชิกในอาร์เรย์ จะเริ่มต้นด้วยชื่ออาร์เรย์และตามด้วยเลขลำดับ(Position Number) กำกับไว้ด้วย ซึ่งเลขอาร์เรย์เหล่านี้สามารถเรียกได้หลายชื่อด้วยกัน เช่น ซับสคริปต์(Subscript) หรือดรรชนี (Index) ซึ่งต่างก็คือความหมายเดียวกันที่ใช้แทนกันได้ โดยเลขดรรชนีจะอยู่ภายในเครื่องหมาย( ) หรือ [ ] ก็ได้ ทั้งนี้ขึ้นอยู่กับภาษาคอมพิวเตอร์แต่ละภาษา
การจัดเก็บอาร์เรย์ในหน่วยความจำ
สมาชิกทุกตัวในอาร์เรย์ต้องเป็นข้อมูลชิดเดียวกันการเข้าถึงข้อมูลในอาร์เรย์แต่ละตำ
แหน่งใช้เวลาในการเข้าถึงข้อมูลเท่าๆกัน
การจัดเก็บข้อมูลใน อาร์เรย์ มี 3 แบบคือ
อาร์เรย์ 1 มิติ (One-Dimension Array)
คือ อะเรย์ที่มีเพียง 1 แถวนอน แต่มี แถวตั้งหลายแถว ซึ่งในการระบุตำแหน่งหรือตัวชี้(index) จะมีแต่ระบุแต่ตำแหน่งของแถวตั้งเท่านั้น โดยนับเริ่มจาก 0
Array Name คือ ชื่อของอาร์เรย์
L คือขอบเขตล่างสุด (Lower Bound)
U คือขอบเขตบนสุด (Upper Bound)
LOC ( a [ i ] ) = B + w ( i – L )
LOC ( a [ i ] ) = ตำแหน่งแอดเดรสที่เก็บ a[i] ในหน่วยความจำ
B = แอสเดรสเริ่มต้นของ a
w = จำนวนช่องของหน่วยความจำที่จัดเก็บข้อมูลต่อหนึ่งสมาชิก
ตัวอย่างเช่น ขนาดหน่วยความจำที่ใช้เก็บข้อมูลสมาชิก 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 นั่นเอง
รูปที่1 แสดงอาร์เรย์ number ที่จัดเก็บอยู่ภายในหน่วยความจำคอมพิวเตอร์
อาร์เรย์สองมิติ (Two Dimension Array)
อาร์เรย์สองมิติจะมีรูปแบบตารางที่ประกอบด้วยแถว (Row) และคอลัมม์ (Column) การอ้าองอิง
อาร์เรย์สองมิติจึงต้องระบุบแนวแถวและคอลัมม์ สำหรับรูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์สองมิติ คือ
ArrayName [L1 : U1 , L2 : U2]
โดยที่ ArrayName คือชื่อของอาร์เรย์
L1 คือขอบเขตล่างสุด (Lower Bound) ของแถว
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 รูปแสดงอาร์เรย์สองมิติชื่อ K ที่มีขนาดมิติ 4 x 3
อย่างไรก็ตาม การจัดเก็บอาร์เรย์สองมิติในหน่วยความจำยังสามารถจัดเก็บได้ 2 วิธี
ด้วยกันคือ
- การจัดเก็บด้วยการเรียงแถวเป็นหลัก (Row Major Order)
- การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก (Column Major Order)
ในกรณีการจัดเก็บอาร์เรย์สองมิติในหน่วยความจำด้วยการเรียงแถวเป็นหลัก การจัด
เรียงจะเริ่มต้นตั้งแต่แถวแรกและเรียงลำดับต่อไปในแต่ละคอลัมน์จนครบ จากนั้นก็ขึ้นแถวใหม่
ไปเรื่อยๆ จนกระทั่งแถวสุดท้าย
รูปที่ 3 ข้อมูลของอาร์เรย์สองมิติชื่อ K ที่จัดเก็บอยู่ในหน่วยความจำหลักในรูปแบบเรียงแถวเป็นหลัก (Row Major Order)
อาร์เรย์สามมิติ(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]
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
ได้มีการประกาศอาร์เรย์ด้วยภาษา 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
ไม่มีความคิดเห็น:
แสดงความคิดเห็น