Содержание
- 2. Часть 8: Структуры данных 8.1. Массивы. 8.2. Списки. 8.3. Стеки. 8.4. Очереди. 8.5. Древовидные структуры. 8.6.
- 3. Основные структуры данных Однородный массив Неоднородный массив Список Стек Очередь Дерево
- 4. Рисунок 8.1 Список, стеки, и очередь
- 5. Терминология списков Список: Набор данных, элементы которого расположены последовательно Головной: Начало списка Хвостовой: Конец списка
- 6. Терминология стеков Стек: список, в котором элементы удаляются и вставляются только на одном конце структуры LIFO:
- 7. Терминология очереди Очередь: список, в котором включение элементов выполняется на одном конце, а извлечение - на
- 8. Рисунок 8.2 Пример организационной структуры
- 9. Терминология для структуры «дерево» Дерево: Набор данных, элементы которого имеют иерархическую организацию Вершина: Элемент дерева Корневая
- 10. Терминология для структуры «дерево» (продолжение) Родительские вершины: Непосредственные предки некоторых вершин Дочерние вершины: Непосредственные потомки некоторых
- 11. Терминология для структуры «дерево» (продолжение) Бинарное дерево: дерево, в котором каждая вершина имеет не более двух
- 12. Рисунок 8.3 Структура «дерево»
- 13. Дополнительные понятия Статические структуры данных: Размеры и формы структур данных, не изменяются Динамические структуры данных: Размеры
- 14. Рисунок 8.4 Романы расположены по названию, но связаны по авторству
- 15. Хранение массивов Однородные массивы Развёртка по столбцам против Развёртки по строкам Адресный полином Неоднородные массивы Компоненты
- 16. Рисунок 8.5 Массив Readings, хранящийся в памяти, начиная с ячейки памяти с адресом х
- 17. Рисунок 8.6 двухмерный массив с четырьмя строками и пятью столбцами, записанный в памяти с развёрткой по
- 18. Рисунок 8.7 Хранение неоднородного массива «Служащий»
- 19. Хранение списков Непрерывный список: Список хранится в однородном массиве Связанный список: Список, в котором каждая запись
- 20. Рисунок 8.8 Список имён, сохраняемый в памяти в виде непрерывного списка
- 21. Рисунок 8.9 Структура связанного списка
- 22. Рисунок 8.10 Удаление элемента из связанного списка
- 23. Рисунок 8.11 Включение элемента в связанный список
- 24. Хранение стеков и очередей Стеки обычно хранятся как смежные списки Очереди обычно хранятся как циклические очереди
- 25. Рисунок 8.12 Организация стека в памяти компьютера
- 26. Рисунок 8.13 Реализация очереди с использованием указателей её начала и конца
- 27. Хранение бинарных деревьев Связанная структура любой узел = данные ячейки + две дочерние вершины Доступ через
- 28. Рисунок 8.14 Циклическая очередь, содержащая буквы F до O
- 29. Рисунок 8.15 Представление вершины бинарного дерева в памяти машины
- 30. Рисунок 8.16 Концептуальная и реальная организации бинарного дерева с использованием связанной системы хранения
- 31. Рисунок 8.17 Древовидная структура, сохранённая в памяти без использования указателей
- 32. Рисунок 8.18 Пример неполного и несбалансированного дерева в концептуальной форме и схема его размещения в памяти
- 33. Управление структурами данных В идеале, структуры данных следует использовать исключительно в предопределенных процедурах. Пример: Типичный стек
- 34. Рисунок 8.19 процедура распечатки связанного списка
- 35. Исследование на конкретном примере Проблема: Построить абстрактный инструмент, состоящий из списка имен в алфавитном порядке вместе
- 36. Рисунок 8.20 Латинские буквы от A до M, организованные в виде упорядоченного дерева
- 37. Рисунок 8.21 Процедура двоичного поиска в связанном бинарном дереве
- 38. Рисунок 8.22 Поиск наикратчайшего пути к J
- 39. Рисунок 8.23 Печать связанного бинарного дерева в алфавитном порядке
- 40. Рисунок 8.24 Процедура печати связанного бинарного дерева в алфавитном порядке
- 41. Рисунок 8.25 Включение элемента M в список B,E,G,Y,J,K,N,P, хранящийся в виде бинарного дерева
- 42. Рисунок 8.26 Процедура включения элемента в связанное упорядоченное бинарное дерево
- 43. Типы данных определяемы пользователем Шаблон для неоднородной структуры Пример: определить тип EmployeeType {char Name[25]; int Age;
- 44. Абстрактные типы данных Типы данных определяемы пользователем с процедурами доступа и обработки Пример: Определить тип StackType
- 45. Классы Абстрактный тип данных с дополнительными функциями Характеристики могут быть унаследованы содержимое может быть инкапсулировано конструктор
- 46. Рисунок 8.27 Стек целых чисел, реализованных в Java и C #
- 47. Указатели в машинном языке Непосредственная адресация: Инструкция содержит доступ к данным Прямая адресация: Инструкция содержит адрес
- 48. Рисунок 8.28 Наша первая попытка на расширение машинного языка в Приложении C, чтобы воспользоваться указателями
- 50. Скачать презентацию