อาร์เรย์

บทที่ 2

การเขียนโปรแกรม

               เนื้อหา

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

•ลักษณะของอาร์เรย์

•การเรียงข้อมูล

•การค้นข้อมูล

•การเก็บอาร์เรย์ในคอมพิวเตอร์

•อาร์เรย์ 1 มิติ

•อาร์เรย์ 2 มิติ

•อาร์เรย์ 3 มิติ

1 โครงสร้าง

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

การทำงานพื้นฐานของอาร์เรย์ คือ การเข้าถึงตำแหน่งในอาร์เรย์ได้โดยตรง (linear list) ดัง

นั้นเวลาที่ใช้ในการเข้าถึงสมาชิกแต่ละตัวในอาร์เรย์จะมีจำนวนเท่ากัน ไม่ขึ้นอยู่กับตำแหน่ง

ของสมาชิก เช่น แถวที่มีสมาชิก 200 ตัว การเข้าถึงสมาชิกตัวที่ 75 จะใช้เวลาเท่ากับการเข้า

ถึงสมาชิกตัวที่ 5

         สมาชิกในอาร์เรย์ เรียกว่า “คอมโปเนนต์” และสมาชิกเหล่านี้เก็บในแถวลำดับแบบ

อันดับ คือ

 สมาชิกตัวที่ 1 สมาชิกตัวที่ 2 ,..., สมาชิกทั้งหมดในแถวลำดับต้องเป็นชนิดเดียวกัน ดังนั้น

 สามารถกำหนดแถวลำดับของจำนวนจริง แถวลำดับของจำนวนเต็ม

 การเรียกใช้สมาชิกภายในอารชนีของอาร์เรย์ ซึ่งเป็นการบอกร์เรย์เรียกได้โดยระบุชื่อแถว

ลำดับและดรตำแหน่งของสมาชิก อาร์เรย์ที่มีดรรชนีเพียง 1 ตัว เรียกว่า อาร์เรย์ 1 มิติ (one 

dimensional array) ส่วนอาร์เรย์ที่มีดรรชนีหลายตัว เรียกว่า (multidimensional array)

ข้อควรจำเกี่ยวกับ Array

  1. เนื้อที่หน่วยความจำมีชื่อเดียวกัน

  2. ลักษณะการเข้าถึงข้อมูลในอาร์เรย์เป็นแบบ linear list

  3. แยกตำแหน่งหรือระบุตำแหน่งของข้อมูลแต่ละตัวด้วยการใช้ดรรชนีกำกับ(Index) หรือ Subscript

  4. การสังเกตดรรชนีกำกับ(Index) หรือ Subscript ทำให้ทราบขนาดและมิติ (Dimension) ของอาร์เรย์

  2 ลักษณะของอาร์เรย์

     ลักษณะของอาร์เรย์ ประกอบด้วย

•ชื่อของอาร์เรย์

•ขนาดของอาร์เรย์

•ค่าสูงสุด (Upper bound) และค่าต่ำสุด (Lower bound) ของอาร์เรย์

ลักษณะทั่วไปของอาร์เรย์ 1 มิติ

                                    A (l :u)

เมื่อ A     คือ  ชื่อของอาร์เรย์

     l    คือ   ดรรชนีกำกับต่ำสุดของอาร์เรย์ (Lower bound)

     u     คือ   ดรรชนีกำกับสูงสุดของอาร์เรย์ (Upper bound)

สูตรการคำนวณหาจำนวนช่องของอาร์เรย์ 1 มิติ 

ช่องของ A(l:u)= ดรรชนีกำกัจำนวนบสูงสุด(u) - ดรรชนีกำกับต่ำสุด(l)+1

หรือ   

จำนวนช่องของ A(l:u) = u – l + 1    

ตัวอย่างการคำนวณหาจำนวนช่องของอาร์เรย์ 1 มิติ

จงคำนวณหาจำนวนช่องของอาร์เรย์ A(-8..4) และ B(2..12)

  A(-8..4)   = 4 - (-8) + 

  = 13 ช่อง

B(2..12)   = 12 - 2 + 1

             = 11 ช่อง

ลักษณะทั่วไปของอาร์เรย์ 2 มิติ•ลักษณะทั่วไปของ อาร์เรย์ 2 มิติ

 A(L1:U1,L2:U2)

              เมื่อ A คือ  ชื่อของ อาร์เรย์

                L1 คือ  ดรรชนีกำกับต่ำสุดของมิติที่ 1

                U1 คือ  ดรรชนีกำกับสูงสุดของมิติที่ 1

                L2 คือ  ดรรชนีกำกับต่ำสุดของมิติที่ 2

                U2 คือ  ดรรชนีกำกับสูงสุดของมิติที่ 2         

