Контрольные вопросы

1. Каково назначение препроцессора языка С?

2. Что такое условная компиляция, осуществляемая препроцессором? В каких целях она производится?

3. Какие Вы знаете операторы препроцессора? Для чего они используются?

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

5. Что такое макроопределение препроцессора? Как оно реализуется?

Библиографический список

1. Дорот В. Л. Толковый словарь современной компьютерной лексики / В. Л. Дорот, Ф. А. Новиков. – 2-е изд., перераб. и доп. – СПб. : БХВ-Петербург, 2001. – 512 с.

2. Керниган Б. У. Язык программирования С / Б. У. Керниган, Д. М. Ритчи. – 2-изд. – М. : Вильямс, 2007. – 304 с.

3. Шилдт Г. Полный справочник по С : пер. с англ. / Г. Шилдт. – 4-е изд. – М. : Вильямс, 2007. – 704 с.

4. Прата С. Язык программирования С. Лекции и упражнения : пер. с англ. / С. Прата. – 5-е изд. – М. : Вильямс, 2006. – 960 с.

5. Дейтел Х. М. Как программировать на С : пер. с англ. / Х. М. Дейтел, П. Дж. Дейтел. – 4-е изд. – М. : Бином-Пресс, 2006. – 912 с.

Тема 20 Программы на языке с при использовании статически подключаемой библиотеки

Cтавится задача создания и применения статической подключаемой библиотеки с помощью MS Visual Studio 2010, осуществления компиляции нескольких файлов, размещенных в ней.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Библиотека представляет собой набор функций [1]. Когда программа обращается к библиотечной функции, редактор связей находит эту функцию и добавляет ее код в программу. Исполняемый файл содержит только те функции, которые используются программой, а не все библиотечные функции [1].

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

Механизм компиляции и компоновки программы на языке C требует, помимо наличия откомпилированного библиотечного модуля, присутствия заголовочных файлов (h-файлов), содержащих объявления структур данных и прототипы функций, предоставляемых библиотекой.

Среда Visual Studio 2010 использует расширение .lib для библиотечных модулей. При создании статически подключаемой библиотеки в среде Visual Studio 2010 необходимо выполнить следующую последовательность действий: разработать новый проект (пункты главного меню: FileNewProject), выбрать тип проекта в списке Project types: Win32Win32Project и задать имя проекта, например containers. При необходимости можно указать место его расположения, используя кнопку Browse. В результате должна получиться форма, показанная на рис.20.1.

Р ис.20.1. Окно создания проекта с подключаемой библиотекой

Далее следует нажать кнопку OK. Появится форма с заголовком «Win32 Application Wizard – containers».

На закладке Application Settings мастера создания проекта нужно сделать следующие настройки:

• установить Application type (тип приложения) в Static Library (статическая библиотека);

• снять флажок с пункта Precompiled header (прекомпилированный заголовок).

После установки настроек появится форма (рис.20.2), которая представляет собой пустой проект статической библиотеки.

Р ис.20.2. Настройка приложения статической библиотеки

Для завершения настройки закладки Application Settings следует нажать кнопку Finish. Появится форма, показанная на рис.20.3.

Р ис.20.3. Окно пустого проекта для статической библиотеки

Добавление файлов в проект библиотеки производится стандартным образом, как и для проекта Win32 Console Application. В соответствии с рис.20.3 существующие файлы, которые будут использоваться в многофайловом проекте, могут быть подключены при установке курсора мыши на папках HeaderFiles, ResourceFiles, SourceFiles с последующим нажатием правой клавиши и выбором пункта меню Add, а именно Existing Item.

Для подключения h-файлов(*.h) следует обратиться к папке проекта HeaderFiles, для с-файлов, (*.с,) использовать папку SourceFiles.

Выполним подключение существующих файлов stack.h/stack.c, queue.h/queue.c, реализующих в простейшем виде две важные структуры данных – стек и очередь.

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

После подключения файлов получится форма с открытой программой файла stack.h (рис.20.4).

