Что определяет структура данных

Что определяет структура данных

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

· стек как логическая структура может быть реализован на основе массива с индексом – указателем стека и односвязного списка (физическое представление);

· пирамидальная сортировка использует массив на уровне физического представления для логической структуры – дерева с двумя потомками, упорядоченного по вертикали ( 8.4);

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

Последовательность как структура данных

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

Физическое представление последовательности может быть самым разным, например, список или дерево с заданной последовательностью обхода. Рассмотрим самый простой способ представления последовательности – ее элементы занимают первые n элементов массива (без «дырок»). Для того, чтобы определить текущее количество элементов последовательности, можно поступить двумя способами :

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

// Последовательность со счетчиком

int insert(int vv, int k)<

if (n==SZ-1 || k>=n) return 0;

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

«Хороший Сагиб у Сами и умный,

Только больно дерется стеком».

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

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

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

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

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

Загадка для программистов: «Кто над нами вверх ногами». Варианты отгадок: а). муха б). стек.

· программный код вызова записывает в стек значения фактических параметров;

· команда вызова функции записывает в стек адрес возврата (текушее значение указателя текущей команды в сегменте команд CS:IP) и выполняет переход к началу тела функции;

· программный код тела функции резервирует в стеке место для локальных переменных;

· перед возвратом из функции из стека удаляются локальные переменные, затем из него же извлекается адрес возврата и по нему производится переход;

· после возврата программным кодом вызова из стека удаляются фактические параметры.

Очередь

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

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

// Очередь в массиве (от начала, со сдвигом)

рис. 61.4. Циклическая очередь в массиве

Источник

Что определяет структура данных

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

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

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

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, т.е. константы, переменные, значения функций или выражения, характеризуются своими типами.

Информация по каждому типу однозначно определяет :

Простые структуры данных.

Простые структуры данных называют также примитивными или базовыми структурами. Эти структуры служат основой для построения более сложных структур. В языках программирования простые структуры описываются простыми (базовыми) типами. К таким типам относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. В дальнейшем изложении мы ориентируемся в основном на язык PASCAL и его реализации в среде MS DOS. Структура простых типов PASCAL приведена на рис 1.2 (через запятую указан размер памяти в байтах, требуемый для размещения данных соответствующего типа). В других языках программирования набор простых типов может несколько отличаться от указанного. Размер же памяти, необходимый для данных того или иного типа, может быть разным не только в разных языках программирования, но и в разных реализациях одного и того же языка.

Рис. 1.2. Структура простых типов PASCAL.

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

Каждую структуру данных характеризуют её логическим и физическим представлениями. Очень часто говоря о той или иной структуре данных, имеют в виду её логическое представление. Физическое представление обычно не соответствует логическому, и кроме того, может существенно различаться в разных программных системах. Нередко физической структуре ставится в соответствие дескриптор, или заголовок, который содержит общие сведения о физической структуре. Дескриптор необходим, например, в том случае, когда граничные значения индексов элементов массива неизвестны на этапе компиляции, и, следовательно, выделение памяти для массива может быть выполнено только на этапе выполнения программы (как в языке PL/1, ALGOL-60). Дескриптор хранится как и сама физическая структура, в памяти и состоит из полей, характер, число и размеры которых зависят от той структуры, которую он описывает и от приня- тых способов ее обработки. В ряде случаев дескриптор является совершенно необходимым, так как выполнение операции доступа к структуре требует обязательного знания каких-то ее параметров, и эти параметры хранятся в дескрипторе. Другие хранимые в дескрипторе параметры не являются совершенно необходимыми, но их использование позволяет сократить время доступа или обеспечить контроль правильности доступа к структуре. Дескриптор структуры данных, поддерживаемый языками программирования, является «невидимым» для программиста; он создается компилятором и компилятор же, формируя объектные коды для доступа к структуре, включает в эти коды команды, обращающиеся к дескриптору.

Полустатические структуры данных.

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

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

Динамические структуры данных.

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

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

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

Массив как базовая структура.

Реализация одних структур на базе других.

Простейшие структуры данных. Стек. Очередь.

Наиболее важными из простейших структур данных являются стек и очередь. Эти структуры встречаются в программировании буквально на каждом шагу, в самых разнообразных ситуациях. Особенно интересен стек, который имеет самые неожиданные применения. В свое время при разработке серии ЭВМ IBM 360 в начале 70-х годов XX века фирма IBM совершила драматическую ошибку, не предусмотрев аппаратную реализацию стека. Эта серия содержала много других неудачных решений, но, к сожалению, была скопирована в Советском Союзе под названием ЕС ЭВМ (Единая Серия), а все собственные разработки были приостановлены. Это отбросило советскую промышленность на много лет назад в области разработки копьютеров.

