Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Chèn node (Insert node) vào DSLK đôi
Trong bài viết này, codehow sẽ hướng dẫn các bạn cách chèn node vào DSLK đôi trong C / C++. Đây là một thao tác rất quan trọng, bởi có nó thì DSLK đôi của chúng ta mới có dữ liệu để thực hiện các thao tác khác.
Tương tự như DSLK đơn, chúng ta có hai cách để chèn node vào DSLK đôi, đó là:
- Chèn node vào đầu DSLK đôi.
- Chèn node vào cuối DSLK đôi.
Bây giờ chúng ta sẽ bắt đầu tìm hiểu từng cách thôi nhé. Sau đó mình sẽ thực hiện một chương trình áp dụng các kiến thức ở bài trước cũng như kiến thức ở bài này cho các bạn tham khảo nhé.
Chèn node vào đầu DSLK đôi
Nếu các bạn đã tìm hiểu về cách chèn node vào DSLK đơn ở bài trước mình giới thiệu, thì đối với DSLK đôi cũng tương tự nhé.
Dưới đây là hàm chèn node vào đầu DSLK đôi, các bạn xem trước rồi sau đó mình sẽ giải thích ngay bên dưới nhé. Lưu ý rằng chúng ta cần tạo các cấu trúc dữ liệu của DSLK đơn rồi mới thực hiện được thao tác chèn.
/* thêm node vào đầu danh sách */
void InsertAtHead(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}Giải thích:
- Đầu tiên chúng ta tạo mới một node bằng cách sử dụng hàm
CreateNote(). - Tiếp đến ta xét điều kiện nếu danh sách rỗng thì node vừa mới tạo chính là node đầu cũng như là node cuối.
- Nếu trong danh sách đã tồn tại phần tử, thì ta thực hiện chèn vào đầu danh sách:
- Dịch chuyển node đầu về NewNode.
Chèn node vào cuối DSLK đôi
Cách chèn node vào cuối DSLK đôi là cách thường dùng nhất. Ví dụ khi chúng ta chèn phần tử vào mảng, thì ta cũng thường chèn vào cuối mảng.
Đầu tiên ta cũng tạo mới node NewNode bằng cách sử dụng hàm CreateNode().
Sau đó kiểm tra xem danh sách có rỗng hay không. Nếu rỗng thì NewNode chính là node đầu cũng như là node cuối.
Ngược lại nếu danh sách tồn tại phần tử thì ta chèn node vào cuối danh sách bằng cách:
- Thiết lập con trỏ next của node tail trỏ đến NewNode.
- Thiết lập con trỏ pre của NewNode trỏ đến node tail.
- Dịch chuyển tail về NewNode.
Như vậy là chúng ta đã chèn xong một node vào cuối DSLK đôi. Dưới đây là hàm mình đã viết sẵn, các bạn có thể tham khảo nhé.
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}Ví dụ chèn node vào DSLK đôi
Trong phần này mình sẽ thực hiện một chương trình áp dụng các kiến thức đã học ở các bài trước, cùng với đó là kiến thức ở bài học này. Cụ thể như sau:
- Tạo cấu trúc dữ liệu của DSLK đôi.
- Chèn node vào đầu danh sách liên kết đôi.
- Chèn node vào cuối danh sách liên kết đôi.
- Duyệt danh sách liên kết đôi từ đầu về cuối và từ cuối về đầu.
Bây giờ chúng ta sẽ bắt đầu thực hiện từng yêu cầu một nhé.
Bước 1: Tạo cấu trúc dữ liệu của DSLK đôi.
using namespace std;
/* tạo cấu trúc node */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node *head, *tail; // Khởi tạo Node head global của dslk đôi.
/* tạo node mới */
struct Node* CreateNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}Bước 2: Chèn node vào đầu DSLK đôi.
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}Bước 3: Chèn node vào cuối DSLK đôi.
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}Bước 4: Duyệt DSLK đôi từ đầu về cuối và từ cuối về đầu.
/* hiển thị từ đầu đến cuối */
void Print() {
struct Node* temp = head;
printf("\nĐầu đến cuối: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
/* hiển thị từ cuối về đầu */
void ReversePrint() {
struct Node* temp = tail;
if(temp == NULL) return; // empty list, exit
// Traversing backward using prev pointer
printf("\nCuối về đầu: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("\n");
}Full code:
#include <iostream>
using namespace std;
/* tạo cấu trúc node */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
struct Node *head, *tail; // Khởi tạo Node head global của dslk đôi.
/* tạo node mới */
struct Node* CreateNode(int x) {
struct Node* newNode
= (struct Node*)malloc(sizeof(struct Node));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* hiển thị từ đầu đến cuối */
void Print() {
struct Node* temp = head;
printf("\nĐầu đến cuối: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
/* hiển thị từ cuối về đầu */
void ReversePrint() {
struct Node* temp = tail;
if(temp == NULL) return; // empty list, exit
// Traversing backward using prev pointer
printf("\nCuối về đầu: ");
while(temp != NULL) {
printf("%d ",temp->data);
temp = temp->prev;
}
printf("\n");
}
/* thêm node vào đầu danh sách */
void InsertFirst(int x) {
//sử dụng hàm tạo Node tạo một Node mới
struct Node* newNode = CreateNode(x);
//nếu danh sách rỗng thì node chèn vào vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách không rỗng thì, dịch chuyển Node head về node mới chèn, và cho con trỏ của newNode trỏ đến Node head
head->prev = newNode;
newNode->next = head;
head = newNode;
}
/* thêm node vào cuối danh sách */
void InsertLast(int x) {
//sử dụng hàm tạo Node để tạo node mới newNode
struct Node* newNode = CreateNode(x);
//Nếu danh sách rỗng thì newNode vừa là node đầu vừa là node cuối
if(head == NULL) {
head = newNode;
tail = newNode;
return;
}
//Nếu danh sách có phần tử thì,
tail->next = newNode;// con trỏ next của tail trỏ đến newNode
newNode->prev = tail;// con trỏ prev của newNode trỏ đến tail
tail = newNode;//dịch chuyển tail về newNode, vì tail luôn luôn quản lý phần tử cuối cùng trong danh sách
}
int main() {
head = NULL;
//gọi hàm thêm node vào đầu danh sách
InsertFirst(2);
InsertFirst(3);
InsertFirst(4);
cout<<"Danh sách sau khi thêm node vào đầu: \n";
Print();
ReversePrint();
cout<<"\n----------end--------------\n";
//gọi hàm thêm node vào cuối danh sách
InsertLast(5);
InsertLast(6);
InsertLast(7);
cout<<"Danh sách sau khi thêm node vào cuối: \n";
Print();
ReversePrint();
cout<<"\n---------------------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
}Kết quả:
