Mảng

Ghế 14C

• Một rạp hát có 300 ghế. Hệ thống đặt chỗ của nó không có 300 biến gọi là Seat1A, Seat1B, Seat1C. Nó có một mảng, và vé của bạn là một địa chỉ trỏ vào đó: hàng 14, ghế C.
• Một tên, hàng trăm giá trị, mỗi giá trị tìm thấy bởi một con số. Thêm một hàng thì mã không thay đổi; lặp qua các con số và bạn đã kiểm tra mọi ghế.
• Hầu hết mọi thuật toán Paper 2 duyệt qua một mảng: tìm kiếm, cộng tổng, sắp xếp, tìm giá trị lớn nhất của nó.
• Bài học này là từ vựng, các khai báo, và bốn thuật toán mà giám khảo yêu cầu bằng giả thuật và bằng lời nói.

Từ vựng

• Một mảng là cấu trúc dữ liệu chứa một số lượng cố định các phần tử có cùng kiểu dữ liệu dưới cùng một định danh, mỗi phần tử truy cập bằng một chỉ số.
• Cận dưới và cận trên là chỉ số hợp lệ đầu tiên và cuối cùng. Số lượng phần tử là cận trên − cận dưới + 1.
• Số chiều là số chỉ số cần cho một phần tử: một cho danh sách, hai cho bảng.
• Trong ThisArray[n] ← 42 mảng có một chiều, chỉ số là biến INTEGER n, và phần tử tại chỉ số đó nhận 42.

Một định danh, một chỉ số cho mỗi phần tử, cận ở cả hai đầu

Ví dụ đã giải quyết: khai báo mảng mà bài tập cần

Xử lý mảng 1-D

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

• Một vòng lặp FOR từ cận dưới đến cận trên truy cập mỗi phần tử đúng một lần.
• Đối với tổng, đếm, cực đại hoặc cực tiểu, thiết lập biến chạy trước vòng lặp và cập nhật nó bên trong.

Mảng 2-D

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99      // row 2, column 3

• Chỉ số đầu là hàng, chỉ số thứ hai là cột. Vòng lặp lồng nhau truy cập mỗi ô: vòng ngoài遍历 hàng, vòng trong遍历 cột.
• Dùng 1-D cho một dãy đơn lẻ và 2-D khi dữ liệu có hai chiều tự nhiên, chẳng hạn như lưới ghế hoặc bảng điểm theo học sinh và môn học.

Grid[row, column], luôn theo thứ tự đó

Ví dụ minh họa: tìm kiếm tuyến tính có thể báo "không tìm thấy"

FoundAt ← -1
FOR i ← 1 TO n
    IF A[i] = Target THEN
        FoundAt ← i
    ENDIF
NEXT i
IF FoundAt = -1 THEN
    OUTPUT "Not found"
ELSE
    OUTPUT "Found at ", FoundAt
ENDIF

Giá trị lớn nhất, và vị trí của nó

Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
    IF A[i] > Largest THEN
        Largest ← A[i]
        Position ← i
    ENDIF
NEXT i
OUTPUT Largest, " at ", Position

• Bắt đầu Largest từ phần tử đầu tiên, không bao giờ bắt đầu từ 0: mảng có thể chứa toàn số âm.
• Hình dạng tương tự đếm hoặc xuất các phần tử không trống: so sánh từng phần tử với dấu hiệu cho phần tử chưa sử dụng, "" hoặc -1, và chỉ đếm những phần tử khác biệt.

Sắp xếp nổi bọt

• Một sắp xếp nổi bọt thực hiện nhiều lượt duyệt qua mảng để so sánh các cặp phần tử kề nhau và hoán đổi những cặp bị sai thứ tự, cho đến khi một lượt duyệt nào đó không còn hoán đổi nào nữa.
• Sau mỗi lượt duyệt, giá trị lớn nhất chưa được sắp xếp đã nổi lên cuối mảng, nên lượt duyệt tiếp theo có thể dừng sớm hơn một vị trí.

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

Mỗi lượt duyệt đưa giá trị lớn nhất còn lại lên cuối mảng

Ví dụ minh họa: nơi đặt các dấu hiệu sắp xếp nổi bọt

Ví dụ minh họa: loại bỏ và chèn

Điểm số dễ mất

Bạn đã nắm vững