Реализация очереди на базе массива.

Использование стека в программировании.

Реализация стека на базе массива.

Источник

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета

Поиск

Введите ваш запрос для начала поиска.

Об авторах

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

Основные цели сайта

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

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

Графическое представление элемента структуры данных.

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

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

Последовательность переходов от логической организации к физической показана на рисунке ниже

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

Структуры данных классифицируются:

1. По связанности данных в структуре:

— если данные в структуре связаны очень слабо, то такие структуры называются несвязанными (вектор, массив, строки, стеки)

— если данные в структуре связаны, то такие структуры называются связанными (связанные списки)

2. По изменчивости структуры во времени или в процессе выполнения программы:

— полустатические структуры (стеки, деки, очереди)

3. По упорядоченности структуры:

— линейные (вектора, массивы, стеки, деки, записи)

— нелинейные (многосвязные списки, древовидные структуры, графы)

Наиболее важной характеристикой является изменчивость структуры во времени.

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

Векторы

M1: Array [1..100] of integer;

M2: Array [1..10] of real;

Вектор состоит из совершенно однотипных данных и количество их строго определено.

Массивы

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

Записи

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

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

Таблицы

При задании таблицы указывается количество содержащихся в ней записей.

Операции с таблицами:

1. Поиск записи по заданному ключу.

2. Занесение новой записи в таблицу.

Источник

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

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

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

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

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

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода.

Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++.

Фундаментальными строительными блоками для большей части структур данных являются массивы, записи ( struct в Си и record в Паскале), размеченные объединения ( union в Си) и ссылки. Например, двусвязный список может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы.

Сравнение структур данных в функциональном и императивном программировании

Проектировать структуры данных для функциональных языков более сложно, чем для императивных, как минимум по двум причинам [1] :

Источник

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

Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.

Обратите внимание, что некоторые структуры данных включают временную сложность в нотации «большого О». Это относится не ко всем из них, так как иногда временная сложность зависит от реализации. Если вы хотите узнать больше о нотации «большого О», посмотрите это видео от Briana Marie.

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

Связные списки

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

Так устроен связный список

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

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

Временная сложность связного списка

Упражнения от freeCodeCamp

Стеки

Стек — это базовая структура данных, которая позволяет добавлять или удалять элементы только в её начале. Она похожа на стопку книг: если вы хотите взглянуть на книгу в середине стека, сперва придется убрать лежащие сверху.

В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

Временная сложность стека

Упражнения от freeCodeCamp

Очереди

Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале — всё как в жизни.

Так устроена очередь

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

Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue) и удалять первый элемент (dequeue).

Временная сложность очереди

Упражнения от freeCodeCamp

Множества

Так выглядит множество

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

Упражнения от freeCodeCamp

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

Так устроена структура map

Упражнения от freeCodeCamp

Хэш-таблицы

Так работают хэш-таблица и хэш-функция

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

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

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

Временная сложность хэш-таблицы

Упражнения от freeCodeCamp

Двоичное дерево поиска

Двоичное дерево поиска

Дерево — это структура данных, состоящая из узлов. Ей присущи следующие свойства:

У двоичного дерева поиска есть два дополнительных свойства:

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

Временная сложность двоичного дерева поиска

Упражнения от freeCodeCamp

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

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

Так устроено префиксное дерево

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

Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

Упражнения от freeCodeCamp

Двоичная куча

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

Так устроены минимальная и максимальная кучи

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

Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.

Временная сложность двоичной кучи

Упражнения от freeCodeCamp

Графы — это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

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

Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

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

Граф в виде матрицы смежности

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

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

Существуют специальные алгоритмы для просмотра рёбер и вершин в графах — так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search) и в глубину (depth-first search). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.

Временная сложность списка смежности (графа)

Упражнения от freeCodeCamp

Узнать больше

Если до этого вы никогда не сталкивались с алгоритмами или структурами данных, и у вас нет какой-либо подготовки в области ИТ, лучше всего подойдет книга Grokking Algorithms. В ней материал подан доступно и с забавными иллюстрациями (их автор — ведущий разработчик в Etsy), в том числе и по некоторым структурам данных, которые мы рассмотрели в этой статье.

Мнение автора и редакции может не совпадать. Хотите написать колонку для «Нетологии»? Читайте наши условия публикации.

Источник