Программы позиционирования для работы со списками

 

    Допустим, что в главной программе, работающей со списком, построенным в результате выполнения функции 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 невозможно удалить.

 

ВВОД, ВЫВОД И ФОРМАТНЫЕ ПРЕОБРАЗОВАНИЯ

ДАННЫХ

Средства ввода/вывода не являются составной частью языка «С», так что мы не выделяли их в нашем предыдущем изложении. Однако реальные программы взаимодействуют со своей окружающей средой гораздо более сложным образом, чем мы видели до сих пор. В этой главе будет описана «стандартная библиотека ввода/вывода», то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для «С»- программ. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операционных систем. Процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали необходимость обойти их «ради эффективности», как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть «переносимыми» в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык «С», и что программы, которые ограничивают свои взаимодействия с системой возможностями, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без изменений.

Мы здесь не будем пытаться описать всю библиотеку ввода/вывода; мы более заинтересованы в том, чтобы продемонстрировать сущность написания «С»-программ, которые взаимодействуют со своей операционной средой.