DANH SÁCH LIÊN KẾT ĐÔI
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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.

Đầ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 Freetuts.net";
}

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é !!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

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

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

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top