logo

25. Основные алгоритмы и структуры данных, применяемые в вычислительных системах.

Классификация логических структур данных.

-Отсутствие или наличие явно заданных связей между элементами структуры:

1)Несвязные структуры данных - в них отсутствуют явно заданные связи;

2)Связные структуры. Элементы структуры явно связаны с другими элементами структуры.

Вектор, массив, строка, стек, дек, очередь, множество, запись, таблица и последовательные связные и несвязные списки, древовидная структура, графическая структура общего вида.

-Характер упорядоченности элементы структуры данных:

1)Линейные. У которых все элементы структуры расположены на одном уровне;

2)Нелинейные элементы структуры расположены на разных уровнях;

Линейные

-Характер взаимного расположения элементов:

1)Последовательные

Вектор, строка, массив, стек, дек, очередь, последовательность;

2)Произвольное связное расположение элементов

Односвязный простой список, двусвязный простой список, ....кольцевой.

Нелинейные

Многосвязные списки, древовидные структуры, графовые структуры общего вида, записи общего вида, таблицы общего вида.

-Изменчивость структуры данных:

Изменение числа элементов или связей между элементами структуры данных

1)Статические

Вектор, массив, запись, таблица;

2)Полустатические

Стек, дек, очередь, последовательность, множество;

3)Динамические

Все списковые структуры, древовидные структуры, графовые структуры, динамический вектор, динамическая матрица ;

Статические структуры данных. Свойство статических структур данных.

Вектор - одномерный массив.

Элементы вектора находятся друг с другом в возможном отношении, а именно отношении непосредственного следования. И строгая упорядоченность элементов вектора позволяет пронумеровать их последовательными целыми индексами элементов логической структуры вектора определенным числом элементов вектора. При описании вектора ему присваивается имя, указывается минимальный и максимальный знак индекса и тип его элементов.

Массив – это вектор , каждый элемент которого тоже вектор.

n-мерный массив – это конечное упорядоченное множество n-1 мерных массивов, элементы которых одного типа. Логическая структура массива описывается подобно логической структуре вектора: имя, тип элементов, для каждого измерения минимальное и максимальное значение индекса.

Два частных случая двумерных массивов:

1)Симметрическая квадратная матрица.

Элементы расположены симметрично относительно главной диагонали, попарно равны друг другу. Может хранить только часть элементов матрицы. Физическая структура будет хранить меньшее количество элементов. Доступ к треугольному массиву организовывается таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и элементов, значение которых не представляется в памяти но может быть определено на основе элементов представленных симметрично относительно диагонали.

2)Разреженный массив.

Большинство элементов равны 0. В памяти хранятся меньше элементов массива.

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

Обобщенным видом записи является такая запись, в которой каждый ее элемент может быть записью более низкого уровня. Причем, элемент записи более низкого уровня также может быть записью более низкого уровня.

Такая иерархическая структура записи может содержать произвольное число уровней и поэтому ее можно назвать многоуровневой записью. При описании много уровневой записи принято выделять уровни ее элементов, причем, предполагается что наименьший принадлежит к 1 уровню. Не зависимо от числа элементов уровней в структуре записи полезная информация содержится среди элементов соответствующих самому нижнему уровню. Остальные элементы записи, а также имя записи используются для доступа полезной информации записи. Элементы записи с полезной информацией называется содержательными элементами.

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

Все рассмотренные структуры характеризуются следующими свойствами:

1)Постоянство структуры в течение всего времени ее существования.

2) смежность элементов.

3)Простота и постоянство отношений между элементами структуры.

Понятия список, линейный список, последовательный список, связный список. Общие операции над всеми ЛСД.

Списком называется линейно упорядоченная последовательность элементов данных а1...аn при n>0.

Каждый элемент последовательности характеризуется набором одних и тех же полей и определенный таким образом список также носит название линейного списка.

Упорядоченность элементов списка также может задаваться неявно путем последовательного расположения элементов. Такой список называется последовательным списком. Упорядоченность элементов может также задаваться с помощью указателей располагаемых вместе с элементами данных и дающих возможность для каждого элемента структуры определить его предшественника или последователя. Такие списки называются связными списками.

Общие операции над всеми ЛСД.

Над всеми структурами данных могут выполняться пять операций: создание, уничтожение, выбор (доступ), обновление, копирование.

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

Операция уничтожения структур данных противоположна по своему действию операции создания. Не все языки дают возможность программисту уничтожать созданные структуры данных. Операция уничтожения Операция выбора используется программистами для доступа к данным внутри самой структуры. Форма операции доступа зависит от типа структуры данных, к которой осуществляется обращение. При выполнении операций выбора используются указатели. В широком смысле слова указатель — это переменная, определяющая место конкретной информации в структуре данных, например, переменная, содержащая значение индекса статического массива. В узком смысле слова указатель указывает на физический адрес чего-то. В последнем случае указатель — это переменная, которая является носителем адреса другой простой или структурированной переменной, а также процедуры. Идея, лежащая в основе концепции указателей, состоит в том, чтобы для достижения контроля правильности использования указателей связать определенный тип данных с конкретным указателем.

Операция обновления позволяет изменить значения данных в структуре данных. Примером операции обновления является операция присваивания или более сложная форма — передача параметров.

Операция копирования создает копию данных в новом месте памяти.

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

помогает эффективно использовать оперативную память.

Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

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

Выделим типовые операции над стеком и его элементами:

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).

Очередь разумнее всего моделировать, отобразив её на двунаправленный кольцевой список. В этом случае в заглавном звене будет присутствовать информация как об указателе на голову, так и на хвост очереди.

Выделим типовые операции над очередями:

В такой очереди массив, в котором храняться элементы очереди, используется как кольцевой список, а не как линейный.

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Операции над деком:

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

Структура данных динамический вектор. Операции над структурой данных динамический вектор.

Динамическим называется вектор, размер которого может меняться во время исполнения программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические векторы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер вектора в соответствии с реально необходимыми объёмами. В отличие от динамических векторов существуют статические векторы. Размер статического вектора определяется на момент компиляции программы. Отличием динамического вектора является автоматическое изменение размеров.