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

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

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

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

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

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

Vec(1)

Vec(2)

…

Vec(I)

…

Vec(N)

รูปที่ 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

ตัวอย่างการใช้อาร์เรย์หนึ่งมิติ

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

จากโปรแกรมในตารางที่ 2.1

ผลลัพธ์ที่ได้

อาร์เรย์ที่สร้างขึ้นมาบันทึกอุณหภูมิมีชื่อว่าTemp โดยดัชนีจะมีค่าที่ขอบเขตล่างเท่ากับ 1 มีค่าที่ขอบเขตบนเท่ากับ 24 จะได้ว่า Temp(I) เป็นอุณหภูมิในช่วงโมงที่ Iโดย 1≤ I ≥ 24 และการประกาศตัวแปร Tempดังนี้

int Temp [24];

เนื่องจากต้องมีดัชนีใช้กับอาร์เรย์จึงประกาศป็นตัวแปร I ดังนี้

Int i;

การทำงานกับสมาชิกในอาร์เรย์จะใช้การวนลูปเพื่อเก็บค่า ดังนี้

rand ( time(NULL) );

for ( i = 0; i < 24; i++ )

Temp[i] = rand( ) %20+20;

เป็นการกำหนดค่าให้แต่ละสมาชิกโดยการสุ่มค่าให้ หลังจากนั้นทำการแสดงผลบนหน้าจอ ดังนี้

for ( i = 0; i < 24; i++ )

printf ( “%d”, Temp [i] );

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

อาร์เรย์สองมิติ

อาร์เรย์สองมิติ (Tow-dimension Array) เป็นอาร์เรย์ที่สมาชิกมีโครงสร้างข้อมูลอาร์เรย์ ลักษณะเป็นตารางที่มีทั้งแถว และคอลัมน์ หรือเรียกว่าแมตทริก ดังในรูปที่ 2.1 เป็นอาร์เรย์สองมิติชื่อ Matrix ที่ประกอบด้วยสมาชิกใยแถว M ตัว แต่ละสมาชิกจะมีสมาชิกในคอลัมน์ N ตัว ก็จะได้เป็นตารางขนาด M ต่อ N

รูปที่ 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 โดยมิติแรกมีช่วงระยะเท่ากับ 2 มิติที่สองมีช่วงระยะเท่ากับ 3 และมิติที่สามมีช่วงระยะเท่ากับ 5 จะมีสมาชิกทั้งหมดเท่ากับ 30 (M*N*P)

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

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

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

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

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

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

B + (I – 1)*S

หรือกรณีที่ใช้ขอบเขตล่าง L เป็นดังนี้

B + (I – L)*S

เช่น มีอาร์เรย์ Vec(4:10) และต้องการหาตำแหน่งแอดเดรสของสมาชิก Ves(6) โดยตำแหน่งเริ่มต้นอยู่ที่แอดเดรส 2500 และแต่ละสมาชิกมีขนาด 80 ไบต์ ก็จะได้ตำแหน่งแอดเดรสอยู่ที่ 250 + (6 – 4) * 80 = 2660

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

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

ลำดับแถวสำคัญ   (Row-Major Order) ทางเลือกหนึ่งที่นำมาใช้คือเก็บสมาชิกทุกตัวของแถวแรกก่อน จากนั้นเก็บแถวที่สอง และสามไปเรื่อย ๆ ดังในรูปที่ 2.4 คือ อาร์เรย์ Mem(1:4,1:6) ซึ่งมีลักษณะรูปแบบตารางในทางตรรกะ

รูปที่ 2.4 อาร์เรย์ Mem (4,6) แสดงเป็นตารางในทางตรรกะ

เมื่อนำไปเก็บไว้ในหน่วยความจำซึ่งมีลักษณะเชิงเส้น ลักษณะอาร์เรย์ทางกายภาพก็จะเป็นเชิงเส้นเหมือนกัน ดังในรูปที่ 2.5

รูปที่ 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

รูปที่ 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 จงเลือกคำตอบที่ถูกต้องเพียงคำตอบเดียว โดยทำเครื่องหมาย X ทับตัวเลือกที่ต้องการ

1.โปรแกรมใดที่จำเป็นต้องใช้ตัวแปรอาร์เรย์

ก.โปรแกรมคำนวนหาพื้นที่รูปวงกลม

