2.1.12 Функция поиска элемента списка

Процесс поиска элемента в списке можно рассматривать независимо от вида списка – упорядоченный список или нет. В этом случае для поиска искомого элемента следует перебрать в среднем половину элементов списка. Однако для упорядоченных списков естественно применить более оптимальные методы поиска, например метод половинного деления.

Поиск элемента в упорядоченном списке. Пусть поиск выполняется по полю Name - ключ поиска. Функция поиска элемента списка по ключу возвращает IndFndEl - номер элемента в массиве, в котором содержится указатель найденного элемента, при FindOK = true, или индекс элемента массива, в котором может размещаться указатель на добавляемый элемент, если искомого элемента в списке нет, при FindOK = false. Ниже приводятся два варианта функции поиска – перебором элементов массива и методом половинного деления.

Функция поиска методом перебора в качестве параметров получает позицию 1-го байта массива указателей на элементы списка, реальное количество элементов списка, ключ поиска и возвращает индекс указателя найденного элемента (индекс возможной вставки указателя нового элемента) и возвращает признак – поиск успешен.

bool FindElSortList1 (TFile &f, int Start_list, int CntElmList, char* Key,

int &PosFndEl)

{

/*процедура имеет двойное назначение - поиск месторасположения искомого элемента и поиск места вставки добавляемого элемента*/

int PosPtrElmLst; /*позиция указателя в массиве указателей*/

TElmArrPtrFile PtrElmLst; /*указатель на элемент списка*/

TRecListFile WElmLst; /*текущий элемент списка*/

bool FindOk = false; /*элемент не найден*/

if (CntElmList == 0)

{

/*список пуст. PosFndEl содержит индекс в массиве возможной вставки указателя на новый элемент*/

PosFndEl = 0;

return FindOk;

}

PosPtrElmLst = Start_list; /*позиция указателя на элемент списка

с индексом 0*/

for ( int J = 0; J < CntElmList; J++)

{

/*чтение очередного указателя*/

fseek(f, PosPtrElmLst, SEEK_SET);

fread (&PtrElmLst, sizeof(PtrElmLst), 1, f);

/*чтение очередного элемента списка*/

fseek (f, PtrElmLst, SEEK_SET );

fread (&WElmLst, sizeof(WElmLst), 1, f);

/*сравнение поля Name элемента списка и Key*/

if (strcmp(WElmLst.Name, Key) >= 0)

{

PosFndEl = J; /*позиция указателя найденного или сле-

дующего большего элемента*/

if (strcmp(WElmLst.Name, Key) == 0)

{

FindOk = true; /*элемент найден. В противном случае PosFndEl

содержит позицию (в массиве указателей) возможной вставки нового элемента*/

}

return FindOk;

}

/*позиция следующего указателя*/

PosPtrElmLst = PosPtrElmLst + sizeof(PtrElmLst);

}

PosFndEl = CntElmList; /*перебран весь массив указателей. PosFndEl

содержит индекс (в массиве указателей) возможной вставки указателя на новый элемент*/

return FindOk;

} /*FindElSortList1*/

Функция поиска методом половинного деления в качестве параметров получает позицию 1-го байта массива указателей на элементы списка, реальное количество элементов списка, ключ поиска и возвращает указателя найденного элемента (индекс в массиве указателей возможной вставки указателя на новый элемент) и возвращает признак – поиск успешен.

bool FindElSortList2 (TFile &f, int Start_list, int CntElmList, char* Key,

int &IndFndEl)

/*поиск выполняется методом половинного деления*/

/*процедура имеет двойное назначение - поиск месторасположения искомого элемента и поиск места вставки добавляемого элемента*/

{

int Middl; /*Middl выступает как средняя граница обрабатываемой

части массива*/

int Hi, Low; /*текущие границы – верхняя и нижняя, обрабатываемой

части массива */

TElmArrPtrFile PtrElmLst; /*указатель на элемент списка*/

TRecListFile WElmLst ; /*текущий элемент списка*/

bool FindOK = false; /*элемент не найден*/

if (CntElmList == 0)

{

/*список пуст. IndFndEl содержит индекс в массиве указателей

возможной вставки указателя на новый элемент*/

IndFndEl = 0;

return FindOK;

}

Low = 0;

Hi = CntElmList-1;

do

{

Middl = (Hi + Low) / 2;

/*чтение указателя очередного среднего элемента*/

fseek (f, Start_list + Middl * sizeof(PtrElmLst), SEEK_SET);

fread (&PtrElmLst, sizeof(PtrElmLst), 1, f);

/*чтение очередного среднего элемента списка*/

fseek (f, PtrElmLst, SEEK_SET );

fread (&WElmLst, sizeof(WElmLst), 1, f);

/*сравнение поля Name элемента списка и Key*/

switch (strcmp(WElmLst.Name, Key))

{

case 0: IndFndEl = Middl;

FindOK = true; /*элемент найден*/

return FindOK;

case 1: Hi = Middl - 1;

break;

case -1: Low = Middl + 1;

break;

}

}while (Low <= Hi);

IndFndEl = Low ; /*перебран весь массив. Искомый элемент не

найден. Определен индекс возможной вставки нового элемента*/

return FindOK;

} /*FindElSortList2*/