Р ис.20.4. Окно проекта статической библиотеки с подключенными

файлами

До выполнения компиляции необходимо произвести настройку параметров компилятора так же, как и для проекта Win32 Console Application. В частности, из пункта меню Project следует выбрать containersProperties (Alt+F7). После раскрытия узла Configuration Properties появится форма, показанная на рис.20.5.

Р ис.20.5. Обращение к странице свойств проекта

Сначала нужно обратиться к пункту General, затем – к закладке CharacterSet, в которой выбрать UseMulty-ByteCharacterSet (как и при настройке консольного приложения). Далее необходимо раскрыть узел С/С++, в котором обратиться к закладке CodeGeneration, затем в другой панели закладка EnableC++Exceptions устанавливается в положение No (как и при настройке консольного приложения).

Результат установки свойств закладки Language представлен на рис.20.6.

Р ис.20.6. Установка свойств закладки Language

Режим работы языка С в MSVisualStudio устанавливается на закладке Advanced (рис.20.7).

Р ис.20.7. Результат выбора компиляции языка С

Важным моментом, на который требуется обратить внимание, является версия используемой библиотеки времени выполнения (runtime library). Библиотека времени выполнения содержит функции стандартной библиотеки языка С, а также некоторое вспомогательное окружение, которое позволяет программе, написанной на языке С, выполняться в ОС Windows. Версии библиотеки времени выполнения для статически подключаемой библиотеки и для программы, ее использующей, должны совпадать. Поэтому статически подключаемую библиотеку часто компилируют в различных конфигурациях, каждая из которых использует свою версию библиотеки времени выполнения. В примере будем использовать многопоточную отладочную версию библиотеки, подключаемую к программе динамически (Multi-threaded Debug DLL) для отладочной сборки библиотеки, и многопоточную версию, подключаемую динамически (Multi-threaded DLL), для конечной версии программы.

Тип используемой библиотеки времени выполнения выбирается на странице свойств [C/C++]|[CodeGeneration]|[RuntimeLibrary]. Он должен совпадать с типом, выбранным при настройке свойств библиотеки, в данном случае Multy-Threaded Debug DLL(\MDd).

Результат выбора типа библиотеки показан на рис.20.8 (по умолчанию).

Р ис.20.8. Установка типа библиотеки времени выполнения

Подключение программных файлов осуществляется обычными средствами, рассмотренными, например, в предыдущей теме. Программный код каждого из подключенных файлов можно вывести (двойным щелчком мыши) в окно редактирования. Для примера выведем код файла stack.h. Результат подключения файлов stack.h/stack.c и queue.h/queue.c, показан на рис. 20.9.

Р ис. 20.9. Форма с подключенными файлами

После выполнения настроек компилятора необходимо выполнить настройки библиотекаря (Librarian) на вкладке после узла С/С++. Страница свойств библиотекаря содержит несколько настроек, из которых основной является имя создаваемой библиотеки. По умолчанию имя библиотеки совпадает с именем проекта. В этом случае следует оставить без изменения имеющиеся настройки закладки General узла Librarian. На закладке General в пункте Output File по умолчанию установлено $OutDir$(TargetName)$(TargetExt), что оставляем без изменения.

Открывающаяся страница свойств представлена на рис. 20.10.

Р ис.20.10. Страница свойств Librarian–General – Output File

Настройка свойств Librarian завершается нажатием клавиш «Применить» и «OK».

После осуществления всех настроек выполняется компиляция и сборка библиотеки. В процессе компиляции модули, входящие в состав библиотеки (файлы с расширением .c), сначала обрабатываются препроцессором языка C, затем компилируются независимо друг от друга. В результате получается набор файлов с расширением .obj, содержащих скомпилированный код библиотечных функций. Затем полученный набор объектных файлов (с расширением .obj) объединяется в библиотечный модуль (файл с расширением .lib).

Процесс сборки проекта статической библиотеки запускается из пункта меню Build  Buildcontainers. Результат выбора показан на рис.20.11.

