Презентация по основам программирования Сложные структуры данных

Сложные структуры данных

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

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

по организации взаимосвязей между элементами сложных структур данных существует следующая классификация: Линейные Массив Список Связанный список Стек Очередь Хэш-таблица Иерархические Двоичные деревья N-арные деревья Иерархический список Сетевые Простой граф Ориентированный граф Табличные Таблица реляционной базы данных Двумерный массив Другие

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

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

Достоинство этой структуры данных, помимо возможности изменять размер, - это простота реализации. Также, благодаря наличию ссылок, каждый элемент в списке, в отличие от массива, может занимать разный объем памяти. Адрес первого элемента в линейном списке однозначно определяется адресом самого списка.

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

Стек – это динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First Out) – последним пришел и первым ушел.

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

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

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

Свойства деревьев Максимальное количество потомков каждого узла и определяет размерность дерева. Отдельно выделяют двоичные или бинарные деревья, поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева.

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

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

Сетевые структуры данных Элемент в сетевой структуре данных характеризуется набором связей с другими - соседними элементами. В таких структурах данных ни начальный, ни корневой элементы явно не выделены.

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

Табличные структуры данных Элемент в табличной структуре данных характеризуется двумерным индексом: индексом строки и индексом столбца, на пересечении которых он находится.

#include <,iostream>, #include <,stdlib.h>, struct tree{ int data, tree *left, *right, }, using namespace std, void create_tree(tree **p, int n, int data) { if (n == 0) { *p = NULL, } Q6a else { tree *newP = new tree, cin >,>, newP->,data, int nl = n / 2, nr = n - nl - 1, create_tree(&newP->,left, nl, data), create_tree(&newP->,right, nr, data), *p = newP, } } int main () { int n, b, tree *root, cout<,<,VVedi razmer: , cin>,>,n, create_tree(&root, n, b), if(root==0) cout<,<,pusto, else cout<,<,b, return 0, }

Вопросы: Виды структур данных. Примеры Линейные структуры. Примеры Иерархические структуры. Примеры Сетевые структуры. Примеры Табличные структуры.