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


 

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

78925. Рациональное, объективное, истинное в СГН 32 KB
  При рассмотрении проблемы истины важно уяснить специфику ее классической неклассической и постнеклассической трактовки а также особенности современного понимания ряда частных вопросов: ситуативность и объективный характер истин социальногуманитарных наук; их взаимосвязь с социальной реальностью; экзистенциальноантропологический подход к истине в гуманитарном знании. Вследствие этого а также вследствие традиций и особенностей каждой из наук они могут пользоваться преимущественно классической неклассической или постнеклассической...
78926. Природа и типы объяснений в СГН 27 KB
  Объяснение логикометодологическая процедура экспликации сущности одного явления через другое имеющее статус достоверного очевидного. Научное объяснение должно отвечать двум требованиям: 1 адекватности его аргументы и характеристики должны иметь непосредственное отношение к предметам явлениям событиям которые они объясняют; 2 принципиальной проверяемости непосредственно или через следствия. По своей логической структуре объяснение представляет рассуждение или умозаключение посылки которого содержат информацию необходимую для...
78927. Объяснение и понимание в СГН 32.5 KB
  Объяснение и понимание в СГН. Объяснение логикометодологическая процедура экспликации сущности одного явления через другое имеющее статус достоверного очевидного. Научное объяснение должно отвечать двум требованиям: 1 адекватности его аргументы и характеристики должны иметь непосредственное отношение к предметам явлениям событиям которые они объясняют; 2 принципиальной проверяемости непосредственно или через следствия. По своей логической структуре объяснение представляет рассуждение или умозаключение посылки которого содержат...
78928. Понимание в гуманитарных науках 27.5 KB
  Понимание в гуманитарных науках. В гуманитарном знании в качестве оснований для объяснения часто выступают типологии а процедуры объяснения с необходимостью дополняются пониманием и интерпретацией. По эвристическим возможностям понимание не уступает рациональному способу познания но значительно расширяет палитру познавательных средств включая в них интуицию чувства переживание. Понимание предполагает проникновение на мотивационный интенциональный уровень человеческой деятельности либо а путем психологического вживания в цели...
78929. Объяснение и понимание в социологии, экономике, психологи 31.5 KB
  Объяснение и понимание в социологии экономике психологи и т. понимающей социологии во второй половине 19 века в философской подпочве социальнонаучного знания в лице Джамбаттиста Вико Фридриха Шлейермахера и всех тех кто различал социальный мир и мир природы и в связи с этим заявляли о необходимости выработки особых методов познания социального мира. Формирование из этой концепции понимания в социологии. Вычленение социологии как отдельного знания из социальной философии О.
78930. Вера, знание и сомнение в СГН 24.5 KB
  Вера знание и сомнение в СГН. Это означает вопервых что вера есть известие весть надеющихся то есть вера раскрывает выявляет тех кто надеется на чтото во что они верят или хотят верить. Вовторых вера обнаруживает то что невидимо недоступно простому взгляду обыкновенному глазу. Другими словами вера это сверхвйдение дополнительное умозрение таинственный если угодно магический или мистический свет с помощью которого человек видит то что не видит человек без веры.
78931. Основные исследовательские программы СГН 29 KB
  Убежденность в том что опираясь на рационализм можно раскрыть глубинную устойчивую внутреннюю основу любого социального объекта лежала в основе поиска экономистами фундаментального экономического отношения историками основного фактора исторического развития юристами центральной идеи права философами социологами и психологами рациональной сущности общества и человека. Прежде культура понималась как деятельность как правило творческая направленная на реализацию природной сущности человека. Теперь культура стала рассматриваться...
78932. Проблема разделения социальных и гуманитарных наук 28 KB
  Предмет науки это ограниченный исследовательскими целями и способами концептуализации фрагмент объективной или мысленной реальности. Социальногуманитарные науки исследуют закономерности социальной жизни ценностные состояния и мотивы действующих субъектов. Социальные науки изучают общие социальные закономерности структуру общества и его законы тогда как предметом гуманитарных наук является человеческий мир. Социальные науки используют натуралистическую программу с присущей ей моделью объяснения разделением субъектобъектных отношений.
78933. Дисциплинарная структура СГН и ее эволюция 28 KB
  Одной из актуальных проблем современного социально-гуманитарного знания является его интеграция, которая выражается в развитии междисциплинарных научных исследований. Общими причинами их появления и развития были, прежде всего, наличие «стыковых» проблем, не укладывающихся в границы предмета существующих дисциплин