Không giống như mảng 2 chiều thông thường, nơi mọi hàng đều phải có số lượng cột cố định. Mảng răng cưa cho phép linh hoạt về kích thước giúp phù hợp với các bài toán có dữ liệu không đồng đều. Bài viết này sẽ giới thiệu chi tiết về mảng răng cưa, từ cách nhập liệu, xử lý, đến các thao tác nâng cao như tính toán trung bình cộng, sắp xếp, thêm phần tử, và làm đầy mảng trong ngôn ngữ lập trình C++.
Xem thêm:
1. Mảng răng cưa là gì?
Mảng răng cưa (Jagged Array) là một loại mảng đặc biệt trong lập trình, còn gọi là “mảng của mảng”. Điểm đặc biệt của mảng răng cưa là:
- Kích thước của từng hàng trong mảng có thể khác nhau.
- Các phần tử trong mảng đều phải có cùng kiểu dữ liệu.
- Các hàng không cần được khởi tạo trước.
2. Sự khác biệt giữa mảng răng cưa và mảng hai chiều
| Mảng hai chiều | Mảng răng cưa |
| Mảng 2 chiều nó như một ma trận. Giả sử mảng 3×4, tức là mảng có 3 hàng x 4 cột thì mỗi hàng đều phải có đủ 4 cột. | Mảng răng cưa là một ma trận trong đó mỗi dòng không đồng đều nhau. Hàng thứ nhất có thể 5 cột, hàng thứ 2 chỉ có 2 cột, hàng thứ 3 lại có 4 cột tạo thành hình dạng răng cưa |
3. Bài toán ví dụ
Bài 24 (TH-CSLT-05): Mảng răng cưa là mảng 2 chiều mà trong đó số phần tử mỗi hàng có thể không bằng nhau (ví dụ như trong Bảng A dưới đây)
| 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 5 | 3 | |
| 2 | 1 | 2 | ||
| 5 | 3 |
Viết chương trình thực hiện các yêu cầu sau:
- Nhập 1 mảng răng cưa (tối đa 20 hàng, 20 cột) gồm các số nguyên khác 0 (mỗi hàng kết thúc việc nhập khi gặp số 0). Hiện mảng ra màn hình.
- Hiện Trung bình cộng của từng hàng trong mảng.
- Hiện mảng theo trật tự số phần tử mỗi hàng giảm dần. (*)
- Cho phép người dùng thêm phần tử vào hàng k (k nhập từ bàn phím) với điều kiện không làm số phần tử của hàng k vượt quá số phần tử của hàng có nhiều phần tử nhất. Hiện lại mảng sau khi thêm phần tử.
- Thực hiện làm đầy mảng bằng cách lấy giá trị hiện có ở các ô không trống ở hàng trên cho các ô trống ở hàng dưới. Hiện mảng sau khi làm đầy (ví dụ sau khi làm đầy của bảng A cho như trong bảng B dưới đây)
Ví dụ với mảng A:
| 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 5 | 3 | |
| 2 | 1 | 2 | ||
| 5 | 3 |
Sau khi làm đầy, mảng trở thành B:
| 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 5 | 3 | 5 |
| 2 | 1 | 2 | 3 | 5 |
| 5 | 3 | 2 | 3 | 5 |
4. Ý tưởng giải quyết bài toán
4.1. Nhập mảng răng cưa
– Sử dụng 2 vòng for lồng nhau để duyệt các phần tử của mảng. Trong đó vòng lặp ngoài sẽ duyệt qua các hàng của mảng, vòng lặp bên trong sẽ duyệt các cột của mảng. Mỗi lần duyệt phần tử sẽ, hàm sẽ thông báo yêu cầu người dùng nhập giá trị và lấy giá trị gán vào mảng.
– Nếu giá trị nhập vào bằng 0, vòng lặp bên trong sẽ bị dừng lại ngay lập tức bằng cách sử dụng câu lệnh break. Tương tự, nếu giá trị của phần tử đầu tiên của hàng hiện tại bằng 0, vòng lặp bên ngoài cũng sẽ bị dừng lại. Như vậy, quá trình nhập giá trị cho mảng sẽ kết thúc khi người dùng nhập giá trị 0 cho phần tử cuối cùng của mảng hoặc khi mảng đã đầy, tức là hàng cuối cùng đã chứa phần tử đầu tiên bằng 0.
4.2. Hiện thị mảng
– Để hiện mảng răng cưa ra màn hình, ta sử dụng 2 vòng for lồng nhau, duyệt các phần tử trong mảng in ra màn hình. Nếu giá trị bằng 0 thì thoát vòng lặp bên trong, tương tự sẽ thoát vòng lặp bên ngoài và kết thúc chương trình.
4.3. Tính trung bình cộng của từng hàng trong mảng
Muốn hiện trung bình cộng của từng hàng trong mảng răng cưa, ta chỉ việc duyệt lần lượt các các giá trị của từng hàng, đếm xem có bao nhiêu phần tử đồng thời cộng các giá trị phần tử vào một biến sum. Kết thúc mỗi hàng thì ta in ra giá trị trung bình cộng và reset lại biến sum và đếm.
4.4. Sắp xếp các hàng giảm dần theo số phần tử
Thực hiện sắp xếp tăng dần các phần tử trong mỗi hàng của mảng 2 chiều a.
- Vòng lặp ngoài cùng duyệt qua các hàng của mảng
a. - Vòng lặp thứ hai duyệt qua các phần tử trong hàng hiện tại của mảng
a. - Vòng lặp thứ ba bắt đầu từ phần tử kế tiếp của phần tử đang xét (
k = j+1) và duyệt qua các phần tử còn lại trong hàng hiện tại của mảnga. - Trong quá trình duyệt các phần tử của hàng hiện tại, nếu phần tử
a[i][k]bằng 0, vòng lặp thứ ba sẽ được dừng lại ngay lập tức bằng lệnhbreak. - Nếu phần tử
a[i][j]lớn hơn phần tửa[i][k], thì giá trị của hai phần tử sẽ được hoán đổi cho nhau. - Sau khi kết thúc vòng lặp thứ ba, phần tử
a[i][j]sẽ là giá trị nhỏ nhất trong các phần tử còn lại trong hàng hiện tại. - Nếu phần tử
a[i][j]bằng 0, vòng lặp thứ hai sẽ được dừng lại ngay lập tức bằng lệnhbreak. - Nếu phần tử đầu tiên của hàng hiện tại bằng 0, vòng lặp ngoài cùng cũng sẽ được dừng lại ngay lập tức bằng lệnh
break.
Kết quả của đoạn code này sẽ là mảng a được sắp xếp tăng dần trong từng hàng.
4.5. Thêm phần tử hàng k
Các bước thêm phần tử:
- Tính số lượng phần tử của hàng có nhiều phần tử nhất.
- Nhập số hàng k cần thêm phần tử
- Nhập phần tử mới cần thêm vào hàng k, kiểm tra xem số phần tử của hàng k có vượt quá số phần tử của hàng có nhiều phần tử nhất không, nếu vượt quá thì yêu cầu nhập lại.
- Thêm phần tử vào hàng k.
- Hiển thị lại mảng sau khi thêm phần tử.
4.6. Làm đầy mảng
Để làm đầy mảng răng cưa, đơn giản ta chỉ xét giá trị của phần tử nếu bằng 0 thì lấy giá trị ở hàng trên gán xuống.
5. Code hoàn chỉnh
#include<iostream>
#include<iomanip>
using namespace std;
//1.Nhập 1 mảng răng cưa (tối đa 20 hàng, 20 cột) gồm các số nguyên khác 0 (mỗi hàng kết thúc việc nhập khi gặp số 0). Hiện mảng ra màn hình.
void nhapmang(int a[][20]){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
cout<<"a["<<i<<"]["<<j<<"]= "; cin>>a[i][j];
if(a[i][j]==0){
break;
}
}
if (a[i][0] == 0) {
break;
}
}
}
//2. Hien mang rang cua ra man hinh
void xuatmang(int a[][20]){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(a[i][j]==0){
break;
}
cout<<setw(5)<<a[i][j];
}
cout<<endl;
if (a[i][0] == 0) {
break;
}
}
}
//3.Hiện Trung bình cộng của từng hàng trong mảng
void TBC(int a[][20]){
int sum=0, dem=0,i,j;
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(a[i][j]==0){
break;
}
sum+=a[i][j];
dem++;
}
if(a[i][0]==0){
break;
}
cout<<" Trung binh cong hang "<<i+1<<" = "<<(float)sum/dem<<endl;
sum=0; dem=0;
}
}
//4.Hiện mảng theo trật tự số phần tử mỗi hàng giảm dần
void sapxeptheohang(int a[][20]){
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
for(int k=j+1;k<20;k++){
if(a[i][k]==0){
break;
}
if(a[i][j]>a[i][k]){
int temp = a[i][j];
a[i][j]=a[i][k];
a[i][k]= temp;
}
}
if(a[i][j]==0){
break;
}
}
if(a[i][0]==0){
break;
}
}
}
//5. Cho phép người dùng thêm phần tử vào hàng k (k nhập từ bàn phím) với điều kiện không làm số phần tử của hàng k vượt quá số phần tử của hàng có nhiều phần tử nhất
void themphantu(int a[][20]){
int max_count=0, k, dem=0;
//Tim hang so luong phan tu nhieu nhat
for(int i=0;i<20;i++){
if(a[i][0]==0){
break;
}
for(int j=0;j<20;j++){
if(a[i][j]==0){
break;
}
dem++;
}
if(max_count<dem){
max_count=dem;
}
dem=0;
}
//nhap hang k can them phan tu
cout<<"Nhap hang k: "; cin>>k;
// Kiem tra so luong phan tu cua hang k co vuot qua so luong phan tu hang lon nhat khong
int rows_count=0;
for(int j=0;j<20;j++){
if(a[k][j]==0){
break;
}
rows_count++;
}
if(rows_count>max_count){
cout<<"So luong phan tu da vuot qua gioi han";
}else{
int x;
cout<<"Nhap phan tu can them: "; cin>>x;
//them phan tu vao hang
a[k][rows_count]=x;
}
}
//6, Thực hiện làm đầy mảng bằng cách lấy giá trị hiện có ở các ô không trống ở hàng trên cho các ô trống ở hàng dưới.
void lamdaymang(int a[][20]){
for (int i = 1; i <20; i++) {
if(a[i][0] == 0){
break;
}
for (int j = 0; j <20; j++) {
if(a[i][j]==0){
a[i][j] = a[i-1][j];
}
}
}
}
int main(){
int n,a[20][20], chon;
do{
cout<<"1. Nhap mang"<<endl;
cout<<"2. Xuat mang"<<endl;
cout<<"3. Hien trung binh cong tung hang"<<endl;
cout<<"4. Sap xep mang theo hang tang dan"<<endl;
cout<<"5. Them phan tu vao hang k"<<endl;
cout<<"6. Lam day mang"<<endl;
cout<<"Lua chon: "; cin>>chon;
switch(chon){
case 1:{
nhapmang(a);
cout<<endl;
break;
}
case 2:{
xuatmang(a);
cout<<endl;
break;
}
case 3:{
TBC(a);
cout<<endl;
break;
}
case 4:{
sapxeptheohang(a);
xuatmang(a);
cout<<endl;
break;
}
case 5:{
themphantu(a);
xuatmang(a);
cout<<endl;
break;
}
case 6:{
lamdaymang(a);
xuatmang(a);
cout<<endl;
break;
}
default: exit(0);
}
}while(chon!=0);
}
6. Kết quả chạy chương trình
Trên đây là đoạn mã về mảng răng cưa ngôn ngữ lập trình C++. Cảm ơn các bạn đã theo dõi trên ttnguyen.net
Tải full bài tập thực hành C/C++ có lời giải:
Bài viết cùng chủ đề:
tính tổng các phần tử trong mảng 2 chiều c++
