সেলফ-অর্গানাইজিং লিস্ট মূলত শেষে সার্চ করা আইটেমের ভিত্তিতে দেওয়া আইটেমের রেঞ্জ আপডেট করে। এই পদ্ধতিতে সিকোয়েনশিয়াল সার্চিং পদ্ধতি ব্যবহার করা হয়। এই অ্যালগরিদম আরও গুরুত্বপূর্ণ ডাটাকে লিস্টের শুরুতে স্থানান্তরিত করে। এই সার্চ টেকনিকের সময় জটিলতা O(n)।
অ্যালগরিদম
শুরু ফাংশন FibonacciSearch()। 'start+fib[index-2]' এক্সপ্রেশন ব্যবহার করে mid মান গণনা করুন। যদি বাছাই করা আইটেম mid ইনডেক্সের মানের সমান হয়, তবে ফলাফল প্রিন্ট করে main-এ ফেরত যান। যদি এটি mid ইনডেক্সের মানের চেয়ে কম হয়, তবে বাম সাব-অ্যারে নিয়ে এগিয়ে যান। যদি এটি mid ইনডেক্সের মানের চেয়ে বেশি হয়, তবে ডান সাব-অ্যারে নিয়ে এগিয়ে যান। যদি গণনা করা mid মান start বা end-এর সমান হয়, তবে আইটেমটি অ্যারেতে নেই। শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
struct node {
int d;
node *next;
};
node* CreateNode(int d) {
node *newnode = new node;
newnode->d = d;
newnode->next = NULL;
return newnode;
}
node* InsertIntoList(node *head, int d) {
node *temp = CreateNode(d);
node *t = new node;
t = head;
if (head == NULL) {
head = temp;
return head;
} else {
while (t->next != NULL)
t = t->next;
t->next = temp;
}
return head;
}
void Display(node *head) {
node *temp = new node;
temp = head;
cout << "\n লিস্টের অবস্থা :";
while (temp->next != NULL) {
cout << "->" << temp->d;
temp = temp->next;
}
}
node* SearchItem(node *head, int item) {
int flag = 0;
node *temp = new node;
node *t = new node;
temp = head;
if (temp->d == item) {
cout << "\nআইটেম হেড নোডে পাওয়া গেছে";
flag = 5;
Display(head);
return head;
} else {
while ((temp->next)->next != NULL) {
if ((temp->next)->d == item) {
cout << "\nআইটেম পাওয়া গেছে";
flag = 5;
break;
}
temp = temp->next;
}
t = (temp->next)->next;
(temp->next)->next = head;
head = temp->next;
temp->next = t;
if (flag == 5)
Display(head);
else
cout << "\nআইটেম পাওয়া যায়নি।";
}
return head;
}
int main() {
int i, n;
char ch;
node *head = new node;
head = NULL;
for (i = 1; i < 20; i++)
head = InsertIntoList(head, i);
Display(head);
up:
cout << "\nসার্চ করার উপাদান লিখুন: ";
cin >> n;
head = SearchItem(head, n);
cout << "\n\n\tআরও সার্চ করতে চান...চয়েস লিখুন (y/n)? ";
cin >> ch;
if (ch == 'y' || ch == 'Y')
goto up;
return 0;
}
আউটপুট
লিস্টের অবস্থা :->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18 সার্চ করার উপাদান লিখুন: 7 আইটেম পাওয়া গেছে লিস্টের অবস্থা :->7->1->2->3->4->5->6->8->9->10->11->12->13->14->15->16->17->18 আরও সার্চ করতে চান...চয়েস লিখুন (y/n)? y সার্চ করার উপাদান লিখুন: 20 আইটেম পাওয়া যায়নি। আরও সার্চ করতে চান...চয়েস লিখুন (y/n)? n
