4884

Структуры и объединения. Перечисления. Поиск и сортировка в массивах структур

Лекция

Информатика, кибернетика и программирование

Структуры и объединения. Перечисления. Поиск и сортировка в массивах структур. Подобно тому, как массив является совокупностью элементов одного типа, структуры в С++ представляют собой совокупность элементов произвольных типов, например: struct Stud...

Русский

2012-11-28

57.5 KB

7 чел.

Структуры и объединения. Перечисления. Поиск и сортировка в массивах структур.

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

struct Student

{

 char name[128];      // Имя: "Андрей Петров"

 char faculty[128];   // Факультет: "ПМ-ПУ"

 unsigned int course; // Курс: 2

 unsigned int id;     // Номер зачетки: 234534

 float grade;         // Средний балл: 4.99

};

Здесь определяется новый тип данных Student, который описывает некоторую информацию о студенте. Заметим, что после закрывающей фигурной скобки, закрывающей определение структуры, обязательно ставится ‘;’. Теперь можно описывать переменные типа Student так же, как и любые другие:

Student s;        // Переменная типа Student

Student group[10]; // Массив элементов типа Student

Student * ps;      // Указатель на переменную типа Student

Инициализировать переменные-структуры можно аналогично массивам:

Student s = { "Andrey Petrov", "PM-PU", 2, 234534, 4.99 };

Обращаться к элементам структуры можно с помощью операции '.' (в случае непосредственной работы с переменной типа struct), а также используя операцию '->' (в случае косвенного обращения к переменной через указатель):

s.name = "Sergei Gerasimov";

s.course++;

ps = & s;

ps->id = 123123;

ps->grade = 4.5;

Объекты структурного типа могут быть присвоены, переданы как фактические параметры функций и возвращены функциями в качестве результата. Другие допустимые операции, например, такие, как сравнение ( == и != ), не определены. Размер объекта структурного типа не обязательно равен сумме размеров всех его членов. Это происходит по той причине, что на многих машинах требуется размещать объекты определенных типов, только выравнивая их по некоторой, зависящей от системы адресации, границе (или просто потому, что работа при таком выравнивании будет более эффективной).

Заметим, что тип можно использовать сразу после его появления в описании, еще до того, как будет завершено все описание:

struct Human // Структура описывает элемент в дереве родословной

{

  Human * mother;   // Указатели на родителей

  Human * father;

  Human * children; // Указатель на массив детей

};

Однако описывать объекты типа структуры нельзя, пока не появится полное её описание, поскольку компилятор не может определить размер структуры:

struct Student

{

  Student neighbor; // Ошибка!

};

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

 

struct Family; // Будет определена позднее (forward declaration)

struct Human

{

  Human * mother;

  Human * father;

  Human * children;

  Family * family;

};

struct Family

{

  Human * members;

}

Объединения.

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

struct Element

{

  char type;

  char s_value *; // Используется только если type == 's'

  int i_value;    // Используется только если type == 'i'

};

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

struct Element

{

  char type;

  union

  {

     char s_value[128]; // Используется только если type == 's'

     int i_value;       // Используется только если type == 'i'

  };

};

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

Перечисления.

Нередко возникает необходимость описания объектов, имеющих фиксированный набор возможных значений-состояний. Например, моделируя работу лифта, можно перечислить возможные состояния, в которых он может находиться (упрощённо):

- лифт стоит, ожидая пассажиров;

- лифт движется вверх;

- лифт движется вниз;

- лифт сломан.

Можно описать состояния лифта набором констант, например:

const int ELEVATOR_STOPPED = 1;

const int ELEVATOR_MOVING_UP = 2;

const int ELEVATOR_MOVING_DOWN = 3;

const int ELEVATOR_DISABLED = 4;

Однако, такой подход может вызвать проблему:

struct Elevator

{

  int state; // Тип int, может принимать любые значения 

};

Elevator e;

e.state = ELEVATOR_STOPPED; // OK

e.state = 5; // Смысловая ошибка, но компилятор ее не видит!


Гораздо удобнее для таких целей использовать перечисления:

enum ElevatorState

{

  ELEVATOR_STOPPED = 1,

  ELEVATOR_MOVING_UP,

  ELEVATOR_MOVING_DOWN,

  ELEVATOR_DISABLED

};

struct Elevator

{

  ElevatorState state;

};

Elevator e;

e.state = ELEVATOR_STOPPED; // ОК

e.state = 5; // Ошибка, неявное преобразование int к enum запрещено

Элементы перечисления, если их значение не указано явно, получают последовательные значения с шагом 1, и начинаются с 0. Таким образом, в приведенном выше примере значение всех элементов ElevatorState совпадает со значением соответствующих констант, рассмотренных ранее. Имя перечисления становится новым типом. С помощью стандартных преобразований тип перечисления может неявно приводиться к типу int. Обратное преобразование (из типа int в перечисление) должно быть задано явно.

Поиск и сортировка в массивах структур.

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

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

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

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


