Array

บทที่ 2 1อาร์เรย์ (ARRAY)WEEK3 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

บทนา◦อารเ์ รย์ (Array) เป็นตวั แปรชุดท่ีมีการกาหนดช่อื ตวั แปรเพียงชื่อเดยี ว แต่สามารถ กาหนดจานวนชอ่ งที่ใช้ในการจัดเกบ็ ขอ้ มูลได้หลายชอ่ ง ชนดิ ขอ้ มูลทจี่ ดั เก็บใน อาร์เรย์ชุดเดยี วกันจะมชี นดิ ข้อมลู เพียงชนดิ เดยี ว และการอา้ งอิงถงึ อารเ์ รย์จะต้อง ระบชุ ่องทขี่ องอารเ์ รย์ เรยี กว่า Subscript หรอื Index◦อาร์เรยเ์ ปน็ โครงสร้างข้อมลู ชนิดเป็นเชิงเสน้ (Linear Structure) กลา่ วคือ ชอ่ งท่ี ใชใ้ นการจัดเกบ็ ขอ้ มูลของอาร์เรยเ์ ดียวกนั จะใช้เนอื้ ทีใ่ นหน่วยความจาเรยี งลาดับ กันไปตง้ั แตช่ อ่ งแรกไปจนถึงช่องสุดทา้ ยของอาร์เรย์ และมจี านวนช่องที่กาหนดไว้ แนน่ อนตายตวัDATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 2

ความหมายของอาร์เรย์ (Array)◦ อารเ์ รย์ (Array) หมายถึง ตวั แปรชดุ โดยการกาหนดชอื่ ตวั แปรเพียงชื่อเดยี ว แต่กาหนดจานวน ชอ่ งทใ่ี ชใ้ นการจัดเกบ็ ข้อมลู ได้หลายชอ่ ง ขอ้ มูลที่เก็บในแต่ละชอ่ งของตวั แปรเดียวกนั จะเปน็ ชนิด ขอ้ มลู เดยี วกนั การใชง้ านหนว่ ยความจาจะใช้งานเรยี งต่อเนื่องกนั ไปตงั้ แตช่ ่องแรกจนถึงชอ่ ง สุดท้าย การเขา้ ถงึ ข้อมูลแตล่ ะชอ่ งจะต้องระบุช่องท่ี เรยี กว่า Subscript หรือ IndexDATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 3

ความหมายของอารเ์ รย์ (Array)จากความหมายของอารเ์ รย์สามารถแสดงได้ ดงั รูปตอ่ ไปน้ีA[1] A[2] A[3] A[4] ชอ่ื อาร์เรย์ และการระบุ10 8 2 3 ข้อมูลในแต่ละชอ่ งของอารเ์ รย์ ตาแหน่งการใชห้ น่วยความจา2000 2002 2004 2008◦ อาร์เรยม์ ีช่ือเดียว คือ อารเ์ รย์ A แตม่ จี านวนช่อง 4 ช่อง◦ ข้อมลู ท่จี ัดเกบ็ เป็นชนดิ เดยี วกัน จากรูปขอ้ มูลเปน็ ตวั เลขจานวนเต็ม◦ ใช้หนว่ ยความจาตอ่ เน่อื งกันไป เพราะจานวนเต็มใชเ้ นื้อที่ 2 byte จึงหา่ งกนั เทา่ กบั 2 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 4

ลักษณะของอารเ์ รย์ 5เปน็ โครงสร้างขอ้ มลู ชนดิ เชงิ เส้น (Linear Structure)จัดเก็บขอ้ มูลชนดิ เดียวมีการกาหนดจานวนชอ่ งไวแ้ น่นอนสามารถเข้าถึงชอ่ งตา่ ง ๆ ไดโ้ ดยตรง DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