Р ис.20.11. Запуск компиляции и сборки библиотеки

В процессе сборки библиотеки компилятор и библиотекарь (Librarian) выводят в окно сообщений (Output) среды Visual Studio диагностическую информацию, содержащую результаты компиляции каждого из модулей, подключенных к проекту статической библиотеки, возможные предупреждения компилятора и конечную статистику (например, количество ошибок и предупреждений) сборки библиотеки (рис.20.12).

В результате произведенной компиляции получаем папку с именем созданной библиотеки (containers), где в папке Debug располагается двоичный объектный библиотечный модуль – файл с расширением .lib. Для данного случая это файл containers.lib.

Р ис.20.12. Окно с сообщением об успешной компиляции библиотеки

Программные коды подключаемых файлов

// file stack.h

#ifndef STACK_H__

#define STACK_H__

/// by default a stack reserves space for 16 items

#define STACK_INITIAL_CAPACITY 16

typedef struct stack {

/// number of items in the stack

int m_length;

/// capacity of the stack

int m_capacity;

/// block of memory for the stack

int *m_items;

} stack_t;

/// create a new stack and returns it

stack_t *stack_create (int capacity);

/// destroys the stack and frees resources

void stack_destroy (stack_t *stack);

/// pushes an item into the stack

int stack_push (stack_t *stack, int item);

/// pops the item from the stack

int stack_pop (stack_t *stack);

/// checks whether the stack is empty

int stack_is_empty (stack_t *stack);

#endif

// file stack.c

#include <assert.h>

#include <malloc.h>

#include <stddef.h>

#include "stack.h"

static int stack_ensure_capacity (stack_t *stack, int capacity)

{

int capacityDesired;

int *p;

if (stack->m_capacity >= capacity)

return 1;

capacityDesired = stack->m_capacity * 2;

p = realloc (stack->m_items, capacityDesired * sizeof (int));

if (!p)

return 0;

stack->m_items = p;

stack->m_capacity = capacityDesired;

return 1;

}

stack_t* stack_create (int capacity) {

stack_t *result;

if (capacity <= 0)

capacity = STACK_INITIAL_CAPACITY;

result = malloc (sizeof (stack_t));

if (!result)

return NULL;

result->m_items = malloc (capacity * sizeof (int));

if (!result->m_items) {

free (result);

return NULL;

}

result->m_capacity = capacity;

result->m_length = 0;

return result;

}

void stack_destroy (stack_t *stack)

{

assert (stack != NULL);

assert (stack->m_items != NULL);

free (stack->m_items);

free (stack);

}

int stack_push (stack_t *stack, int item)

{

assert (stack != NULL);

assert (stack->m_capacity > 0);

assert (stack->m_items != NULL);

if (!stack_ensure_capacity (stack, stack->m_length + 1))

return 0;

stack->m_items[stack->m_length++] = item;

return 1;

}

int stack_pop (stack_t *stack)

{

assert (!stack_is_empty (stack));

return stack->m_items[--stack->m_length];

}

int stack_is_empty (stack_t *stack)

{

assert (stack != NULL);

return stack->m_length <= 0;

}

// file queue.h

#ifndef QUEUE_H__

#define QUEUE_H__

typedef struct queue_item

{

/// pointer to the next item in the queue

struct queue_item *m_next;

/// item data

int m_item;

} queue_item_t;

typedef struct queue

{

/// number of items in the queue

int m_length;

/// first item in the queue

struct queue_item *m_head;

/// last items in the queue

struct queue_item **m_tailnext;

} queue_t;

/// creates a new queue and returns it

queue_t *queue_create ();

/// destroys the queue and frees resources

void queue_destroy (queue_t *queue);

/// pushes an item into the queue adding it to the queue's tail

int queue_push (queue_t *queue, int item);

/// pops the item from the queue, removing it from the queue's head

int queue_pop (queue_t *queue);

/// checks whether the queue is empty

