Elettracompany.com

Компьютерный справочник
9 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Основные структуры данных программирование

Структуры данных

Структуры данных

В 1976 году швейцарец Никлаус Вирт опубликовал книгу «Алгоритмы и структуры данных». Несмотря на то, что после публикации этой книги уже прошло более 40 лет, работа Вирта «Алгоритмы и структуры данных» до сих чрезвычайно актуальна. Это обусловлено тем, что любой разработчик ПО должен прекрасно теоретические основы структур данных. Косвенно это подтверждается тем, что практически на любом ИТ-собеседовании возникает вопрос на данную тематику.

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

Структура базы данных представляет собой контейнер для хранения информация в заданной форме. Такая «компоновка» позволяет этой информации быть эффективной при выполнении одних операций и абсолютно бесполезной для решения других заданий. Главной задачей разработчика считается выбор наилучшего варианта структуры данных для решения определенной задачи.

Назначение структур данных

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

Самые востребованные структуры данных

Перед тем, как перейти к изучению всех известных структур хранения данных, вспомним их полный перечень:

  • стек;
  • массив;
  • очередь;
  • связный список;
  • дерево;
  • граф;
  • префиксное дерево;
  • хеш-таблица.

Массивы

Массивы считаются самой простой и востребованной структурой. Ниже приведен пример одномерного массива, состоящего из четырех элементов (1, 2, 3, 4).

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

Выше указан одномерный массив, но также существует его многомерный аналог. Простыми словами его можно назвать массивы массивов.

Разработчики имеют возможность осуществлять с массивами самые разные операции, но все-таки чаще всего эта структура данных предусматривает выполнение:

  • вставки;
  • извлечения нужного элемента по индексу;
  • удаления;
  • определения количества элементов в массиве.

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

  • Как найти минимальный элемент?
  • Как объединить 2 отсортированных массива?
  • Как поменять местами положительные и отрицательные значения?

Стеки

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

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

Для понимания работы стека стоит привести самый тривиальный пример. Предположим, на столе одна на одной лежит куча тетрадок. Чтобы взять тетрадку из середины, необходимо удалить тетрадки, которые лежат сверху. Таким образом работаем принцип «последним пришел – первым ушел. В среде разработчиков этот принцип называется LIFO (Last In First Out).

Ниже приведен пример стека.

Элемент со значением «3» находится в самом верху. Следовательно, он будет удален первым.

Если говорить об операциях со стеками, то прежде всего нужно отметить:

  • вставку элемента в топ;
  • извлечение и последующее удаление верхнего элемента;
  • проверку на пустоту стека;
  • извлечение первого элемента.

На ИТ-собеседованиях программисту стоит быть готовым к таким вопросам:

  • Как отсортировать стек?
  • Как проверить соответствие скобок в выражении?

Очереди

Очередь – линейная структура данных, хранящая элементы в определенной последовательности. В очереди используется принцип «первым пришел – первым ушел» (FIFO).

Принцип очереди в программировании ничем не отличается от аналога в обычной жизни. Рассмотрим, обычный пример – очередь в продуктовый магазин. Человек, который пришел первым, получит необходимый товар также первым. Тот, кто пришел последним, встанет в конец очереди.

Ниже приведен пример очереди, состоящей из 4 элементов.

В этом примере элемент со значением «1» находится в начале очереди. Следовательно, именно этот элемент первым выйдет из очереди.

К основным действиям с queue стоит отнести:

  • вставку в конец;
  • удаление первого элемента;
  • проверку на пустоту очереди;
  • извлечение первого элемента.

На собеседовании разработчика могут попросить:

  • создать стек посредством очереди;
  • сгенерировать двоичные числа посредством очереди.

Связный список

Создание структуры базы данных также предусматривает использование связных списков. Эта структура очень схожа с массивом. Но все-таки она отличается:

  • организацией;
  • принципом распределения памяти;
  • принцип выполнения операций Insert и Delete.

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

Главной задачей связных списков является систем хранения файлов. Ниже приведен пример этой структуры:

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

  • вставка в начало или конец;
  • удаление первого или выбранного элемента;
  • поиск определенного элемента;
  • проверка на пустоту списка.

Во время собеседования разработчика могут попросить выполнить такие задания:

  • удалить дубликаты
  • развернуть список
  • получить заданный узел с конца списка.

Графы

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

Графы делятся на два типа – ориентированные и неориентированные. В программировании эта структура данных представлена в виде матрицы или списка смежности. Обход графов может осуществляться как в ширину, так и в длину.

