อาร์เรย์

บทที่1

อาร์เรย์

เนื้อหา

โครงสร้างข้อมูลแบบอาร์เรย์
             ลักษณะของอาร์เรย์
             การเรียงข้อมูล
             การค้นข้อมูลการเก็บอาร์เรย์ในคอมพิวเตอร์             อาร์เรย์ 1 มิติ
             อาร์เรย์ 2 มิติ
             อาร์เรย์ 3 มิติ

อันดับเรียงตามสดมภ์ (Column Major Order)

           อันดับเรียงตามสดมภ์ จะเข้าถึงข้อมูลโดยยึดสดมภ์เป็นหลักโดยเปลี่ยนแถว(Row) ก่อน  เช่น Num(1,1) Num(2,1) Num(1,2) Num(2,2)

โครงสร้างอาร์เรย์ (Array)

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

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

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

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

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

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

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

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

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

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

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

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

—ให้ A เป็น อาร์เรย์ ที่เก็บอยู่ในหน่วยความจำ หากเราต้องการจะพิมพ์รายการของแต่ละ Element หรือนับจำนวน

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

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

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

— ให้ A เป็น อาร์เรย์ ที่อยู่ในหน่วยความจำของคอมพิวเตอร์ การแทรกเป็นการเพิ่มข้อความ 1 Element เข้าไปใน อาร์เรย์ และการลบเป็นการเอาข้อมูล 1 Element ออกจาก อาร์เรย์

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

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

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

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

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

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

Flowchart

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

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

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

—  จำนวนครั้งที่เราต้องการเปรียบเทียบทั้งสิ้น 10 * 10 = 100 ครั้ง ถ้าอาร์เรย์ A เป็นอาร์เรย์ขนาด N และมีตัวเลข N ตัวเก็บอยู่ เราต้องทำการเปรียบเทียบทั้งสิ้น N2 ครั้ง จึงจะได้อาร์เรย์ที่เรียงค่ากัน

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

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

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