อารเ์ รย์ 1 มิติคือ อารเ์ รย์ท่มี ีแถวเพียง 1 แถว แต่จะมีชอ่ งหรือคอลัมน์หลายคอลัมน์ ในการอา้ งองิ ถงึ อาร์เรย์ 1 มติ ิ หากกาหนดให้ อาร์เรย์ A มแี ถวจานวน 1 แถว มคี อลัมน์จานวน 5 คอลัมน์สามารถแสดงรปู อารเ์ รย์ 1 ไดด้ ังน้ี A[0] A[1] A[2] A[3] A[4] double[] myList = new double[10]; 6DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

อาร์เรย์ 1 มติ ิ 7ในการกาหนดอารเ์ รย์ 1 มิติ เพอื่ ให้ทราบคา่ เริ่มตน้ และค่าสุดทา้ ยของชอ่ งที่ใช้ในการจัดเกบ็ ขอ้ มลู จะใช้รปู แบบดงั นี้ รปู แบบ ชื่ออารเ์ รย์ [ช่องเรม่ิ ต้น..ชอ่ งสดุ ท้าย]ตวั อย่าง เชน่ A[1..10] หมายถงึ อารเ์ รย์ A มชี อ่ งจัดเกบ็ ข้อมลู ตัง้ แตช่ ่องที่ 1 ถึงช่องท่ี 10 B[-5..5] หมายถึง อาร์เรย์ B มชี ่องจดั เก็บขอ้ มูลตงั้ แตช่ อ่ งท่ี -5 ถงึ ชอ่ งที่ 5 C[2..7] หมายถึง อาร์เรย์ C มีชอ่ งจัดเก็บข้อมลู ตงั้ แต่ชอ่ งท่ี 2 ถงึ ช่องท่ี 7 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

