Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Cách gộp hai danh sách liên kết đôi
Trong bài viết này, codehow sẽ hướng dẫn các bạn cách gộp hai danh sách liên kết đôi trong C / C++. Đây là thao tác thường gặp khi chúng ta sử dụng DSLK đôi, sau khi gộp hai danh sách ta sẽ được một danh sách mới bảo gồm các node của hai danh sách.
Trước khi đi vào bài viết này, các bạn cần nẵm rõ về cấu trúc dữ liệu của DSLK đôi và các thao tác như chèn, duyệt danh sách đã nhé. Các bạn có thể xem lại tại đây nhé.
Còn bây giờ thì hãy bắt đầu cùng mình tìm hiểu cách nối hai danh sách liên kết đôi thôi nào.
Gợi ý cách gộp hai danh sách liên kết đôi
Về lý thuyết thì chúng ta sẽ gộp hai danh sách liên kết đôi vào một danh sách liên kết đôi khác. Nghĩa là ta sẽ duyệt từng phần tử của danh sách một rồi chuyển qua danh sách ba, rồi chuyển các phần tử của danh sách hai sang danh sách ba.
Vậy chúng ta cần có cấu trúc dữ liệu của các danh sách liên kết đôi, rồi mới thực hiện được. Ở đây mình sẽ thực hiện gộp hai danh sách bao gồm một danh sách các số chẵn và một danh sách các số lẻ.
- Tạo cấu trúc dữ liệu cho danh sách các số chẵn, danh sách các số lẻ và danh sách nối hai danh sách này.
- Tạo cấu trúc node và khởi tạo cho nó.
- Tạo hàm chèn node vào cuối danh sách.
- Tạo hàm duyệt danh sách.
- Tạo hàm nối danh sách.
- Hàm main để chạy chương trình.
Trong các yêu cầu trên chỉ có yêu cầu thứ 5 là trong bài này chúng ta sẽ tìm hiểu. Còn các yêu cầu khác mình đã giới thiệu cụ thể ở các bài trước rồi nhé.
Chương trình gộp hai danh sách liên kết đôi
Bây giờ chúng ta sẽ thực hiện từng yêu cầu dựa vào gợi ý ở phần một nhé. Chương trình được viết bằng ngôn ngữ C++, các bạn có thể tham khảo nhé.
Bước 1: Tạo cấu trúc node.
/* tạo cấu trúc node */
struct node {
int data;
struct node *prev;
struct node *next;
};Bước 2: Tạo cấu trúc cho các DSLK đôi, bao gồm ba danh sách đó là: danh sách các số chẵn, danh sách các số lẻ, danh sách để nối hai danh sách.
/* 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;
Bước 3: Chèn node vào cuối danh sách liên kết đôi. Ở bước này chúng ta đang khởi tạo giá trị cho các danh sách số chẵn và số lẻ.
/* 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;
}
}
}Bước 4: Duyệt danh sách từ đầu đến cuối danh sách.
/* 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";
}Bước 5: Tạo hàm gộp hai danh sách liên kết đôi.
/* 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;
}Việc gộp hai danh sách nghĩa là ta sẽ trỏ con next của phần tử cuối danh sách một sang phần tử đầu danh sách hai. Sau đó trỏ con trỏ prev của phần tử đầu danh sách hai sang phần tử cuối của danh sách một.
Khi đó ta được một danh sách mới bao gồm các phần tử của hai danh sách và các mối liên kết cũng được nối với nhau.
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 codehow.net";
}Kết quả:
Như vậy là chúng ta đã cùng nhau tìm hiểu về cách gộp hai danh sách liên kết đôi trong C / C++. Đây cũng là thao tác cuối cùng mình muốn hướng dẫn các bạn trong series danh sách liên kết đôi. Ở bài viết tiếp theo, mình sẽ giới thiệu đến các bạn cấu trúc cây nhị phân trong C / C++, các bạn chú ý theo dõi nhé!!!
