Array ตามปกติ โครงสร้างข้อมูลแบ่งออกเป็น 2 ประเภทใหญ่ๆ ด้วยกัน คือ
1.โครงสร้างข้อมูลแบบเชิงเส้น (Linear Lists) เป็นรายการต่อเนื่อง ข้อมูลที่จัดเก็บมีลักษณะเป็นแถวลำดับต่อเนื่องกันไป เช่น Array,Stack,Queues เป็นต้น
2.โครงสร้างข้อมูลแบบไม่เป็นเชิงเส้น (Non-Linear Lists) ตรงกันข้ามกับโครงสร้างแบบเชิงเส้น เช่น Trees และ Graphs เป็นต้น
โครงสร้างข้อมูลแบบArray
อาร์เรย์ หรือ แถวลำดับ คือการวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวแทนข้อมูลสมาชิกได้หลายๆตัวใช้เลขดรรชนี(Index)หรือซับสคริปต์(Subscript)เป็นตัวอ้างอิงตำแหน่งสมาชิกบนแถวลำดับ
| score[1] คือ คะแนนทดสอบของนักศึกษา score[50] คือ คะแนนทดสอบของนักศึกษาคนสุดท้าย |
คุณสมบัติสำสคัญของอาร์เรย์
1. อาร์เรย์เป็นตัวแทนของกลุ่มของมูลที่มีความสัมพันธ์กันเช่น เดือน 12 เดือน ซึ่งประกอบด้วยเดือนมกราคมถึงเดือนธันนวาคม ราคาหุ้นในรอบ 30 วัน เป็นต้น
2. สมาชิกในอาร์เรย์จะมีคุณสมบัติเหมือนๆกัน เช่น ชนิดของข้อมูลของตัวแปร
3. ขนาดของอาร์เราย์จะมีขนาดลดลงคงที่
4. ผู้ใช้สามารถอ้างอิงเพื่อเข้าถึงข้อมูลที่ต้องการได้ทันที
การอ้างอิงตำแหน่งสมาชิกในอาร์เรย์
ต้องเริ่มต้นด้วยชื่ออาร์เรย์และตามด้วยเลขลำดับกำกับไว้ด้วย ซึ่งลำดับเหล่านี้สามารถเรียกได้หลายชื่อด้วยกัน เช่น ซัปสคริปต์ หรือเลขดรรชนี
ขอบเขตของอาร์เรย์ [Bounds]
1. ภาษา C,C++,C#,JAVA จะถูกกำหนดขอบเขตล่างสุดเท่ากับ 0
2. ภาษา FRONTRAN จะถูกกำหนดขอบเขตล่างสุดเท่ากับ 1
3. ADA,PL/1,PASCAL สามารถทำการกำหนดขอบเขตล่างสุดและขอบเขตบนสุดของอาร์เรย์ได้ รวมถึงกำหนดขอบเขตค่าติดลบได้
การคำนวณจำนวนสามาชิกของอาร์เรย์ 1 มิติ
| จำนวนสมาชิก = U + L + 1 |
การคำนวณจำนวนสามาชิกของอาร์เรย์ 2 มิติ
| จำนวนสมาชิก = (U1 – L1 + 1) x (U2 – L2 + 1) |
การคำนวณจำนวนสามาชิกของอาร์เรย์ 3 มิติ
| จำนวนสมาชิก = (U1 – L1 + 1) x (U2 – L2 + 1) x (U3 – L3 + 1) |
การจัดเก็บอาร์เรย์ในหน่วยความจำ
รูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์
อาร์เรย์ 1 มิติ ใช้สูตร ArrayName [ L:U ]
ตัวอย่าง a[1:10] = a[10]
อาร์เรย์ 2 มิติ ใช้สูตร ArrayName [ L1:U1,L2:U2 ]
ตัวอย่าง a[4,5] = a[0:3,0:4]
อาร์เรย์ 3 มิติ ใช้สูตร ArrayName [ L1:U1,L2:U2 ,L3:U3 ]
ตัวอย่าง a[6,5,4] = a[0:5,0:4,0:3]
การคำนวณหาตำแหน่งแอดเดรสในหน่วยความจำ
อาร์เรย์ 1 มิติ ใช้สูตร LOC(a[i]) = B + w(i – L)
โดยที่
LOC(a[i]) คือ ตำแหน่งแอดเดรสที่เก็บ a[i] ในหน่วยความจำ
B คือ แอดเดรสเริ่มต้นของ a
w คือ ขนาดของข้อมูลในการจัดเก็บ
i คือ ตำแหน่งของสมาชิกในอาร์เรย์
L คือ ขอบเขตล่างสุด
ตัวอย่าง อยากทราบอาร์เรย์ a[10] (ภาษา C ) ถูกจัดเก็บในหน่วยความจพเดรสใด กำหนดให้ : แอดเดรสเริ่มต้น = 1000 w = 1 ไบต์
LOC(a[i]) = B + w(i – L)
= 1000 + 1(10-0)
= 1000 + 10
= 1010
อาร์เรย์ 2 มิติ
การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก
ใช้สูตร LOC(a[i]) = B + w[C(i – L1) + ( j – L2)]
โดยที่ C คือตำแหน่งคอลัมน์ของแถวลำดับ ( R*C )
ตัวอย่าง ต้องการทราบตำแหน่งที่เก็บข้อมูลอาร์เรย์ K แถวที่ 2 คอลัมน์ 1 กำหนด B = 500, w = 4 ( ภาษา C )
LOC(K[i,j] = B + w[C(i – L1) + ( j – L2)]
LOC(K[2,1]) = 500 + 4[3(2– 0) + ( 1 – 0)]
= 500 + 4[6 +1]
= 500 +28
= 528
อาร์เรย์ 3 มิติ
การจัดเก็บด้วยการเรียงแถวเป็นหลัก ใช้สูตร
LOC(s[i,j,k]) = B + [ w * R * C( i - L1)
+ [w * C( j – L2 )] + [w(k-L3)]
ตัวอย่าง ต้องการทราบตำแหน่งที่เก็บข้อมูลอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4 กำหนดให้ B = 500, w =4 (ภาษา C S[3][4][5] )
LOC(s[i,j,k]) = B + [ w * R * C( i - L1)
+ [w * C( j – L2 )] + [w(k-L3)]
LOC(s[0,3,4]) = 500 + [ 4 * 4 * 5( 0 - 0)
+ [4 * 5( 3– 0 )] + [4(4-0)]
= 500 + 0 + 60 + 16
= 576
อาร์เรย์ 3 มิติ
การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก ใช้สูตร
LOC( S[i,j,k]) = B + [w * K * R * C(j – L2) ]
+ [ w * K * R(i – L1 )] + [k – L3]
ไม่มีความคิดเห็น:
แสดงความคิดเห็น