La lista autoorganizada es una lista que se reorganiza o se reorganiza para un mejor rendimiento. En una lista simple, un elemento a buscar se busca de manera secuencial, lo que da la complejidad temporal de O(n). Pero en un escenario real, no todos los elementos se buscan con frecuencia y, la mayoría de las veces, solo unos pocos elementos se buscan varias veces.
Por lo tanto, una lista autoorganizada usa esta propiedad (también conocida como localidad de referencia) que trae los elementos usados con más frecuencia al principio de la lista. Esto aumenta la probabilidad de encontrar el elemento al principio de la lista y aquellos elementos que rara vez se usan se empujan al final de la lista.
En el método de recuento , se cuenta el número de veces que se busca cada Node (es decir, se mantiene la frecuencia de búsqueda). Por lo tanto, se asocia un almacenamiento adicional con cada Node que se incrementa cada vez que se busca un Node. Y luego los Nodes se organizan en orden no creciente de conteo o frecuencia de sus búsquedas. Esto asegura que el Node al que se accede con más frecuencia se mantenga al principio de la lista.
Ejemplos:
Input : list : 1, 2, 3, 4, 5
searched : 4
Output : list : 4, 1, 2, 3, 5
Input : list : 4, 1, 2, 3, 5
searched : 5
searched : 5
searched : 2
Output : list : 5, 2, 4, 1, 3
Explanation : 5 is searched 2 times (i.e. the
most searched) 2 is searched 1 time and 4 is
also searched 1 time (but since 2 is searched
recently, it is kept ahead of 4) rest are not
searched, so they maintained order in which
they were inserted.
Implementación:
CPP
// CPP Program to implement self-organizing list
// using count method
#include <iostream>
using namespace std;
// structure for self organizing list
struct self_list {
int value;
int count;
struct self_list* next;
};
// head and rear pointing to start and end of list resp.
self_list *head = NULL, *rear = NULL;
// function to insert an element
void insert_self_list(int number)
{
// creating a node
self_list* temp = (self_list*)malloc(sizeof(self_list));
// assigning value to the created node;
temp->value = number;
temp->count = 0;
temp->next = NULL;
// first element of list
if (head == NULL)
head = rear = temp;
// rest elements of list
else {
rear->next = temp;
rear = temp;
}
}
// function to search the key in list
// and re-arrange self-organizing list
bool search_self_list(int key)
{
// pointer to current node
self_list* current = head;
// pointer to previous node
self_list* prev = NULL;
// searching for the key
while (current != NULL) {
// if key is found
if (current->value == key) {
// increment the count of node
current->count = current->count + 1;
// if it is not the first element
if (current != head) {
self_list* temp = head;
self_list* temp_prev = NULL;
// finding the place to arrange the searched node
while (current->count < temp->count) {
temp_prev = temp;
temp = temp->next;
}
// if the place is other than its own place
if (current != temp) {
prev->next = current->next;
current->next = temp;
// if it is to be placed at beginning
if (temp == head)
head = current;
else
temp_prev->next = current;
}
}
return true;
}
prev = current;
current = current->next;
}
return false;
}
// function to display the list
void display()
{
if (head == NULL) {
cout << "List is empty" << endl;
return;
}
// temporary pointer pointing to head
self_list* temp = head;
cout << "List: ";
// sequentially displaying nodes
while (temp != NULL) {
cout << temp->value << "(" << temp->count << ")";
if (temp->next != NULL)
cout << " --> ";
// incrementing node pointer.
temp = temp->next;
}
cout << endl
<< endl;
}
// Driver Code
int main()
{
/* inserting five values */
insert_self_list(1);
insert_self_list(2);
insert_self_list(3);
insert_self_list(4);
insert_self_list(5);
// Display the list
display();
search_self_list(4);
search_self_list(2);
display();
search_self_list(4);
search_self_list(4);
search_self_list(5);
display();
search_self_list(5);
search_self_list(2);
search_self_list(2);
search_self_list(2);
display();
return 0;
}
List: 1(0) --> 2(0) --> 3(0) --> 4(0) --> 5(0) List: 2(1) --> 4(1) --> 1(0) --> 3(0) --> 5(0) List: 4(3) --> 5(1) --> 2(1) --> 1(0) --> 3(0) List: 2(4) --> 4(3) --> 5(2) --> 1(0) --> 3(0)
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA