Что такое структура в программировании
Перейти к содержимому

Что такое структура в программировании

  • автор:

Учебники. Программирование для начинающих.

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

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

Assembler

Глава 2. Основы программирования

Структуры и записи

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

meddata struc ;Структура с именем meddata

index dd 0 ; Номер карты

sex db 0 ;Пол

birth dw 0 ;Год рождения

datein db ‘ / / ‘ ;Дата поступления

dateout db ‘ / / ‘ ;Дата выписки

meddata ends ;Конец описания структуры

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

data segment

pat 1 meddata

pat2 meddata

pat3 meddata

pattemp meddata <>

data ends

Имена patl, pat2 и т.д. будут служить именами переменных, каждая из которых содержит полный комплект данных об одном пациенте. Угловые скобки ограничивают конкретные данные, поступающие в каждую структурную переменную. Для переменной с именем pattemp транслятор выделит в памяти 23 байт, поместив в нее в точности то, что было указано в описании структуры (нули и два символьные шаблона для даты):

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

mov EAX,patl.index ;ЕАХ=1234567

mov SI,offset patl.datein ;31=смещение элемента patl.datein

mov DL,pat3.sex ;DL=’ж’

Особенности использования в приложениях DOS 32-разрядных регистров (ЕАХ в первой строке приведенного фрагмента) будут описаны в гл. 4.
Адрес конкретной структурной переменной можно поместить в базовый или индексный регистр, и пользоваться им в конструкциях с косвенной адресацией:

mov BX,offset pat3 ;ВХ=смещение pat3

mov EAX,[BX].index ;EAX=4389012

mov [BX].sех=’м’ ;Программная инициализация

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

mov BX, off set pat2 ;ВХ=смещение pat2

add BX,sex ;ВХ=смещение pat2.sex

mov DL, [BX] ;DL=’M’

mov SI,birth ;SI=5 (сомнительная команда)

Записи, как и структуры, представляют собой шаблоны, накладываемые на реальные данные с целью введения удобных мнемонических обозначений отдельных элементов данных. В отличие от структур, дающих имена байтам, словам, двойным словам или целым массивам, в записях определяются строки битов внутри байтов, слов или двойных слов.
Известно, что дата создания файла хранится в каталоге диска в виде 16-битового слова, в котором старшие 7 бит обозначают год (от 1980), следующие 4 бит — месяц и последние 5 бит — день (рис. 2.14).

Рис. 2.14. Формат записи даты в каталоге диска.

Эти данные удобно специфицировать с помощью записи filedate, определяемой в программе следующим образом:

Ключевое слово record говорит о том, что имя fdate относится к записи, а мнемонические обозначения year, month и day являются произвольными именами отдельных битовых полей описываемого слона.
Включение в программу описания шаблона битовых полей позволяет отказаться от утомительного и чреватого ошибками определения «вручную» содержимого полного данного по задаваемым значениям его отдельных составляющих. Для приведенной выше записи объявления конкретных переменных будут выглядеть следующим образом:

filel fdate ;7 июня 1985г.

file2 fdate ;30 декабря 1998г.

file3 fdate <> ;»Пустая» (пока) переменная

Переменная filel будет определена, как число 0AC7h, file2 — как число 259Eh, а fileЗ — как число 0000h. При необходимости программного заполнения переменной типа fdate можно пользоваться именами ее составляющих, которые трактуются ассемблером, как индексы соответствующих битовых полей, отсчитываемые от младшего конца слова. Для приведенного примера day=0, month=5, a year=9. Однако в системе команд МП 86 практически нет средств работы с битовыми полями. Поэтому программное заполнение придется осуществлять с помощью команд сдвигов и логического сложения:

mov flle3,30 ;Помещаем день

mov AX,12 ;Месяц пока в АХ

mov CL,month ;Будем сдвигать на month бит

shl AX,CL ; Сдвинули месяц в АХ на 5 бит

or file3,AX ;Добавили биты месяца в file3

mov AX, 18 ;Год пока в АХ

mov CL,month ;Будем сдвигать на year бит

shl AX,CL ;Сдвинули год в АХ на 9 бит

or file3,AX ;Добавили биты года в file3

В итоге в переменной file3 окажется тот же код 259Eh, что и в переменной file2.

Структуры

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

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

struct addr char name[30];
char street [40]; char city[20];
char state[3];
unsigned long int zip;
>;

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

На данный момент на самом деле не создано никакой переменной. Определена только форма данных. Для объявления настоящей переменной, соответствующей данной структуре, следует написать:

struct addr addr_info;

В данной строке происходит объявление переменной addr_info типа addr. При объявлении структуры определяется переменная смешанного типа. До тех пор, пока не будет объявлена переменная данного типа, она не будет существовать.

Когда объявлена структурная переменная, компилятор автоматически выделяет необходимый участок памяти для размещения всех ее членов. Рис. показывает размещение addr_info в памяти.

Понятие структуры данных для программиста. Массивы

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

Но начать следует с описания структуры данных как таковой. Что же определяет это понятие? Если не вдаваться в сложные определения и термины, можно сказать одним простым предложением: структура данных — это не что иное, как определенный способ организации данных, обеспечивающий максимально эффективное их использование. Ничего сложного в этом описании нет и быть не может: ведь у нас всегда есть некая информация в цифровом виде, и этой информацией приходится постоянно оперировать. И чтобы использование было эффективным, нужно все это как-то организовать. Как?

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

  • доступ (получаем информацию);
  • поиск (находим информацию);
  • вставка (добавляем новое);
  • удаление (удаляем ненужное).

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

Понятие структуры данных для программиста. Массивы

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

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

Массив как структура данных

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

Представим, что у нас есть следующий массив:

Понятие структуры данных для программиста. Массивы

Что вообще с ним можно сделать? Ну, к примеру, получить нужный элемент, обратившись к индексу.

Понятие структуры данных для программиста. Массивы

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

Понятие структуры данных для программиста. Массивы

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

Понятие структуры данных для программиста. Массивы

Но вернемся к нашей сложности O(1). Разработчик, используя индекс (уникальный идентификатор), может мгновенно получить любой элемент массива, причем даже несуществующий (в таком случае будет undefined). Точно так же по индексу можно выполнять и запись.

Понятие структуры данных для программиста. Массивы

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

Понятие структуры данных для программиста. Массивы

Сложность операции будет тоже O(1).

А что насчет удаления с конца?

Понятие структуры данных для программиста. Массивы

Тут мы тоже имеем O(1). Неплохо. Давайте посмотрим, что у нас получается при добавлении и удалении с начала массива:

Понятие структуры данных для программиста. Массивы

А вот здесь несколько иная картина. И вставка, и удаление элементов с начала списка обладают линейной сложностью О(n).

Понятие структуры данных для программиста. Массивы

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

Таким образом, это уже менее эффективно. Именно потому разные реализации стеков (stack) основываются не на unshift & shift, а на push & pop. Немного отвлечемся и вспомним про такую структуру данных, как стек. Стек можно представить как стопку книг: лежащую сверху мы берем для чтения первой, а если добавляем новую книгу, то кладем ее поверх стопки, то есть теперь уже она становится первой для чтения. Такой подход называют LIFO — last in, first out. Наиболее популярными в разработке являются различные стеки операций, к примеру:

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

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

Также стоит упомянуть и прочие методы работы с массивами, имеющие сложность О(n) — это, по сути, почти все основные методы, используемые при работе с массивами — всё, что мы ищем, фильтруем, переворачиваем, перебираем и даже трансформируем в строку (toString) — всё вышеперечисленное имеет сложность O(n).

На этом все, если хотите знать большое, вам могут быть полезны следующие статьи:

Структура (программирование)

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

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

Пример объявления структуры

Си

struct str_name  int member_1; float member_2; char member_3[256]; /* . */ >; // примеры инициализации структуры. struct str_name struct0; struct str_name struct1 = 1, 3.1416, "doit" /* . */>; struct str_name struct2 = member_1:2, member_2:3.1416, member_3:"doit" /* . */>; struct str_name struct2 = .member_1=2, .member_2=3.1416, .member_3="doit" /* . */>; 

