Массивы и структуры могут комбинироваться различными способами.
40. Работа со структурами в С++: хранение структур в файлах. Структуры и бинарные файлы.
41. Битовые поля в С++.
Специальная переменная-член класса, называемая битовым полем, предназначена для хранения определенного количества битов. Битовые поля обычно используют в случае, когда программа должна передать бинарные данные другой программе или аппаратному устройству. Битовое поле представляет собой целочисленный тип данных. Оно может быть знаковым или беззнаковым. Чтобы объявить член класса битовым полем, после его имени располагают двоеточие и константное выражение, указывающее количество битов. Битовые поля, определенные в последовательном порядке внутри тела класса, если это возможно, упаковываются внутри смежных битов того же целого числа. Таким образом достигается уплотнение хранилища.
42. Объединения в С++.
Объединение- это класс специального вида. Объединение может иметь несколько переменных-членов, однако в каждый момент времени только одна из них будут содержать значение. Когда значение присваивается одному из членов объединения, все остальные переходят в неопределенное состояние. Для объединения резервируются такой объем памяти, которого хватит, по крайней мере, для размещения его самой большой переменной-члена. Подобно любому другому классу, определение объединения создает новый тип. Объединение позволяет создать набор взаимоисключающих значений, которые могут иметь разные типы. Определения объединения начинается с ключевого слова union, за которым следует имя объединения и набор его членов, заключенный в фигурные скобки. Подобно любому классу, объем памяти, резервируемой для объекта объединения, определяет его тип. Во время компиляции размер каждого объекта объединения фиксирован: он должен быть достаточен для хранения самой большой переменной-члена объединения.
43. Динамические структуры данных: основные понятия. Достоинства и недостатки связного представления данных.
Любая программа предназначена для обработки данных, от способа организации которых зависят алгоритмы работы, поэтому выбор структур данных должен предшествовать созданию алгоритмов. Наиболее часто в программах используются массивы, структуры и их сочетания, например, массивы структур, полями которых являются массивы и структуры.
Память под данные выделяется либо на этапе компиляции (в этом случае необходимый объем должен быть известен до начала выполнения программы, то есть задан в виде константы), либо во время выполнения программы (необходимый объем должен быть известен до распределения памяти). В обоих случаях выделяется непрерывный участок памяти.
Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти.
Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Например, если в процессе выполнения программы требуется многократно упорядочивать большой массив данных, имеет смысл организовать его в виде линейного списка. При решении задач поиска элемента в тех случаях, когда важна скорость, данные лучше всего представить в виде бинарного дерева.
Элемент любой динамической структуры данных представляет собой структуру, содержащую по крайней мере два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: основного, составного или типа указатель. Описание простейшего элемента (компоненты, узла) выглядит следующим образом:
struct Node{
Data d: // тип данных Data должен быть определен ранее
Node *p; };
44. Динамическая структура данных: линейные списки. Реализация односвязного списка.
Самый простой способ связать множество элементов — сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа: при упорядочивании списка по алфавиту ключом будет фамилия, а при поиске, к примеру, ветеранов труда ключом будет стаж. Ключи разных элементов списка могут совпадать.
Над списками можно выполнять следующие операции:
· начальное формирование списка (создание первого элемента);
· добавление элемента в конец списка;
· чтение элемента с заданным ключом;
· вставка элемента в заданное место списка;
· удаление элемента с заданным ключом;
· упорядочивание списка по ключу.
Рассмотрим двунаправленный линейный список. Для формирования списка и заботы с ним требуется иметь по крайней мере один указатель — на начало списка. Удобно завести еще один указатель — на конец списка. Для простоты допустим, что список состоит из целых чисел, то есть описание элемента списка выглядит следующим образом:
struct Node{
int d;
Node *next;
Node *prev;};
45. Динамическая структура данных: линейные списки. Реализация двусвязного списка.
Самый простой способ связать множество элементов — сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список.
Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Например, если создается линейный список из записей, содержащих фамилию, год рождения, стаж работы и пол, любая часть записи может выступать в качестве ключа: при упорядочивании списка по алфавиту ключом будет фамилия, а при поиске, к примеру, ветеранов труда ключом будет стаж. Ключи разных элементов списка могут совпадать.
Над списками можно выполнять следующие операции:
· начальное формирование списка (создание первого элемента);
· добавление элемента в конец списка;
· чтение элемента с заданным ключом;
· вставка элемента в заданное место списка;
· удаление элемента с заданным ключом;
· упорядочивание списка по ключу.
Рассмотрим двунаправленный линейный список. Для формирования списка и заботы с ним требуется иметь по крайней мере один указатель — на начало списка. Удобно завести еще один указатель — на конец списка. Для простоты допустим, что список состоит из целых чисел, то есть описание элемента списка выглядит следующим образом:
struct Node{
int d;
Node *next;
Node *prev;};
46. Динамические структуры данных: линейные списки. Реализация кольцевого списка.
47. Динамические структуры данных: стек и его реализация.
Стек — это частный случай однонаправленного списка, добавление элементов в Который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Сегмент стека назван так именно потому, что память под локальные переменные выделяется по принципу LIFO. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.
48. Динамические структуры данных: очередь и его реализация.
Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.
49. Динамические структуры данных: дек и его реализация.
50. Динамические структуры данных: бинарные деревья и их реализация.
Бинарное дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. На рисунке 1 приведен пример бинарного дерева (корень обычно изображается сверху). Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потомками. Высота дерева определяется количеством уровней, на которых располагаются его узлы.