एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें तत्व पॉइंटर्स के माध्यम से जुड़े होते हैं। लिंक की गई सूची के प्रत्येक तत्व या नोड में एक डेटा भाग और लिंक होता है, या हम अनुक्रम में अगले तत्व के लिए सूचक कह सकते हैं। तत्व स्मृति में गैर-सन्निहित स्थान ले सकते हैं।
हमें एक सिंगल लिंक्ड लिस्ट दी जाती है जिसमें एक डेटा पार्ट होता है और अगले एलिमेंट का लिंक होता है। अन्य इनपुट एक संख्या 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
स्पष्टीकरण - हेड नोड से ट्रैवर्स करते हुए, डेटा भाग को 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
स्पष्टीकरण - हेड नोड से ट्रैवर्स करते हुए, डेटा भाग को K से विभाजित करते रहें और जांचें कि क्या यह पूरी तरह से विभाज्य है, यानी शेषफल 0 आता है।
केवल 12, और 144, 4 से विभाज्य हैं जिनमें से 12 न्यूनतम है और 144 अधिकतम है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
एक लिंक्ड सूची नोड बनाएँ। यहां हमने एक वर्ग SLLnode बनाया है, जिसमें सूचना भाग और अगला सूचक है।
-
एक लिंक्ड सूची बनाएं। यहां हमने सदस्य के रूप में SLLnode ऑब्जेक्ट के साथ एक वर्ग SLList बनाया है। तो SLList में SLLnodes होते हैं।
-
फ़ंक्शन addtohead(int) इस सूची में नोड्स जोड़ रहा है।
-
SLList में तत्वों को जोड़ने के लिए हम LIST नामक SLList ऑब्जेक्ट का उपयोग करके addtohead(int) को कॉल कर रहे हैं।
-
एक बार SLList बन जाने के बाद हम फंक्शन डिविजिबल (SLLnode, int) कहते हैं, जो दो इनपुट पैरामीटर हेड ऑफ लिस्ट और इंटीजर K लेता है।
-
अब डिविजिबल के अंदर हम लिंक्ड लिस्ट के मैक्सिमम और मिनिमम एलिमेंट को स्टोर करने के लिए दो वेरिएबल्स मैक्सडी और मिनडी लेते हैं जो किसी दिए गए नंबर के से विभाज्य है।
-
maxD को -1 से प्रारंभ किया गया है और minD को 9999 प्रारंभ किया गया है। इसे उस श्रेणी के रूप में माना जाता है जिसमें इनपुट निहित है।
-
लूप के अंदर हम सिर से शुरू होने वाली लिंक की गई सूची को पार करते हैं। इसके लिए वेरिएबल स्टार्ट हेड की ओर इशारा कर रहा है।
-
प्रत्येक नोड के जानकारी भाग की तुलना maxD और minD से करें और यह K से विभाज्य है। यदि वर्तमान नोड की जानकारी विभाज्य है और minD से कम है तो minD को वर्तमान जानकारी भाग के साथ अपडेट करें।
-
अगर मौजूदा नोड की जानकारी K से विभाज्य है और मैक्सडी से बड़ी है, तो मैक्सडी को मौजूदा जानकारी वाले हिस्से से अपडेट करें।
-
प्राप्त परिणाम को 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