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!"); } }