สูตรการคำนวณหาจำนวนช่องของอาร์เรย์ 2 มิติ

 จำนวนช่อง = (U1 - L1 + 1) * (U2 - L2 + 1)

              เมื่อ L1 คือ  ดรรชนีกำกับต่ำสุดของมิติที่ 1

                U1 คือ  ดรรชนีกำกับสูงสุดของมิติที่ 1

                L2 คือ  ดรรชนีกำกับต่ำสุดของมิติที่ 2

                U2 คือ  ดรรชนีกำกับสูงสุดของมิติที่ 2

         

2. การคำนวณหาจำนวนสมาชิกของอาร์เรย์ 2 มิติ

•ตัวอย่าง

   A[-3..1,-2..1] = (1-(-3)+1)*(1-(-2)+1) = 20 Element

   B[-3..4,-2..2] = (4-(-3)+1)*(2-(-2)+1) = 40 Element

การคำนวณหาเนื้อหน่วยความจำของอาร์เรย์

1. การคำนวณหาเนื้อหน่วยความจำของอาร์เรย์ 1 มิติ

2. การคำนวณหาเนื้อหน่วยความจำของอาร์เรย์ 2 มิติ

สูตรการคำนวณหาเนื้อที่หน่วยความจำของอาร์เรย์ 1 มิติ  

 เนื้อที่ = ( U- L +1) * ขนาดของข้อมูล 1 Element

ตัวอย่างการคำนวณหาเนื้อที่หน่วยความจำของอาร์เรย์ 1 มิติ

จงคำนวณขนาดของหน่วยความจำสำหรับเก็บข้อมูลที่ระบุดังนี้

Class(-5:5) แต่ละช่องเก็บ 5 ตัวอักษร (byte)

วิธีทำ

  class(-5:5)   = 5-(-5)+1* 5

  = 55 byte

   ตัวอย่างการคำนวณหาเนื้อที่หน่วยความจำของอาร์เรย์ 1 มิติ  

จงหาเนื้อหน่วยความจำที่ใช้ในการเก็บข้อมูลของ Num(1..5) และกำหนดให้

ขนาดของข้อมูลเป็น 2 Byte ต่อ 1 Element

วิธีทำ

    จากสูตร เนื้อที่ = ( U- L +1) * ขนาดของข้อมูล 1 Element

   แทนค่าจะได้ = (5-1+1)*2

                  = 10 Byte

  เพราะฉะนั้นเนื้อที่ทั้งหมดเท่ากับ 10 Byte 

        

สูตรการคำนวณหาเนื้อหน่วยความจำของอาร์เรย์ 2 มิติเนื้อที่ 

= (U1 - L1 + 1) * (U2 - L2 + 1) * ขนาดของข้อมูล 1 Element

ตัวอย่างการคำนวณหาเนื้อหน่วยความจำของอาร์เรย์ 2 มิติ  

จงหาเนื้อหน่วยความจำที่ใช้ในการเก็บข้อมูลของ Num(-3..2,-1..5) และ

กำหนดให้ขนาดของข้อมูลเป็น 2 Byte ต่อ 1 Element

วิธีทำ

  จากสูตร เนื้อที่ = (U1-L1+1)*(U2-L2+1)*ขนาดของข้อมูล 1 Element

                    แทนค่าจะได้ = (2-(-3)+1)*(5-(-1)+1)*2

                                         = 6 * 7 * 2 Byte

                                         = 84 Byte

         เพราะฉะนั้นเนื้อที่ทั้งหมดเท่ากับ 84 Byte

2. การเก็บค่าในอาร์เรย์

การคำนวณตำแหน่งที่อยู่ของอาร์เรย์  การคำนวณตำแหน่งที่อยู่ของ

อาร์เรย์ หมายถึง การคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ เพื่อเข้าถึงข้อมูล

ของ อาร์เรย์ โดยจะอ้างอิงกับตำแหน่งที่อยู่ของข้อมูลแรก 

(Baseaddress) ของอาร์เรย์

การคำนวณตำแหน่งที่อยู่ของอาร์เรย์

1. ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 1 มิติ

2. ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 2 มิติ   

3. ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 3 มิติ

1.ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 1 มิติ

สูตร Address A[i] = Address A(i) + C(i-l)

              เมื่อ

 Address A(i) คือ ตำแหน่งที่อยู่ของข้อมูลแรกของอาร์เรย์

              i คือ อาร์เรย์ ตัวที่ต้องการหาตำแหน่ง

              l คือ ค่าต่ำสุดของดรรชนีกำกับของอาร์เรย์

              C คือ ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว

         

การคำนวณตำแหน่งที่อยู่ของอาร์เรย์

ตัวอย่างที่ 1 ถ้า A เป็น A(1..3) โดยกำหนดให้เริ่มเก็บข้อมูลที่ตำแหน่ง 

