C++ Program to Perform Searching using Self-Organizing Lists
Posted by Superadmin on August 08 2022 05:52:43

C++ Program to Perform Searching using Self-Organizing Lists

 

 

C++ Program to implement Self-Organizing List.

Problem Description

1. Self-Organizing list updates on the basis of last searched item.
2. The sequential searching approach is used.
3. In general search, 80% time only specific 20% of data is accessed.
4. This algorithm shifts the more important data to the beginning of the list.
5. The time complexity of search is O(n).

Problem Solution

1. Create a linked list with the data element.
2. Search the element in the list.
3. If element found, delete it from the list and add at the beginning of the list.
4. Exit.

Program/Source Code

C++ program to compare Binary and Sequential Search.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
// A structure to representing a node.
struct node
{
	int data;
	node *next;
};
 
// A function to create a new node.
node* CreateNode(int data)
{
	node *newnode = new node;
	newnode->data = data;
	newnode->next = NULL;
	return newnode;
}
 
// A function to add the data at the end of the list.
node* InsertIntoList(node *head, int data)
{
	node *temp = CreateNode(data);
	node *t = new node;
	t = head;
	if(head == NULL)
	{
		head = temp;
		return head;
	}
	else
	{
		// Traversing to the end of the list.
		while(t->next != NULL)
			t = t->next;
		// Add the node at the end. 
		t->next = temp;
	}
	return head;
}
 
void Display(node *head)
{
	node *temp = new node;
	temp = head;
	cout<<"\n The list state is :";
	// Display the list.
	while(temp->next != NULL)
	{
		cout<<"->"<<temp->data;
		temp = temp->next;
	}
}
 
node* SearchItem(node *head, int item)
{
	int flag = 0;
	node *temp = new node;
	node *t = new node;
	temp = head;
	if(temp->data == item)
	{
		cout<<"\nItem found at head node";
		flag = 5;
		Display(head);
		return head;
	}
	else
	{
		while((temp->next)->next != NULL)
		{
			if((temp->next)->data == item)
			{
				cout<<"\n item found";
				flag = 5;
				break;
			}
			temp = temp->next;
		}
		// Organising the list.
		// Shifting the searched node to the head.
		t = (temp->next)->next;
		(temp->next)->next = head;
		head = temp->next;
		temp->next = t;
		if(flag == 5)
			Display(head);
		else
			cout<<"\nItem not found.";
	}
	return head;
}
 
int main()
{
	int i, n;
	char ch;
	node *head = new node;
	head = NULL;
 
	for(i = 1; i < 11; i++)
		head = InsertIntoList(head, i);
 
	Display(head);
 
	up:
	cout<<"\nEnter the Element to be searched: ";
	cin>>n;
	// Update the head of the list.
	head = SearchItem(head, n);
 
	cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
	cin>>ch;
	if(ch == 'y' || ch == 'Y')
	goto up;
 
	return 0;
}
Program Explanation

1. Add the data into the linked list using InsertIntoList().
2. Display the list using Display().
3. Take the input of the item to be searched.
4. Call SearchItem().
5. If item found, shift that node to beginning and display the list.
6. If not found, simply return to the main() and ask the user for another search.
7. Display the state of the list.
8. Exit.