русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Учебно-методические материалы по дисциплине


Дата добавления: 2013-12-23; просмотров: 786; Нарушение авторских прав


Таблицы

 

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

 

Часто в качестве ключей используются целые положительные числа. Можно использовать строки. Над типом данных, используемым для представления ключа, должны быть определены операции сравнения. Если встроенных операций нет, можно разработать функции, сравнивающие ключи.

 

Операции, определенные над таблицей, как структурой данных:

- поиск записи с заданным ключом;

- включение в таблицу записи с заданным ключом (обычно считается, что если в таблице уже есть запись с таким ключом, то старые значения заменяются новыми);

- удаление записи из таблицы.

 

Существует несколько способов организации таблицы. Выбор того или иного способа определяется характером использования таблицы:

 

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.

 



<== предыдущая лекция | следующая лекция ==>
Двоичные деревья | Сортировка


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.