Mảng Hai Chiều - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (14 trang)

Trang chủ

Công Nghệ Thông Tin

Kỹ thuật lập trình

Mảng hai chiều

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (354.18 KB, 14 trang )

Mảng hai chiều Giáo trình Bài Tập Kỹ Thuật Lập Trình Trang 64 CHƯƠNG 6 MẢNG HAI CHIỀU Đây là kiểu dữ liệu dùng để biểu diễn dữ liệu kiểu bảng, kiểu dữ liệu này rất thích hợp cho các bài toán liên quan đến đồ thị, biểu diễn ảnh, … I. TÓM TẮT LÝ THUYẾT I.1. Khái niệm Mảng hai chiều thực chất là mảng một chiều trong đó mỗi phần tử của mảng là một mảng một chiều, và được truy xuất bởi hai chỉ số dòng và cột. Từ khái niệm trên ta có thể đưa ra một khái niệm về mảng nhiều chiều như sau: mảng có từ hai chiều trở lên gọi là mảng nhiều chiều. I.2. Khai báo mảng Từ khái niệm trên ta có cú pháp khai báo mảng hai chiều như sau: • Cách 1: Con trỏ hằng < Kiểu dữ liệu > < Tên mảng > [ < Số dòng tối đa > ][ < Số cột tối đa> ]; Ví dụ: int A[10][10]; // Khai báo mảng 2 chiều kiểu int gồm 10 dòng, 10 cột float b[10][10]; // Khai báo mảng 2 chiều kiểu float gồm 10 dòng, 10 cột • Cách 2 : Con trỏ < Kiểu dữ liệu > **<Tên mảng>; Ví dụ : int **A ; // Khai báo mảng động 2 chiều kiểu int float **B ; // Khai báo mảng động 2 chiều kiểu float Tương tự như mảng một chiều, để sử dụng ta phải cấp phát vùng nhớ cho nó bằng malloc hoặc calloc và huỷ sau khi dùng bằng free Ví dụ : Khai báo mảng các số nguyên A có kích thước 5x6 int **A; A = ( int **) malloc (5) ; for ( int i = 0 ; i < 5 ; i ++ ) A[i]=(int *) malloc (6) ; I.3. Truy xuất phần tử của mảng Để truy xuất các thành phần của mảng hai chiều ta phải dựa vào chỉ số dòng và chỉ số cột. Mảng hai chiều Giáo trình Bài Tập Kỹ Thuật Lập Trình Trang 65 Ví dụ: int A[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} }; Với các khai báo như trên ta có : A[0][0] = 2; A[0][1] = 3; A[1][1] = 6; A[1][3] = 6; Với ví dụ trên ta có hình dạng của một ma trận như sau 0 1 2 3 0 2 3 9 4 1 5 6 7 6 2 2 9 4 7 # Lưu ý: Khi nhập liệu cho mảng hai chiều, nếu là mảng các số nguyên thì ta nhập liệu theo cách thông thường. Nhưng nếu là mảng các số thực thì ta phải thông qua biến trung gian. Ví dụ : float a[10][10]; // Mang so thuc a float tmp; // Bien trung gian tmp scanf (“%f”, &tmp); // Nhap lieu cho bien trung gian a[2][2] = tmp; // Gan du lieu vao phan tu a[2][2] I.4. Ma trận vuông và các khái niệm liên quan a. Khái niệm Là ma trận có số dòng và số cột bằng nhau. b. Tính chất của ma trận vuông • Đường chéo loại 1 o Đường chéo loại 1 bao gồm đường chéo chính và những đường chéo song song với đường chéo chính. Trong đó đường chéo chính là đường chéo có : chỉ số dòng = chỉ số cột Mảng hai chiều Giáo trình Bài Tập Kỹ Thuật Lập Trình Trang 66 o Truy xuất các phần tử trên đường chéo loại 1 : để truy xuất các phần tử trên các đường chéo loại 1 ta có thể dựa vào chỉ số dòng và chỉ số cột như sau : cột – dòng = hằng số Ví dụ : Cho ma trận vuông A(n x n). Gọi (io, jo) là toạ độ điểm xuất phát, ta có thể duyệt đừơng chéo xuất phất từ (io, jo) như sau : for ( i = io, j = jo ; i < n ; i ++, j ++ ) printf (“%4d”,A[i][j]); • Đường chéo loại 2: o Đường chéo loại 2 bao gồm đường chéo phụ và những đường song song với nó. Trong đó đường chéo phụ là đường chéo có: chỉ số cột + chỉ số dòng = số dòng ( hoặc số cột ) o Truy xuất các phần tử trên đường chéo loại 2 : để truy xuất các phần tử trên các đường chéo loại 1 ta có thể dựa vào chỉ số dòng và chỉ số cột như sau : cột + dòng = hằng số Ví dụ: Cho ma trận vuông A(n x n). Gọi (io, jo) là toạ độ điểm xuất phát, ta có thể duyệt đường chéo xuất phất từ (io, jo) như sau : for ( i = io , j = jo ; i < n && j > = 0 ; i ++ , j --) printf (“%4d”,A[i]][j]); II. BÀI TẬP Để đơn giản trong việc khai báo ma trận, ta định nghĩa kiểu ma trận các phần tử với kiểu dữ liệu bất kỳ như sau: #define MAX 100 typedef <kiểu dữ liệu> MATRAN[MAX][MAX]; Ví dụ: Khai báo ma trận các số nguyên a. #define MAX 100 Mảng hai chiều Giáo trình Bài Tập Kỹ Thuật Lập Trình Trang 67 typedef int MATRAN[MAX][MAX]; MATRAN a; II.1. Một số kĩ thuật cơ bản • Phương pháp nhập xuất ma trận void Nhap (MATRAN a, int &d, int &c ) { printf (“\nNhap so dong: ”); scanf (“ %d”, &d ); printf (“\nNhap so cot: ”); scanf (“%d”, &c ); for ( int i = 0; i < d; i ++ ) for (int j = 0; j < c; j ++) { printf (“ a[%d][%d] = ”, i, j ); scanf (“%d”, &a[i][j]); } } void Xuat (MATRAN a, int d, int c) { printf (“\nNoi dung ma tran:\n”); for (int i = 0; i < d; i++) { for (int j = 0; j < c; j++) printf (“ \t %d ”, a[i][j] ); printf (“\n”); } } • Kĩ thuật đặt cờ hiệu Viết hàm kiểm tra xem trong ma trận các số nguyên có tồn tại các số nguyên lẻ lớn hơn 100 không? int KiemTraLe (MATRAN a, int d, int c) { int flag = 0; //tra ve 1 neu co nguoc lai tra ve 0 for (int i = 0; i < d; i ++ ) for (int j = 0; j < c; j++) if ( a[i][j] % 2 != 0 && a[i][j] > 100 ) { flag = 1; break; } return flag; } Mảng hai chiều Giáo trình Bài Tập Kỹ Thuật Lập Trình Trang 68 • Kĩ thuật đặt lính canh Viết hàm tìm phần tử nhỏ nhất trong ma trận. int Min (MATRAN a, int d, int c ) { int min = a[0][0]; for ( int i = 0 ; i < d ; i ++ ) for (int j = 0 ; j < c ; j ++) if ( a[i][j] < min ) min = a[i][j]; return min; } • Phương pháp tính tổng Viết hàm tính tổng các phần tử trong ma trận. long Tong (MATRAN a, int d, int c) { long tong = 0; for ( int i = 0; i < d; i ++ ) for ( int j = 0; j < c; j ++) tong + = a[i][j]; return tong; } • Phương pháp sắp xếp Viết hàm sắp xếp ma trận tăng dần từ trên xuống dưới và từ trái sang phải không dùng mảng phụ. void SapTang(MATRAN a, int d, int c) { for (int i = 0; i <= d*c-2; i ++) for (int j = 0; j <= d*c-1; j ++) if (a[i/c][i%c] < a[j/c][j%c]) { int tmp = a[i/c][i%c] ; a[i/c][i%c] = a[j/c][j%c] ; a[j/c][j%c] = tmp ; } } • Phương pháp đếm Viết hàm đếm các phần tử chẵn trong ma trận. int DemChan (MATRAN a, int d, int c) { int dem = 0;