487. Диапазоны значений битовых полей структуры

В С486 было показано, как Си представляет биты в структуре битовых полей. При создании такой структуры необходимо выделить достаточное количество битов для каждого поля, чтобы в них могло содержаться требуемое значение. Для того чтобы помочь сориентироваться с количеством требуемых битов, в табл. 487 указан диапазон значений, которые можно хранить в указанном количестве битов.

Таблица 487. Диапазоны значений, предсгпавимых в заданном количестве битов

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

Например, в следующем цикле while показан поиск в массиве значения 1001:

found = 0;
i = 0;

while ((i < ARRAY_ELEMENTS) && (! found)) 
 if (array[i] ==1001)

 found = true;
else
 i++;

if (i < ARRAY_ELEMENTS)
 printf("Значение найдено на элементе номер %d\n", i);
else
 printf("Значение не найдено");

Если элементы массива расположены в порядке возрастания (массив отсортирован по возрастанию), то программа может выполнить двоичный поиск, который подробно описан в С489.

Итак, один из способов поиска значения в массиве - простой просмотр каждого его элемента. Такой способ поиска приемлем для массивов небольших размеров. Последовательный поиск в большом массиве может потребовать много времени. Если элементы массива отсортированы, то для поиска значения можно использовать двоичный поиск. Такой поиск называется двоичным потому, что при каждой операции количество просматриваемых значений уменьшается в два раза. Наилучший способ понять механизм двоичного поиска- это представить, как в словаре организуется поиск нужного слова. Допустим, нужно найти слово "Dalmatian." Для этого открываем словарь где-то посередине и просматриваем открывшиеся слова. Допустим, что все слова на этой странице на букву М, в этом случае ясно, что нужное слово - в первой половине словаря. Таким образом, исключается вторая половина словаря. Далее открываем словарь на половине оставшейся части, и видим там слова, начинающиеся на букву F. Теперь исключена половина оставшейся части. Разделим надвое оставшуюся часть. На этой странице увидим слова на букву С. Следовательно, слово "Dalmatian" находится на страницах между буквами С и F. После того как мы откроем словарь на середине оставшейся части, мы с большой вероятностью попадем на слова, начинающиеся с буквы D. Повторяя процесс деления пополам, мы можем быстро найти страницу со словом "Dalmatian".

Примечание: При двоичном поиске значения в массиве должны быть отсортированы в порядке возрастания.

Как можно убедиться в С489, двоичный поиск дает способ быстрого нахождения указанного значения в отсортированном массиве. В следующей программе BINARY.C выполняется двоичный поиск в массиве count, который содержит значения от 1 до 100. Для лучшего понимания процедуры двоичного поиска в функции binary_search выводятся сообщения о каждом шаге выполнения поиска:

#include <stdio.h>

int binary_search(int array[], int value, int size) 
{
int found = 0;

int high = size, low = 0, mid;

mid = (high + low) / 2;

printf("\nПоиск значения %d\n", value);

while ((! found) && (high >= low))
 {
 printf("Индексы: Нижний %d Текущий %d Верхний %d\n",low,mid, high);
 
 if (value == array[mid])
 found = 1;
 else if (value < array[aid])
 high = mid - 1;
 else
 low = mid + 1;

 mid = (high + low) / 2;
 } return((found) ? mid: -1);
}

void main(void) 
{
int array[100], i;

for (i = 0; i < 100; i++) 
 array[i] = i;

printf("Результат поиска %d\n", binary_search(array, 33, 100));
printf("Результат поиска %d\n", binary_search(array, 75, 100));
printf("Результат поиска %d\n", binary_search(array, 1, 100));
printf("Результат поиска %d\n", binary_search(array, 1001, 100));
}

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

Использование массивов дает возможность хранить связанные значения одного и того жетипа. При работе с массивами может возникнуть необходимость сортировки значений массива как по возрастанию (от меньшего к большему), так и по убыванию (от большего к меньшему). Для сортировки массива есть несколько различных алгоритмов: метод пузырька, метод выбора, метод Шелла и быстрая сортировка. Далее описан каждый из этих методов

Алгоритм метод пузырька - наиболее простой метод сортировки массива, известный большинству программистов. Из-за своей простоты этот метод не очень эффективен и требует процессорного времени больше, чем остальные методы. Однако для сортировки небольших массивов, с 30 или меньшим количеством элементов, использование метода пузырька приемлемо. Предположим, что массив сортируется в порядке возрастания, тогда метод пузырька использует цикл по значениям массива, перемещая постепенно наибольшие значения в конец массива (подобно тому, как в воде всплывает на поверхность пузырек). На рис. 492 показаны две итерации метода пузырька. При второй итерации второе наибольшее значение перемещается на вторую позицию. При третьей итерации третье наибольшее значение перемещается на третью позицию и т.д.