Что касается наиболее популярных вопросов на собеседованиях, то разработчикам могут попросить выполнить такие задания:

  • реализация поиска;
  • определение количества ребер;
  • проверка на то является ли граф деревом.

Дерево

Если говорить о структуре данных дерево, то она состоит из множества вершин и ребер, соединяющих их. Основным отличием деревьев от графом является тот факт, что их невозможно зациклить.

Именно эта структура используется для создания интеллектуальных машин.

Ниже приведен пример простого дерева:

Стоит добавить, что в программирование существует несколько видов деревьев:

  • N-арное;
  • сбалансированное;
  • бинарное;
  • AVL;
  • красно-черное;
  • 2-3;
  • бинарное дерево поиска.

К наиболее часто задаваемым вопросам по деревьям стоит отнести:

  • определение высоты дерева;
  • поиск максимального значения;
  • поиск предков определенного узла.

Префиксное дерево

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

Ниже приведен пример префиксного дерева.

Объекты поиска указываются сверху вниз. Зеленым цветом выделены элементы, которые показывают конец каждого объекта поиска.

На ИТ-собеседованиях разработчику могут задать такие задания, связанные с префиксными деревьями:

  • создание словаря Т9;
  • определение общего количества элементов;
  • сортировка массива.

Хэш-таблица

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

Производительность хэш-таблиц зависит от следующих нюансов:

  • хеширования;
  • размера;
  • способа обработки коллекций.

Ниже приведен пример, в котором хэш отображается в массиве:

На ИТ-собеседовании разработчику могут быть заданы такие задания:

  • поиск симметричных пар;
  • определение того является ли определенный массив подмножеством другого;
  • проверка массивов на пересекаемость.

Резюмируя, стоит сказать, что вышеописанные 8 структур данных должен знать любой разработчик, желающий успешно пройти IT-собеседование.

Структуры данных: общее понятие, реализация. Простейшие структуры данных: очередь, стек. Использование стека и обратная польская запись

Структуры данных

«Алгоритмы + структуры данных = программы». Это — название книги Никлауса Вирта, знаменитого швейцарского специалиста по программированию, автора языков Паскаль , Модула-2, Оберон. С именем Вирта связано развитие структурного подхода к программированию. Н.Вирт известен также как блестящий педагог и автор классических учебников.

Читать еще:  Обучение программированию ижевск

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

Общее понятие структуры данных

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

Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс , сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java .

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

  1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;
  2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных

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

Основные структуры данных

Структура данных (англ. data structure) — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс.

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений:

  • Абстрактный тип данных;
  • Реализация какого-либо абстрактного типа данных;
  • Экземпляр типа данных, например, конкретный список;
  • В контексте функционального программирования — уникальная единица (англ. unique identity), сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров.

Абстра́ктный тип да́нных (АТД)

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

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

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

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

Ассоциативный массив

Абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу.

Стек (LIFO)

Абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

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

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

Для отслеживания точек возврата из подпрограмм используется стек вызовов. Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений.

Очередь (FIFO)

Абстрактный тип данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется. Очередь может иметь векторную или списковую структуру хранения, но при векторной структуре хранения может произойти переполнение очереди.

Двусвязная очередь

Двусвязная очередь (жарг. дэк, дек от англ. deque — double ended queue; двухсторонняя очередь, двусвязный список, очередь с двумя концами) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

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

Граф называется: * связным, если для любых вершин u,v есть путь из u в v. * деревом, если он связный и не содержит простых циклов. * полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром. * двудольным, если его вершины можно разбить на два непересекающихся подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с вершиной из V2. * планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.

Читать еще:  Программирование на с с нуля

Свя́зный спи́сок

Базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Линейный однонаправленный список

Cтруктура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

Двусвязный список (двунаправленный связный список)

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

Кольцевой связный список

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

Дерево

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

Любой узел дерева с потомками на всех уровнях так же образует дерево, называемое поддеревом.

M-арное дерево

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

Если в дереве на каждом уровне задан порядок следования вершин, то такое дерево называется упорядоченным

Бинарное дерево поиска

Это двоичное дерево, для которого выполняются следующие условия:

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

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

АВЛ-Дерево

Сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

Красно-чёрное дерево

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

  • Узел либо красный, либо чёрный.
  • Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
  • Все листья(NIL) — чёрные.
  • Оба потомка каждого красного узла — чёрные.
  • Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число чёрных узлов.

B-дерево

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

