Gộp hai danh sách liên kết đôi - 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 ...
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.
Đầ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<<"
[head] ";
//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<<" ";
ptr = ptr->next;
}
cout<<" [tail]
";
}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<<"
[head] ";
//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<<" ";
ptr = ptr->next;
}
cout<<" [tail]
";
}
/* 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<<"
----------------------------------
";
cout<<"Chương trình này được đăng tại Zaidap.com.net";
}Kết quả:
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é !!!
