Часть 2: «Методы программирования»

Содержание Данные и алгоритмы. Абстрактные структуры данных и структуры хранения. Создание и обработка списков Таблицы Очереди. Стеки.

Графы Деревья. Обход дерева Обход графа. Кратчайшие пути и расстояния в графе Древовидные таблицы

Методы хранения структур данных 1. Последовательное (сплошное) представление данных. Элементы структуры располагаются в памяти друг за другом без промежутков. Наиболее используемой структурой хранения является вектор.

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

Абстрактные структуры данных Таблицы Очереди. Стеки. Графы Деревья Множества

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

Обработка списков Составные части списка ABC X... Указатель списка Пустой указатель Значение элемента Указатель следующего Элементы списка

Обработка списков Строка символов в виде списка Указатель списка Пустой указатель – конец строки СОН X

Представление списка в памяти Символ ЭлементспискаСсылка АдресЯчейкаАдресЯчейка 101O'107''H' С' Указатель списка 111

Обработка списков Включение элемента в список Пустой указатель – конец строки Указатель списка СОН X Л

Обработка списков Двунаправленный (симметричный ) список Указатель списка … Ссылка вперед Ссылка назад

Обработка списков Циклический список... Указатель списка