Gộp hai danh sách liên kết đôi

Trong hướng dẫn này mình sẽ giới thiệu đến các bạn cách nối hai danh sách liên kết đôi thành một danh sách liên kết đôi khác.

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết đôi. Để làm được bài này các bạn cần nắm vững kiến thức về danh sách liên kết đôi. Các thao tác tạo cấu trúc dữ liệu, thêm, duyệt danh sách liên kết đôi.

1. Gợi ý cách thực hiện

Trong bài toán ta cần nối hai danh sách liên kết đôi thành một danh sách liên kết đôi khác. Cụ thể ta sẽ nối hai danh sách, một danh sách là số chẵn và một danh sách là số lẻ.

  • Tạo cấu trúc Node.
  • Tạo cấu trúc dữ liệu cho các danh sách số chẵn, số lẽ và danh sách để nối hai danh sách này.
  • Tạo danh sách liên kết đôi với thao tác thêm Node vào cuối danh sách.
  • Viết hàm hiển thị danh sách.
  • Viết hàm nối danh sách.
  • Hàm main để chạy chương trình và kiểm tra kết quả.

2. Nối hai danh sách liên kết đôi

Chúng ta sẽ thực hiện lần lượt các bước như mình đã gợi ý ở trên. Như đã nói, để hiểu được các bạn cần có kiến thức về danh sách liên kết.

Bài viết này được đăng tại [kiso.vn]

Đầu tiên ta tạo cấu trúc cho Node với giá trị data và cỏn trỏ next, prev.

/* tạo cấu trúc node */
struct node {
   int data;
   struct node *prev;// tạo con trỏ prev trỏ về phần tử phía trước
   struct node *next;// tạo con trỏ next trỏ về phần tử phía sau
};

Tiếp đến ta cần tạo cấu trúc dữ liệu cho các danh sách liên kết đôi. Ở đây ta cần ba danh sách, một cho các số lẻ, một cho các số chẵn và danh sách còn lại để gộp hai danh sách này.

/* tạo cấu trúc dữ liệu cho danh sách sau khi nối */
struct node *list = NULL;
struct node *list_last = NULL;
/* tạo cấu trúc dữ liệu cho danh sách các số chẵn */
struct node *even = NULL;
struct node *even_last = NULL;
/* tạo cấu trúc dữ liệu cho danh sách các số lẻ */
struct node *odd = NULL;
struct node *odd_last = NULL;
/* tạo cấu trúc dữ liệu node hiện tại */
struct node *current = NULL;

Sau khi tạo xong cấu trúc dữ liệu cho danh sách, ta thực hiện tạo danh sách liên kết đôi và khởi tạo giá trị cho danh sách. Trong hàm này mình sử dụng InsertLast để thêm Node vào danh sách, đây là cách thường dùng khi muốn thêm node.

// Nếu head trống thì tạo list mới
   if(data%2 == 0) {
      if(even == NULL) {
         even = link;
         return;
      }else {
         current = even;

         while(current->next != NULL)
            current = current->next;

         // chèn node vào cuối danh sách
         current->next = link; 
         even_last = link;
         link->prev = current;
      }
   }else {
      if(odd == NULL) {
         odd = link;
         return;
      }else {
         current = odd;

         while(current->next!=NULL)
            current = current->next;
         // chèn node vào cuối danh sách
         current->next = link; 
         odd_last = link;
         link->prev = current;
      }
   }
}

Để hiển thị danh sách ta cần tạo một hàm hiển thị, trong phần này mình viết hàm duyệt danh sách từ đầu đến cuối.

/* hiển thị danh sách */
void printList(struct node *head) {
   struct node *ptr = head;

   cout<<"n[head] t";
   //dùng vòng lặp while lặp từ phần tử đầu đến phần tử cuối của list
   while(ptr != NULL) {        
      cout<<ptr->data<<"t";
      ptr = ptr->next;
   }
   cout<<" [tail]n";
}

Và cuối cùng ta tạo một hàm combine() để nối hai danh sách các số chẵn và số lẻ.

/* nối hai danh sách */
void combine() {
   struct node *link;
   list = even;
   link = list;
   while(link->next!= NULL) {
      link = link->next;
   } 
   link->next = odd;
   odd->prev = link;
   // gắn con trỏ next tới danh sách mới
   while(link->next!= NULL) {
      link = link->next;
   }
   list_last = link;  
}

Phần này ta muốn cho danh sách các số lẻ nối vào đuôi danh sách các số chẵn. Vì vậy ta sẽ cho con trỏ prev của danh sách số lẻ trỏ về danh sách số chẵn và ngược lại cho con trỏ next của danh sách chẵn trỏ đến danh sách lẻ.

Full code:

#include<iostream>
using namespace std;
/* tạo cấu trúc node */
struct node {
   int data;
   struct node *prev;
   struct node *next;
};
/* tạo cấu trúc dữ liệu cho danh sách sau khi nối */
struct node *list = NULL;
struct node *list_last = NULL;
/* tạo cấu trúc dữ liệu cho danh sách các số chẵn */
struct node *even = NULL;
struct node *even_last = NULL;
/* tạo cấu trúc dữ liệu cho danh sách các số lẻ */
struct node *odd = NULL;
struct node *odd_last = NULL;
/* tạo cấu trúc dữ liệu node hiện tại */
struct node *current = NULL;

/* tạo danh sách liên kết đôi */
void insert(int data) {
   // cấp phát bộ nhớ cho node mới;
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->data = data;
   link->prev = NULL;
   link->next = NULL;

   // Nếu head trống thì tạo list mới
   if(data%2 == 0) {
      if(even == NULL) {
         even = link;
         return;
      }else {
         current = even;

         while(current->next != NULL)
            current = current->next;

         // chèn node vào cuối danh sách
         current->next = link; 
         even_last = link;
         link->prev = current;
      }
   }else {
      if(odd == NULL) {
         odd = link;
         return;
      }else {
         current = odd;

         while(current->next!=NULL)
            current = current->next;
         // chèn node vào cuối danh sách
         current->next = link; 
         odd_last = link;
         link->prev = current;
      }
   }
}

/* hiển thị danh sách */
void printList(struct node *head) {
   struct node *ptr = head;

   cout<<"n[head] t";
   //dùng vòng lặp while lặp từ phần tử đầu đến phần tử cuối của list
   while(ptr != NULL) {        
      cout<<ptr->data<<"t";
      ptr = ptr->next;
   }
   cout<<" [tail]n";
}

/* nối hai danh sách */
void combine() {
   struct node *link;
   list = even;
   link = list;
   while(link->next!= NULL) {
      link = link->next;
   } 
   link->next = odd;
   odd->prev = link;
   // gắn con trỏ next tới danh sách mới
   while(link->next!= NULL) {
      link = link->next;
   }
   list_last = link;  
}

int main() {
   int i;

   for(i=1; i<=10; i++)
      insert(i);

   cout<<"Danh sách các số chẵn: ";
   printList(even);

   cout<<"Danh sách các số lẻ: ";
   printList(odd);

   combine();
   cout<<"Danh sách các số sau khi nối: ";
   printList(list);
   
   cout<<"n----------------------------------n";
   cout<<"Chương trình này được đăng tại Kiso.vn";
}

Kết quả:

dslk doi 11 PNG

3. Kết luận

Như vậy là chúng ta đã thực hiên xong chương trình nối hai danh sách liên kết đôi trong C++. Đây là một bài tập áp dụng các kiến thức trong DSLK, các bạn hãy luyện tập thật nhiều để có thể thành thạo nó. Hãy chú ý các bài hướng dẫn hấp dẫn khác của mình nhé !!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *