Читайте также:
|
В просматриваемой таблице порядок расположения элементов никак не связан со значениями ключей (рис. II-34). Поэтому поиск элемента по ключу осуществляется обычным просмотром всех элементов таблицы, начиная с первого и до искомого (если он есть в таблице; тогда поиск заканчивается успешно), или до конца таблицы (тогда поиск заканчивается неуспешно).
| Ключ | Информация |
| ... | |
| ... | |
| ... | |
| ... | |
| ... |
Рис. II‑34.
Можно определить длину поиска элемента с ключом ki, находящегося в i-ой позиции таблицы (например, элемент с ключом 47 находится в позиции 3):
S = i.
Очевидно, что для просматриваемой таблицы дольше всего выполняется поиск последнего элемента таблицы; следовательно, максимальная длина поиска
T = n,
где n – размер таблицы.
Вообще говоря, средняя длина поиска будет зависеть от частоты обращения к различным записям. Так, например, если в просматриваемой таблице первая запись требуется гораздо чаще, чем все остальные, то средняя длина поиска будет близка к 1. В соответствии с этим среднюю длину поиска можно определить следующим образом:
D = 
ipi
где i – порядковый номер записи, а pi – вероятность того, что требуемая запись имеет номер i.
Если частота обращений неизвестна, можно предположить, что к каждой записи таблицы будет произведено одинаковое количество обращений, т.е. искомая запись с равной вероятностью находится на любом месте таблицы и 
. Тогда средняя длина поиска
Просматриваемая таблица может быть и статической, и динамической; она может быть отображена в памяти и вектором, и списком. Рассмотрим особенности реализации операций для разных способов отображения просматриваемой таблицы.
Просматриваемая таблица-список
При отображении просматриваемой таблицы списком не играет роли, какую – статическую или динамическую – таблицу использовать; структура элемента таблицы (списка) будет одинакова. Поиск в таблице осуществляется простым просмотром списка и не вызывает каких-либо затруднений. При включении в таблицу новый элемент может быть размещен в любом месте таблицы (списка), поэтому удобнее (эффективнее) включать его в начало списка, используя соответствующий алгоритм стека. Здесь эта функция не приводится.
Некоторые осложнения могут возникнуть при удалении элемента из таблицы.
Если некоторый элемент удаляется из списка, действия, выполняемые при этом, могут быть разными в зависимости от того, какой элемент удаляется (рис. II-37).
Рис. II‑37.
Если удаляется первый элемент списка, в этом случае должен быть модифицирован указатель на начало списка (таблицы). Если же удаляется некоторый элемент из середины списка, тогда модифицируется поле указателя предыдущего элемента
(рис. II-37).
Таким образом, при удалении элемента надо:
· иметь доступ к предшествующему элементу списка,
· различать вид предшествующего элемента.
Поскольку операция поиска возвращает искомый элемент и не сообщает о месте его размещения в списке, при реализации операции удаления элемента из списка приходится (a) либо повторять поиск элемента, (b) либо следует несколько изменить реализацию операции поиска. Способ (b) удобно реализуется средствами языка С. Рассмотрим оба способа.
Алгоритм удаления элемента из просматриваемой таблицы-списка по варианту a) приведен на рис. II-38.
В приведенном алгоритме отдельно рассматриваются удаление первого и промежуточного элементов таблицы, поскольку это приводит к необходимости модифицировать разные структуры: указатель на начало таблицы при удалении первого элемента и поле указателя в элементе списка при удалении промежуточного элемента. В результате в блоке C2 сравниваются ключи первого элемента таблицы и удаляемого элемента и, при их совпадении, в блоке D2 переопределяется указатель на начало таблицы.
Рис. II‑38.
Если удаляется не первый элемент, осуществляется в цикле (блоки C3, D3, E3) поиск удаляемого элемента. При этом используются два указателя – на текущий (cur) и на предыдущий (prev) элементы таблицы. При совпадении ключей переопределяется поле ссылки в предыдущем элементе (на который указывает prev), в результате чего элемент удаляется из таблицы-списка.
Ниже приводится текст программы, соответствующий приведенному алгоритму.
struct Item{
int key;
Type info;
struct Item *next;
};
Item *ptab; /* указатель на начало таблицы */
int del1(int k)
{
Item *cur, *prev;
cur = ptab;
/* проверяем, есть ли в таблице элементы */
if(!cur)
return -1; /* таблица пуста – отказ */
/* возможно, требуется удалить первый элемент таблицы */
if(cur->key == k){
/* удаляем первый элемент */
ptab = cur->next;
delete cur;
return 0;
}
/* ищем удаляемый элемент среди других элементов таблицы */
while(cur->next){ /* есть другие элементы */
prev = cur;
cur = cur->next;
if(cur->key == k){
/* нашли элемент, который надо удалить */
prev->next = cur->next;
delete cur;
return 0;
}
}
/* естественный выход из цикла – в таблице нет элемента с ключом k */
return -1;
}
Эту функцию можно сократить за счет использования данных типа "указатель на указатель на...". Введя такую переменную, мы можем записать в нее адрес указателя на элемент списка, что позволит совместить удаление первого и промежуточных элементов таблицы. Текст функции приводится ниже.
struct Item{
int key;
Type info;
struct Item *next;
};
Item *ptab; /* указатель на начало таблицы */
int del2(int k)
{
Item *cur, **pptr;
pptr = &ptab; /* указатель на указатель на первый элемент таблицы */
/* ищем удаляемый элемент среди всех элементов таблицы */
while(*pptr){ /* еще есть элементы */
if((*pptr)->key == k){
/* нашли элемент, который надо удалить */
cur = *pptr; /* указатель на удаляемый элемент */
*pptr = cur->next;
Delete cur;
return 0;
}
/* продвигаемся к следующему элементу таблицы */
pptr = &(*pptr)->next;
}
/* естественный выход из цикла – в таблице нет элемента с ключом k */
return -1;
}
Чтобы понять, как работает данная функция, рассмотрим следующую иллюстрацию (рис. II-39).
Рис. II‑39.
В исходном состоянии переменная pptr указывает на элемент ptab – на указатель на указатель на первый элемент таблицы (списка). Таким образом, значением pptr является значение указателя на переменную ptab (адреса этой переменной); значением (результатом вычисления выражения) *pptr – значение самой переменной ptab, то есть, значение указателя на первый элемент таблицы; наконец, результатом вычисления выражения (*pptr)->key будет ключ первого элемента таблицы.
Если ключ элемента совпадает с заданным, значит, найден удаляемый элемент. Тогда: переменной cur присваивается значение *pptr, то есть, значение указателя на этот элемент таблицы; cur->next определяет следующий элемент таблицы, указатель на который должен быть записан в ptab, то есть, в *pptr. Указатели переопределяются, и найденный элемент удаляется из списка.
Если ключи не совпадают, надо продолжить поиск в таблице. Для этого переменной pptr присваивается значение указателя на поле next текущего элемента, тем самым обеспечивая, что *pptr указывает на следующий элемент таблицы, и все вычисления выполняются аналогично рассмотренным выше (*pptr указывает на второй элемент таблицы, (*pptr)->key определяет ключ второго элемента, (*pptr)->next - указатель на следующий, третий элемент таблицы, и так далее).
Тексты функций приведены также в файле Programs/tab1lst.cpp.
Если разработать функцию поиска элемента в таблице, которая возвращает указатель на указатель на найденный элемент, ее можно будет использовать в функции удаления элемента из таблицы. Реализацию данного варианта функций предлагаю в качестве самостоятельной работы.
Дата добавления: 2015-12-07; просмотров: 97 | Нарушение авторских прав