Таблица - некоторый (вообще говоря неупорядоченный) набор именованных записей. Имена могут выбираться достаточно произвольным образом, но чтобы можно было организовать эффективный поиск записи по ее имени, нужно сравнивать любые два имени записей и устанавливать, какое из них больше, а какое меньше. Имя записи в таблице называется ключом записи.
Часто в качестве ключей используются целые положительные числа. Можно использовать строки. Над типом данных, используемым для представления ключа, должны быть определены операции сравнения. Если встроенных операций нет, можно разработать функции, сравнивающие ключи.
Операции, определенные над таблицей, как структурой данных:
- поиск записи с заданным ключом;
- включение в таблицу записи с заданным ключом (обычно считается, что если в таблице уже есть запись с таким ключом, то старые значения заменяются новыми);
- удаление записи из таблицы.
Существует несколько способов организации таблицы. Выбор того или иного способа определяется характером использования таблицы:
1. Односвязный список.
Простейший способ представления таблицы.
Достоинства:
- кроме полезной информации присутствует только один указатель на следующую запись, следовательно, память ЭВМ используется достаточно эффективно;
- алгоритм перебора при поиске очень прост;
- включение в таблицу заведомо новой записи можно сделать максимально эффективно, помещая новую запись в фиксированное место таблицы, например, в начало или в конец.
Недостатки:
- основной недостаток заключается в том, что поиск может оказаться длительным, так как для неупорядоченного списка возможен (практически) только последовательный поиск. В среднем случае просматривается половина записей, а в худшем - все. Если число записей N невелико, то неэффективностью поиска можно пренебречь, отдав предпочтение простоте алгоритма и быстродействию. Если N велико - то наоборот;
- даже если исконной записи нет, то для установления этого факта при поиске придется пересмотреть всю таблицу.
2. Упорядоченный список.
Записи в таблице расположены в порядке возрастания или убывания ключей. В этом случае неудачный поиск можно прекратить при достижении записи с ключом больше (если ключи отсортированы в порядке возрастания) заданного.
Усложняется процедура включения новой записи в таблицу, так как должна поддерживаться упорядоченность, а следовательно, предварительно нужно найти соответствующее место для вставки записи.
Достоинство:
- упорядоченный список позволяет использовать двоичный поиск.
3. Массив записей.
В каждой записи хранится ключ и указатель на полезную информацию. Так как размер записей одинаков, их можно объединить в массив, упорядочив по возрастанию ключей. Следовательно, массив - это упорядоченный список с разорванными связями.
Достоинства:
- двоичный поиск;
- очень быстрый доступ при индексации массива.
Недостатки:
- плохо подходит для включения и удаления записей, так как связи разорваны и приходится сдвигать все элементы массива;
- может применяться лишь для таблиц фиксированного размера.
4. Двоичное дерево.
Достоинство:
- Наиболее эффективная реализация операций.
Недостаток:
Сложность некоторых операций (поддержание сбалансированного дерева, удаление узла из дерева).
1. Альфред Ахо, Джон Э. Хопкрофт, Д. Ульман Структуры данных и алгоритмы. М., Изд-во "Вильямс", 2000 г.
2. Н. Вирт Алгоритмы + структуры данных = программы. М., "Мир", 1985 г.
3. Н. Вирт Алгоритмы и структуры данных. М., Издат-во "Вильямс", 1998 г.
4. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., переиздание - М.,Изд-во "Вильямс", 2000 г.
5. Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. М., "Мир", 1978 г., переиздание - М.,Изд-во "Вильямс", 2000 г.
6. Уильям Топп, Уильям Форд. Структуры данных в С++. М., Изд-во "Бином", 2000 г.
7. Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М: Мир, 1986 –218с.
8. Лэгсам Й, Огенстайн М. Структуры данных для персональных ЭВМ – М: Мир, 1989 –586с.
9. Турбо Паскаль 7.0 – Киев: BHV, 1998 – 448c.
10. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах: Учебное пособие для вузов. - М.: Высшая школа, 1987.
11. Разумов О.С. Организация данных в вычислительных системах. - М.: Статистика, 1978.
12. Берзтисс А.Т. Структуры данных.: Пер. с англ. - М.: Статистика, 1974.
13. Трамбле Ж., Соренсон П. Введение в структуры данных.: Пер. с англ. Введение в структуры данных. М.: Машиностроение, 1982.
14. Кондратьева С.Д. Введение в структуры данных: лекции и упражнения по курсу – М.: Изд-во МГТУ им. Н.Э. Баумана, 2000.
