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


 

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

28676. Политика «военного коммунизма», ее сущность, содержание. Продразверстка. Всеобщая трудовая повинность 13.36 KB
  й чрезвычайных мер управления эккой харных для периода Гражданской войны. Поскольку жесткая система контроля и распредя основывалась на уравнительном распреди для трудящихся она получила название коммунизма а поскольку система возникла как чрезвычайная мера в период войны название военного коммунизма. С окончанием Гражданской войны он был отменен.
28677. Перестройка государственного аппарата в годы гражданской войны и иностранной военной интервенции. Совет рабочей и крестьянской обороны 13.45 KB
  В перерывах между съездами Советов высшим органом власти являлся ВЦИК. был установлен сессионный порядок работы ВЦИК. С сессионным порядком работы ВЦИК изменился и харер деятти его Президиума: он был наделен правом руководить заседаниями ВЦИК наблюдать за выпем его постановлений назначать наркомов инструктировать центральные и местные органы отменять постановления СНК и др. Президиум ВЦИК был наделен законодательными полномочиями.
28678. Военно-политический и хозяйственный союз республик в годы гражданской войны -и иностранной военной интервенции (1918- 1920 гг.) 12.25 KB
  Военнополитический и хозяйственный союз республик в годы гражданской войны и иностранной военной интервенции 1918 1920 гг. ознаменовался рождением Российской Советской Федеративной Социалистической Республики. На первом этапе на территории бывшей царской России возникли автономные республики территориальные автономии с учетом национального состава населения появились суверенные Советские республики. Второй этап объединительного движения народов советских республик связан с периодом гражданской войны и иностранной военной интервенции...
28679. Переход Советского государства к новой экономической политике, ее сущность Совершенствование государственного аппарата и законодательства в период перехода к НЭПу 13.46 KB
  Переход Советского государства к новой экономической политике ее сущность Совершенствование государственного аппарата и законодательства в период перехода к НЭПу. X съезд Коммунистической партии принял решение о переходе от продразверстки к продналогу и о переходе к новой экономической политике нэпу. Переход к новой эккой политике означал отказ от методов военного коммунизма. предполагалось начать выпуск новой валюты.
28680. Судебная реформа 1922 г. и создание единой судебной системы. Упразднение чрезвычайных судебных органов. Создание прокуратуры и адвокатуры 13.61 KB
  ВЦИК утвердил Положение о судоустройстве РСФСР положившее начало новой судебной реформе. Положение вводилось в действие на всей терории РСФСР с 1 января 1923 г. Данным нормативным актом создавалась единая судебная система: народный суд в составе постоянного народного судьи; народный суд в составе постоянного народного судьи и 2ух народных заседателей; губернский суд; Верховный суд РСФСР и его коллегии. Параллельно с единой системой народных судов РСФСР действовали специальные суды: военные трибуналы военнотранспортные трибуналы...
28681. Развитие законодательства и его кодификация в 1922 г. Кодексы законов о труде, земле, гражданский и уголовный кодексы 1922 г. 14.06 KB
  ГК РСФСР состоял из 4 разделов: общ. ЗК РСФСР состоял из Оснх положений и 3 частей: о трудовом землепользи о городских землях и госных земельных имвах о землеустройстве и переселении. Кодекс закрепил отмену частной собствти на землю недра воды и леса в пределах РСФСР. КЗоТ РСФСР сост.
28682. Национально-государственное размежевание в Средней Азии и образование новых советских социалистических республик 12.23 KB
  Первыми субъектами СССР были четыре союзные республики: РСФСР УССР БССР и ЗСФСР. В дальнейшем СССР пополнялся новыми субъектами. На первом этапе развития Союза ССР происходило национальногосударственное размежевание в Средней Азии на территории Туркестанской АССР входившей в состав РСФСР и двух самостоятельных государств Хорезмской и Бухарской народных советских республик. были приняты декларации об образовании Узбекской ССР и Туркменской ССР.
28683. Образование СССР. Договор и Декларация об образовании СССР, их правовые основы 13.48 KB
  Образование СССР. Договор и Декларация об образовании СССР их правовые основы. Образование СССР определяется след. предпосылкой образования СССР было существование в республиках аналогичного режима диктатуры пролетариата.
28684. Разработка и принятие Конституции СССР 1924 г. Ее основные положения 12.45 KB
  Разработка и принятие Конституции СССР 1924 г. Конституция СССР 1924г. Она была принята ЦИК СССР 6 июля 1923 г. II Всесоюзным съездом Советов СССР.