1.Cách tìm kiếm phần tử trong danh sách liên kết đơn

Từ một danh sách đầu vào gồm các thành phần (các Node) như hình bên dưới:

Vấn đề bây giờ, tôi cần tìm kiếm một Node có trong danh sách theo dữ liệu X là thứ cần tìm kiếm.

Để thực hiện được việc tìm kiếm này tôi cần thực hiện 2 bước:

• Bước đầu tiên: Duyệt toàn bộ danh sách liên kết đơn
• Bước thứ hai: Kiểm tra thành phần data của từng node có trong danh sách đang được duyệt, nếu có data = X thì trả về địa chỉ của Node đó.

Xem hình dưới đây để hiểu hơn hai bước trên:

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

Hàm NODE* TimKiem(LIST ds, int x) dưới đây nhận LIST ds là danh sách cần tìm kiếm và int x là dữ liệu cần tìm kiếm trong các node có trong danh sách liên kết đơn:

NODE* TimKiem (LIST ds, int x){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau tien
    p = ds.pHead;
    //trong khi p!= NULL (chua la phan tu cuoi) va 
    //p->data !=x (du lieu cua p khong trung voi x tim kiem)
    while ((p!=NULL) && (p->data!=x)){
        //thuc hien tro den NODE tiep theo trong danh sach
        p=p->next;
    }
    //tra ve node p
    return p;
}

Nếu tìm thấy phần tử trong danh sách, hàm trên sẽ trả về node p. Ngược lại trong trường hợp không tìm thấy phần tử thì hàm trên sẽ trả về NULL

3.Chương trình hoàn chỉnh tìm kiếm phần tử trong danh sách liên kết đơn

Trước khi sử dụng hàm tìm kiếm, tôi sẽ cần nhập một vài node vào trong danh sách liên kết đơn. Sau khi đã có node trong danh sách liên kết đơn, tôi sẽ thực hiện tìm kiếm, nếu trong danh sách có giá trị tìm kiếm sẽ hiển thị ra màn hình dòng chữ “Tìm thấy kết quả!” ngược lại nếu không tìm thấy sẽ hiển thị ra “Không tìm thấy!”.

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    //khai bao thanh phan du lieu co kieu int
    int data;
    //khai bao con tro next co kieu Node
    Node *next;
};
typedef struct Node NODE;

struct list{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct list LIST;

void KhoiTao(LIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

int KiemTraRong(LIST ds){
    //neu phan tu dau danh sach NULL
    if (ds.pHead == NULL){
        //tra ve 1 la co NULL
        return 1;
    }
    //truong hop nguoc lai tra ve khong null
    return 0;
}

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //tra ve node p da tao
    return p;
}
void ChenDau(LIST &ds, NODE *p) {
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL){
        //chen dau va cuoi deu bang node p
        ds.pHead = p;
        ds.pTail = p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro next cua node p bang phan tu dang la dau tien cua danh sach
        p->next = ds.pHead;
        //gan pHead bang node p
        ds.pHead = p;
    }
}

void ChenCuoi (LIST &ds, NODE *p){
    //neu phan tu dau rong thi danh sach rong
    if (ds.pHead==NULL) {
        //chen dau va cuoi deu bang node p
        ds.pHead=p;
        ds.pTail=p;
    }
    //nguoc lai danh sach khong rong
    else {
        //gan con tro cua phan tu cuoi trong danh sach bang node p
        ds.pTail->next=p;
        //gan pTail bang node p
        ds.pTail=p;
    }
}

void Nhap(LIST &ds, int n){
    //duyet N lan
    for(int i = 0; i < n; i++){
        //nhap du lieu la so nguyen int x
        int x;
        printf("Nhap vao so x: ");
        scanf("%d",&x);
        //tao node p
        NODE *p = new NODE;
        //dua du lieu vua nhap vao node p
        p = TaoNode(x);
        //dua node p vao ham chen dau
        ChenCuoi(ds,p);
    }
}

void Xuat(LIST ds){
    //khoi tao mot node
    NODE *p = new NODE;
    //duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
    for(p = ds.pHead; p!= NULL; p=p->next){
        //hien thi du lieu cua tung node
        printf("%d\n",p->data);
    }
}

NODE* TimKiem (LIST ds, int x){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau tien
    p = ds.pHead;
    //trong khi p!= NULL (chua la phan tu cuoi) va 
    //p->data !=x (du lieu cua p khong trung voi x tim kiem)
    while ((p!=NULL) && (p->data!=x)){
        //thuc hien tro den NODE tiep theo trong danh sach
        p=p->next;
    }
    //tra ve node p
    return p;
}

int main(){
    //khai bao mot danh sach
    LIST ds;
    //nhap so luong N tu ban phim
    int n;
    printf("Nhap N: ");
    scanf("%d",&n);
    //khoi tao danh sach
    KhoiTao(ds);
    //goi ham nhap va truyen danh sach va so luong N vao
    Nhap(ds,n);
    //goi ham xuat du lieu 
    printf("\nDU LIEU TRONG DANH SACH LIEN KET DON\n");
    Xuat(ds);
    //nhap gia tri x can tim kiem
    int x;
    printf("Nhap gia tri can tim kiem: ");
    scanf("%d",&x);
    //tao node p
    NODE *p = new NODE;
    //goi ham tim kiem va truyen ds va x vao ham sau do gan ket qua tim kiem vao node p
    p = TimKiem(ds,x);
    if(p == NULL){
        printf("\nKhong tim thay!");
    }else{
        printf("\nTim thay ket qua!");
    }
}