연결 목록은 요소가 포인터를 통해 연결된 선형 데이터 구조입니다. 연결 목록의 각 요소 또는 노드에는 데이터 부분과 연결이 있거나 순서대로 다음 요소에 대한 포인터라고 할 수 있습니다. 요소는 메모리에서 인접하지 않은 위치를 사용할 수 있습니다.
데이터 부분과 다음 요소에 대한 링크가 있는 단일 연결 목록이 제공됩니다. 다른 입력은 숫자 K입니다. 작업은 숫자 K로 나눌 수 있는 연결 목록의 최대 및 최소 요소를 찾는 것입니다. 선형 연결 목록은 한 방향으로만 이동할 수 있습니다. 각 노드에서 데이터 부분의 분할 가능성을 K로 확인합니다. 해당 숫자가 지금까지 발견된 최대값 또는 최소값이면 MaxD 및 MinD 값을 업데이트합니다.
입력
SList : 5-->2-->10-->12-->3-->20-->7, K=5
출력
Maximum element which is divisible by K : 20 Maximum element which is divisible by K : 5
설명 − Head 노드에서 순회하면서 데이터 부분을 K로 계속 나누어 완전히 나누어지는지, 즉 나머지가 0인지 확인합니다.
5, 10, 20만 5로 나눌 수 있으며 그 중 5는 최소값이고 20은 최대값입니다.
입력
SList : 12-->2-->5-->18-->3-->144-->7, K=4
출력
Maximum element which is divisible by K : 144 Maximum element which is divisible by K : 12
설명 − Head 노드에서 순회하면서 데이터 부분을 K로 계속 나누어 완전히 나누어지는지, 즉 나머지가 0인지 확인합니다.
12와 144만 4로 나눌 수 있으며 그 중 12는 최소값이고 144는 최대값입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
연결 목록 노드를 만듭니다. 여기에서 정보 부분과 다음 포인터가 있는 클래스 SLLnode를 만들었습니다.
-
연결 목록을 만듭니다. 여기에서 SLLnode 객체를 멤버로 사용하여 SLList 클래스를 만들었습니다. 따라서 SLList는 SLLnode로 구성됩니다.
-
addtohead(int) 함수가 이 목록에 노드를 추가하고 있습니다.
-
SLList에 요소를 추가하기 위해 LIST라는 SLList 객체를 사용하여 addtohead(int)를 호출합니다.
-
SLList가 생성되면 목록의 head와 정수 K의 두 입력 매개변수를 취하는 Divisible(SLLnode,int) 함수를 호출합니다.
-
이제 Divisible 내에서 주어진 숫자 K로 나눌 수 있는 연결 목록의 최대 및 최소 요소를 저장하기 위해 두 개의 변수 maxD와 minD를 사용합니다.
-
maxD는 -1로 초기화되고 minD는 9999로 초기화됩니다. 이것은 입력이 있는 범위로 가정합니다.
-
for 루프 내부에서 헤드에서 시작하여 연결 목록을 탐색합니다. 이 변수의 경우 시작은 머리를 가리키고 있습니다.
-
각 노드의 정보 부분을 maxD, minD와 비교하여 K로 나눗셈성입니다. 현재 노드의 정보가 나눌 수 있고 minD보다 작으면 minD를 현재 정보 부분으로 업데이트합니다.
-
현재 노드의 정보가 K로 나눌 수 있고 maxD보다 크면 현재 정보 부분으로 maxD를 업데이트합니다.
-
minD 및 maxD에서 얻은 결과를 인쇄하십시오.
예시
#include<iostream.h>
#include<process.h>
#include<conio.h>
class SLLnode{
public:
int info;
SLLnode *next;
SLLnode(int e1,SLLnode *ptr=0){
info=e1;
next=ptr;
}
};
class SLList{
public:
SLLnode *head;
SLList()
{ head=0; }
void addtohead(int); };
void SLList::addtohead(int el)
{ head=new SLLnode(el,head); }
void Divisible(SLLnode* head, int K){
int minD=9999;
int maxD=-1;
SLLnode* start=head;
for(start;start->next!=NULL;start=start->next){
if ((start->info < minD) && (start->info % K == 0))
minD = start->info;
if ((start->info > maxD) && (start->info % K == 0))
maxD = start->info;
}
cout << "Max Element divisible by K: " << maxD << endl;
cout << "Min Element divisible by K: " << minD;
}
// Driver Code
int main(){
clrscr();
// Start with empty list
SLList LIST;
LIST.addtohead(50);
LIST.addtohead(21);
LIST.addtohead(32);
LIST.addtohead(45);
LIST.addtohead(11);
LIST.addtohead(23);
LIST.addtohead(90);
LIST.addtohead(56);
int K = 5;
Divisible(LIST.head, K);
getch();
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Max Element divisible by K: 90 Min Element divisible by K: 45