Динамическое выделение памяти для структур

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

sizeof(имя структуры);

Пример Библиотека из 3 книг

#include <stdio.h> #include <stdlib.h>

#include <malloc.h> struct book {

 char title [15];

 char author [15];

 int value; }; int main() {

  struct book *lib;

  int i;

  system("chcp 1251");

  system("cls");

  lib = (struct book*)malloc(3*sizeof(struct book));

  for(i=0;i<3;i++)

  {

    printf("Введите название %d книги:",i+1);

    gets((lib+i)->title);

    printf("Введите автора %d книги: ",i+1);

    gets((lib+i)->author);

    printf("Введите цену %d книги: ",i+1);

    scanf("%d",&(lib+i)->value);

    getchar();

  }

  for(i=0;i<3;i++)

  {

    printf("\n %d. %s ", i+1, (lib+i)->author);

    printf("%s %d", (lib+i)->title, (lib+i)->value);

  }

  getchar();

  return 0; }

Результат выполнения аналогичен предыдущему решению.

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.

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

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

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

• 2) множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

• 3) множество допустимых операций, которые применимы к объекту описываемого типа.

СТРУКТУРА ДАННЫХ - совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.

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

ДИНАМИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время работы программ.

Динамические структуры данных базируются на двух элементах языка программирования:

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

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

Таким образом, близко к истине и такое определение: динамические структуры данных -это динамические переменные и массивы, связанные указателями. Говоря о структурах данных, нельзя забывать, что обычные переменные размещаются в оперативной памяти (внутренней памяти компьютера). Поэтому обычно и структуры данных имеют отношение к памяти. Однако существует еще и внешняя память, которая в языке доступна опосредованно через операторы (Паскаль) или функции (Си), работающие с файлами. В режиме двоичного файла произвольного доступа любой файл представляет собой аналог неограниченной прямо адресуемой области памяти, то есть с точки зрения программы выглядит так же, как обычная память. Естественно, что программа может копировать переменные из памяти в произвольное место файла и обратно, а значит и организовывать в файле любые (в том числе и динамические) структуры данных. Структура данных - это исполнитель, который организует работу с данными, включая их хранение, добавление и удаление, модификацию, поиск и т.д. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку. При описании структуры данных нужно перечислить набор действий, которые возможны для нее, и четко описать результат каждого действия. Будем называть такие действия предписаниями. С программной точки зрения, системе предписаний структуры данных соответствует набор функций, которые работают над общими переменными. Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс, сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java. Тем не менее, структуры данных столь же успешно можно реализовывать и в традиционных языках программирования, таких как Фортран или Си. При этом следует придерживаться объектно-ориентированного стиля программирования: четко выделить набор функций, которые осуществляют работу со структурой данных, и ограничить доступ к данным только этим набором функций. Сами данные реализуются как статические (не глобальные) переменные. При программировании на языке Си структуре данных соответствуют два файла с исходными текстами: 1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;  2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных Структура данных обычно реализуется на основе более простой базовой структуры, ранее уже реализованной, или на основе массива и набора простых переменных. Следует четко различать описание структуры данных с логической точки зрения и описание ее реализации. Различных реализаций может быть много, с логической же точки зрения (т.е. с точки зрения внешнего пользователя) все они эквивалентны и различаются, возможно, лишь скоростью выполнения предписаний.

Урок 24. Массивы - как пример гомогенной структуры данных: размещение в памяти, доступ к элементам.

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

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

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

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

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

Кратко об основных контейнерах

1. вектор		хранение элементов всегда осуществляется единым блоком все элементы проиндексированы и доступ легко осуществляется по индексу
2. стек		хранение элементов осуществляется в едином блоке памяти доступ возможен к элементу находящемуся на вершине стека
3. очередь		хранение элементов осуществляется в едином блоке памяти доступ возможен к первому элементу внесенному в очередь
4. список		хранение элементов: разбросаны по памяти как угодно, т.к. каждый элемент содержит указатель на последующий и предыдущий возможен только перебор
5. дерево		хранение последовательное возможен обхода дерева от корня. Доступ к элементам зная родителя, который содержит ссылки на дочерние элементы
6. ассоциативный массив		хранение последовательное доступ организуется с помощью обхода дерева по ключу