Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm phần tử đỉnh trong danh sách liên kết đã cho.
Phần tử đỉnh là phần tử lớn hơn các phần tử xung quanh. Hãy xem các bước để giải quyết vấn đề.
-
Tạo một nút cấu trúc cho danh sách được liên kết.
-
Tạo danh sách được liên kết với dữ liệu giả.
-
Kiểm tra các trường hợp cơ sở như danh sách được liên kết trống hay có độ dài 1.
-
Lưu trữ phần tử đầu tiên trong một biến được gọi là trước đó.
-
Lặp lại danh sách được liên kết.
-
Kiểm tra xem phần tử hiện tại có lớn hơn phần tử trước đó và phần tử tiếp theo hay không.
-
Trả lại nếu điều kiện trên thỏa mãn.
-
Cập nhật phần tử trước đó.
-
-
In kết quả
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void insertNewNode(struct Node** head_ref, int new_data) {
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
*head_ref = new_node;
}
int findPeakElement(struct Node* head) {
if (head == NULL) {
return -1;
}
if (head->next == NULL) {
return head->data;
}
int prev = head->data;
Node *current_node;
for (current_node = head->next; current_node->next != NULL; current_node = current_node->next) {
if (current_node->data > current_node->next->data && current_node->data > prev) {
return current_node->data;
}
prev = current_node->data;
}
if (current_node->data > prev) {
return current_node->data;
}
return -1;
}
int main() {
struct Node* head = NULL;
insertNewNode(&head, 7);
insertNewNode(&head, 4);
insertNewNode(&head, 5);
insertNewNode(&head, 2);
insertNewNode(&head, 3);
cout << findPeakElement(head) << endl;
return 0;
} Đầu ra
Nếu bạn thực thi đoạn mã trên, bạn sẽ nhận được kết quả sau.
5
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.