Методы оптимизации поиска для односвязного списка, полем данных которого будут целые числа, на языке С++ можно реализовать следующими функциями:
/* Функция поиска элемента в списке с перестановкой найденного элемента в начало списка */
PNode Find1(PNode& First, int KEY)
{
PNode search=0;
PNode q=NULL;
PNode p=First;
while (p)
{
if (KEY==p->Data)
{
search=p;
if (!q)
{
return 0;
}
q->Next=p->Next;
p->Next=First;
First=p;
return 0;
}
q=p;
p=p->Next;
}
search=0;
return search;
}
/* Функция поиска элемента в списке с транспозицией */
PNode Find2(PNode& First, int KEY)
{
PNode search=0;
PNode S=0;
PNode q=0;
PNode p=First;
while (p)
{
if (KEY==p->Data)
{
if (!q)
{
return 0;
}
q->Next=p->Next;
p->Next=q;
if (!S) First=p;
else
{
S->Next=p;
search=p;
}
return search;
}
S=q;
q=p;
p=p->Next;
}
search=0;
return search;
}