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


 

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

29455. Модели равновесия в национальной экономике.Модель доходы-расходы. Инфляционный и рецессионный разрыв 44.95 KB
  Модель доходырасходы. Совокупные расходы включают в себя расходы всех хозяйствующих субъектов в том числе потребительские инвестиционные и государственные расходы а также чистый экспорт который мы считаем равным нулю.Модель национальный доход совокупные расходыиллюстрирует значение государственных расходов и поощрения частных инвестиций. совокупные расходы недостаточны для обеспечения полной занятости ресурсов хотя равновесие AD = AS достигнуто.
29456. Антициклическая политика и её инструменты 16.21 KB
  Особенности антициклической политики современных государств показаны на схеме Антициклическая политика государства Фазы цикла Спад Подъем Характер антициклической политики Экспансия Сдерживание Инструменты Фискальная политика Снижение налоговыхставокРост государственных расходовНалоговые льготы на новые инвестиции Повышение налоговСнижение государственных расходов Кредитноденежная политика Понижение ставки рефинансирования и уровня резервных требованийПокупка ценных бумаг Повышение ставок рефинансирования и уровня резервных...
29457. Цикличность экономики: причины, фазы и их специфика, типы циклов 14.19 KB
  Сторонники второй позиции утверждают что цикличность явление внутреннее присущее самой экономической системе и порождается: недостаточным потреблением по сравнению с производством; превышением производства средств производства над производством предметов потребления; нарушениями в области денежного обращения. Помимо уже упомянутых можно назвать еще ряд факторов и противоречий в экономику порождающих кризисы и циклы в частности: противоречие между четкой организацией современного производства и стихийным характером рынка; противоречие...
29458. Эффект храповика 25.09 KB
  Эффект храповика Начальное макроэкономическое равновесие наблюдается в точке Е1 при уровне цен P1 и реальном объеме производства Y1. Предположим что в этой ситуации правительство ставит задачу достичь макроэкономического равновесия на уровне Y2 и успешно справляется с поставленной задачей например осуществляя необходимые государственные расходы и тем самым стимулируя спрос до AD2. Новое макроэкономическое равновесие возникает при более высоком уровне цен Р2 но и при более высоком уровне реального объема производства Y2. Однако возможно что...
29459. Эффект бережливости в рыночной экономике 22.67 KB
  Эффект бережливости в рыночной экономике Парадокс бережливости это парадоксальное явление суть которого состоит в сокращении сбережений вследствие усиления стремления к сбережениям то есть роста бережливости. Парадокс бережливости Сдвиг вверх графика функции сбережений от S до S1 при неизменном уровне автономных инвестиций I приведет к тому что изза эффекта мультипликатора экономика будет функционировать на уровне более низкого выпуска. Таким образом парадокс бережливости означает что увеличение сбережений приводит к уменьшению дохода.
29460. Равновесие в модели IS-LM.Факторы,воздействующие на равновесие на денежном и товарном рынках 35.57 KB
  Кривая IS отражает соотношение процентной ставки и уровня национального дохода при котором обеспечивается равновесие на товарных рынках. Кривая IS отражает множество равновесных ситуаций на товарном рынке. Кривая LM отражает зависимость между процентной ставкой и уровнем дохода возникающую на рынке денежных средств. Кривая LM соответствует таким парам точек Y i для которых спрос на деньги L определяющий уровень их ликвидности равен предложению денежной массы М.
29461. Абсолютная сходимость. Абсолютная сходимость числовых рядов 16.52 KB
  Смотрите также: условная неабсолютная сходимость числовых рядов СвойстваПравить из сходимости ряда вытекает сходимость ряда . При исследовании абсолютной сходимости ряда используют признаки сходимости рядов с положительными членами. Если ряд расходится то для выявления условной сходимости числового ряда используют более тонкие признаки: Признак Лейбница признак Абеля признак Дирихле. Абсолютная сходимость в математике вид сходимости рядов и интегралов.
29462. Условно сходящиеся числовые ряды и теорема Римана 78.92 KB
  Если числовой ряд сходится а ряд составленный из абсолютных величин его членов расходится то исходный ряд называется условно неабсолютно сходящимся. Теорема Римана об условно сходящихся рядах помогает при вычислении суммы бесконечного ряда. Пусть ряд сходится условно тогда для любого числа S можно так поменять порядок суммирования что сумма нового ряда будет равна S.
29463. Признак Абеля, пример 33.9 KB
  Признак Абеля сходимости несобственных интегралов[править] Признак Абеля дает достаточные условия сходимости несобственного интеграла. Признак Абеля для несобственного интеграла Iрода для бесконечного промежутка. Признак Абеля для несобственного интеграла IIрода для функций с конечным числом разрывов.