m – порядок В-дерева – это максимальное число потомков для любого узла. Кроме узлов в дереве присутствует ещё одна сущность – ключи. Именно в них и содержится вся полезная информация. Каждый узел дерева можно представить в виде упорядоченной последовательности ”потомок1; ключ1; потомок2; ключ2; … потомок(N-1); ключ(N-1); потомокN”. Важно заметить, что ключи располагаются между ссылками на потомков и, таким образом, ключей всегда на 1 меньше. В организации В-дерева можно выделить несколько ключевых правил:

  • Каждый узел содержит строго меньше m (порядок дерева) потомков.
  • Каждый узел содержит не менее m/2 потомков.
  • Корень может содержать меньше m/2 потомков.
  • У корневого узла есть хотя бы 2 потомка, если он не является листом.
  • Все листья находятся на одном уровне и содержат только данные (ключи).

Читайте также

Как известно, родных типов данных в php немного. На самом деле в программировании, типов данных конечно же неограниченное множество, особенно…

Редко когда приходится делать перечисление всех таблиц, колонок, прав — при разработке это всё делает клиентская программа. Но когда разработка…

Я в своей жизни ещё ни разу не встречал проекта, где бы всё было сделано по правилам проектирования архитектуры, с…

Основные структуры данных программирование

1. Какие бывают данные и их структуры?

2. Как задаются структуры данных?

… Лучше, чтобы в 100 функциях

использовалась одна структура данных,

чем в 10 функциях — 10 структур

А. Дж. Перлис

Всякая программа, предназначенная для реализации на ЭВМ, представляет собой формальное описание алгоритма решения той или иной задачи. Действия, выполняемые программой в соответствии с этим алгоритмом, направлены на преобразование некоторых объектов, определяющих текущее состояние процесса решения задачи. Такие внутренние объекты программы мы и называем данными. Основная цель любой программы состоит в обработке данных. Данные различных типов хранятся в памяти компьютера и обрабатываются по-разному. Согласно концепции типов данных, каждый тип данных однозначно определяет: множество значений, которые может принимать переменная заданного типа; операции и функции, которые можно применять к этой переменной; внутреннее представление переменной в памяти компьютера. Напомним, что память выделяется не для типа данных, а для размещения переменных или констант определенных типов.

Будем исходить из того представления, что структура данных – программная единица, позволяющая хранить и обрабатывать множество однотипных или логически связанных данных в вычислительной технике (https://ru.wikipedia.org/wiki/Структура_данных). Она формируется с помощью типов данных, ссылок и операций над ними в выбранном языке программирования.

3.1 Классификация структур данных

В языке Си различают следующие категории типов данных : базовые (или простые, основные, стандартные) типы данных и производные (или сложные, составные) типы данных. Основные типы данных представлены на рис. 3.1.

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

Рисунок 3.1 — Основные типы данных, применяемые в программировании

Указание типа данных четко определяет:

  • размер памяти, отведенной под данную структуру и способ ее размещения в памяти;
  • значения, допустимые для данного типа данных;
  • операции, которые возможно над этими данными выполнять.
Читать еще:  Язык программирования html

В си несколько основных базовых типов. Разделим их на две группы — целые и числа с плавающей точкой.

  • char — размер 1 байт. Всегда! Это нужно запомнить.
  • short — размер 2 байта
  • int — размер 4 байта
  • long — размер 4 байта
  • long long — размер 8 байт.

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


Список.


Двунаправленный список.

Рисунок 3.4 – Структуры данных «Однонаправленный и двунаправленный список»

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

Рисунок 3.5 – Структура данных «Связанный список»

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

struct spis *next; >; // Указатель на структуру

Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.

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

3.2.3 Стек

Стек – это динамическая линейная структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in first out, «последним пришёл — первым вышел»).

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

Пример задания стека :

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

Рисунок 3.6 – Структура данных «стек»

Рисунок 3.7 — Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

3.2.4 Очередь

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

Рисунок 3.8 – Структура данных «Очередь»

Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от «store»— «сохранять», «retrieve» — «получать»). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение.

3.2.5 Дек

Дек – структура данных одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов структур данных.

Рисунок 3.9 – Структура данных «дек»

3.2.6 Хэш-таблица

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

Рисунок 3.10 – Структура данных «хэш – таблица»

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

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

Рисунок 3.11 — Телефонная книга на примере хэш-таблицы

3.2.7 Иерархические структуры данных

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

Деревья

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

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

Пример представления дерева:

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


Рисунок 3.12 – Структура данных «дерево»

Иерархический список

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


Рисунок 3.13 – Структура данных «Иерархический список»

Примеры применения структур данных

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

Пример 3.2. Пример создания и просмотра односвязного списка (http://c.guti.ru/dstruktury.asp ).

Пример 3.3. Пример реализации структуры данных «стек».

голоса
Рейтинг статьи
Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector