2D Array Traversals
แนะนำใหม่| English | ความหมาย |
|---|---|
| nested loops/ˈnestɪd luːps/ | ลูปซ้อนกัน |
| row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/ | ลำดับหลักแถว |
| enhanced for/enˈhænst fɔː/ | ลูป for ที่ปรับปรุงแล้ว |
ตารางสี่เหลี่ยมผืนผ้าเผยให้เห็นขอบเขตลูปที่ผิดพลาด
- ตารางมีสองแถวและสามหลัก. ลูปที่มีขอบเขตโดย g.length สำหรับตัวชี้ทั้งสองจะ访问เพียงสองหลักแรกเท่านั้น
- ใช้ r < g.length และสำหรับแต่ละแถว c < g[r].length. วิธีนี้จัดการกับแถวที่มีความยาวแตกต่างกันได้ ในขณะที่ g[0].length สมมติว่ามีตารางสี่เหลี่ยมผืนผ้าที่ไม่ว่าง
Nested loops for a grid
- เพื่อ访问ทุกเซลล์ของ 2-D array, ใช้ nested loops (จาก Unit 2). ลูปภายนอก over rows, ลูปภายใน over columns:
for (int r = 0; r < g.length; r++) { for (int c = 0; c < g[r].length; c++) { ... g[r][c] ... } }ลูปภายใน sweep แถวเต็มก่อนที่ลูปภายนอกจะย้ายไปยังแถวถัดไป
Row-major order
- การ nesting นี้访问เซลล์ตาม row-major order: ทั้งหมดของแถว 0, จากนั้นแถว 1, …
g[0][0], g[0][1], …, g[1][0], g[1][1], … - นี่คือลำดับการอ่านที่เป็นธรรมชาติ — จากซ้ายไปขวา, จากบนลงล่าง. สำหรับตารางสี่เหลี่ยมผืนผ้าที่ไม่ว่าง หลักสามารถเป็นลูปภายนอกแทนเพื่อ访问เซลล์ตามหลัก. Ragged array ต้องการนโยบายที่ระบุชัดสำหรับหลักที่บางแถวไม่มี
The for-each version
- enhanced for loop บน/array 2-D จะให้ แถว (array 1-D) ออกมาทีละแถว
for (int[] row : g) { for (int x : row) { ... x ... } } - ตัวแปรภายนอกคือทั้งแถว; ตัวแปรภายในจะวนผ่านค่าของแถวนั้น ตัวแปร primitive loop ไม่อัปเดตเซลล์ที่เก็บไว้เมื่อมีการกำหนดค่าใหม่ ตัวแปรแถวยังคงเป็น reference ดังนั้น nested loop แบบใช้ดัชนีสามารถแก้ไข
row[c]ได้
Row-major traversal
Outer loop over rows, inner over columns: 1,2,3,4,5,6
รูปแบบใดต่อไปนี้ที่เยี่ยมชมเซลล์ทุกเซลล์ของ array 2-D int ที่ไม่ null โดยที่ reference ของแถวทุกแถวไม่ null?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Outer over rows, inner over columns
ลูปภายนอกของการ traverses แบบ row-major 2-D ที่แสดงควรถูกจำกัดด้วย...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
วงลูปแถวภายนอกใช้ g.length; วงลูปเซลล์ภายในใช้ g[r].length ซึ่งจัดการกับกรณีความยาวแถวที่ไม่เท่ากัน
สำหรับตารางขนาด 2-แถว, 3-คอลัมน์ ลูปที่ซ้อนกันจะเข้าถึงเซลล์ทั้งหมดกี่เซลล์?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
rows × columns = 2 × 3 = 6
Row-major traversal visits cells in the order...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Row-major = left to right, top to bottom
ใน for (int[] row : g), ตัวแปร row คือ...
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The outer for-each variable is a row array
การใช้ g.length สำหรับขอบเขตทั้งสองของวงลูปจะทำให้เกิดข้อผิดพลาดเสมอหากตารางไม่ใช่สี่เหลี่ยมจัตุรัส
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ผิด: ในตารางขนาด 2-แถว, 3-คอลัมน์ มันจะเข้าถึงเพียงสองคอลัมน์และข้ามเซลล์ไปโดยไร้เสียง ในตารางที่สูงกว่ากว้าง มันอาจวิ่งข้ามขอบเขตของแถวได้
การกำหนดขอบเขตที่ถูกต้อง
- ขอบเขตภายนอก:
r < g.length(จำนวนแถว) ขอบเขตภายใน:c < g[r].length(ความยาวของแถวปัจจุบัน) การใช้ความยาวผิดสำหรับ loop เป็นข้อผิดพลาดที่ซับซ้อนในตารางที่ไม่ใช่สี่เหลี่ยมจตุรัส - สำหรับตารางสี่เหลี่ยมไม่เต็มที่มีข้อมูล
g[0].lengthยังให้จำนวนคอลัมน์รวมด้วย และบอดี้ภายในจะวนrows × columnsครั้ง สำหรับแถวที่มีความยาวต่างกัน ให้บวกความยาวของแต่ละแถว; reference ของแถวทั้งหมดต้องไม่ใช่ null
ใช้ g.length สำหรับจำนวนแถวและ g[r].length สำหรับเซลล์ของแถวปัจจุบัน การใช้นับจำนวนแถวเป็นทั้งสองขอบเขตอาจทำให้ข้ามคอลัมน์ในตารางกว้าง หรือเกิด out of bounds ในตารางสูง Array ภายนอกว่างเปล่าไม่ต้องเข้าถึง g[0]; แถวที่เป็น null ต้องมีนโยบายจัดการอย่างชัดเจนก่อนอ่านความยาว
Order the cells visited in row-major traversal of a 2×2 grid.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The inner loop finishes one row before the outer loop advances.
สำหรับ int[][] g = {{1, 2, 3}, {}, {4}};, การ traverse ต่อแถวจะเข้าถึงเซลล์ทั้งหมดจำนวนเท่าใด?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
บวกความยาวของแต่ละแถวเข้าด้วยกัน: 3 + 0 + 1 = 4. แถวที่ว่างเปล่าไม่มีส่วนร่วมในการนับเซลล์
การรวมผล 2-D array:
for (int r = 0; r < g.length; r++)for (int c = 0; c < g[r].length; c++)sum += g[r][c];— เข้าถึงทุกเซลล์ตามลำดับแถว โดยสมมติว่าไม่มีแถวใดเป็น null
ขยายเหตุผลไปยังกรณีใหม่
- สำหรับ
int[][] g = {{1, 2, 3}, {}, {4}};ความยาวของแถวคือ 3, 0 และ 1 ขอบเขตแต่ละแถวเข้าถึงสี่เซลล์และมีผลรวมเท่ากับ 10;g[0].lengthไม่ใช่ขอบเขตที่ถูกต้องสำหรับทุกแถว - คุณสามารถแก้ไข row[c] ด้วย nested loop แบบใช้ดัชนี; การกำหนดค่า x แบบ primitive ใหม่ใน enhanced loop ภายในจะไม่อัปเดตเซลล์ที่เก็บไว้
traverses array 2-D ด้วย nested loops: ภายนอกวนตามแถว (r < g.length), ภายในวนตามคอลัมน์ (c < g[r].length), เข้าถึง g[r][c] สิ่งนี้จะเข้าถึงเซลล์ตามลำดับ row-major (ผลรวมของความยาวแถว; rows × columns สำหรับตารางสี่เหลี่ยม) enhanced for (for (int[] row : g)) ส่ง reference ของแถวหนึ่งต่อครั้ง; การ assign ตัวแปร primitive ของ loop ภายในจะไม่เปลี่ยนเซลล์ที่เก็บไว้