int queue_is_empty (queue_t *queue);

#endif

// file queue.c

#include <assert.h>

#include <malloc.h>

#include <stddef.h>

#include "queue.h"

queue_t* queue_create ()

{

queue_t *queue;

queue = malloc (sizeof (queue_t));

if (!queue)

return NULL;

queue->m_head = NULL;

queue->m_tailnext = &(queue->m_head);

queue->m_length = 0;

return queue;

}

void queue_destroy (queue_t *queue)

{

queue_item_t *p;

assert (queue != NULL);

for (p = queue->m_head; p != NULL; p = p->m_next)

free (p);

free (queue);

}

int queue_push (queue_t *queue, int item)

{

queue_item_t *p;

assert (queue != NULL);

assert (queue->m_tailnext != NULL);

// create new queue item and insert it into tail

p = malloc (sizeof (queue_item_t));

if (!p)

return 0;

p->m_next = NULL;

p->m_item = item;

*queue->m_tailnext = p;

queue->m_tailnext = &(p->m_next);

++queue->m_length;

return 1; }

int queue_pop (queue_t *queue) {

queue_item_t *p;

assert (!queue_is_empty (queue));

// detach head and return the item

p = queue->m_head;

if (p) {

int item = p->m_item;

queue->m_head = p->m_next;

// if the last one was removed than

// we should reset our tail

if (queue->m_tailnext == &(p->m_next))

queue->m_tailnext = &(queue->m_head);

free (p);

--queue->m_length;

assert (queue->m_length >= 0);

return item;

}

assert (1 != 1);

// should not happen

return 0;

}

int queue_is_empty (queue_t *queue)

{

assert (queue != NULL);

return queue->m_length <= 0;

}

Для работы с библиотекой следует подготовить проект с главной функцией main(), в которой подключаются файлы, расположенные в созданной статической библиотеке, с помощью директивы #include. Для подключаемых файлов необходимо указать путь, где они расположены. Обычно это делается с помощью нотации "..\..\stack.h", которая указывает, что файл stack.h находится на два уровня выше, чем функция main(), в которой он будет использоваться.

Настройка проекта с главной функцией main() выполняется при установке режима компиляции языка С системы MS Visual Studio 2010. Для этого в меню системы MS Visual Studio последовательно выбирается File  New  Project. Далее из списка типа проекта Projecttypes также последовательно выбираются VisualC++Win32 Win32ConsoleApplication. В поле Name прописывается имя проекта, например Lab20. Далее осуществляется настройка проекта в режиме компиляции языка С (см. тему 1).

При настройке параметров компилятора дополнительно необходимо указать компилятору пути к заголовочным файлам stack.h и queue.h, содержащим объявления интерфейса созданной библиотеки containers. Это можно сделать в пункте AdditionalIncludeDirectories (дополнительные каталоги с заголовочными файлами) на странице свойств [C/C++]|[General]. Затем указывается путь к папке containers, в которой находятся библиотечные файлы stack.h/stack.с и queue.h/queue.с в виде ..\..\containers\ containers.

Форма с установкой пути к созданной статической библиотеке показана на рис. 20.13.

Р ис.20.13. Установка пути к файлам созданной библиотеки

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

На странице свойств [Linker]|[Input] необходимо указать путь к объектному файлу библиотеки. Форма с установкой свойств компоновщика показана на рис.20.14.

Р ис.20.14. Настройка компоновщика Linker–Input–Additional 

Dependencies

После выполнения всех настроек можно компилировать программу и запускать ее на выполнение.

Проект с главной функцией main() и включенными заголовочными файлами из созданной библиотеки представлен на рис.20.15.

Р ис.20.15. Форма с откомпилированным проектом

Программный код главной функции проекта

#include <stdio.h>

#include <conio.h>

#include "..\..\stack.h"

#include "..\..\queue.h"

int main (void)

