Trong những bài trước, khi một danh sách liên kết đơn được cài đặt mặc định cho danh sách này sẽ được duyệt từ đầu danh sách cho đến cuối danh sách liên kết đơn. Tuy nhiên trong một số trường hợp, ta cần duyệt ngược lại danh sách đó. Trong bài này, ta sẽ cùng nhau xử lý một số yêu cầu về duyệt ngược lại danh sách liên kết đơn từ cuối về đầu danh sách bằng phương pháp đảo ngược danh sách liên kết đơn.
1.Cách đảo ngược danh sách liên kết đơn
Giả sử ban đầu, danh sách liên kết đơn của tôi bao gồm các NODE (hay các phần tử) được minh họa ở hình dưới đây.
Khi thực hiện thao tác duyệt danh sách liên kết đơn trên và hiển thị ra dữ liệu có trong các NODE, kết quả nhận được sẽ có thứ tự là: A->B->C->D->NULL
Tuy nhiên, vấn đề đặt ra rằng ta cần duyện ngược lại (hay đảo ngược) danh sách liên kết đơn trên để mong muốn nhận được kết quả sẽ có thứ tự là: D->C->B->A->NULL
Để thực hiện được việc đảo ngược danh sách liên kết đơn trên ta chỉ cần hiểu đơn giản là sẽ phải thay đổi con trỏ next trong mỗi NODE bằng cách trỏ ngược lại con trỏ next để đảo ngược lại danh sách.
Nếu bạn vẫn thấy khó hiểu về việc thay đổi con trỏ trong mỗi NODE ở danh sách liên kết đơn để đảo ngược danh sách, vui lòng xem hình bên dưới:
Tóm tắt các bước đảo ngược danh sách liên kết đơn:
- Khởi tạo NODE* current chính là NODE hiện tại và gán bằng ds.pHead
- Khởi tạo NODE* prev chính là NODE trước NODE current hiện tại và gán ban đầu bằng NULL
- Khởi tạo NODE *next chính là NODE sau NODE hiện tại và gán ban đầu bằng NULL
- Duyệt toàn bộ danh sách từ đầu cho đến NULL bằng vòng lặp, sau đó trong vòng lặp thực hiện các bước sau:
- next = current->next;
- current->next = prev;
- prev = current;
- current = next;
- Bên ngoài vòng lặp gán lại phần tử đầu danh sách: ds.pHead = prev;
2.Hàm đảo ngược danh sách liên kết đơn
Để thực hiện việc xây dựng một hàm dùng cho việc đảo ngược danh sách liên kết đơn ta cần khởi tạo 3 node đó là: NODE* current = l.pHead; NODE *prev = NULL; NODE *next = NULL;
Hàm void DaoNguocDS(LIST &ds) nhận tham số đầu vào là danh sách cần đảo ngược LIST &ds và sau đó sẽ thực hiện việc khởi tạo và đảo ngược danh sách liên kết đơn.
void DaoNguocDS(LIST &ds){ //khoi tao NODE hien tai NODE *current = ds.pHead; //khoi tao NODE truoc NODE hien tai NODE *prev = NULL; //khoi tao NODE sau NODE hien tai NODE *next = NULL; //duyet tu dau den cuoi danh sach while (current != NULL) { //gan next bang node phia sau node hien tai next = current->next; //gan con tro next cua node hien tai ve node phia sau no current->next = prev; //gan node phai sau bang node hien tai prev = current; //gan hien tai bang node phia sau current = next; } //gan lai node dau danh sach lien ket ds.pHead = prev; }
3.Chương trình hoàn chỉnh đảo ngược danh sách liên kết đơn
Chương trình dưới đây, được kết hợp cả hai hàm đã nêu trên để thực hiện việc đảo ngược lại danh sách liên kết đơn. Chương trình ban đầu sẽ được nhập vào danh sách liên kết đơn và hiển thị ra các số theo thứ tự từ đầu đến cuối, sau khi thực hiện gọi hàm void DaoNguocDS(LIST &ds) việc hiện thị sẽ theo thứ tự từ cuối đến đầu.
#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 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 [%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 chen cuoi 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 \t",p->data); } } void DaoNguocDS(LIST &ds){ //khoi tao NODE hien tai NODE *current = ds.pHead; //khoi tao NODE truoc NODE hien tai NODE *prev = NULL; //khoi tao NODE sau NODE hien tai NODE *next = NULL; //duyet tu dau den cuoi danh sach while (current != NULL) { //gan next bang node phia sau node hien tai next = current->next; //gan con tro next cua node hien tai ve node phia sau no current->next = prev; //gan node phai sau bang node hien tai prev = current; //gan hien tai bang node phia sau current = next; } //gan lai node dau danh sach lien ket ds.pHead = prev; } 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("DANH SACH VUA NHAP VAO LA\n"); Xuat(ds); //goi ham dao nguoc danh sach va hien thi ra ket qua printf("\nDANH SACH DUOC DAO NGUOC LA\n"); DaoNguocDS(ds); Xuat(ds); }
Nhap N: 6
Nhap vao so [0]: 7 Nhap vao so [1]: 3 Nhap vao so [2]: 6 Nhap vao so [3]: 9 Nhap vao so [4]: 8 Nhap vao so [5]: 0 DANH SACH VUA NHAP VAO LA 7 3 6 9 8 0 DANH SACH DUOC DAO NGUOC LA 0 8 9 6 3 7 |