C++

struct str_name  private: int member_1; float member_2; public: std::string member_3; // . >; // примеры инициализации структуры. str_name struct0; str_name struct1 = 1, 3.1416, "doit" /* . */>; str_name struct2 = member_1:2, member_2:3.1416, member_3:"doit" /* . */>; str_name struct2 = .member_1=2, .member_2=3.1416, .member_3="doit" /* . */>; 

C#

struct str_name  private int member_1; private float member_2; public string member_3; // . >; 

Pascal

type str_name = record begin public: member_1 : integer; member_2 : extended; private: member_3 : string; end; 

Отличия от классов

Отличия классов от структур в разных языках разнится. Отличия для языка С#:

  • Размещение: в области стека (классы — управляемая куча (heap)
  • Копирование: создаётся отдельная копия объекта, которая после копирования живёт «своей жизнью» (классы — создаётся ссылка на тот же класс (т. н. instance)
  • Наследование: не разрешается дополнение своими свойствами; от него нельзя наследовать (класс — позволяет, кроме случаев когда класс создавался с ключевым словом sealed, не разрешающим наследование)
  • Передача параметров: как локальные копии переменных (в классах — как ссылки)
  • Конструктор: да, кроме конструктора по умолчанию, который не требует параметров (в классах — да, без ограничений)
  • Освобождение переменной: при выходе за пределы видимости (в классах — во время процесса сборки мусора (garbage collector)

Отличия для языка C++:

  • Члены структуры по умолчанию (без явного указания спецификатора доступа) являются публичными, а члены класса — закрытыми

Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void

Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism

  • Типы данных

Wikimedia Foundation . 2010 .

  • Струковский сад
  • Структура данных для непересекающихся множеств

Полезное

Смотреть что такое «Структура (программирование)» в других словарях:

  • Программирование — процесс составления упорядоченной последовательности действий (программы (См. Программа)) для ЭВМ; научная дисциплина, изучающая программы для ЭВМ и способы их составления, проверки и улучшения. Каждая ЭВМ является автоматом,… … Большая советская энциклопедия
  • ПРОГРАММИРОВАНИЕ ТЕОРЕТИЧЕСКОЕ — математическая дисциплина, изучающая математич. абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие определенной информационной и логич. структурой и подлежащие исполнению на автоматич. устройствах. П. т.… … Математическая энциклопедия
  • СТРУКТУРА ИССЛЕДОВАНИЯ: — деятельностная: мотивы – цели – задачи – содержание – формы – методы – критерии – результаты; управленческая: первичный анализ – прогнозирование – программирование – планирование – организация – регулирование – контроль – анализ – корригирование… … Современный образовательный процесс: основные понятия и термины
  • Класс (программирование) — У этого термина существуют и другие значения, см. Класс. Класс в программировании набор методов и функций. Другие абстрактные типы данных метаклассы, интерфейсы, структуры, перечисления характеризуются какими то своими, другими… … Википедия
  • Нейро-лингвистическое программирование — Нейролингвистическое программирование (НЛП) (англ. Neuro linguistic programming) (также встречается вариант «нейро лингвистическое программирование») комплекс моделей, техник и операционных принципов (контекстуально зависимых убеждений),… … Википедия
  • Ретроспектива в программирование — Разработка программного обеспечения Процесс разработки ПО Шаги процесса Анализ • Проектирование • Реализация • Тестирование • … Википедия
  • Структурное программирование — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей … Википедия
  • Неструктурированное программирование — Структурное программирование методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70 х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом. В … Википедия
  • Нейролингвистическое программирование: Библиография — Одна из статей на тему Нейролингвистическое программирование (НЛП) Основные статьи НЛП · Принципы · НЛП психотерапия · История Новый код · НЛП и наука · Библиография · Словарь Принципы и методы Моделирование · Метамодель · Милтон модель Позиции… … Википедия
  • Парадигма (программирование) — Парадигма программирования это совокупность идей и понятий, определяющая стиль написания программ. Парадигма, в первую очередь, определяется базовой программной единицей и самим принципом достижения модульности программы. В качестве этой единицы … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *