1.Cách thêm một phần tử vào giữa danh sách

Tôi sẽ sử dụng lại danh sách mảng gồm các giá trị: 1,2,3,4,5,6,7,8,9,10,11 (hình minh họa bên dưới)

Vấn đề lần này của tôi là cần chèn một số X vào một vị trí P bất kỳ nào đó trong danh sách (xem hình minh họa bên dưới)

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

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

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

• 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 giữa danh sách

2.1 Xây dựng hàm chèn giữa

Hàm void ChenGiua(DSKe &ds, int x, int p) 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 giữa danh sách). Ngoài ra cần chuyền vào một tham số là int p để xác định vị trí sẽ chèn x vào đó:

void ChenGiua(DSKe &ds, int x, int p){
   //neu vi tri p bang 0 thi thuc hien chen dau
   if (p==0){
      //ham chen dau
      ChenDau(ds,x);
   }
   else if (p==ds.n){ // nguoc lai vi tri p bang ds.n thi thuc hien chen cuoi
      //ham chen cuoi
      ChenCuoi(ds,x);
   }else{
      //kiem tra rong thi khong chen
      if (KiemTraDay(ds)==1){
         return;
      }
      //dich chuyen phan tu tu vi tri p sang ben phai
      for (int i=ds.n; i>p; i--){
         ds.A[i] = ds.A[i-1];
      }
   ds.A[p] = x; // Chen X vao vi tri p
   ds.n += 1; // tang phan tu trong danh sach len 
   }
}

Chú ý:

• Hàm ChenGiua() cũng nhận 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 giữa dánh sách sẽ làm thay đổi lại các phần tử có trong danh sách ban đầu.
• Nếu vị trí p = 0 thì tương đương với việc chèn đầu
• Nếu vị trí p = ds.n thì tương đương với việc chèn cuối

2.2 Chương trình hoàn chỉnh sử dụng hàm chèn giữa 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 vị trí P giữa danh sách kề sử dụng mảng. Lưu ý rằng hàm chèn giữa này cần sự có mặt của cả hàm chèn đầu và chèn cuối.

#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 
}

void ChenCuoi(DSKe &ds, int x){
   //neu day thi khong duoc phep chen
   if (KiemTraDay(ds)==1){
      return;
   }
   //truy cap vao phan tu cuoi cung cua danh sach va chen X vao
   ds.A[ds.n]=x;
   //tang phan tu trong danh sach len
   ds.n += 1;
}

void ChenGiua(DSKe &ds, int x, int p){
   //neu vi tri p bang 0 thi thuc hien chen dau
   if (p==0){
      //ham chen dau
      ChenDau(ds,x);
   }
   else if (p==ds.n){ //neu vi tri p bang ds.n thi thuc hien chen cuoi
      //ham chen cuoi
      ChenCuoi(ds,x);
   }else{
      //kiem tra day thi khong chen
      if (KiemTraDay(ds)==1){
         return;
      }
      //dich chuyen phan tu tu vi tri p sang ben phai
      for (int i=ds.n; i>p; i--){
         ds.A[i] = ds.A[i-1];
      }
   ds.A[p] = x; // Chen X vao vi tri p
   ds.n += 1; // tang phan tu trong danh sach len 
   }
}

int main(){
   //khai bien ds co kieu DSKe
   DSKe ds;
   //dua ds vao ham khoitao
   KhoiTao(ds);
   //khai bao bien x can chen giua co gia tri la 55
   int x = 55;
   //khai bao vi tri p can chen
   int p = 6;
   //Chen x vao giua danh sach
   ChenGiua(ds,x,p);
}