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


 

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

81479. Основные фосфолипиды и гликолипиды тканей человека (глицерофосфолипиды, сфингофосфолипиды, гликоглицеролипиды, гликосфиголипиды). Представление о биосинтезе и катаболизме этих соединений 264.19 KB
  Функции гликосфинголипидов можно суммировать следующим образом: Взаимодействие между: клетками; клетками и межклеточным матриксом; клетками и микробами. Церамид служит предшественником в синтезе большой группы сфинголипидов: сфингомиелинов не содержащих углеводов и гликосфинголипидов. В распаде сфингомиелинов участвуют 2 фермента сфингомиелиназа отщепляющая фосфорилхолин и церамидаза продуктами действия которой являются сфингозин и жирная кислота Катаболизм гликосфинголипидов. Катаболизм гликосфинголипидов начинается с перемещения их...
81480. Нарушение обмена нейтрального жира (ожирение), фосфолипидов и гликолипидов. Сфинголипидозы 124.68 KB
  Сфинголипиды метаболизм: заболевания сфинголипидозы таблица Заболевание Фермент недостаточностькоторого обусловливает заболевание Накапливающийся :липид : Клинические симптомы Фукозидоз альфаФукозидаза CerGlcGlNcCl:Fuc НИзоантиген Слабоумие спастическое состояние мышц утолщение кожи Генерализованный ганглиозидоз GM1бетаГалактозидаза CerGlcGlNeucGlNc:Gl Ганглиозид GM1 Умственная отсталость увеличениепечени деформация скелета Болезнь ТеяСакса Гексозаминидаза А CerGlcGlNeuc:GlNc Ганглиозид GM2 Умственная отсталость...
81481. Строение и биологические функции эйкозаноидов. Биосинтез простагландинов и лейкотриенов 107.74 KB
  Биосинтез простагландинов и лейкотриенов. Структура номенклатура и биосинтез простагландинов и тромбоксанов Хотя субстраты для синтеза эйкозаноидов имеют довольно простую структуру полистовые жирные кислоты из них образуется большая и разнообразная группа веществ. Структура и номенклатура простагландинов и тромбоксанов Простагландины обозначают символами например PG А где PG обозначает слово простагландин а буква А обозначает заместитель в пятичленном кольце в молекуле эйкозаноида. Каждая из указанных групп простагландинов состоит из 3...
81482. Холестерин как предшественник ряда других стероидов. Представление о биосинтезе холестерина. Написать ход реакций до образования мевалоновой кислоты. Роль гидроксиметилглутарил-КоА-редуктазы 165.9 KB
  В печени синтезируется более 50 холестерола в тонком кишечнике 15 20 остальной холестерол синтезируется в коже коре надпочечников половых железах. В сутки в организме синтезируется около 1 г холестерола; с пищей поступает 300500 мг Холестерол выполняет много функций: входит в состав всех мембран клеток и влияет на их свойства служит исходным субстратом в синтезе жёлчных кислот и стероидных гормонов. Предшественники в метаболическом пути синтеза холестерола превращаются также в убихинон компонент дыхательной цепи и долихол...
81483. Синтез желчных кислот из холестерина. Конъюгация желчных кислот, первичные и вторичные желчные кислоты. Выведение желчных кислот и холестерина из организма 104.99 KB
  Конъюгация желчных кислот первичные и вторичные желчные кислоты. Выведение желчных кислот и холестерина из организма. Жёлчные кислоты синтезируются в печени из холестерола.
81484. ЛПНП и ЛПВП - транспортные, формы холестерина в крови, роль в обмене холестерина. Гиперхолестеринемия. Биохимические основы развития атеросклероза 110.43 KB
  Содержание холестерола и его эфиров в ЛППП достигает 45; часть этих липопротеинов захватывается клетками печени через рецепторы ЛПНП которые взаимодействуют и с апоЕ и с апоВ100. Транспорт холестерола в составе ЛПНП. Рецепторы ЛПНП. На ЛППП оставшиеся в крови продолжает действовать ЛПлипаза и они превращаются в ЛПНП содержащие до 55 холестерола и его эфиров.
81485. Механизм возникновения желчнокаменной болезни (холестериновые камни). Применение хенодезокеихолевой кислоты для лечения желчнокаменной болезни 103 KB
  Выделение холестерола в жёлчь должно сопровождаться пропорциональным выделением жёлчных кислот и фосфолипидов удерживающих гидрофобные молекулы холестерола в жёлчи в мицеллярном состоянии У большинства больных желчнокаменной болезнью активность ГМГКоАредуктазы повышена следовательно увеличен синтез холестерола а активность 7αгидроксилазы участвующей в синтезе жёлчных кислот снижена. В результате синтез холестерола увеличен а синтез жёлчных кислот из него замедлен что приводит к диспропорции количества холестерола и жёлчных кислот...
81486. Общая схема источников и путей расходования аминокислот в тканях. Динамическое состояние белков в организме 134.22 KB
  Значение аминокислот для организма в первую очередь определяется тем что они используются для синтеза белков метаболизм которых занимает особое место в процессах обмена веществ между организмом и внешней средой. Аминокислоты непосредственно участвуют в биосинтезе не только белков но и большого количества других биологически активных соединений регулирующих процессы обмена веществ в организме таких как нейромедиаторы и гормоны производные аминокислот. Аминокислоты служат донорами азота при синтезе всех азотсодержащих небелковых...
81487. Переваривание белков. Протеиназы - пепсин, трипсин, химотрипсин; проферменты протеиназ и механизмы их превращения в ферменты. Субстратная специфичность протеиназ. Экзопептидазы и эндопептидазы 110.2 KB
  Подавляющее их количество входит в состав белков которые гидролизуются в ЖКТ под действием ферментов протеаз пептидщцролаз. Под действием всех протеаз ЖКТ белки пищи распадаются на отдельные аминокислоты которые затем поступают в клетки тканей. Источником Н является Н2СО3 которая образуется в обкладочных клетках желудка из СО2 диффундирующего из крови и Н2О под действием фермента карбоангидразы карбонатдегидратазы: Н2О СО2 → Н2СО3 → НСО3 H Диссоциация Н2СО3 приводит к образованию бикарбоната который с участием специальных...