Thuật toán chèn phần tử vào một mảng bằng code c++

0
4450
Thuật toán chèn phần tử vào một mảng bằng code c++
Thuật toán chèn phần tử vào một mảng bằng code c++

Bài viết hôm nay mình sẽ hướng dẫn các bạn cách chèn phần tử vào mảng một chiều sử dụng code c++.

Giới thiệu cách chèn phần tử vào mảng

Giả sử mảng của chúng ta có n phần tử: a0, a1, a2, a3, …, a(k-1), ak, …,a(n-1). Bây giờ bạn muốn chèn vào một phần tử có giá trị là b tại vị trí k trong mảng ( 0 ≤k≤n).

Khi đó mảng của chúng ta sẽ là: a0, a1, a2, a3, …,a(k-1), b, ak, …,a(n-1). Tại phần tử b bây giờ sẽ có chỉ số là k tức là giá trị a[k] = b.

Ta có chỉ số của mảng trước khi bị chèn sẽ là: 0, 1, 2, …, k-1, k, .., n-2, n-1

Chỉ số của mảng sau khi bị chèn sẽ là: 0, 1, 2, …, k’-1, k’, …, n’-2, n’-1. Với k’ chính là chỉ số của phần tử vừa chèn.

Ta nhận thấy như sau:

  • a[k’-1] = a[k-1]
  • a[k’] = b
  • a[k’+1] = a[k]
  • a[k’+2] = a[k+1]
  • a[n’-1] = a[n-1]

Với n' = n+1

Cách chèn phần tử vào mảng một chiều bằng cách dùng mảng phụ

Ta nhận thấy như sau:

  • Các phần tử trước vị trí k sẽ không thay đổi. Từ đây ta copy các phần tử của mảng cần chèn (giả sử mảng a) sang một mảng phụ b.
  • Ta sẽ gán giá trị a[k] = value ( tức là giá trị cần chèn)
  • Sau đó ta tiến hành copy các phần tử từ a[k] trở đi của mảng a sang mảng b.
  • Vậy là mảng b chính là mảng mà chúng ta đang cần. Ta chỉ cần cấp phát động lại mảng a và tiến hành copy tất cả các giá trị của mảng b sang là đã xong bài toán.

Mô phỏng bằng tay:

Code tham khảo:

Cách chèn phần tử vào mảng tối ưu hơn.

Như các bạn có thể thấy sau khi chèn vào vị trí k thì các phần tử a[k’+1] = a[k]. Từ đây ta chỉ cần dịch các giá trị a[i] (i chạy từ k đến n-1) về phía sau và sau đó gán phần tử a[k] = ak.

Để dịch được thì các bạn dùng một vòng for chạy từ n-1 đến k. Ta sẽ lấy giá trị a[i] = a[i-1].

Mô phỏng bằng tay:

Code tham khảo:

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

avatar
  Subscribe  
Notify of