public static void main(String[] args) { 8 // TODO code application logic heredouble[] myList = {1.9, 2.9, 3.4, 3.5}; for (int i = 0; i < myList.length; i++) { System.out.println(myList[i] + \" \"); }double total = 0; for (int i = 0; i < myList.length; i++) { total += myList[i]; } System.out.println(\"Total is \" + total);double max = myList[0]; for (int i = 1; i < myList.length; i++) if (myList[i] > max) max = myList[i]; System.out.println(\"Max is \" + max); } DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

run: 9 1.9 2.9 3.4 3.5Total is 11.7 Max is 3.5 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

อารเ์ รย์ 2 มติ ิ คืออาร์เรย์ทม่ี ีแถวหลายแถว แต่ละแถวจะมหี ลายคอลัมน์ ในการอา้ งอิงถึงอารเ์ รย์ 2 มิติ จะใช้ตวั ระบชุ อ่ งท่ี 2 ตวั หากกาหนดให้ อารเ์ รย์ A มีแถวจานวน 2 แถว มีคอลัมน์จานวน 5 คอลัมน์สามารถแสดงรูป อาร์เรย์ 2 มติ ิ ไดด้ งั นี้ 12345 1 A[1,1] A[1,2] A[1,3] A[1,4] A[1,5] 2 A[2,1] A[2,2] A[2,3] A[2,4] A[2,5]DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 10

อาร์เรย์ 2 มิติในการกาหนดอาร์เรย์ 2 มติ ิ เพือ่ ให้ทราบคา่ เร่มิ ตน้ และคา่ สดุ ท้ายของแต่ละมิติท่ีใชใ้ นการจัดเก็บข้อมลู จะใช้รูปแบบ ดงั นี้รูปแบบ ช่ืออาร์เรย์ [ชอ่ งเร่ิมต้นมติ ิ1.. ช่องสดุ ท้ายมิติ1, ชอ่ งเร่ิมต้นมิต2ิ ..ช่องสดุ ท้ายมติ ิ2]ตวั อย่าง เช่นA[1..2,1..5] หมายถงึ อาร์เรย์ A มีแถวตั้งแต่แถวที่ 1 จนถึงแถวท่ี 2 และแต่ละแถวมีชอ่ งจดั เก็บข้อมูลตงั้ แต่ช่องที่ 1 ถึง ชอ่ งท่ี 5 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 11

การจดั เรียงลาดบั ช่องของอาร์เรยใ์ นหน่วยความจาถ้าเปน็ อาร์เรย์ 2 มิติ และอารเ์ รย์ 3 มิติ จะจัดแบง่ การจดั เรียงลาดบั ช่องอารเ์ รย์ในหน่วยความจา เป็น 2 แบบ คอืแบบใช้แถวเปน็ หลกั (Row Major)แบบใช้คอลัมน์เป็นหลกั (Column Major)DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 12

แบบใชแ้ ถวเป็นหลกั (Row Major) ของอาร์เรย์ 2 มิติคือ จดั เรยี งชอ่ งขออารเ์ รยเ์ รียงลาดบั กนั ไปทีละแถว โดยใหห้ มดจานวนช่องของแถวท่ี 1 ก่อน แล้วจึงจะเรมิ่ แถวท่ี 2รูปต่อไปน้จี ะแสดงการอ้างอิงถึงชอ่ งของอารเ์ รย์ A ทีม่ ีจานวน 3 แถว แถวละ 4 คอลมั น์ ดังน้ี 1 2 3 41 A[1,1] A[1,2] A[1,3] A[1,4]2 A[2,1] A[2,2] A[2,3] A[2,4]3 A[3,1] A[3,2] A[3,3] A[3,4] DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 13

แบบใชแ้ ถวเป็นหลกั (Row Major) ของอารเ์ รย์ 2 มติ ิ 1 23411 23425 67839 10 11 12เมอ่ื แทนหน่วยความจาทีม่ ลี ักษณะเป็นเชิงเส้น ช่องของอาร์เรยท์ จี่ ดั เรียงแบบใชแ้ ถวเปน็ หลัก(Row Major) ของอาร์เรย์ ทีจ่ ัดเรียงแบบใชแ้ ถวเป็นหลัก (Row Major) ของอาร์เรย์ 2 มิติ จะเรยี งลาดบั ดงั รูปต่อไปน้ี 1,1 1,2 1,3 1,4 2,1 2,2 2,3 2,4 3,1 3,2 3,3 3,4 1 2 3 4 5 6 7 8 9 10 11 12 DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 14

แบบใชค้ อลัมน์เป็นหลัก (Column Major) ของอาร์เรย์ 2 มติ ิคือ จัดเรยี งชอ่ งของอาร์เรย์เรยี งลาดับกันไปทลี ะคอลมั น์ โดยใหห้ มดจานวนช่องของคอลัมนท์ ี่ 1 ก่อน แล้วจึงจะเริ่มต้นของคอลมั นท์ ี่ 2 1234 1 A[1,1] A[1,2] A[1,3] A[1,4] 2 A[2,1] A[2,2] A[2,3] A[2,4] 3 A[3,1] A[3,2] A[3,3] A[3,4]DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 15

แบบใช้คอลัมนเ์ ป็นหลัก (Column Major) ของอาร์เรย์ 2 มิติ 1234 1 1 4 7 10 2 2 5 8 11 3 3 6 9 12 เมอื่ แทนหน่อยความจาทีม่ ลี ักษณะเปน็ เชิงเสน้ ช่องของอารเ์ รยท์ ่ีจัดเรียงแบบใชค้ อลัมนเ์ ปน็ หลัก (Column Major) ของอารเ์ รย์ 2 มิติ จะเรยี งลาดบั ดังรูปตอ่ ไปน้ี1,1 2,1 3,1 1,2 2,2 3,2 1,3 2,3 3,3 1,4 2,4 3,4 1 2 3 4 5 6 7 8 9 10 11 12DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 16

การคานวณจานวนชอ่ งของอาร์เรย์ในการใช้งานอารเ์ รย์นั้น ต้องระบุขนาดของอารเ์ รยก์ อ่ น ดงั นัน้ เพ่อื ให้รู้ถึงจานวนชอ่ งของอารเ์ รย์ท่ปี ระกาศว่ามีจานวนช่องทั้งหมดกีช่ ่อง จึงตอ้ งคานวณหาจานวนชอ่ งของอารเ์ รย์ โดยมีสูตรในการคานวณหาจานวนช่องของอารเ์ รย์ ดงั นี้◦ การคานวณหาจานวนชอ่ งของอารเ์ รย์ 1 มติ ิ◦ การคานวณหาจานวนช่องของอาร์เรย์ 2 มิติDATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 17

การคานวณหาจานวนชอ่ งของอาร์เรย์ 1 มิติ 18ใช้สูตร จานวนช่อง = U – L + 1 โดยท่ี U คอื ค่าสูงสดุ ของอารเ์ รย์ (Upper bound) L คอื ค่าต่าสุดของอาร์เรย์ (Lower bound) DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

ตัวอย่าง 2-3กาหนด อาร์เรย์ A[1..8] จงคานวณหาจานวนช่องของอารเ์ รย์ A วิธที า อาร์เรย์ A[1..8]ดงั นั้น U = 8 L=1จานวนชอ่ ง =U–L+1 = 8 – 1 +1 =8ดังนั้น อาร์เรย์ A มีจานนชอ่ งทง้ั หมด 8 ช่อง ได้แก่ A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 19

ตัวอย่าง 2-4กาหนดอาร์เรย์ B[-5..0] จงคานวณหาจานวนช่องของอาร์เรย์ Bวิธที า อารเ์ รย์ B[-5..0]ดังน้นั U = 0 , L = -5จานวนชอ่ ง =U–L+1 = 0 – (-5) +1 =6ดงั น้ัน อาร์เรย์ B มจี านวนชอ่ งทง้ั หมด 6 ช่อง ได้แก่ B[-5] B[-4] B[-3] B[-2] B[-1] B[0] DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 20

การคานวณหาจานวนช่องของอาร์เรย์ 2 มติ ิ 21ใช้สูตร จานวนช่อง = (U1 – L1 + 1) * (U2 – L2 + 1) โดยท่ี U1 คอื ค่าสงู สดุ ของอาร์เรยม์ ติ ิที่ 1 (Upper bound) L1 คอื คา่ ต่าสดุ ของอาร์เรย์มติ ิที่ 1 (Lower bound) U2 คือ ค่าสูงสดุ ของอาร์เรยม์ ิติที่ 2 (Upper bound) L2 คือ ค่าตา่ สดุ ของอารเ์ รย์มติ ทิ ่ี 2 (Lower bound) DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA

ตัวอย่างที่ 2-5กาหนดอารเ์ รย์ A[1..5,-1..2] จงคานวณหาจานวนชอ่ งของอาร์เรย์ ADATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 22

ตวั อย่างท่ี 2-6กาหนดอารเ์ รย์ B[-3..-1,0..2] จงคานวณหาจานวนชอ่ งของอาร์เรย์ BDATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 23

แบบฝึกหัดทา้ ยบทอารเ์ รย์ (Array) หมายถึงอะไรอาร์เรยม์ ลี กั ษณะเปน็ อยา่ งไรการจดั เรยี งลาดบั ช่องของอารเ์ รย์ในหนว่ ยความจา แบง่ เป็นกีแ่ บบ อะไรบ้างจากข้อมลู ทก่ี าหนดใหจ้ งจดั เรยี งแบบคอลมั ภเ์ ปน็ หลักกาหนดอาร์เรย์ A[1..5,-2..4] จงวาดรปู แสดงการเรยี งลาดบั ช่องของอารเ์ รย์ในหนว่ ยความจา ทัง้ แบบใชแ้ ถวเปน็ หลัก และแบบคอลมั น์เป็นหลกั DATA STRUCTURE AND ALGORTHM : NUPAN RUJIRA 24