Saturday, April 25, 2020

Thuật toán Thêm/ xóa phần tử trong mảng 1 chiều

Mảng một chiều là một dãy hữu hạn các phần tử có cùng kiểu. Mảng được đặt tên và mỗi phần tử mang một chỉ số. Để mô tả mảng một chiều cần xác định kiểu của các phần tử và cách đánh chỉ số các phần tử.
Thuật toán Thêm/ xóa phần tử trong mảng 1 chiều

Đầu tiên, bạn hãy xử lý xong phần nhập xuất mảng nhé. Chúng ta bắt buộc phải sử dụng nhập/ xuất mảng để sử dụng trong quá trình thêm xóa phần tử mảng.
void NhapMang(int a[], int n){
    for(int i = 0;i < n; i++){
        printf("Nhap so thu %d: ", i);
        scanf("%d", &a[i]);
    }
}

void XuatMang(int a[], int n){
    for(int i = 0;i < n; i++){
        printf("%4d", a[i]);
    }
}
Sau đây là thuật toán thêm phần tử vào mảng 1 chiều
Bạn có thể hình dung cách thêm 1 phần tử vào mảng qua hình ảnh dưới đây nhé.
Thuật toán Thêm/ xóa phần tử trong mảng 1 chiều

Quy trình thêm phần tử vào mảng:

  • Kiểm tra mảng có thể thêm được phần tử nữa không? Nếu không, thoát hàm
  • Kiểm tra giá trị pos hợp lệ không. Ở đây nếu không hợp lệ mình cho về chỉ số đầu/cuối.
  • Thực hiện dịch chuyển mảng(phần phía sau nơi chèn + vị trí chèn)
  • Chèn vào vị trí cần chèn
  • Tăng số lượng phần tử

void ThemPhanTu(int a[], int &n, int val, int pos){
     if(n >= MAX){
        return;
    }
 
    if(pos < 0){
        pos = 0;
    }
 
    else if(pos > n){
        pos = n;
    }
 
    for(int i = n; i > pos; i--){
        a[i] = a[i-1];
    }
 
    a[pos] = val;
 
    ++n;
}
Thuật toán Xóa phần tử trong mảng 1 chiều
Bạn có thể hình dung cách xóa 1 phần tử trong mảng qua hình ảnh dưới đây nhé.

Quy trình xóa phần tử trong mảng:

  • Kiểm tra có thể xóa hay không? Nếu không => thoát hàm
  • Kiểm tra giá trị pos hợp lệ không. Ở đây nếu không hợp lệ mình cho về chỉ số đầu/cuối.
  • Dịch chuyển mảng lùi 1 chỉ số – phần phía sau nơi xóa
  • Giảm số lượng phần tử

void XoaPhanTu(int a[], int &n, int pos){
    if(n <= 0){
        return;
    }
    if(pos < 0){
        pos = 0;
    }
    else if(pos >= n){
        pos = n-1;
    }
    for(int i = pos; i < n - 1; i++){
        a[i] = a[i+1];
    }
    --n;
}

No comments:

Post a Comment