Thêm Phần Tử Vào đầu Mảng Danh Sách Kề Trong C/C++

Trước khi vào bài này, bạn đọc hãy đảm bảo rằng mình đã đọc qua Bài 1: Cài đặt danh sách kề sử dụng mảng, bởi vì việc thêm phần tử vào trong danh sách kề sử dụng mảng sẽ cần dùng các hàm đã được tôi nêu ra ở bài trước!

1.Cách thêm một phần tử vào đầu danh sách

Giả sử tôi có một danh sách kề sử dụng mảng và có các phần từ trong đó là các số: 1,2,3,4,5,6,7,8,9,10,11 (hình minh họa bên dưới).

Đặt vấn đề rằng tôi cần thêm một số X vào vị trí đầu tiên có trong mảng nghĩa là số X này sẽ đứng trước số 1 (xem hình bên dưới)

Để thực hiện được việc này tôi cần thực hiện 3 bước:

• Bước đầu tiên: Dồn tất cả các phần tử từ đầu đến cuối sang phải một vị trí:

• Bước thứ hai: Đặt số X vào vị trí trống ở đầu:

• Bước thứ ba: Tăng số lượng phần tử trong danh sách lên 1 đơn vị

2.Hàm thêm một phần tử vào đầu danh sách

2.1 Xây dựng hàm chèn đầu

Hàm void ChenDau(DSKe &ds, int x) duới đây nhận tham chiếu đầu vào là DSKe &ds và số nguyên int x (chính là phần tử cần chèn vào đầu danh sách)

void ChenDau(DSKe &ds, int x){ //neu danh sach da day thi khong thuc hien chen if (KiemTraDay(ds)==1){ return; } //kiem tra dieu kien trong danh sach co phan tu thi dich chuyen sang phai if (ds.n>0){ //Dich chuyen cac phan tu for (int i = ds.n; i>=1; i--){ ds.A[i] = ds.A[i-1]; } } ds.A[0] = x; //Chen phan tu dau tien bang X ds.n = ds.n+1; //tang so luong phan tu trong danh sach len }

Chú ý:

• Khi thao tác chèn, ta cần chuyền vào hàm ChenDau() dưới dạng tham chiếu DSKe &ds bởi vì ta mong muốn rằng sự thay đổi của danh sách khi phần tử được chèn vào đầu sẽ làm thay đổi lại các phần tử có trong danh sách ban đầu.
• Trước khi chèn phần tử x vào ta cần sử dụng hàm KiemTraDay() để kiểm tra rằng danh sách đó đã đầy hay chưa (nếu đã đầy thì không được chèn thêm vào)
• Hàm KiemTraDay() đã được nêu ra ơ bài Bài 1: Cài đặt danh sách kề sử dụng mảng

2.2 Chương trình hoàn chỉnh sử dụng hàm chèn đầu vào danh sách

Chương trình dưới đây nêu ra đầy đủ các hàm (hay các nội dung cần thiết) để thực hiện việc chèn một giá trị vào đầu danh sách kề sử dụng mảng:

#include <stdio.h> #define MAX 100 //dinh nghia so luong phan tu cua mang co the luu tru typedef struct DSKe{ //mang int a voi kich thuoc MAX = 100 int A[MAX]; //quan ly so luong N phan tu int n; }DSKe; //khai bao ham khoi tao void KhoiTao(DSKe &ds){ //ban dau danh sach la rong (n = 0) ds.n = 0; } int KiemTraRong(DSKe ds){ //neu ds.n == 0 thi rong if (ds.n==0){ return 1; } return 0; } int KiemTraDay(DSKe ds){ //neu ds.n == MAX thi da day if (ds.n == MAX){ return 1; } return 0; } void ChenDau(DSKe &ds, int x){ //neu danh sach da day thi khong thuc hien chen if (KiemTraDay(ds)==1){ return; } //kiem tra dieu kien trong danh sach co phan tu thi dich chuyen sang phai if (ds.n>0){ //Dich chuyen cac phan tu for (int i = ds.n; i>=1; i--){ ds.A[i] = ds.A[i-1]; } } ds.A[0] = x; //Chen phan tu dau tien bang X ds.n = ds.n+1; //tang so luong phan tu trong danh sach len 1 } int main(){ //khai bien ds co kieu DSKe DSKe ds; //dua ds vao ham khoitao KhoiTao(ds); //khai bao bien x can chen co gia tri bang 0 int x = 0; //Chen x vao dau danh sach ChenDau(ds,x); }