Рис. 492. Сортировка методом пузырька

В С492 был проиллюстрирован алгоритм метода пузырька. В следующей программе BUBBLE.C метод пузырька используется для сортировки массива из 30 случайных значений

#include <stdio.h>
#include <stdlib.h>

void bubble_sort(int array[], int size) 
{
int temp, i, j;

for (i = 0; i < size; i++) 
 for (j = 0; j < size; j++) 
 if (array[i] < array[j]) 
 {
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;
 }
}

void main(void) 
{
int values[30], i;

for (i = 0; i < 30; i++) 
 values[i] = randO % 100;

bubble_sort(values, 30);

for (i = 0; i < 30; i++) 
 printf("%d ", values[i]);
}

Примечание: Функция bubble_sort сортирует значения по возрастанию от меньшего к большему. Для сортировки массива в обратном порядке нужно просто изменить условие сравнения на if (array [i] > array [j]).

Как и сортировка методом пузырька, представленная в С493, сортировка методом выбора очень проста. Этот метод также рекомендуется использовать только для сортировки небольших массивов (порядка 30 элементов). Сортировка методом выбора начинается с выбора одного из элементов массива (например первого элемента). После этого делается просмотр всего массива и находится минимальное значение. Это значение помещается в начало; затем находится второй по возрастанию элемент и помещается на второе место и т.д. На рис. 494 показаны две итерации алгоритма сортировки методом выбора.

Рис. 494. Сортировка методом выбора

В С494 был проиллюстрирована сортировка методом выбора. В следующей программе SELECT.C этот метод используется для сортировки массива из 30 случайных значений:

#include <stdio.h>
#include <stdlib.h>

void selection_sort (int array [], int size)
{
int temp, current, j;

for (current =0; current < size; current++) 
 for (j = current +1; j < size; j++) 
 if (array[current] > array[j])
 {
 temp = array[current];
 array[current] = array[j];
 array[j] = temp;
 }
}

void main(void)
{
int values[30], i;

for (i = 0; i < 30; i++)
 values[i] = rand() % 100;

selection_sort(values, 30);

for (i = 0; i < 30; i++) 
 printf("%d ", values[i]);
}

Примечание: Функция selection_sort сортирует значения по возрастанию от меньшего к большему. Для сортировки массива в обратном порядке нужно просто изменить условие сравнения на if (array [current] < array [j]).

Метод Шелла получил свое название по фамилии создателя этого метода, Дональда Шелла. Этот метод заключается в сравнении элементов массива, разделенных одинаковым расстоянием таким образом, чтобы элементы по этому расстоянию были упорядочены. Затем это расстояние делится пополам и процесс продолжается. В конце это расстояние равно 1; если изменений нет, то массив отсортирован. На рис. 496 проиллюстрирована сортировка массива методом Шелла.

Рис. 496. Сортировка массива методом Шелла

В С497 была проиллюстрирована сортировка по методу Шелла. В следующей программе SHELL.C этот метод используется -для сортировки массива из 30 случайных значений:

#include <stdio.h> 
#include <stdlib.h>

void shell_sort(int array[], int size) 
{
int temp, gap, i, exchange_occurred;

gap = size / 2;

do { 
 do {
 exchange_occurred = 0;

 for (i = 0; i < size - gap; i++) 
 if (array[i] > array[i + gap]) 
 {
 temp = array[i];
 array[i] = array[i + gap];
 array[i + gap] = temp;
 exchange_occurred = 1;
 }
 } while (exchange_occurred);
 } while (gap = gap / 2);
}

void main(void) 
{
int values[50], i;

for (i = 0; i < 50; i++) 
 values[i] = randO % 100;
shell_sort(values, 50);

for (i = 0; i < 50; i++) 
 printf("%d ", values[i]);
}

Примечание: Функция shell Jsort сортирует значения по возрастанию ощ меньшего к большему. Для сортировки массива в обратном порядке нужно просто изменить условие сравнения на if (array [i] < array [i + gap]).

При возрастании количества элементов массива используется метод быстрой сортировки - один из наилучших по быстродействию. Этот метод рассматривает массив как список значений. Сначала выделяется среднее значение как сепаратор (фактор разбиения) списка. Список разбивается на два: в одном из них значения меньше сепаратора, а в другом - больше или равны. Далее процедура сортировки рекурсивно вызывает саму себя для каждого из двух списков. Каждый раз при вызове сортировки список элементов разбивается на два меньших. На рис. 498 показана сортировка массива из десяти значений методом быстрой сортировки.

Рис. 498. Сортировка значений методом быстрой сортировки

В С498 была проиллюстрирована сортировка по методу быстрой сортировки. В следующей программе QUICK.C этот метод используется для массива из 100 случайных значений:

