- •Предисловие
- •Библиографический список
- •Контрольные вопросы
- •Библиографический список
- •Тема 2 Переменные и базовые типы данных языка с
- •Контрольные вопросы
- •Библиографический список
- •Тема3 Организация циклов в языке с
- •Контрольные вопросы
- •Библиографический список
- •Тема 4 Принятие решений. Условные операторы в языке с
- •Контрольные вопросы
- •Библиографический список
- •Тема 5 Числовые массивы в языке программирования с
- •Тип имя_массива[размер];
- •Тип имя_массива[размер1] [размер2];
- •Тип имя_массива[размер1] [размер2] [размерN];
- •Контрольные вопросы
- •Библиографический список
- •Тема 6 Символьные массивы в языке с. Работа со строками
- •Тип имя_массива[размер];
- •Тип имя_массива[размер1] [размер2];
- •Тип имя_массива[размер1] [размер2] [размерN];
- •Контрольные вопросы
- •Библиографический список
- •Тема 7 Указатели в языке программирования с
- •Int *ptr; // объявили указатель на целую переменную
- •Контрольные вопросы
- •Библиографический список
- •Тема 8 Указатели и массивы в языке с
- •Int data[7]; // обычный массив
- •Int *pd[7]; // массив указателей
- •Контрольные вопросы
- •Библиографический список
- •Тема 9 Динамическое распределение памяти в языке с
- •If (!ptr) // условие логического отрицания
- •If (!ptr) // условие логического отрицания
- •Контрольные вопросы
- •Библиографический список
- •Тема 10 Функции Общие сведения о функциях языка с
- •Fun(тип имя_перем1, тип имя_перем2, , тип имя_перем n)
- •Контрольные вопросы
- •Библиографический список
- •Тема 11 Указатели и функции в языке программирования с
- •Тип_возвращаемый_функцией(*имя_указателя_на_функцию)(аргументы);
- •Контрольные вопросы
- •Библиографический список
- •Тема 12 Файловый ввод/вывод в языке с
- •Контрольные вопросы
- •Библиографический список
- •Тема 13 Структуры – производные типы данных языка с
- •Int age; // возраст
- •Int age; // возраст
- •Int age; // возраст
- •Int age; // возраст
- •Int age; // возраст
- •Int age; // возраст
- •Контрольные вопросы
- •Библиографический список
- •Тема 14 Объединения и перечислимые типы в языке с
- •Контрольные вопросы
- •Библиографический список
- •Тема 15 Структуры и функции языка с
- •Контрольные вопросы
- •Библиографический список
- •Тема 16 Операции с разрядами (битами) в языке с
- •Контрольные вопросы
- •Библиографический список
- •Тема 17 Программы, состоящие из нескольких файлов, на языке с
- •Спецификатор extern
- •Спецификатор static
- •Спецификатор register
- •Спецификатор auto
- •Контрольные вопросы
- •Библиографический список
- •Тема 18 Рекурсивные алгоритмы и функции
- •Переместить (a, b);
- •Контрольные вопросы
- •Библиографический список
- •Тема 19 Препроцессор языка с
- •Директива #define
- •Директива #error
- •Директива #include
- •Директивы условной компиляции
- •2_ Я_последовательность операторов программного кода
- •3_ Я_последовательность операторов программного кода
- •Директива #line
- •Директива#pragma
- •Предопределенные символические константы
- •Макрос подтвержденияassert
- •Контрольные вопросы
- •Библиографический список
- •Тема 20 Программы на языке с при использовании статически подключаемой библиотеки
- •Контрольные вопросы
- •Библиографический список
- •Тема 21 Использование аргументов командной строки в с
- •Контрольные вопросы
- •Контрольная работа № 2 Покупки в супермаркете
- •Приложение Управление конфигурациями проекта в Visual Studio 2010
Контрольные вопросы
Каково назначение препроцессора языка С?
Что такое условная компиляция, осуществляемая препроцессором? В каких целях она производится?
Какие Вы знаете операторы препроцессора? Для чего они используются?
Какие директивы препроцессора наиболее часто используются в программах, написанных на языке С?
Что такое макроопределение препроцессора? Как оно реализуется?
Библиографический список
Дорот В. Л.Толковый словарь современной компьютерной лексики / В. Л. Дорот, Ф. А. Новиков. – 2-е изд., перераб. и доп. – СПб. : БХВ-Петербург, 2001. – 512 с.
Керниган Б. У.Язык программирования С / Б. У. Керниган, Д. М. Ритчи. – 2-изд. – М. : Вильямс, 2007. – 304 с.
Шилдт Г. Полный справочник по С : пер. с англ. / Г. Шилдт. – 4-е изд. – М. : Вильямс, 2007. – 704 с.
Прата С. Язык программирования С. Лекции и упражнения : пер. с англ. / С. Прата. – 5-е изд. – М. : Вильямс, 2006. – 960 с.
ДейтелХ.М. Как программировать на С : пер. с англ. / Х. М. Дейтел, П. Дж. Дейтел. – 4-е изд. – М. : Бином-Пресс, 2006. – 912 с.
Тема 20 Программы на языке с при использовании статически подключаемой библиотеки
Cтавится задача создания и применения статической подключаемой библиотеки с помощьюMSVisualStudio2010, осуществления компиляции нескольких файлов, размещенных в ней.
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Библиотека представляет собой набор функций [1]. Когда программа обращается к библиотечной функции, редактор связей находит эту функцию и добавляет ее код в программу. Исполняемый файл содержит только те функции, которые используются программой, а не все библиотечные функции [1].
Библиотека называется статически подключаемой, если код, содержащийся в ней, непосредственно компонуется к основной программе. Такая библиотека содержит набор уже откомпилированных объектных файлов с функциями и данными. Библиотеки целесообразно применять для хранения функций, которые могут быть использованы при создании различных программ, реализующих распространенные алгоритмы и осуществляющих поддержку и обработку распространенных структур данных.
Механизм компиляции и компоновки программы на языке Cтребует, помимо наличия откомпилированного библиотечного модуля, присутствия заголовочных файлов (h-файлов), содержащих объявления структур данных и прототипы функций, предоставляемых библиотекой.
Среда Visual Studio 2010 использует расширение .libдля библиотечных модулей. При создании статически подключаемой библиотеки в среде Visual Studio 2010 необходимо выполнить следующую последовательность действий: разработать новый проект (пункты главного меню:FileNewProject), выбрать тип проекта в спискеProject types:Win32Win32Projectи задать имя проекта, напримерcontainers. При необходимости можно указать место его расположения, используя кнопкуBrowse. В результате должна получиться форма, показанная на рис.20.1.
Рис.20.1. Окно создания проекта с подключаемой библиотекой
Далее следует нажать кнопку OK. Появится форма с заголовком «Win32 Application Wizard – containers».
На закладке Application Settingsмастера создания проекта нужно сделать следующие настройки:
установить Application type(тип приложения) вStatic Library(статическая библиотека);
снять флажок с пункта Precompiled header(прекомпилированный заголовок).
После установки настроек появится форма (рис.20.2), которая представляет собой пустой проект статической библиотеки.
Рис.20.2. Настройка приложения статической библиотеки
Для завершения настройки закладки ApplicationSettingsследует нажать кнопкуFinish. Появится форма, показанная на рис.20.3.
Рис.20.3. Окно пустого проекта для статической библиотеки
Добавление файлов в проект библиотеки производится стандартным образом, как и для проекта Win32 Console Application. В соответствии с рис.20.3 существующие файлы, которые будут использоваться в многофайловом проекте, могут быть подключены при установке курсора мыши на папкахHeaderFiles,ResourceFiles,SourceFilesс последующим нажатием правой клавиши и выбором пункта менюAdd, а именноExisting Item.
Для подключения h-файлов(*.h) следует обратиться к папке проектаHeaderFiles, дляс-файлов, (*.с,) использовать папкуSourceFiles.
Выполним подключение существующих файлов stack.h/stack.c,queue.h/queue.c, реализующих в простейшем виде две важные структуры данных – стек и очередь.
Статическая библиотека является не исполняемой программой, а только механизмом для хранения подпрограмм, поэтому среди ее функций не должно быть функции main().
После подключения файлов получится форма с открытой программой файла stack.h (рис.20.4).
Рис.20.4. Окно проекта статической библиотеки с подключенными
файлами
До выполнения компиляции необходимо произвести настройку параметров компилятора так же, как и для проекта Win32 Console Application. В частности, из пункта меню Projectследует выбратьcontainersProperties(Alt+F7). После раскрытия узлаConfigurationPropertiesпоявится форма, показанная на рис.20.5.
Рис.20.5. Обращение к странице свойств проекта
Сначала нужно обратиться к пункту General, затем – к закладкеCharacterSet, в которой выбратьUseMulty-ByteCharacterSet(как и при настройке консольного приложения). Далее необходимо раскрыть узелС/С++, в котором обратиться к закладкеCodeGeneration, затем в другой панели закладкаEnableC++Exceptionsустанавливается в положениеNo(как и при настройке консольного приложения).
Результат установки свойств закладки Languageпредставлен на рис.20.6.
Рис.20.6. Установка свойств закладкиLanguage
Режим работы языка СвMSVisualStudioустанавливается на закладкеAdvanced(рис.20.7).
Рис.20.7. Результат выбора компиляции языкаС
Важным моментом, на который требуется обратить внимание, является версия используемой библиотеки времени выполнения (runtimelibrary). Библиотека времени выполнения содержит функции стандартной библиотеки языкаС, а также некоторое вспомогательное окружение, которое позволяет программе, написанной на языкеС, выполняться в ОС Windows. Версии библиотеки времени выполнения для статически подключаемой библиотеки и для программы, ее использующей, должны совпадать. Поэтому статически подключаемую библиотеку часто компилируют в различных конфигурациях, каждая из которых использует свою версию библиотеки времени выполнения. В примере будем использовать многопоточную отладочную версию библиотеки, подключаемую к программе динамически (Multi-threadedDebugDLL) для отладочной сборки библиотеки, и многопоточную версию, подключаемую динамически (Multi-threaded DLL), для конечной версии программы.
Тип используемой библиотеки времени выполнения выбирается на странице свойств [C/C++]|[CodeGeneration]|[RuntimeLibrary]. Он должен совпадать с типом, выбранным при настройке свойств библиотеки, в данном случае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в пунктеOutputFileпо умолчанию установлено$OutDir$(TargetName)$(TargetExt), что оставляем без изменения.
Открывающаяся страница свойств представлена на рис. 20.10.
Рис.20.10. Страница свойств Librarian–General – Output File
Настройка свойств Librarianзавершается нажатием клавиш «Применить» и «OK».
После осуществления всех настроек выполняется компиляция и сборка библиотеки. В процессе компиляции модули, входящие в состав библиотеки (файлы с расширением .c), сначала обрабатываются препроцессором языкаC, затем компилируются независимо друг от друга. В результате получается набор файлов с расширением.obj, содержащих скомпилированный код библиотечных функций. Затем полученный набор объектных файлов (с расширением.obj) объединяется в библиотечный модуль (файл с расширением.lib).
Процесс сборки проекта статической библиотеки запускается из пункта меню BuildBuildcontainers. Результат выбора показан на рис.20.11.
Рис.20.11. Запуск компиляции и сборки библиотеки
В процессе сборки библиотеки компилятор и библиотекарь (Librarian) выводят в окно сообщений (Output) средыVisualStudioдиагностическую информацию, содержащую результаты компиляции каждого из модулей, подключенных к проекту статической библиотеки, возможные предупреждения компилятора и конечную статистику (например, количество ошибок и предупреждений) сборки библиотеки (рис.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() выполняется при установке режима компиляции языкаСсистемыMSVisualStudio2010. Для этого в меню системыMSVisualStudioпоследовательно выбираетсяFile New Project. Далее из списка типа проектаProjecttypesтакже последовательно выбираютсяVisualC++Win32 Win32ConsoleApplication. В полеName прописывается имя проекта, напримерLab20. Далее осуществляется настройка проекта в режиме компиляции языкаС (см. тему 1).
При настройке параметров компилятора дополнительно необходимо указать компилятору пути к заголовочным файлам stack.hиqueue.h, содержащим объявления интерфейса созданной библиотекиcontainers. Это можно сделать в пункте AdditionalIncludeDirectories(дополнительные каталоги с заголовочными файлами) на странице свойств [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"); if (!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");
if (!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
К проекту подключите статическую библиотеку с файлами xyx.h,xyx.c. Осуществите сборку проекта из приведенных файлов.
Предусмотрите ввод чисел массива с клавиатуры.
Напишите функцию типа xyx(), которая обрабатывает одномерные символьные массивы данных.
Видоизмените программу для преобразования массива с действительными числами, которые формируются случайным образом из данного интервала [–2X;2X], где Х – номер компьютера, на котором выполняется лабораторная работа.
Разработайте функцию сортировки чисел массива, поместите ее в статическую библиотеку и используйте для сортировки заданного массива по убыванию в соответствии с предыдущим пунктом задания. После сортировки произведите преобразование массива с помощью созданной библиотечной функции 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()нужно выполнить следующие шаги:
обойти вызовом inOrder() левое поддерево;
обработать значение в узле;
обойти вызовом inOrder() правое поддерево.
Обход двоичного дерева поиска вызовом функции inOrder() выдает значения в узлах в возрастающем порядке. Процесс создания двоичного дерева поиска фактически сортирует данные, поэтому называетсясортировкой двоичного дерева[2].
Возможный результат работы программы показан на рис.20.19.
Рис.20.19. Пример обхода двоичного дерева
Задание2
Функции заполнения и обхода двоичного дерева поместите в статическую библиотеку. Выполните настройки проекта с подключаемой статической библиотекой.
Напишите программу с использованием вещественных чисел, помещаемых в узлы двоичного дерева. Случайные числа (значения узлов дерева) задайте из интервала [–2X,2X], где Х – номер компьютера, на котором выполняется лабораторная работа.
Увеличьте число узлов дерева до 11Х, где Х – номер компьютера, на котором выполняется лабораторная работа. Результат выполнения программы запишите в текстовый файл вида treeX.txt, где Х – первая буква фамилии пользователя.