{

int i;

queue_t *q = queue_create();

stack_t *s = stack_create(-1);

for (i = 0; i < 16; ++i) // заполнение стека

stack_push (s, i);

printf("\n Stack content:\n");

while (!stack_is_empty (s))

printf (" %3d\n", stack_pop (s));

stack_destroy (s); // разрушение стека

for (i = 0; i < 14; ++i) // заполнение очереди

queue_push (q, i);

printf("\n Queue content:\n");

while (!queue_is_empty (q))

printf (" %3d\n", queue_pop (q));

queue_destroy (q); // разрушение очереди

printf("\n\n Press any key: ");

_getch(); return 0; }

Р езультат выполнения программы приведен на рис.20.16.

Рис.20.16. Результат выполнения программы с файлами из библиотеки

ПРАКТИЧЕСКАЯ ЧАСТЬ

Пример1. Разработать библиотечную функцию для симметричного представления одномерного массива данных относительно первого значения. Например, пусть дан исходный одномерный массив

3 5 1 8 12 21 25.

Результат симметричного представления:

25 21 12 8 1 5 3 5 1 8 12 21 25.

Программный код решения примера состоит из двух файлов

// Файл основного модуля проекта main.c

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include "xyx.h"

int main (void) {

int i, n = 7;

int M[] = {3, 5, 1, 8, 12, 21, 25};

printf("\n Initial array:\n");

for (i = 0; i < n; ++i)

printf(" %3d", M[i]);

printf("\n\n New array:\n");

for (i = 0; i < (2*n-1); ++i)

printf(" %3d", *(xyx(M, n)+i));

printf("\n\n Press any key: ");

_getch();

return 0;

}

// Подключаемый заголовочный файл xyx.h

// file xyx.h

int *xyx(int M[], int n);

// Подключаемый файл xyx.c

#include <stdlib.h>

int *xyx(int M[], int n) {

int j, p = 2*n - 1;

int *PTR;

PTR = (int *)calloc(p,sizeof(int));

for (j = 0; j < p; ++j)

PTR[j] = 0;

for (j = 0; j < p; ++j)

if (j < n)

PTR[j] = M[(n-1) - j];

else

PTR[j] = M[j - (n-1)];

return PTR; }

Р езультат выполнения программы показан на рис.20.17.

Рис.20.17. Результат симметричного преобразования массива

Задание1

1. К проекту подключите статическую библиотеку с файлами xyx.h, xyx.c. Осуществите сборку проекта из приведенных файлов.

2. Предусмотрите ввод чисел массива с клавиатуры.

3. Напишите функцию типа xyx(), которая обрабатывает одномерные символьные массивы данных.

4. Видоизмените программу для преобразования массива с действительными числами, которые формируются случайным образом из данного интервала [–2X;2X], где Х – номер компьютера, на котором выполняется лабораторная работа.

5. Разработайте функцию сортировки чисел массива, поместите ее в статическую библиотеку и используйте для сортировки заданного массива по убыванию в соответствии с предыдущим пунктом задания. После сортировки произведите преобразование массива с помощью созданной библиотечной функции xyx().

Пример 2. Разработать абстрактный тип данных – двоичное дерево поиска. Выполнить вставки узлов в двоичное дерево случайными числами и произвести обход дерева с порядковой выборкой [2]. Созданные функции заполнения и обхода двоичного дерева поместить в статическую библиотеку.

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

Двоичное дерево поиска (с неповторяющимися значениями в узлах) устроено так, что значения в любом левом поддереве меньше, а значения в любом правом поддереве больше, чем значение в родительском узле [2]. На рис.20.18 изображена схема двоичного дерева поиска с 12 значениями.

Р ис. 20.18. Пример двоичного дерева поиска

В программах, реализующих стеки, очереди, деревья и т.д., используются автореферентные структуры (self-referential), которые содержат в качестве элемента указатель, ссылающийся на структуру того же типа.

Например, определение

struct node { int data; struct node *nextPtr; };

описывает тип struct node. Элемент nextPtr указывает на структуру типа struct node – структуру того же самого типа, что и объявленная, т.е. структура ссылается сама на себя.

