Sau khi có danh sách liên kết đôi và đã được nhập xuất các phần tử vào danh sách liên kết đôi đó, đôi khi ta cần thực hiện việc tìm kiếm và kiểm tra các phần tử trong danh sách đó nhằm phục vụ cho mục đích sắp xếp, sửa hoặc xóa các phần tử trong danh sách liên kết đôi.

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

Hàm tìm kiếm của chúng ta đang cần xây dựng với mong muốn đầu vào là danh sách cần tìm kiếm và khóa (hay dữ liệu) cần tìm kiếm trong danh sách.

Việc tìm kiếm thành công sẽ trả cho chúng ta đầu ra là con trỏ tới khóa cần tìm kiếm (hay chính là phần tử được tìm thấy).

Để thực hiện việc tìm kiếm trong danh sách liên kết đôi ta cần thực hiện các bước sau:

• B1: Tạo Node p và gán bằng đầu danh sách: p=pHead
• B2: Sử dụng vòng lặp while (p!= NULL) và (p->data != x)
  • Thực hiện p = p->next; // p trỏ tới phần tử kế tiếp
• B3: Kiểm tra kết quả sau khi thực hiện vòng lặp ở B2
  • Nếu p==NULL không có phần tử cần tìm;
  • Ngược lại: nếu p != NULL thì trỏ đến phần tử cần tìm

2.Hàm tìm kiếm một phần tử trong danh sách liên kết đôi

Ở phần trên, tôi đã trình bày các bước để thao tác tìm kiếm phần tử có trong danh sách theo dữ liệu x làm khóa tìm kiếm.

Các bước trên có vẻ hơi “mông lung” nên bạn đọc có thể đọc code ở dưới đây để hiểu rõ hơn về hàm tìm kiếm:

NODE* TimKiem(DLIST ds, int x){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau danh sach
    p = ds.pHead;
    //su dung vong lap
    while ((p!=NULL) && (p->data!=x)){
        p=p->next;
    }
    //tra ve ket qua, neu NULL thi khong tim thay
    return p;
}

Hàm tìm kiếm trên có kiểu trả về là NODE và truyền vào danh sách cần tìm kiếm và khóa int x để tìm kiếm trong danh sách đó.

Chú ý rằng hàm trên dù có tìm thấy kết quả hay không thì đều trả về một node p. Nếu p = NULL thì ta kết luận không tìm thấy, và nếu tìm thấy kết quả thì p != NULL và ta nhận được kết quả chính là node p.

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

Trước khi sử dụng hàm tìm kiếm, tôi cần đảm bảo rằng đã có các phần tử nằm trong danh sách cần tìm kiếm, vì thế tôi sẽ nhập các phần tử vào trong danh sách trước sau đó mới gọi hàm tìm kiếm.

#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 de chua dia chi phan tu sau
    Node *next;
    //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc
    Node *prev;
};
typedef struct Node NODE;

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

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

NODE* TaoNode(int x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho va ket thuc viec tao node
    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;
    //gan con tro prev = NULL
    p->prev = NULL;
    //tra ve node p da tao
    return p;
}

void ThemCuoi(DLIST &ds, NODE*p){
    //kiem tra danh sach rong neu rong thi them vao dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else{
        //dat con tro next cua pTail hien tai vao p la node can them cuoi
        ds.pTail->next = p;
        //dat con tro prev cua node p ve phan tu cuoi danh sach
        p->prev = ds.pTail;
        //thay doi lai phan tu cuoi danh sach
        ds.pTail = p;
    }
}
void Nhap(DLIST &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 %d: ",i);
        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 them cuoi va truyen vao node p vua tao
        ThemCuoi(ds,p);
    }
}
void Xuat(DLIST 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(DLIST ds, int x){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau danh sach
    p = ds.pHead;
    //su dung vong lap
    while ((p!=NULL) && (p->data!=x)){
        p=p->next;
    }
    //tra ve ket qua, neu NULL thi khong tim thay
    return p;
}
int main(){
    //khai bao mot danh sach lien ket doi
    DLIST ds;
    //nhap n phan tu 
    int n;
    printf("NHAP N: ");
    scanf("%d",&n);
    //khoi tao danh sach
    KhoiTao(ds);
    //goi ham nhap tryuyen vao danh sach va N phan tu
    Nhap(ds,n);
    //goi ham xuat cac du lieu co trong danh sach
    printf("DANH SACH VUA NHAP\n");
    Xuat(ds);
    //nhap gia tri can tim kiem
    int x;
    printf("NHAP GIA TRI CAN TIM KIEM: ");
    scanf("%d",&x);
    //goi ham tim kiem truyen vao gia tri x va gan vao node p
    NODE *p = TimKiem(ds,x);
    //kiem tra ket qua tim kiem
    if(p == NULL){
        printf("\nKHONG TIM THAY KET QUA");
    }else{
        printf("\nTIM THAY KET QUA: ");
        printf("%d",p->data);
    }
}

Sau khi gọi NODE TimKiem() và gán vào NODE p ta sẽ kiểm tra điều kiện nếu p == NULL thì không tìm thấy kết quả. Ngược lại thì p!= NULL nghĩa là tìm thấy kết quả trong danh sách với khóa X cần tìm.