Текст программы, уничтожающей список, построенный функцией createlist, приведен ниже.
// Глобальные описания и переменные
struct scb
{
double lat; // Географическая широта пункта
double lon; // Географическая долгота пункта
struct scb *sb; // Указатель на следующий пункт
struct scb *th; // Указатель на предыдущий пункт
char village[25]; // Название населен. пункта
int number; // Номер пункта (и узла)
};
int lenth; // Число узлов в списке
struct scb *current; // Указатель на текущий узел
struct scb *listbeg; // Указатель на первый узел
struct scb *listend; // Указатель последнего узла
// deletelist: мусорщик удаляет двунаправленный список
void deletelist(int n)
{
int i;
struct scb *space; // Текущий указатель узла
space = listbeg;
for (i = 1; i <= n; i++)
{
delete spaсe;
if (i < n)
space = space->sb;
}
}
Для того, чтобы удалить список, созданный после выполнения функции createlist(20), нужно выполнить функцию deletelist(lenth) . Понятно, что в глобальной переменной lenth после выполнения createlist(20) находится число 20.
8.4. Программы позиционирования для работы со списками
Допустим, что в главной программе, работающей со списком, построенным в результате выполнения функции createlist(20), нужно в переменную с плавающей точкой double latitude поместить широту населенного пункта, название которого находится в элементе village узла с номером k, а порядковый номер узла расположен в элементе number того же узла. В результате программа сможет определить, насколько севернее экватора расположен населенный пункт. Но это можно будет сделать только после того, как будет получен адрес узла с номером k.
Пример 8-3. Напишем соответствующую программу knotpointer, которая является функцией, возвращающей вызывающей (т.е. главной) программе адрес узла, если указать его номер в качестве аргумента.
// Глобальные описания и переменные
struct scb
{
double lat; // Географическая широта пункта
double lon; // Географическая долгота пункта
struct scb *sb; // Указатель на следующий пункт
struct scb *th; // Указатель на предыдущий пункт
char village[25]; // Название населен. пункта
int number; // Номер пункта (и узла)
};
int lenth; // Число узлов в списке
struct scb *current; // Указатель на текущий узел
struct scb *listbeg; // Указатель на первый узел
struct scb *listend; // Указатель последнего узла
// knotpointer: получает адрес k-го узла
struct scb *knotpointer(int k)
{
int n; // Счетчик позиций сдвига
int i; // Рабочая переменная
if (current->number == k)
; // Позиционер уже установлен
else if (listbeg->number == k || lenth == 1)
current = listbeg; // Установлен в начало
else if (listend->number == k)
current = listend; // Установлен в конец
else if (listbeg->number < k
&& k < listend->number)
if (k > current->number)
{ // Подвинуть к концу списка
n = k - current->number;
for (i=1; i <= n; i++)
{
space = space->sb;
current = space;
}
}
else
{ // Подвинуть к началу списка
n = current->number - k;
for (i=1; i <= n; i++)
{
space = space->th;
current = space;
}
}
else
printf(("Указан несуществующий номер узла !\n"
return(current);
}
Если указан неправильный номер узла (т.е. либо k<1, либо k>lenth), то будет сообщение об ошибке.
Возвратимся к поставленной задаче получения широты пункта. Имея программу knotpointer, можно получить широту пункта, информация о котором находится в 3-м узле, следующим образом:
void main(void)
{
int k;
double latitude;
...
k = 3;
...
latitude = (knotpointer(k))->lat;
...
}
Следует отметить, что могут быть и более сложные программы позиционирования. Если, например, нужно получить адрес узла, ближайшего в смысле координат к точке, широта и долгота которой – это аргументы программы позиционирования, то нужно запрограммировать дополнительно алгоритм получения точных расстояний между двумя произвольными точками на поверхности Земли. Для точных расчетов обычно Земля представляется в виде геометрического тела вращения, называемого эллипсоидом Красовского (в данном пособии мы это рассматривать не будем).
Списки могут расширяться за счет включения дополнительных узлов. Причем линейные списки желательно после этого перенумеровывать. Программа knotin добавления нового узла в соответствующее место может работать различным образом. Для нашего двунаправленного списка типовыми будут два способа:
1) новый узел нужно поставить в список между двумя узлами, имеющими наиболее близкие координаты на поверхности Земли (этот случай мы не будем рассматривать из-за его сложности);
2) новый узел с номером k, 1 £ k £ lenth, нужно поставить на место k в списке, подвинув последующие (lenth–k) элементов к концу списка и увеличив их номера на единицу.
Списки могут сокращаться за счет исключения имеющихся узлов. Причем линейные списки желательно после этого перенумеровывать. Программа knotout исключения узла из соответствующего места списка может работать различным образом. Для нашего двунаправленного списка типовыми будут также два способа:
1) нужно в списке найти узел, ближайший к точке, чьи географические координаты указаны в качестве аргументов knotout , и исключить его из списка;
2) нужно найти узел с номером k, 1 £ k £ lenth, исключить его из списка, подвинув последующие (lenth–k) элементов к началу списка и уменьшив их номера на единицу.
Упражнение 8-1. Написать функцию knotin(k), которая возвращает значение true, если новый узел с номером k, успешно поставлен в список, или false, если узел с номером k поставить в список невозможно.
Упражнение 8-2. Написать функцию knotout(k), которая возвращает значение true, если узел с номером k, успешно удален из списка, или false, если узел с номером k невозможно удалить.
9. ВВОД, ВЫВОД И ФОРМАТНЫЕ ПРЕОБРАЗОВАНИЯ
Средства ввода/вывода не являются составной частью языка «С», так что мы не выделяли их в нашем предыдущем изложении. Однако реальные программы взаимодействуют со своей окружающей средой гораздо более сложным образом, чем мы видели до сих пор. В этой главе будет описана «стандартная библиотека ввода/вывода», то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для «С»- программ. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операционных систем. Процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали необходимость обойти их «ради эффективности», как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть «переносимыми» в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык «С», и что программы, которые ограничивают свои взаимодействия с системой возможностями, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без изменений.
Мы здесь не будем пытаться описать всю библиотеку ввода/вывода; мы более заинтересованы в том, чтобы продемонстрировать сущность написания «С»-программ, которые взаимодействуют со своей операционной средой.
9.1. Обращение к стандартной библиотеке
Каждый исходный файл, который обращается к функции из стандартной библиотеки, должен вблизи начала содержать строку:
#include <stdio.h> .
В файле stdio.h определяются некоторые макросы и переменные, используемые библиотекой ввода/вывода. Использование угловых скобок вместо обычных двойных кавычек – указание компилятору искать этот файл в папках Visual Studio (операционная система Windous) или в справочнике-директории, содержащем заголовки стандартной информации (в системе Unix).
Кроме того, при загрузке программы может оказаться необходимым указать библиотеку явно:
1) на супер-компьютерах VAX или обычных PDP-11 при использовании операционной системы Unix (версия BSD-4.2, разработка Университета Беркли, Калифорния) команда компиляции программы имела бы следующий вид:
cc исходные файлы –ls ,
где флаг -ls указывает на загрузку из стандартной библиотеки;
2) компиляторы Microsoft для Windous в консольном режиме имеют аналогичную возможность:
cl –al исходные файлы ,
однако она редко используется из-за высокой степени автоматизма оболочки Visual Studio, используемой профессиональными программистами.
9.2. Стандартный ввод и вывод: функции getchar и putchar
Самый простой механизм ввода заключается в чтении по одному символу за раз из «стандартного ввода», обычно с терминала пользователя – с клавиатуры, с помощью функции getchar. Функция getchar при каждом к ней обращении возвращает следующий вводимый символ. В большинстве сред, которые поддерживают язык «С», терминал может быть заменен некоторым файлом с помощью обозначения < (символа «меньше»): если некоторая программа prog использует функцию getchar то командная строка:
prog<infile
приведет к тому, что prog будет читать из файла infile, а не с терминала. Переключение ввода делается таким образом, что сама программа prog не замечает изменения. В частности строка "<infile" не включается в командную строку аргументов в argv.
Переключение ввода оказывается незаметным и в том случае, когда вывод поступает из другой программы посредством поточного pipe-механизма*. В этом случае командная строка:
otherprog | prog
прогоняет две программы, otherprog и prog, и организует так, что стандартным вводом для prog служит стандартный вывод otherprog.
Функция getchar возвращает значение EOF, когда она попадает на конец файла, какой бы ввод она при этом не считывала. Стандартная библиотека полагает символическую константу EOF равной -1 (посредством #define в файле stdio.h), но проверки следует писать в терминах EOF, а не -1, чтобы избежать зависимости от конкретного значения.
Вывод можно осуществлять с помощью функции putchar, помещающей символ 'с' в «стандартный ввод», который по умолчанию является терминалом. Вывод можно направить в некоторый файл с помощью обозначения > (символа «больше») : если PROG использует putchar, то командная строка: