Mảng răng cưa (Jagged Array) là một loại mảng đặc biệt và có tên gọi khác là mảng của mảng. Mỗi mảng có kích thước khác nhau nhưng bắt buộc phải có chung kiểu cơ sở. Mảng phần tử thậm chí có thể không cần khởi tạo.
1. Bài toán
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:
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.
2. Hiện Trung bình cộng của từng hàng trong mảng.
3. Hiện mảng theo trật tự số phần tử mỗi hàng giảm dần. (*)
4. 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ử.
5. 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)
| 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 5 | 3 | 5 |
| 2 | 1 | 2 | 3 | 5 |
| 5 | 3 | 2 | 3 | 5 |
2. Ý tưởng bài toán
2.1 Nhập 1 mảng răng cưa 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)
– 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.
2.2 Hiện mảng răng cưa
– Để 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.
2.3 Hiện 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.
2.4 Sắp xếp mảng tăng dần theo hàng
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.
2.5 Thêm phần tử
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ử.
2.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.
3. Code
#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);
}
4. Kết quả
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 |
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
