โครงสร้างข้อมูลอาร์เรย์

บทที่ 2 โครงสร้างข้อมูลอาร์เรย์

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

โครงสร้างข้อมูลอาร์เรย์

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

 อาร์เรย์หนึ่งมิติ

อาร์เรย์หนึ่งมิติ (One-dimension Array) มีลักษณะที่ง่ายที่สุดเป็นตารางที่มีเพียงแถวเดียว บางครั้งก็เรียกว่าเว็กเตอร์

2.1 ตัวอย่างเป็นอาร์เรย์หนึ่งมิติชื่อ Vec มีสมาชิก N ตัว

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

การกำหนดอาร์เรย์หนึ่งมิติ

การกำหนดอาร์เรย์หนึ่งมิติจะมีรูปแบบที่กำหนดไว้เป็นดังนี้

V(L:U) = { V(I) }

สำหรับ I = L,L+1,…,U-1,U ซึ่งสมาชิกแต่ละตัว V(I) จะมีโครงสร้างข้อมูล T หมายความว่าอาร์เรย์ V มีสมาชิกที่มีโครงสร้างข้อมูล T และมีดัชนีมีค่าเริ่มจาก L ไปสิ้นสุดที่ U จะได้ช่วงดัชนีจาก L ไป U เท่ากับ U-L+1 ถ้าหากให้อาร์เรย์ V(1:N) จะได้ช่วงดัชนีเท่ากับ N ในการกำหนดค่าให้กับ L อาจเป็น 0 หรือเป็นค่าติดลบได้ เช่น V(-5:5) และมีช่วงดัชนีเท่ากับ 5-(-5)+1 = 11

2.2 ตัวอย่างอาร์เรย์สองมิติชื่อMatrix มีสมาชิก M*N ตัว

อาร์เรย์สองมิติจะใช้ดัชนีสองตัวเพื่ออ้างไปยังตำแหน่งของแต่ละสมาชิกแยกกัน โดยดัชนีตัวแรกใช้กับสมาชิกในแถว ส่วนตัวที่สองใช้กับสมาชิกในคอลัมน์ ดังนั้นสมาชิกอาร์เรย์ Matrix(I,J) จึงอยู่ในตำแหน่งแถวที่ I ตำแหน่งคอลัมน์ที่ J อาร์เรย์ Matrix จะเรียกว่าอาร์เรย์มิติ M ต่อ N แต่ละแถวมีสมาชิกเท่ากับ N แต่ละคอลัมน์มีสมาชิกเท่ากับ M จะได้สมาชิกทั้งหมดเท่ากับ M*N

การเขียนอัลกอริทึมเพื่อใช้อาร์เรย์สองมิติจะนำโครงสร้างควบคุมการทำงานแบบวนลูปมาใช้ 2 ลูป โดยส่วนใหญ่จะให้ลูปแรกอยู่ด้านนอกใช้ควบคุมสมาชิกในแถว ส่วนลูปที่สองซ้อนอยู่ภายในลูปแรกใช้ควบคุมสมาชิกในคอลัมน์

การกำหนดอาร์เรย์สองมิติ

การกำหนดอาร์เรย์สองมิติจะมีรูปแบบคล้ายกับอาร์เรย์หนึ่งมิติ ซึ่งการกำหนดจะเป็นดังนี้

M(L1:U1,L2:U2) = { M(I,J) }

สำหรับ L1 ≤ I ≤ U1 และ L2 ≤ I ≤ U2 ซึ่งสมาชิกแต่ละตัว M(I,J) จะมีโครงสร้างข้อมูล T

อาร์เรย์ M มีสมาชิกที่มีโครงสร้างข้อมูล T มีสมาชิกในแถวเท่ากับ U2 – L2 + 1 และมีสมาชิกในคอลัมน์เท่ากับ U1 – L1 + 1ดังนั้นสมาชิกทั้งหมดจะเท่ากับ (U2 – L2 +1)*(U1 – L1 +1)

2.3 ตัวอย่างการใช้อาร์เรย์สามมิติชื่อ Triangle มีสมาชิก 30 ตัว (M*N*P)

อาร์เรย์ในหน่วยความจำ

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

1. การเข้าถึงเรียกใช้สมาชิกต้องมีความเรียบง่าย

2. ง่ายต่อการเข้าไปหาแต่ละสมาชิกที่มีหลายเส้นทาง

3. ประสิทธิภาพของการจัดเก็บที่ง่ายต่อการเข้าถึงแต่ละสมาชิก

4. ง่ายต่อการเพิ่มขนาดอาร์เรย์ให้มากขึ้น

 การเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำ

เมื่อพิจารณาพื้นที่ในหน่วยความจำที่จะเก็บอาร์เรย์หนึ่งมิติ เช่น อาร์เรย์ Vec ในรูปที่ 2.1 ซึ่งมีดัชนีที่ขอบเขตล่างเท่ากับ 1 ส่วนขอบเขตบนเท่ากับ N วิธีที่จะเก็บอาร์เรย์หนึ่งมิติในหน่วยความจำก็คือ ลำดับของสมาชิกในทางกายภาพ เรียงเป็นแบบเดียวกับลำดับของสมาชิกในทางตรรกะ ดังนั้น พื้นที่จัดเก็บสมาชิก Vec(I+1) จะอยู่ต่อเนื่องจากพื้นที่ จัดเก็บสมาชิก Vec(I) สำหรับ

