อาร์เรย์ ( Array )

โครงสร้างอาร์เรย์ (Array)
            โครงสร้างชนิดนี้ใช้เก็บข้อมูลชนิดเดียวกันที่มีขอบเขตจำกัดและมีขนาดคงที่ การทำงานพื้นฐานของอาร์เรย์ คือ การเข้าถึงตำแหน่งในอาร์เรย์ได้โดยตรง (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) ของอาร์เรย์

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

                       1.ชื่อของอาร์เรย์

                   2.ขนาดของอาร์เรย์

                   3.ค่าาสูงสุด (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

ลักษณะทั่วไปของอาร์เรย์ 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

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

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

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

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

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

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

การคำนวณตำแหน่งที่อยู่ของอาร์เรย์ หมายถึง การคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ เพื่อเข้าถึงข้อมูลของ อาร์เรย์ โดยจะอ้างอิงกับตำแหน่งที่อยู่ของข้อมูลแรก (Base address) ของอาร์เรย์

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

             

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

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

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

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

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

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

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

               1. อันดับเรียงตามสดมภ์(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                คือ       ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว

                2. อันดับเรียงตามแถว (Row Major Order) จะเข้าถึงข้อมูลโดยยึดแถวเป็นหลักโดยจะเปลี่ยนสดมภ์ก่อน เช่น 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                  คือ       ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว

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

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

                  1. กำหนดให้ Num มีค่าเท่ากับค่าต่ำสุดของ อาร์เรย์ (Lower Bound)

                  2. ตรวจสอบว่า Num มีค่ามากกว่าหรือเท่ากับค่าสูงสุดของ อาร์เรย์ (Upper Bound)หรือไม่

                       - ถ้าไม่ให้ไปทำข้อ 3 และ4

                       - ถ้าใช้ให้ไปทำข้อ 5

                  3. แสดงข้อมูลของ อาร์เรย์ ณ ตำแหน่ง Num

                  4. เพิ่มค่า Num = Num+1 และขึ้นไปทำข้อ 2

                  5. จบการทำงาน

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

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

การกระทำบน Array (Operation)

            โอเปอเรชั่น (Operation) คือ การกระทำที่เราสามารถทำกับโครงสร้างนั้น ๆได้ เช่น การแทรก การลบ การท่องไปในสมาชิก เป็นต้น โอเปอเรชั่นใน array มีดังนี้

                 1.  การท่องไปในอาร์เรย์ (Traversal)

                 2.  การค้นหาข้อมูลที่ต้องการ (Searching)
                        3.  การแทรกข้อมูลใหม่ (Insertion)
                        4.  การลบข้อมูล (Deletion)
                        5.  การเรียงลำดับ (Sorting)

การเรียงข้อมูล (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