S1

2

S3

S4

S5

S6

S1

S2

S3

S4

S5

S6

&S1

p1

p2

p3

p4

p5

p6

&S2

&S3

&S4

&S5

&S6

&S3

p1

p2

p3

p4

p5

p6

&S1

&S4

&S6

&S2

&S5


 

А также другие работы, которые могут Вас заинтересовать

38759. Экономика и управление на предприятии ОАО «Новосибирская макаронная фабрика» 126.5 KB
  Королева Отчет по преддипломной практике по предприятию ОАО Новосибирская макаронная фабрика по специальности Экономика и управление на предприятие Выполнила: Детюченко В. Данную работу можно разделить на несколько разделов: 1 Уставные характеристики организации 2 История предприятия ОАО Новосибирская макаронная фабрика 3 Приоритетные направления деятельности ОАО Новосибирская макаронная фабрика 4 Анализ структуры предприятия 5 Анализ системы закупок Заключение Список использованной литературы Содержание...
38760. Социальная психология и психотерапия 456.5 KB
  психика это системное качво мозга которое реализуется чз функциональные сисмы мозга кторые формируются у Ч в прцессе жизни и овладения им истор сложившихся форм Дти и опыта человва чз собственную активную Дть. Фрейд определял генезис психического как одну из важных детерминант полноценного функционирования взрослого человека Принцип субъекта предполагает рассматривать человека как автономную инициативную личность способную в определенных пределах изменять себя и окружающий мир. Формы взаимодействия чел в миром. Выполняя...
38761. Ответы по географии для 9 класса 251 KB
  Географические различия в хозяйственной деятельности населения России привести конкретные примеры. Культурноисторические особенности народов России. Особенности природы населения и хозяйства отдельных территорий России привести примеры. Часовые пояса на территории России.
38763. Коммуникативная концепция права: Проблемы генезиса и теоретико-правового обоснования 294 KB
  Задачей диссертационного исследования является исследование и обоснование узловых аспектов коммуникативной теории права как одного из возможных вариантов интегрального правопонимания. Согласно такому целостному подходу право, как интерсубъективная правовая реальность, рассматривается в коммуникативно-деятельном, ценностном, семиотическом и психологическом аспектах и соответственно онтологически интерпретируется и феноменологически....
38764. Изучение городского пространства Исследование Витебского вокзала по заданному алгоритму 6.42 MB
  Список группы: Белова Елена Витальевна Веснина Мария Воробьёва Марина Евгеньевна Гайдукова Екатерина Владимировна Гусейнова Дина Денисова Ирина Михайловна Иванова Людмила Валентиновна Иванова Светлана Ильинична Киселёва Татьяна Станиславовна Группа за работой в музее Задание №1 Изучение городского пространства Исследование Витебского вокзала по заданному алгоритму. Задание №2 Исследование картин. Кроме работы на курсах было дано задание провести фасилитированное обсуждение...
38765. Юриспруденция. Методические указания 919 KB
  Изложенные материалы предназначены для оказания практической помощи студентам специальности 021100 030501 Юриспруденция при выборе темы дипломной работы ее написания оформления и защиты. Иркутский государственный технический университет Кафедра государственноправовых дисциплин ИрГТУ ОГЛАВЛЕНИЕ [1] ОГЛАВЛЕНИЕ [2] ВВЕДЕНИЕ [3] ВЫБОР И УТВЕРЖДЕНИЕ ТЕМЫ ДИПЛОМНОГО СОЧИНЕНИЯ [4] ВЫДАЧА ЗАДАНИЯ СОСТАВЛЕНИЕ КАЛЕНДАРНОГО ГРАФИКА РАБОТЫ И ПЛАНА ДИПЛОМНОГО СОЧИНЕНИЯ [5] ТРЕБОВАНИЯ К ОГЛАВЛЕНИЮ ДИПЛОМНОЙ РАБОТЫ [6] СБОР АНАЛИЗ И...
38766. Рынок чистой монополии 146.5 KB
  Для формирующегося рынка России характерна высокомонополизированная структура поддерживаемая созданием в последние годы различного рода концернов ассоциаций и других объединений одной из целей которых является поддержание высоких цен и обеспечение себе спокойного существования . Например для открытия коммерческого банка в России помимо установленного минимального размера уставного фонда требуется специальное разрешение Центрального банка РФ получить которое достаточно сложно. Развитие системы государственного регулирования естественных...
38767. Обследование хирургического больного 1.74 MB
  Следует также выяснить функцию различных систем организма в течение заболевания: сердечнососудистой боли в области сердца одышка сердцебиение отеки дыхательной кашель мокротаколичество запах цвет примеськрови пищеварительной тошнота отрыжка рвота стул нервной сон раздражительность головные боли мочевыделительной частота боль при мочеиспускании примесь крови. Усиленный рост волос на теле гипертрихоз наблюдается при расстройстве функций некоторых желез внутренней секреции в частности надпочечников а также...