Понятия объединения и перечисления. Битовые поля.

Понятия объединения и перечисления

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

               union { описание элемента 1;

                                                       ...

               описание элемента n; };

                   

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

Доступ к элементам объединения осуществляется тем же способом, что и к структурам. Тег объединения может быть формализован точно так же, как и тег структуры.

Объединение применяется для следующих целей:

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

- интерпретации основного представления объекта одного типа, как если бы этому объекту был присвоен другой тип.

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

Пример:

               union {

                                                        char fio[30];

                                                        char adres[80];

                                                        int vozrast;

                                                        int telefon; } inform;

               union {

                                                        int ax;

                                                        char al[2]; } ua;

При использовании объекта infor типа union можно обрабатывать только тот элемент который получил значение, т.е. после присвоения значения элементу inform.fio, не имеет смысла обращаться к другим элементам. Объединение ua позволяет получить отдельный доступ к младшему ua.al[0] и к старшему ua.al[1] байтам двухбайтного числа ua.ax.

Битовые поля

Элементом структуры может быть битовое поле, обеспечивающее доступ к отдельным битам памяти. Вне структур битовые поля объявлять нельзя. Нельзя также организовывать массивы битовых полей и нельзя применять к полям операцию определения адреса. В общем случае тип структуры с битовым полем задается в следующем виде:

               struct { unsigned идентификатор 1: длина-поля 1;

                                     unsigned идентификатор 2: длина-поля 2; }

Длинна - поля задается целым выражением или константой. Эта константа определяет число битов, отведенное соответствующему полю. Поле нулевой длинны обозначает выравнивание на границу следующего слова.

Пример:

               struct { unsigned a1: 1;

                                                         unsigned a2: 2;

                                                         unsigned a3: 5;

                                                         unsigned a4: 2; } prim;

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

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

 

Методы сортировки данных. Пузырьковая сортировка. Сортировка посредством выбора. Сортировка вставками. Улучшенный алгоритм сортировки: сортировка Шелла, быстрая сортировка. Сортировка строк и структур.

При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них.

Пузырьковая сортировка

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=< K’1, K’2,...,K’n >, в котором для любого 1<=i<=n элемент K’ (i) <= K’(i+1).

При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.

Пример:

               B=<20,-5,10,8,7>, исходный список;

               B1=<-5,10,8,7,20>, первый просмотр;

               B2=<-5,8,7,10,20>, второй просмотр;

               B3=<-5,7,8,10,20>, третий просмотр.

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

Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.

/* сортировка пузырьковым методом      */

float * bubble(float * a, int m, int n)

                                     {

                                     char is=1;

                                     int i;

                                     float c;

                                    while(is)

                                    {

                                                        is=0;

                                                        for (i=m+1; i<=n; i++)

                                                        if (a[i] < a[i-1])

                                                        {

                                                                            c=a[i];

                                                                            a[i]=a[i-1];

                                                                        a[i-1]=c;

                                                                            is=1;

                                                        }

                                    }

                                    return(a);

                                     }

                                     

Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.