I = 1,…,N-1 ในการคำนวณหาแอดเดรสเริ่มต้นของสมาชิก Vec(I) จำเป็นต้องทราบในเรื่องต่อไปนี้

1. ตำแหน่งแอดเดรสเริ่มต้นของพื้นที่หน่วยความจำที่จะเก็บอาร์เรย์ เรียกว่าตำแหน่งเริ่มต้น (Base Location)

2. ขนาดพื้นที่เก็บแต่ละสมาชิกของอาร์เรย์ กำหนดให้มีขนาด S ไบต์

การหาตำแหน่งแอดเดรสของสมาชิกอาร์เรย์ Vec ตัวที่ I จะได้ ดังนี้

2.4 อาร์เรย์ Mem (4,6) แสดงเป็นตารางในทางตรรกะเมื่อนำไปเก็บไว้ในหน่วยความจำซึ่งมีลักษณะเชิงเส้น ลักษณะอาร์เรย์ทางกายภาพก็จะเป็นเชิงเส้นเหมือนกัน 

 2.5 ลักษณะอาร์เรย์ Mem (1:4,1:6) ในลักษณะแบบลำดับแถวสำคัญแบบแผนการจัดเก็บแบบลำดับแถวสำคัญนำมาใช้กับอาร์เรย์ในภาษาเขียนโปรแกรมหลายภาษา เช่น ภาษาโคบอล  ภาษาปาสคาล และภาษาซี ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมิติจะมีวิธีการคำนวณ เช่นหาแอดเดรสเริ่มต้นของสมาชิก Mem(I,J) ในอาร์เรย์ Mem(L1:U1,L2:U2) จะได้ดังนี้

B + (I – L1) * (U2 – L2 + 1) *S + (J – L2) *S

สมมุติต้องการทราบแอดเดรสสมาชิก Mem(2,5) โดยตำแหน่งเริ่มต้นอาร์เรย์คือแอดเดรส 1000 และแต่ละสมาชิกในอาร์เรย์มีขนาด 8 ไบต์ ก็จะได้ 1000+(2-1)*(6-1+1)*8+(5-1)*8 = 1080

ลำดับคอลัมน์สำคัญ (Column – Major Order)

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

2.6 ลักษณะอาร์เรย์ Men(4,6) ในลักษณะแบบลำดับคอลัมน์สำคัญแบบแผนการจัดเก็บแบบลำดับคอลัมน์สำคัญมีการใช้ภาษาเขียนโปรแกรม  เช่น

ภาษาฟอร์แทรน ถ้าต้องการทราบแอดเดรสเริ่มต้นของแต่ละสมาชิกในอาร์เรย์สองมอตอจะมีวิธี การคำนวณหาของสมาชิก Men(I,J)จะได้ดังนี้

B + (J – L2) * (U1 – L1 + 1) *S + (I – L1) *S

ถ้าต้องการทราบแอดเดรสสมาชิก Men(2,5) แบบลำดับคอลัมน์ก็จะได้

1000+(5-1)*(4-1+1)*8+(2-1)*8 = 1136

แบบทดสอบ
1. ข้อใดคือความหมายของ Array
   ตัวแปร1ตัวเก็บค่าได้1ค่า
   ตัวแปรต่างชนิดกันเก็บค่าได้ในชื่อตัวแปรเดียวกัน
   ตัวแปรประเภทตัวเลข int , float สามารถเก็บรวมเป็นประเภทเดียวกันได้
   ตัวแปรประเภทเดียวกันหลายๆค่า เก็บข้อมูลในชื่อตัวแปรเดียวกัน

2. รูปแบบอาเรย์2มิติ
   ชนิดข้อมูล ชื่อตัวแปร;
   ชนิดข้อมูล ชื่อตัวแปร[ ];
   ชนิดข้อมูล ชื่อตัวแปร[ ] [ ] ;
   ชนิดข้อมูล ชื่อตัวแปร[ ] [ ] [ ] ;

3. การเข้าถึงข้อมูล (index) เริ่มนับจากค่าใด
   0
   1
   2
   3

4. คำสั่งใดสามารถใช้ร่วมกับ อาเรย์ได้
   for
   while
   if
   ถูกทุกข้อ

5. การเข้าถึงข้อมูลในอาเรย์2มิติทำได้อย่างไร
   a[0] [0] ;
   a[0] [1] ;
   a[1] [0] ;
   ถูกทุกข้อ

6. ใช้โจทย์นี้ตอบคำถามข้อ 6-10 int b[2] [3] ={1,2,3,4,5,6}; คำถาม b[0] [0] คือข้อใด
   1
   2
   3
   4

7. b[1] [2] คือข้อใด
   3
   4
   5
   6

8. b[0] [1] คือข้อใด
   1
   2
   3
   4

9. b[1] [1] +b[0] [2] คือข้อใดคือข้อใด
  56

  89

10. b[1] [0] - b[0] [1] คือข้อใดคือข้อใด
  123-3

เฉลย  1.ง 2.ค 3.ข 4.ข 5.ข 6.ง 7.ข 8ข 9.ข 10.ง