Bài giảng Chương 1: Mảng 2 chiều

Chương 1: MẢNG 2 CHIỀU 1. Định nghĩa và Khai báo mảng 2 chiều 2. Duyệt qua mảng 2 chiều 3. Nhập xuất dữ liệu cho mảng 2 chiều 4. Một số thuật toán trên mảng 2 chiều a. Thuật toán tính tổng số và tích số b. Thuật toán đếm c. Thuật toán tìm kiếm d. Thuật toán sắp xếp 1. Định nghĩa và Khai báo mảng 2 chiều • Định nghĩa – Mảng 2 chiều dùng để lưu các phần tử cùng tên và cùng kiểu dữ liệu – Người ta dùng 1 cặp chỉ số để lưu các đối tượng 2 chiều như dòng cột, hoành độ tung độ, ma trận, ma phương • Khai báo – Cú pháp tenmang[size1][size2] trong đó • là kiểu dữ liệu vô hướng hoặc có cấu trúc • tenmang: được đặt theo qui tắc tên biến • [size1]/[size2] là kích thước 2 chiều tương ứng 2. Duyệt qua mảng 2 chiều • Không giống như mảng 1 chiều, mảng hai chiều có những cách duyệt như sau: – Duyệt qua các phần tử của mảng – Duyệt qua các phần tử trên cùng hàng hoặc cùng cột – (Mang vuong)Duyệt qua các phần tử nằm trên đường chéo chính(i==j)/phụ (i+j==n-1) của mảng vuông – Duyệt qua nửa mảng vuông[i<=j]/[i+j<=n- 1]/[i>=j]/[i+j>=n-1]. 3. Nhập xuất dữ liệu cho mảng 2 chiều • Truy cập đến từng phần tử của mảng 2 chiều: tenmang[cs1][cs2] trong đó – cs1 có giá trị từ 0size1-1 – cs2 có giá trị từ 0size2-1 • Nhập dữ liệu – Duyệt qua từng phần tử của mảng để nhập. – Việc đưa dữ liệu vào mảng 2 chiều thường hay phát sinh lỗi nên người ta thường dùng biến temp để nhập liệu rồi gán cho phần tử của mảng. • Xuất dữ liệu – Duyệt qua từng phần tử của mảng 2 chiều và xuất dữ liệu. 4. Một số thuật toán trên mảng 2 chiều a. Thuật toán tính tổng số và tích số •Gọi P = tập hợp một số cặp chỉ số của mảng 2 chiều A. •S = 0; /S = 1 •Lặp với mọi (i,j) thuộc P làm nếu A[i][j] thỏa điều kiện thì S = S+A[i][j] /S = S * A[i][j] •Cuối lặp 4. Một số thuật toán trên mảng 2 chiều b. Thuật toán đếm •Gọi P = tập hợp một số cặp chỉ số của mảng 2 chiều A. •count = 0 •Lặp với mọi (i,j) thuộc P làm nếu A[i][j] thỏa điều kiện thì count = count +1 •Cuối lặp 4. Một số thuật toán trên mảng 2 chiều c. Thuật toán tìm kiếm •Gọi P = tập hợp một số cặp chỉ số của mảng 2 chiều A. •Lặp trong khi (i,j) thuộc P và chưa tìm thấy nếu A[i][j] thỏa điều kiện thì đánh dấu cặp chỉ số (i,j) thoát •Cuối lặp •Chú ý: Thông thường chúng ta dùng cohieu để báo cho biết đã tìm thấy chưa. 4. Một số thuật toán trên mảng 2 chiều d. Thuật toán sắp xếp • Do tính chất của mảng 2 chiều gồm dòng và cột nên bài toán sắp xếp cần được xác định rõ là sắp xếp theo qui tắc nào. • Bài toán sắp xếp trên mảng hai chiều là sự phối hợp giữa các phương pháp duyệt qua mảng 2 chiều và sắp xếp trên mảng 1 chiều. • Có thể sắp xếp theo cột, theo dòng • Giữa các cột, dòng lại có thể sắp xếp độc lập theo qui tắc riêng – Ví dụ: cột thứ nhất sắp xếp theo chiều tăng, cột thứ hai sắp xếp theo chiều giảm.