ข้อมูลชนิดอาร์เรย์
อาร์เรย์ เป็นแบบหนึ่งของโครงสร้างที่เรียกว่า 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
ความหมายของอาร์เรย์
โครงสร้างข้อมูลแบบอาร์เรย์ (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