โครงสร้างอาร์เรย์
โครงสร้างชนิดนี้ ใช้เก็บข้อมูลชนิดเดียวกันที่มีขอบเขตจำกัดและมีขนาดคงที่
การทำงานพื้นฐานของอาร์เรย์ คือ การเข้าถึงตำแหน่งในอาร์เรย์โดยตรง ดังนั้นเวลาที่ใช้ในการเข้าถึงสมาชิกแต่ละตัวในอาร์เรย์จะมีจำนวนเท่ากัน ไม่ขึ้นอยู่กับตำแหน่งของสมาชิก
สมาชิกในอาร์เรย์ เรียกว่า "คอมโปเนนต์"
ข้อควรจำเกี่ยวกับอาร์เรย์
1. เนื้อที่หน่วยความจำมีชื่อเดียวกัน
2. ลักษณะการเข้าถึงข้อมูลในอาร์เรย์เป็นแบบ linear list
3. แยกตำแหน่งหรือระบุตำแหน่งของของข้อมูลแต่ละตัวด้วย
4. การสังเกตดัชนีกำกับ (Index) หรือ Subscript ทำให้ทราบขนาดและมิติของอาร์เรย์
ลักษณะของอาร์เรย์
- ชื่อของอาร์เรย์
- ขนาดของอาร์เรย์
- ค่าสูงสุดและค่าต่ำสุดของอาร์เรย์
ลักษณะทั่วไปของอาร์เรย์ 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)
การเข้าถึงข้อมูลในอาร์เรย์
ให้ 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 ตัวเก็บอยู่ เราต้องทำการเปรียบเทียบทั้งสิ้น N2 ครั้ง จึงจะได้อาร์เรย์ที่เรียงค่ากัน
การค้นข้อมูล(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
ไม่มีความคิดเห็น:
แสดงความคิดเห็น