Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Tìm kiếm phần tử trong DSLK đôi
Trong bài viết này, codehow sẽ hướng dẫn các bạn cách để tìm kiếm một phần tử trong DSLK đôi. Đây là bài toán tìm kiếm thường gặp khi chúng ta làm việc với cấu trúc dữ liệu nói chung và danh sách liên kết đôi nói riêng.
Thông thường để tìm kiếm phần tử có tồn tại hay không chúng ta sẽ duyệt từng phần tử, sau đó kiểm tra xem có phần tử nào bằng nó hay không. Đây là cách thông thường và dễ sử dụng nhất, vậy nên việc tìm kiếm trong DSLK đôi cũng áp dụng cách này để thực hiện.
Vậy làm thế nào để thực hiện nó đối với DSLK đôi thì hãy bắt đầu cùng mình ngay thôi nào.
Tìm kiếm phần tử trong DSLK đôi
Để tìm kiếm phần tử trong DSLK đôi, ta cần xác định được hai đối tượng trước tiên. Đối tượng thứ nhất là danh sách liên kết đôi chứa phần tử cần tìm kiếm. Đối tượng thứ hai chính là giá trị của phần tử cần tìm kiếm.
/* Tìm kiếm phần tử k trong danh sách */
bool search(Node l, int k ){ // thanm số truyền vào bao gồm một danh sách và phần tử k
Node *p = head;//tạo một node tạm p để thay thế cho node head
//sử dụng vòng lặp while để lặp từng phần tử trong danh sách
while(p!=NULL) {
if(p->data == k )return true;//nếu giá trị tại node hiện tại == k thì return true
else p = p->next;//Nếu không == k thì trỏ đến node kế tiếp
}
return false;//Kết thúc vòng lặp vẫn ko tìm thấy thì return false
}Sau khi xác định được hai đối tương này, việc tiếp theo chúng ta cần tạo mới một node *p. Node này có nhiệm vụ thay thế cho node head để thực hiện duyệt danh sách. Bởi vì node head luôn quản lý node đầu nên chúng ta không thể lấy nó để thực hiện thao tác được.
Sử dụng vòng lặp while với điều kiện danh sách không rỗng (tức là khác NULL). Lặp từng phần tử trong danh sách và so sánh với node *p, nếu phần tử nào bằng *p thì đó thì phần tử cần tìm có tồn tại. Ngược lại thì chúng ta trỏ đến phần tử tiếp theo cho đến khi kết thúc vòng lặp.
Trường hợp kết thúc vòng lặp rồi nhưng vẫn chưa tìm thấy phần tử cần tìm thì return false rồi thoát khỏi vòng lặp và kết thúc hàm.
Ví dụ tìm kiếm phần tử trong DSLK đôi
Trong phần này, mình sẽ thực hiện một chương trình để tìm kiếm phần tử k có tồn tại trong danh sách liên kết đôi hay không. Qua chương trình này các bạn có thế ôn lại các thao tác như chèn node, duyệt danh sách, .. .
Cụ thể các yêu cầu của chương trình dưới đây:
- Xây dựng cấu trúc của DSLK đôi.
- Thêm node mới.
- Chèn node vào đầu danh sách.
- Duyệt danh sách từ đầu về cuối và từ cuối về đầu.
- Tìm kiếm phần tử k được nhập bởi người dùng xem có tồn tại trong danh sách hay không. Sau đó thông báo cho người dùng biết.
Bây giờ chúng ta sẽ bắt đầu thực hiện theo từng yêu cầu của chương trình thôi nhé.
Bước 1: Xây dựng cấu trúc 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.Bước 2: Thêm node mớ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 3: Chèn node vào đầu danh sách.
/* 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 4: Duyệt danh sách 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");
}Bước 5: Yêu cầu người dùng nhập vào một số k, sau đó tìm kiếm xem k có tồn tại trong danh sách hay không.
bool search(Node l, int k ){
Node *p = head;
while(p!=NULL) {
if(p->data == k )return true;
else p = p->next;
}
return false;
}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
}
bool search(Node l, int k ){
Node *p = head;
while(p!=NULL) {
if(p->data == k )return true;
else p = p->next;
}
return false;
}
int main() {
Node l;
int k, x, lc;
head = NULL;
//gọi hàm thêm node vào đầu danh sách
InsertLast(2);
InsertLast(3);
InsertLast(4);
InsertLast(5);
InsertLast(6);
InsertLast(7);
InsertLast(8);
cout<<"Danh sách sau khi thêm node vào đầu: \n";
Print();
ReversePrint();
cout<<"\n----------end--------------\n";
//tìm kiếm node
cout<<"\nNhập số cần tìm trong danh sách: "; cin>> k;
if(search(l,k) == true){
cout<<"Đã tìm thấy "<<k<<" trong danh sách";
}
else{
cout<<"không tìm thấy "<<k<<" trong danh sách";
}
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 tìm kiếm phần tử trong DSLK đôi. Ở bài tiếp theo mình sẽ hướng dẫn các bạn cách gộp hai DSLK đôi. Các bạn chú ý theo dõi nhé, cảm ơn các bạn rất nhiều !!!
