Вопросы программной реализации важнейших структур данных, таких как стеки, очереди, списки, деревья и их комбинации. Статические и динамические способы их создания. Алгоритмы сортировки данных. Методы обработки массивов. Примеры фрагментов программ.
Татарский институт содействия бизнесу Рекомендовано к печати научно-методическим советом ТИСБИ4.2 Комбинированные структуры данных: массивы и списки указателейОсновные понятия о древовидных структурах6.2 Добавление вершины в дерево поискаДополнительные вопросы обработки деревьев. 7.1 Проблемы использования деревьев поискаПростейшие методы сортировки 1.3 Простейшие методы сортировки: метод обменаУлучшенные методы сортировки массивовСпециальные методы сортировкиПоиск с использованием хеш-функцийВнешний поиск и внешняя сортировка 5.2 Организация внешнего поиска с помощью Б-деревьевОтнесение переменных к тому или иному типу позволяет установить внутренний формат хранения значений этой переменной и набор допустимых операций. Все распространенные языки программирования имеют набор базовых простейших типов данных (целочисленные, вещественные, символьные, логические) и возможность объединения их в составные наборы - массивы, записи, файлы. Понятие структуры данных определяется двумя моментами: · способом объединения отдельных компонент в единую структуру Например, классическая структура МАССИВ есть объединение однотипных компонент, причем каждая компонента имеет фиксированный порядковый номер-индекс размещения в массиве. Аналогично, структура ЗАПИСЬ является объединением разнотипных компонент-полей, доступ к которым выполняется по имени поля.Недостатком такого способа распределения памяти является его жесткость - для изменения объема памяти, выделенной под какую-либо переменную необходимо перекомпилировать программу. Механизм динамического распределения памяти основан на использовании специальных переменных, которые называют указателями. · связать эту переменную с адресуемыми данными, указав их тип или имя с помощью специального символа ^: var указатель: ^ базовый тип; Например, указатели на простейшие базовые типы вводятся следующим образом: PINT: ^integer; {указатель на отдельное целое число} Можно ввести указатели на структурные типы (массивы, записи), используя для этого предварительно объявленные типы: type TMYARRAY = array [1..100]of integer;Для этого можно использовать специальный оператор взятия адреса @: var x: real; {обычная переменная вещественного типа} PREAL: ^real; {указатель на вещественный тип} begin x:= 1.5; {обычная переменная x получает значение 1.5} PREAL:= @x; {указатель получает адрес размещения числа 1.5} Принципиальное отличие данного способа использования указателя от ранее рассмотренного состоит в том, что здесь НЕ используется механизм динамического распределения памяти, т.е. В качестве примера рассмотрим массив указателей на записи некоторой структуры. type TREC = record {описание базового типа-записи} x, y: integer;Как вводится переменная-указатель на текстовые строки (2 способа)? Как вводится переменная-указатель на массив? Как вводится переменная-указатель на структуру-запись? Если p - переменная-указатель на запись, то как можно определить некоторое поле этой записи? Если Pointers есть массив указателей, то что определяет выражение Pointers [j]^?Пусть в стеке требуется сохранять целые числа, причем заранее известно их максимальное количество. Тогда для реализации стека надо объявить массив и одну переменную - указатель вершины стека (SP - Stack Pointer). Тогда указатель SP может определять либо последнюю занятую ячейку массива, либо первую свободную ячейку. Со стеком связываются две основные операции: добавление (вталкивание, PUSH) элемента в стек и удаление (выталкивание, POP) элемента из стека.В отличие от статической реализации на основе массива, при использовании механизма динамического выделения памяти в стек можно занести любое число элементов. Это приводит к необходимости добавления в каждый элемент стека нового связующего поля для хранения адреса соседнего элемента. В этом случае физическое размещение элементов в памяти НЕ обязано всегда соответствовать логическому порядку следования элементов. Структура оперативной памяти в этом случае может выглядеть следующим образом: Для построения логического порядка следования элементов достаточно знать вершинный элемент, все остальное восстанавливается по адресным частям элементов независимо от их реального размещения в памяти. Для простоты будем считать, что информационное поле каждого элемента содержит только одно целое число.Тогда для реализации очереди надо объявить массив и две переменные - указатель начала очереди First и указатель конца очереди Last. Тогда пустую очередь определим, как First = Last = 1 (если индексация элементов массива начинается с 1), и при каждом добавлении нового элемента переменная Last увеличивается на 1, а при удалении на 1 увеличивается указатель First.
План
Оглавление
Введение
Раздел 1. Основные структуры данных
1. Введение в структуры данных. Динамическое распределение памяти
1.1 Классификация структур данных
1.2 Переменные-указатели и динамическое распределение памяти
1.3 Дополнительные вопросы использования переменных-указателей
1.4 Контрольные вопросы по теме
2. Структуры данных "стек" и "очередь"
2.1 Что такое стек и очередь?
2.2 Статическая реализация стека
2.3 Динамическая реализация стека
2.4 Статическая реализация очереди
2.5 Динамическая реализация очереди
2.6 Практические задания
2.7 Контрольные вопросы по теме
3. Основы реализации списковых структур
3.1 Структуры данных типа "линейный список"
3.2 Первый способ статической реализации списка
3.3 Второй способ статической реализации списка
3.4 Управление памятью при статической реализации списков
3.5 Динамическая реализация линейных списков
3.6 Практические задания
3.7 Контрольные вопросы
4. Усложненные списковые структуры
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
