1.Cách tìm kiếm phần tử trong danh sách

Giả sử một danh sách ban đầu là một mảng gồm các phần tử: 1,2,3,4,5,6,7,8,9,10,11 (như hình dưới)

Công việc tìm kiếm phần tử trong danh sách với yêu cầu đầu vào là giá trị X cần tìm và đầu ra là index (chỉ số) của phần tử X mà ta tìm ra được. Ví dụ dưới đây, tôi cần tìm kiếm giá trị phần tử X = 6 ở trong mảng trên thì kết quả nhận được sẽ là index = 5.

Để thực hiện được công việc tìm kiếm trên ta cần thực hiện 3 bước:

• Bước đầu tiên: Duyệt toàn bộ phần tử có trong danh sách

• Bước thứ hai: Kiểm tra giá trị đầu vào X với từng giá trị phần tử có trong danh sách và sau đó lưu lại index tìm được.

• Bước thứ ba: Lưu lại toàn bộ index vừa tìm được ở bước thứ hai vào một mảng.

2. Hàm tìm kiếm các phần tử có trong danh sách

2.1 Xây dựng hàm tìm kiếm các phần tử

Hàm void TimKiem(DSKe ds, int x) duới đây nhận đầu vào là DSKe ds chính là danh sách cần được tìm kiếm các phần tử và tham số int x chính là giá trị cần tìm kiếm. Hàm này sẽ thực hiện duyệt từ vị trí p = 0 (đầu danh sách) cho đến vị trí p < ds.n (cuối danh sách). Nếu như có phần tử tại vị trí ds.A[p] = X thì sẽ lưu vị trí p đó vào mảng chứa các địa chỉ được tìm thấy.

void TimKiem(DSKe ds, int x){
   //khai bao vi tri p ban dau
   int p = 0; 
   //khai bao bien dem
   int d = 0; 
   //khai bao mang chua dia chi khi tim thay
   int B[10];
   //duyet qua danh sach
   while (p<ds.n){
      //neu co phan tu trong mang = x
      if (ds.A[p]==x){
         //them vi tri p vao mang chua dia chi tim thay
         B[d] = p;
         //tang bien dem len 1 don vi
         d++;
      }
      p += 1;
   }
   //neu bien dem lon hon 0
   if (d>0){
      //hien thi cac vi tri duoc luu trong mang B
      printf("Cac vi tri tim thay: ");
      //duyet mang B
      for (int i=0; i<d; i++){
         printf("%d ", B[i]);
      }
   }else{//nguoc lai d < 0 thi khong tim thay
      printf("Khong co phan tu can tim!\n");
   } 
}

Chú ý:

• Vì việc tìm kiếm sẽ không làm thay đổi các giá trị có trong mảng nên danh sách truyền vào không cần truyền theo kiểu tham chiếu DSKe &ds
• Mảng B chính là nơi lưu trữ các địa chỉ được tìm thấy
• Biến đếm d chính là việc kiểm tra xem có kết quả nào được tìm thấy hay không.

2.2 Chương trình hoàn chỉnh sử dụng hàm tìm kiếm phần tử trong danh sách

Trước khi thực hiện tìm kiếm phần tử trong danh sách, ta cần đảm bảo rằng trong danh sách đã có phần tử. Vì thế tôi sẽ thêm một số phần tử vào danh sách trước bằng cách gọi hàm void ChenDau(ds,x)

Sau đó tôi sẽ thực hiện việc tìm kiếm phần tử trong danh sách với đầu vào X = 6. Bằng cách gọi hàm void TimKiem(ds, 6)

#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 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 DuyetDS(DSKe ds){
   //duyet tu phan tu dau tien
   int p = 0;
   //chua den dia chi cuoi cung trong danh sach thi tiep tuc duyet
   while (p<ds.n){
      //Xu ly cac phan tu duoc xet
      printf("%d ",ds.A[p]);
      //tang den vi tri den phan tu tiep theo trong danh sach
      p++;
   }
}

void TimKiem(DSKe ds, int x){
   //khai bao vi tri p ban dau
   int p = 0; 
   //khai bao bien dem
   int d = 0; 
   //khai bao mang chua dia chi khi tim thay
   int B[10];
   //duyet qua danh sach
   while (p<ds.n){
      //neu co phan tu trong mang = x
      if (ds.A[p]==x){
         //them vi tri p vao mang chua dia chi tim thay
         B[d] = p;
         //tang bien dem len 1 don vi
         d++;
      }
      p += 1;
   }
   //neu bien dem lon hon 0
   if (d>0){
      //hien thi cac vi tri duoc luu trong mang B
      printf("\nCac vi tri tim thay: ");
      //duyet mang B
      for (int i=0; i<d; i++){
         printf("%d ", B[i]);
      }
   }else{//nguoc lai d < 0 thi khong tim thay
      printf("Khong co phan tu can tim!\n");
   } 

}

int main(){
   //khai bien ds co kieu DSKe
   DSKe ds;
   //dua ds vao ham khoitao
   KhoiTao(ds);
   //nhap N so luong phan tu cua danh sach can chen
   int n;
   printf("Nhap N: ");
   scanf("%d", &n);
   //nhap gia tri cho tung phan tu X
   for(int i = 0; i < n; i++){
      int x;
      printf("Nhap phan tu thu [%d] trong danh sach: ",i);
      scanf("%d",&x);
      //chen gia tri cua cac phan tu vao danh sach theo cach chen cuoi
      ChenCuoi(ds,x);
   }
   //goi ham duyet danh sach
   printf("\nDANH SACH BAN DAU\n");
   DuyetDS(ds);
   //nhap gia tri can tim kiem trong danh sach vao bien x
   int x;
   printf("\nNhap gia tri can tim kiem: ");
   scanf("%d",&x);
   //goi ham tim kiem 
   TimKiem(ds,x);
}