31.5. Очереди
Очередь – структура данных, для которой удаление или добавление элементов осуществляется с помощью указателей начала (head) и конца (tail) очереди в соответствии с правилом FIFO (first-in, first-out – первым пришел, первым ушел).
Основные операции:
Добавление элемента в конец очереди.
Удаление элемента из начала очереди.
Ниже приводятся примеры функций для очереди (структура элемента очереди совпадает со структурой элемента стека в примере выше):
struct Node *head = NULL; // начало очереди
struct Node *tail = NULL; // конец очереди
// добавление элемента в конец очереди
struct Node *addQueue(Info add) {
struct Node *p;
p = (struct Node *)malloc(sizeof(struct Node));
if (p) { // память выделена успешно
p->data = add; // заполнение данных
p->next = NULL; // элемент будет последний в очереди
if (tail != NULL) // в очереди есть элементы
tail->next = p; // вставка в конец очереди
else // вставка первого элемента
head = p; // в очереди появился элемент
tail = p; // новый конец очереди
}
return p; // возврат адреса нового элемента или NULL – ошибка добавления
}
// удаление элемента из начала очереди
void delQueue() {
struct Node *p;
if (head != NULL) { // очередь не пустая
p = head->next; // запомнить адрес следующего
free(head); // освобождение памяти
head = p; // новое начало очереди
if (head == NULL) // очередь стала пустой
tail = NULL; // очередь не имеет конца
}
}
// печать содержимого очереди
void printQueue() {
struct Node *p;
printf("==================\n");
p = head; // стать в начало очереди
while (p != NULL) {
printf("%s %d\n", p->data.name, p->data.kol);
p = p->next; // переход к следующему элементу
}
}
Очереди также находят многочисленные применения. Примеры прикладных задач – нахождение кратчайшего пути в графе, нахождение максимального потока в сети (поиск в ширину, в отличие от рекурсии – поиска в глубину). Примеры системных задач – очереди к различным ресурсам в операционных системах, компьютерные сети. Процессор в каждый конкретный момент времени может обслуживать только одну задачу. Остальные задачи ставятся в очередь. Очереди также используются в некоторых алгоритмах замещения страниц при страничной организации памяти. Еще одно применение – очереди к устройствам монопольного доступа (принтер). Информационные пакеты в компьютерных сетях также проводят часть времени, ожидая в очередях.
32. Препроцессор языка с
Препроцессор используется для обработки текста программы до непосредственной ее компиляции. Компилятор вызывает препроцессор автоматически.
Директивы препроцессора нужны для того, чтобы облегчить написание и модификацию программ, а также сделать их более независимыми от аппаратных платформ и операционных систем. Директивы препроцессора позволяют заменять лексемы в тексте программы, вставлять в файл содержимое других файлов, запрещать компиляцию части файла или делать ее зависимой от некоторых условий и т. д. Хотя препроцессор и расширяет возможности языка программирования, его использование не лишено недостатков: использование препроцессора требует дополнительного просмотра текста программы и, как следствие, добавочного времени.
Директивы препроцессора – это инструкции, записанные непосредственно в исходном тексте программы на языке С. Все директивы препроцессора начинаются с символа #, перед которым в строке могут находиться только пробелы. После директив препроцессора точка с запятой не ставится. Директива препроцессора может занимать одну строку, а может продолжаться и на следующей строке программы, если в конце первой строки поставить символ обратной косой черты (\).
Директивы могут быть записаны в любом месте исходного файла. Их действие распространяется от точки программы, в которой они записаны, и до конца исходного файла или же до явной отмены директивы. Часть директив могут содержать аргументы.
Можно выделить следующие основные виды директив:
вставка файлов;
определение макрокоманд (макросов);
условная компиляция программы.