Для заданного примера используем целые случайные числа из интервала от 0 до 14.

Программный код решения примера состоит из трех файлов

// Файл основного модуля проекта main.c

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <time.h>

#include <locale.h>

//#include "tree.h"

#define N 10 // количество случайных чисел - узлов

#define R 15 // случайные числа от 0 до R-1

// Автореферентная структура

struct treeNode {

struct treeNode *LeftPtr; //для левого поддерева

int data;

struct treeNode *RightPtr; // для правого поддерева

};

typedef struct treeNode TreeNode;

typedef TreeNode *TreeNodePtr;

// Прототипы функций

void insertNode (TreeNodePtr *treePtr, int value);

void inOrder(TreeNodePtr treePtr);

int main (void) {

int i;

int item;

time_t tic;

TreeNodePtr rootPtr = NULL; // пустое дерево

setlocale(LC_ALL, ".1251"); // русские шрифты

srand((unsigned) time(&tic)); // рандомизация случайных чисел

printf("\n Числа двоичного дерева:\n");

// Размещение в дереве случайных значений от 0 до (R-1)

for (i = 1; i <= N; ++i) {

item = rand() % R;

printf(" %4d", item);

insertNode (&rootPtr, item);

}

// Обход дерева с порядковой выборкой

printf("\n");

printf("\n Результат обхода дерева с порядковой выборкой:\n");

inOrder(rootPtr); // вызов функции

printf("\n\n Нажмите любую клавишу (Press any key): ");

_getch();

return 0;

}

// Функция insertNode()

// Вставка узла в дерево

void insertNode (TreeNodePtr *treePtr, int value) {

if (*treePtr == NULL) {

*treePtr = malloc(sizeof(TreeNode));

// Присвоение данных

if (*treePtr != NULL) {

(*treePtr)->data = value;

(*treePtr)->LeftPtr = NULL;

(*treePtr)->RightPtr = NULL;

}

else {

printf(" %d не вставлено. Нет памяти.\n", value);

}

}

else { //когда дерево не пусто

if ( value < (*treePtr)->data )

insertNode (&( (*treePtr)->LeftPtr), value);

else if( value > (*treePtr)->data )

insertNode (&( (*treePtr)->RightPtr), value);

else

printf("Дубл."); // Дубликаты значений в узлах дерева

}

}

// Функция inOrder()

// Обход дерева с порядковой выборкой

void inOrder (TreeNodePtr treePtr)

{

if (treePtr != NULL) {

inOrder(treePtr->LeftPtr);

printf(" %4d", treePtr->data);

inOrder(treePtr->RightPtr);

}

}

Функции insertNode(), inOrder() используются рекурсивно, т.е. вызывают сами себя из тела функции.

В теле функции inOrder() нужно выполнить следующие шаги:

1. обойти вызовом inOrder() левое поддерево;

2. обработать значение в узле;

3. обойти вызовом inOrder() правое поддерево.

Обход двоичного дерева поиска вызовом функции inOrder() выдает значения в узлах в возрастающем порядке. Процесс создания двоичного дерева поиска фактически сортирует данные, поэтому называется сортировкой двоичного дерева [2].

В озможный результат работы программы показан на рис.20.19.

Рис.20.19. Пример обхода двоичного дерева

Задание 2

1. Функции заполнения и обхода двоичного дерева поместите в статическую библиотеку. Выполните настройки проекта с подключаемой статической библиотекой.

2. Напишите программу с использованием вещественных чисел, помещаемых в узлы двоичного дерева. Случайные числа (значения узлов дерева) задайте из интервала [–2X,2X], где Х – номер компьютера, на котором выполняется лабораторная работа.

3. Увеличьте число узлов дерева до 11Х, где Х – номер компьютера, на котором выполняется лабораторная работа. Результат выполнения программы запишите в текстовый файл вида treeX.txt, где Х – первая буква фамилии пользователя.