ข.โปรแกรมคำนวนหาพื้นที่รูปวงกลม 20 วง

ค.โปรแกรมหาคำนวนหาพื้นที่และเส้นรอบวงของวงกลม

ง.โปรแกรมหาพื้นที่วงกลมใดที่มีค่ามากที่สุดจาก 20 วง

2.ตัวแปร A เป็นตัวแปรแบบอาร์เรย์แล้ว กลุ่มข้อมูลใดสามารถจัดเก็บที่ตัวแปร A ได้

ก. 25,60,boy,T

ข. A,B,C,D

ค. Dog ,cat 2.50

ง.True ,Somsri ,10.25

3.จากโปรแกรมต่อไปนี้ Data มีผลลัพธ์เป็นเท่าไร

Program Test 1;

Var Data : integer

Begin

 Data : =60 ;

 Data : =20;

Writeln (Data);

End.

ก. 60

ข. 20

ค. 80

ง. 40

4.ข้อใดต่อไปนี้ที่ผู้เขียนโปรแกรมควรกำหนดเป็นตัวแปรอาร์เรย์

ก. I เก็บค่าการนับรอบของลูป

ข. Score เก็บค่าคะแนนนักศึกษา 20 คน

ค. Mean เก็บค่าคะแนนเฉลี่ยนักศึกษา 20 คน

ง. Max เก็บค่าคะแนนนักศึกษาที่มีคะแนนสูงสุดจาก 20 คน

5.ตัวแปรอาร์เรย์ต่างกับตัวแปรเดี่ยวอย่างไร

ก.ตัวแปรอาร์เรย์เก็บค่าในฮาร์ดดิสก์ตัวแปรเดี่ยวเก็บค่าใน RAM

ข.ตัวแปรอาร์เรย์เก็บค่าแบบ Numeric ตัวแปรเดี่ยวเก็บค่าแบบ String

ค.ตัวแปรอาร์เรย์เก็บค่าคงที่ ตัวแปรเดี่ยวเก็บค่าเปลี่ยนแปลงได้

ง.ตัวแปรอาร์เรย์เก็บค่าได้หลายค่า ตัวแปรข้อมูลเดี่ยวเก็บค่าได้เพียงค่าเดียว

6.ประกาศตัวแปร A:array[1..20] of integer; ตัวแปรอาร์เรย์ชุดที่ประกาศนี้สามารถเก็บค่าได้ทั้งหมดกี่ค่า

ก. 1 ค่า

ข. 19 ค่า

ค. 20 ค่า

ง. 21 ค่า

7.J : Array [1..100,1..5] of Integer; ตัวแปรอาร์เรย์ J ประกอบด้วยสมาชิกกี่ค่า

ก. 5

ข. 100

ค. 50

ง. 500

8.ข้อใดคือความหมายของโครงสร้างข้อมูลแบบอาร์เรย์

ก.กลุ่มข้อมูลที่มีค่าชนิดเดียวกัน

ข.กลุ่มข้อมูลที่เป็นตัวเลขเท่านั้น

ค.กลุ่มข้อมูลที่มีความสัมพันธ์กัน

ง.กลุ่มข้อมูลที่มีการลดความซ้ำซ้อน

9.ถ้าประกาศตัวแปรอาร์เรย์ดังนี้ Data :array [1…5] of integer ;

ข้อมูลใดไม่สามารถเก็บในอาร์เรย์ชุดนี้ได้

ก. 500   20   40   25  2.5

ข. 601    2   0   13  100

ค. 1    0   0   0  1

ง.  0    0   0   0  0

10.การประกาศตัวแปรอาร์เรย์เพื่อใช้งานต้องประกอบด้วยอะไรบ้าง

ก. ชื่ออาร์เรย์ ชนิดข้อมูล 

ข. ชื่ออาร์เรย์ ค่าสูงสุดและค่าต่ำสุด ชนิดข้อมูล 

ค. ชื่ออาร์เรย์ ค่าสูงสุดและค่าต่ำสุด มิติของอาร์เรย์ ชนิดข้อมูล 

ง. ชื่ออาร์เรย์ ค่าสูงสุดและค่าต่ำสุด มิติของอาร์เรย์ ชนิดข้อมูล จำนวนสมาชิก