100 ข้อมูลแต่ละค่าใช้เนื้อที่ 10 Byte จงหาตำแหน่งที่อยู่ของ A(3)

         วิธีทำ

  สูตร Address A[i]   = Address A(i) +C(i-l)    

  แทนค่า Address A[3]   = 100 + 10(3-1)

                                         = 120

การคำนวณตำแหน่งที่อยู่ของอาร์เรย์

ตัวอย่างที่ 2 จงหาตำแหน่งที่อยู่ของ A(0) และ A(2) ใน อาร์เรย์ A(-2..4)

 เมื่อกำหนดให้ A(-2) อยู่ที่ 1500 ในหน่วยความจำและสมาชิกแต่ละตัวใช้

เนื้อที่ 25 Byte

           วิธีทำ   สูตร   Address A(i)   = Address A(i) +C(I-L)   แทนค่า 

Address A(0)  = 1500 + (0-(-2)) * 25

     = 1550

              

  สูตร   Address A(i)   = Address A(i) +C(I-L)

   แทนค่า  Address A(2)  = 1500 + (2-(-2)) * 25   

                                     = 1600      

 การคำนวณตำแหน่งที่อยู่ของอาร์เรย์

จากตัวอย่างสามารถแสดงการแทนที่ในหน่วยความจำได้ดังนี้

2. ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 2 มิติ

มีลักษณะการเข้าถึง 2 ลักษณะคือ

•1. อันดับเรียงตามสดมภ์(Column Major Order) จะเข้าถึงข้อมูลโดยยึด

สดมภ์เป็นหลักโดยเปลี่ยนแถว(Row)ก่อน

• 2. อันดับเรียงตามแถว (Row Major Order) จะเข้าถึงข้อมูลโดยยึดแถว

เป็นหลักโดยจะเปลี่ยนสดมภ์ก่อน

อันดับเรียงตามสดมภ์ (Column Major Order)•อันดับเรียงตามสดมภ์ จะเข้าถึงข้อมูลโดยยึดสดมภ์เป็นหลักโดยเปลี่ยนแถว(Row) ก่อน             

•       เช่น Num(1,1) Num(2,1) Num(1,2) Num(2,2)

อันดับเรียงตามสดมภ์

สูตร  

Address (A(I,J)) = Lo + ((J-L2)*(U1-L1+1)*C) + ((I-L1)*C)

            เมื่อ

                  Lo คือ ตำแหน่งที่อยู่ของข้อมูลแรกของอาร์เรย์

                  I คือ อาร์เรย์ตัวที่ต้องการหาตำแหน่งใน Row

                  J คือ อาร์เรย์ตัวที่ต้องการหาตำแหน่งใน Column

                  L1 คือ ค่าต่ำสุดของดรรชนีกำกับของอาร์เรย์มิติที่ 1

                  U1 คือ ค่าสูงสุดของดรรชนีกำกับของอาร์เรย์มิติที่ 1

                  C คือ ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว

ตัวอย่าง

จงหาตำแหน่งของ Num(2,3) เมื่อกำหนดให้ Num เป็น อาร์เรย์

Num(1..2,1..5) ให้ Lo=100 และ C=10

วิธีทำ  

สูตร Address(A(I,J)) = Lo+((J-L2)*(U1-L1+1)*C)+((I-L1)*C)

Address(Num(2,3)) = 100+((3-1)*(2-1+1)*10)+((2-1)*10)

                                           = 150

จากตัวอย่างสามารถแสดงการแทนที่ในหน่วยความจำได้ดังนี้ 

จากตัวอย่างสามารถแสดงการแทนที่ในหน่วยความจำได้ดังนี้อันดับ

เรียงตามแถวจะเข้าถึงข้อมูลโดยยึดแถวเป็นหลักโดยจะเปลี่ยนสดมภ์ก่อน

  เช่น Num(1,1) Num(1,2) Num(2,1) Num(2,2) 

อันดับเรียงตามแถว

สูตร Address (A(I,J))  = Lo+((I-L1)*(U2-L2+1)*C)+((J-L2)*C)

                       เมื่อ   

  Lo  คือ ตำแหน่งที่อยู่ของข้อมูลแรกของอาร์เรย์

     I  คือ อาร์เรย์ ตัวที่ต้องการหาตำแหน่งใน Row

     J  คือ อาร์เรย์ ตัวที่ต้องการหาตำแหน่งใน Column

     L1  คือ ค่าต่ำสุดของดรรชนีกำกับของอาร์เรย์มิติที่ 1

     L2  คือ ค่าต่ำสุดของดรรชนีกำกับของอาร์เรย์มิติที่ 2

     U2  คือ ค่าสูงสุดของดรรชนีกำกับของอาร์เรย์มิติที่ 2

     C  คือ ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว

