- •1.Классификация структур данных
- •2.Операции над структурами
- •3. Структурность данных и технологии программирования
- •4. Целочисленные типы
- •5. Вещественные типы
- •6. Битовые типы
- •7. Логический тип
- •10. Интервальный тип
- •11. Указатели
- •8. Символьный тип
- •9. Перечислимый тип
- •12. Массивы
- •13. Свободные массивы
- •14. Треугольные и разреженные матрицы
- •15. Множества
- •16. Записи
- •17. Абстрактный тип данных «Список»
- •18. Методы реализации списков
- •19. Двунаправленные списки
- •20. Абстрактный тип данных «Стек»
- •21. Методы реализации стеков
- •22. Применение стеков при разработке приложений
- •23. Абстрактный тип данных «Очередь»
- •24. Методы реализации очередей
- •25. Абстрактный тип данных «Дек». Методы реализации
- •26. Строки: логическая структура, операции и представление в памяти
- •27. Деревья. Их обходы
- •28. Помеченные деревья и деревья выражений
- •29. Абстрактный тип данных «Дерево»
- •30. Методы реализации деревьев
- •31. Двоичные деревья. Методы их представления
- •32. Коды Хаффмана
- •33. Абстрактный тип данных «Множество»
- •34. Абстрактный тип данных с операторами множеств
- •35. Методы реализации абстрактного типа данных «Множество»
- •36. Словари. Методы их реализации
- •37. Структуры данных основанные на хеш-таблицах
- •38. Оценка эффективности хеш-функций
- •39. Очереди с приоритетами. Методы их реализации
- •40. Реализация очереди с приоритетами частично упорядоченными деревьями
- •41. Деревья двоичного поиска. Методы их реализации
- •42. Нагруженные деревья. Методы их реализации
- •43. Реализация множеств посредством сбалансированных 2-3 деревьев
- •45. Задача наибольшей общей подпоследовательности
- •44. Множества с операторами merge и find. Методы их реализации
- •46. Сбалансированные и несбалансированные деревья поиска
- •48. Методы представления графов
- •49. Внешняя сортировка. Основные характеристики сортировок методом слияний
- •50. Алгоритм прямого слияния
- •51. Алгоритм естественного слияния
- •52. Сбалансированное многопутевое слияние
- •53. Многофазная сортировка
- •54. Хранение данных в файлах
- •55. Внешние деревья поиска
17. Абстрактный тип данных «Список»
Это набор связанных элементов данных, которые в общем случае могут быть разного типа.
Пример списка:
E1, E2, ........, En,... n > 1 и не зафиксировано.
Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:
1) Несвязные
2) Связные
В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.
Стеки, деки и очереди - это несвязные списки. Кроме того они относятся к последовательным спискам, в которых неявная связь отображается их последовательностью.
18. Методы реализации списков
Реализация списков посредством массивов
При реализации списков с помощью массивов элементы списка располагаются в смежных ячейках массива.
Легко просматривать содержимое списка и вставлять новые элементы в его конец.
Но вставка нового элемента в середину списка требует перемещения всех последующих элементов на одну позицию к концу массива, чтобы освободить место для нового элемента.
Удаление элемента также требует перемещения элементов, чтобы закрыть освободившуюся ячейку.
Реализация списков посредством указателей
Используются указатели, связывающие последовательные элементы списка. Эта реализация освобождает от использования непрерывной области памяти для хранения списка и от необходимости перемещения элементов списка при вставке или удалении элементов.
Однако ценой за это удобство становится дополнительная память для хранения указателей.
19. Двунаправленные списки
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности. Дело в том, что по однонаправленному списку можно двигаться только в одном направлении, от заглавного звена к последнему звену списка.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено списка. Динамическая структура, состоящая из элементов такого типа, называется двунаправленным или двусвязным списком.
Двусвязный список характеризуется тем, что у любого элемента есть два указателя. Один указывает на предыдущий элемент (обратный), другой указывает на следующий элемент (прямой).
20. Абстрактный тип данных «Стек»
Очередь вида LIFO, при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком.
В стеке доступна единственная его позиция, которая называется вершиной стека - это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека.
Операции, производимые над стеками:
1. Занесение элемента в стек.
2. Выборка элемента из стека.
3. Определение пустоты стека.
4. Прочтение элемента без его выборки из стека.