여기서 우리는 단일 원형 연결 선형 목록에서 최소값과 최대값을 얻는 방법을 볼 것입니다. 기본 개념은 매우 간단합니다. 마지막 노드의 다음 부분은 첫 번째 노드를 가리키고 첫 번째 노드도 시작 포인터를 사용하여 가리킵니다. 목록에 일부 요소를 삽입하면 새로 삽입된 노드의 다음 부분이 시작 노드의 주소로 업데이트됩니다.
처음에 min은 양의 무한대로 할당되고 max는 음의 무한대로 할당됩니다. 이제 왼쪽에서 오른쪽으로 목록을 탐색합니다. 현재 요소가 최소 요소보다 작으면 최소를 업데이트하고 현재 요소가 최대 요소보다 크면 최대를 업데이트합니다. 따라서 최소값과 최대값을 얻을 수 있습니다.
예
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node *next;
};
Node* getNode(int key){
Node *newNode = new Node();
newNode->data = key;
newNode->next = NULL;
return newNode;
}
void insert(Node **start, int data){
Node *current = *start;
Node *newNode = getNode(data);
if(*start == NULL){
newNode->next = newNode;
*start = newNode;
return;
}
while (current->next != *start) {
current = current->next;
}
newNode->next = *start;
current->next = newNode;
}
void displayList(Node *start){
Node* current = start;
if (start == NULL) {
cout << "Display List is empty";
return;
} else {
do {
cout << current->data << " ";
current = current->next;
}
while (current != start);
}
cout << endl;
}
void getMinMax(Node **start){
if(*start == NULL){
return;
}
Node* current;
current = *start;
int min = INT_MAX, max = INT_MIN;
while (current->next != *start) {
if (current->data < min) {
min = current->data;
}
if (current->data > max) {
max = current->data;
}
current = current->next;
}
cout << "Minimum: " << min << ", Maximum: " << max;
}
int main() {
int data[] = {99, 11, 22, 10, 44, 55, 66};
int n = sizeof(data)/sizeof(data[0]);
Node *start = NULL;
for(int i = 0; i<n; i++){
insert(&start, data[i]);
}
displayList(start);
getMinMax(&start);
} 출력
99 11 22 10 44 55 66 Minimum: 10, Maximum: 99