ตัวอย่าง

จงหาตำแหน่งของ Num(2,3) เมื่อกำหนดให้ Num เป็น อาร์เรย์ 

Num(1..2,1..5)   ให้ Lo=100 และ C=10    

      

วิธีทำ 

สูตร Address (A(I,J)) = Lo+(C(I-L1)*(U2-L2+1))+(C(J-L2))

    Address (Num(2,3))   = 100+((2-1)*(5-1+1)*10)+((3-1)*10)

  = 170

จากตัวอย่างสามารถแสดงการแทนที่ในหน่วยความจำได้ดังนี้

การเข้าถึงข้อมูลในอาร์เรย์

•ให้ A เป็น อาร์เรย์ ที่เก็บอยู่ในหน่วยความจำ หากเราต้องการจะพิมพ์

รายการของแต่ละ Element หรือนับจำนวน

•Element ใน อาร์เรย์ A ที่มีลักษณะของข้อมูลที่กำหนด ทำได้โดยการเข้า

ถึงข้อมูล ซึ่งเป็นการติดต่อกับข้อมูลในแต่ละ

•Element ของ A ซึ่งจะมี Algorithm ในการเข้าถึงดังนี้

Flowchart 

การแทรกและการลบ

• ให้ A เป็น อาร์เรย์ ที่อยู่ในหน่วยความจำของคอมพิวเตอร์ การแทรก

เป็นการเพิ่มข้อความ 1 Element เข้าไปใน อาร์เรย์ และการลบเป็นการเอา

ข้อมูล 1 Element ออกจาก อาร์เรย์

•การเพิ่มข้อมูลใน อาร์เรย์ จะทำได้ง่ายที่สุดหากเป็นการเพิ่มในส่วนท้าย

ของ อาร์เรย์ และพื้นที่หน่วยความจำที่จัดไว้ใหญ่พอ แต่ถ้าหากเป็นการ

เพิ่มในส่วนตรงกลางของ อาร์เรย์ จะต้องมีการย้าย Element ที่เหลือลงไป

ด้านล่างเพื่อให้เกิดช่องว่างสำหรับ Element ตัวใหม่

การแทรกและการลบ  

เช่นเดียวกัน ในการลบข้อมูลในอาร์เรย์  จะทำได้ง่ายที่สุดหากเป็นการลบ

ในส่วนท้ายของอาร์เรย์ แต่ถ้าเราต้องการจะลบข้อมูลที่อยู่ตรงกลางจะต้อง

มีการย้าย Element ที่เหลือขึ้นมา 

การเรียงข้อมูล (Sorting) ใน Array

§  การเรียงข้อมูลให้ลดหลั่นจากมากไปน้อยหรือจากน้อยไปมาก    มีความ

สำคัญมากในการประมวลผลข้อมูลเพื่อประโยชน์ใน    การใช้งาน  โดยจะ

สมมติว่า

§  ข้อมูลตัวเลข 10 ตัว ได้เก็บอยู่ในอาร์เรย์ ชื่อ A(10) จุดประสงค์ของเรา

คือ ต้องการเขียนโปรแกรมเพื่อเรียงข้อมูลทั้ง 10 ค่านี้ให้เรียงค่าจากน้อย

ไปมาก ความคิดเบื้องต้นที่ง่ายที่สุดคือ ให้ตรวจค่าทั้ง 10 ในอาร์เรย์ A 10

ครั้ง แต่ละครั้งให้เลือกค่าน้อยที่สุดออกมา

§  จำนวนครั้งที่เราต้องการเปรียบเทียบทั้งสิ้น 10 * 10 = 100 ครั้ง ถ้า

อาร์เรย์ A เป็นอาร์เรย์ขนาด N และมีตัวเลข N ตัวเก็บอยู่ เราต้องทำการ

เปรียบเทียบทั้งสิ้น N² ครั้ง จึงจะได้อาร์เรย์ที่เรียงค่ากัน

การค้นข้อมูล(Searching)ใน Array       

ถ้าเราต้องการค้นว่าข้อมูล X อยู่ในอาร์เรย์ A(N) หรือไม่ เราต้องเขียน

โปรแกรมที่เป็นวงจรปิด แล้วทำการเปรียบเทียบ N ครั้ง (มากที่สุด) จะได้

ผลลัพธ์ว่า X อยู่ ใน A หรือไม่ การค้นแบบนี้เรียกว่า การค้นแบบเชิงเส้น 

(linear search) ลักษณะโปรแกรมจะเป็น

  DO  I = 1  TO  N

  IF  X = A(I)  THEN X อยู่ที่ตำแหน่ง I ใน A

  END

  IF  I > N  THEN   ตรวจทั้ง N ช่องแล้วไม่พบ X