#include <stdio.h>
#include <stdlib.h>

void quick_sort(int array [], int first, int last)
{
int temp, low, high, list_separator;

low = first;
high = last;
list_separator = array[(first + last) / 2];

do {
 while (array[low] < list_separator) low++;

 while (array[high] > list_separator) high--;

 if (low <= high) 
 {
 temp = array[low];
 array[low++] = array[high];
 array[high--] == temp;
 }
} while (low <= high);

if (first < high)
 quick_sort(array, first, high);
if (low < last)
 quick_sort(array, low, last);
}

void main(void) 
{
int values[100], i;

for (i = 0; i < 100; i++) 
 values[i] = rand() % 100;

 quick_sort (values, 0 , 99);

for (i = 0; i < 100; i++) 
 printf("%d ", values[i]);
}

Примечание: Функция quick _sort сортирует значения по возрастанию от меньшего к большему. Для сортировки массива в обратном порядке нужно просто изменить условия сравнения в двух операторах while на:

while (array[low] > list_separator) 
 low++;
while (array[high] < list_separator) 
 high++;

void quick_sort(float array[], int first, int last)
{
float temp, list separator;
int low, high;

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

Как известно, Си дает возможность создавать массив символьных строк:

char *days[] = { "Понедельник", "Вторник", "Среда" );

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

#include <stdio.h>
#include <stdlib.h> 
#include <string.h>

void bubble_sort(char *array[], int size) 
{
char *temp;
int i, j;

for (i = 0; i < size; i++) 
 for (j=0; j < size; j++)
 if (strcmp(array[i], array[j]) < 0) 
 {
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;
 } 
}

void main(void) 
{
char *values[] = ("AAA", "CCC", "BBB", "EEE", "DDD"};
int i;

bubble_sort(values, 5);

for (i = 0; i < 5; i++) 
 printf("%s ", values [i]);
}

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

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

#include <stdlib.h>

void *lfind(const void *element, void *base,
 size_t *number_of_entries, size_t element_width, 
 int (*compare)(const void *, const void *));

Как видим, список параметров функции изобилует указателями. Параметр element - указатель на значение, которое требуется найти. Параметр base-указатель наначало массива. Параметр number_of_entries - указатель на количество элементов массива. В параметре element_width указывается количество байтов на каждый элемент массива. Наконец, параметр compare - указатель на другую функцию, которая сравнивает два элемента массива. В отличие от функций, рассмотренных ранее и возвращающих индекса массиве найденного элемента, функция Ifind возвращает указатель на требуемый элемент массива или NULL, если значение не найдено. В следующей nporpaммe LFIND.C функция lfind используется для поиска значения типа int и значения типа float:

#include <stdlib.h>
#include <stdio.h>

int compare_int(int *a, int *b)
{
return(*a - *b);
}

int compare_float(float *a, float *b) 
{
return((*a == *b) ? 0: 1);
}

void main(void) 
{
int int_values[] = {1, 3, 2, 4, 5);
float float_values[] = {1.1, 3.3, 2.2, 4.4, 5.5);

int *int_ptr, int_value = 2, elements = 5;
float *float_ptr, float_value = 33.3;

int_ptr = lfind(&int_value, int_values, 
 &elements, sizeof(int), 
 (int (*) (const void *, const void *)) compare_int);

if (*int_ptr)
 printf("Значение %d найдено\n", int_value);
else
 printf("Значение %d не найдено\n", int_value);

float_ptr = lfind(&float_value, float_values, 
 &elements, sizeof(float), 
 (int (*) (const void *, const void *)) compare_float);

if (*float_ptr)
 printf("Значение %3.1f найдено\n", float_value);
else
 printf("Значение %3.1f не найдено\n", float_value);
}

Как уже обсуждалось ранее, несоответствия типов были препятствием для поиска и сортировки. Теперь при использовании указателей этого можно избежать.

В С502 для поиска в массиве элемента с требуемым значением использовалась функция Iflnd. Если требуемый элемент найден, функция возвращает указатель на него, иначе возвращает 0. В программе может понадобиться добавить значение в массив, если оно не найдено. В этом случае удобно использовать функцию lsearch:

#include <stdlib.h>

void *lsearch(const void *element, void *base,
 size_t *number_of_entries, size_t element_width, 
 int (*compare)(const void *, const void *));

#include <stdlib.h> 
#include <stdio.h>

int compare_int(int *a, int *b) 
{
return(*a - *b);
}

int compare_float(float *a, float *b) 
{
return((*a == *b) ? 0: 1);
}

void main(void) 
{
int int_values[10] = {1, 3, 2, 4, 5};
int *int_ptr, int_value = 1001, elements =5, i;

printf("Содержимое массива до поиска\n");
for (i = 0; i < elements; i++) 
 printf("%d ", int_values[i]);

int_ptr = lsearch(&int_value, int_values, 
 &elements, sizeof(int), 
 (int (*) (const void *, const void *)) compare_int);

printf("\nСодержимое массива после поиска\n");
for (i = 0; i < elements; i++) 
 printf("%d ", int_values[i]);
}

Как можно видеть, при добавлении значения в массив функция Isearch изменяет и значение параметра, в котором указывается количество элементов массива.

Примечание: При использовании функции Isearch необходимо предусмотреть дополнительное место в массиве для добавляемых значений.

В С489 мы видели, что при двоичном поиске в отсортированном массиве местоположение требуемого значения определяется путем деления пополам количества элементов исследуемого массива с каждой итерацией. Для операции двоичного поиска используется функция bsearch:

#include <stdlib.h> 
void *lfind(const void *element, void *base,
 size_t *number_of_entries, size_t element_width, 
 int (*compare)(const void *, const void *));

Как можно видеть, в функции очень часто используются указатели. Параметр element - указатель на значение, которое требуется найти. Параметр base - указатель на начало массива. Параметр number_of_entries - указатель на количество элементов массива. В параметре element_width указывается количество байтов, занимаемое каждым элементом массива. Наконец, параметр compare - указатель на другую функцию, которая сравнивает два элемента массива. В отличие функций, рассмотренных ранее и возвращающих индекс найденного элемента в массиве, функция bsearch возвращает указатель на элемент массива, содержащий требуемое значение или NULL, если значение не найдено. В следующей программе BSEARCH.C функция bsearch используется для поиска значения типа int и значения типа float:

#include <stdlib.h>
#include <stdio.h>

int compare_int(int *a, int *b) 
{
return(*a - *b);
}

int compare_float(float *a, float *b)
{
return((*a == *b) ? 0: 1);
}

void main(void) 
{
int int_values[] ={1,3,2,4,5);
float float_values[] = (1.1, 3.3, 2.2, 4.4, 5.5);

int *int_ptr, int_value = 2, elements = 5;
float *float_ptr, float_value = 33.3;

int_ptr = bsearch(&int_value, int_values, 
 elements, sizeof(int), 
 (int (*) (const void *, const void *)) compare_int);

if (*int_ptr)
 printf("Значение %d найдено\n", int value);
else
 printf("Значение %d не найдено\n", int_value);

float_ptr = bsearch(&float_value, float_values, 
 elements, sizeof(float), 
 (int (*) (const void *, const void *)) compare_float) ,

if (*float_ptr)
 printf("Значение %3.1f найдено\n", float_value);
else
 printf("Значение %3.1f не найдено\n", float_value);
}

Примечание: Для использования функции bsearch необходимо, чтобы значения элементов массива были отсортированы в порядке возрастания.

Из С498 нам известно, что при сортировке по методу быстрой сортировки массив рассматривается как список элементов. Метод быстрой сортировки путем разделения элементов массива на списки меньшего размера оказывается очень эффективным. Для того чтобы сортировать массивы всех типов с использованием алгоритма быстрой сортировки, библиотека Си предоставляет функцию qsort:

#include <stdlib.h>

void *qsort(void *base, size_t number_of_entries, 
 size_t element_width, 
 int (*compare)(const void *, const void *));

Как можно видеть, в прототипе функции очень часто используются указатели. Параметр base -указатель на начало массива. Параметр number_of_entries - указатель на количество элементов массива. В параметре element_width указывается количество байтов, занимаемое каждым элементом массива. Наконец, параметр compare - указатель на другую функцию, которая сравнивает два элемента массива следующим образом:

*а < *b // Возврат значения < О
*а == *а // Возврат О
*а > *b // Возврат значения > О

В следующей программе QSORT.C функция qsort используется для сортировки значений типа int и значений типа float:

#include <stdlib.h>
#include <stdio.h>

int compare_int(int *a, int *b) 
{
return(*a - *b);
}
int compare_float( float *a, float *b) 
{
if (*a < *b) 
 return(-1);
else if (*a == *b) 
 return (0);
else
 return(1);
}

void main(void) 
{
int int_values[] = (51, 23, 2, 44, 45);
float float_values[] = (21.1, 13.3, 22.2, 34.4, 15.5);

int elements = 5, i;

qsort(int_values, elements, sizeof(int),
 (int (*) (const void *, const void *)) compare_int);

for (i = 0; i < elements; i++) 
 printf ("%d ", int_values[i]);

putchar('\n');

qsort(float_values, elements, sizeof(float),
 (int (*) (const void *, const void *)) compare_float);

for (i = 0; i < elements; i++)
 printf ("% 4.1f ", float_values[i]);