วันเสาร์ที่ 8 เมษายน พ.ศ. 2560
บทที่ 2
อาร์เรย์
ARRAY
โครงสร้างอาร์เรย์
(Array
การเรียกใช้สมาชิกภายในอาร์เรย์เรียกได้โดยระบุชื่อแถวลำดับและดรรชนีของอาร์เรย์
ซึ่งเป็นการบอกตำแหน่งของสมาชิก อาร์เรย์ที่มีดรรชนีเพียง 1 ตัว เรียกว่า อาร์เรย์
1 มิติ (one dimensional array) ส่วนอาร์เรย์ที่มีดรรชนีหลายตัว เรียกว่า
(multidimensional array)
สิ่งที่ควรจำเกี่ยงกับ Array
1. เนื้อที่หน่วยความจำมีชื่อเดียวกัน
2.
ลักษณะการเข้าถึงข้อมูลในอาร์เรย์เป็นแบบ linear list
3.
แยกตำแหน่งหรือระบุตำแหน่งของข้อมูลแต่ละตัวด้วยการใช้ดรรชนีกำกับ(Index) หรือ
Subscript
4.
การสังเกตดรรชนีกำกับ(Index) หรือ Subscript ทำให้ทราบขนาดและมิติ (Dimension)
ของอาร์เรย์
ลักษระของอาร์เรย์ ประกอบด้วย
- ชื่อของอาร์เรย์
- ขนาดของอาร์เรย์
- ค่าสูงสุด (Upper bound) และค่าต่ำสุด (Lower bound) ของอาร์เรย์
สูตรการคำนวณหาจำนวนช่องของอาร์เรย์ 1 มิติ
จำนวนช่องของ A(l:u)=
ดรรชนีกำกับสูงสุด(u) -
ดรรชนีกำกับต่ำสุด(l)+1
หรือ
จำนวนช่องของ A(l:u) = u – l + 1
สูตรการคำนวณหาจำนวนช่องของอาร์เรย์ 2 มิติ
จำนวนช่อง = (U1 - L1 + 1) * (U2 - L2 + 1)
เมื่อ L1 คือ ดรรชนีกำกับต่ำสุดของมิติที่
1
U1 คือ ดรรชนีกำกับสูงสุดของมิติที่ 1
L2 คือ ดรรชนีกำกับต่ำสุดของมิติที่ 2
U2 คือ ดรรชนีกำกับสูงสุดของมิติที่ 2
การคำนวณตำแหน่งที่อยู่ของอาร์เรย์
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.
ฟังก์ชันการคำนวณหาตำแหน่งที่อยู่ของอาร์เรย์ 2 มิติ
มีลักษณะการเข้าถึง 2 ลักษณะคือ
•1.
อันดับเรียงตามสดมภ์(Column
Major Order) จะเข้าถึงข้อมูลโดยยึดสดมภ์เป็นหลักโดยเปลี่ยน
แถว(Row)ก่อน
• 2.
อันดับเรียงตามแถว (Row Major Order)
จะเข้าถึงข้อมูลโดยยึดแถวเป็นหลักโดยจะเปลี่ยนสดก่อน.
อันดับเรียงตามแถว
สูตร
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 คือ ขนาดของหน่วยความจำที่ใช้เก็บข้อมูลแต่ละตัว
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 ที่มีลักษณะของข้อมูลที่กำหนด ทำได้โดยการเข้าถึงข้อมูล ซึ่งเป็นการติดต่อ
กับข้อมูลในแต่ละ
•Element
ของ
A
ซึ่งจะมี
Algorithm
ในการเข้าถึงดังนี้
การแทรกและการลบ
- ให้ A เป็น อาร์เรย์ ที่อยู่ในหน่วยความจำของคอมพิวเตอร์ การแทรกเป็นการเพิ่มข้อความ 1 Element เข้าไปใน อาร์เรย์ และการลบเป็นการเอาข้อมูล 1 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 ช่องแล้วไม่พบ
