Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
 Скачать 1.25 Mb.
|
|
Деревья Дерево – одна из наиболее распространённых структур данных, используемых в программировании. Формально дерево определяется рекурсивно следующим образом: это конечное множество Т, состоящее из одного или более узлов таких, что: 1. Имеется один узел, называемый корнем дерева. 2. Остальные узлы, исключая корень, содержатся в m≥0 попарно непересекающихся множествах Т 1 , Т 2 ,….Т m , каждое из которых в свою 162 очередь является деревом. При этом деревья Т 1 , Т 2 ,….Т m называются поддеревьями (потомками) данного корня. Поддеревья некоторой вершины еще иногда называют кустами, а конечные вершины дерева из которых больше не выходит ни одной связи (т.е. для такого узла m=0), называют листьями. Наиболее распространены в программировании бинарные (двоичные) деревья, в которых каждый узел может иметь не более двух потомков. Рекурсивное определение бинарного дерева задает его как корень и два бинарных поддерева: левое и правое, – причем любое из них может быть пустым. Бинарные деревья используются как структура данных в том случае, когда в каждой точке процесса должно быть принято одно из двух возможных решений. Например, они применяются для синтаксического анализа, поиска, сортировки, управления базами данных и в других приложениях. Пример 37. Приведем пример бинарного дерева (рис.44), которое может использоваться для вычисления алгебраического выражения (A*B+C*D)/(B*C), если двигаться от листьев дерева к корню. Бинарные деревья наиболее часто используются в программировании. Это основывается на том факте, что любое дерево может быть приведено к бинарному. Основное правило такого преобразования: левая ветвь каждого узла соединяет его с первым узлом следующего уровня, а правая – с другими узлами следующего уровня (братьями). Рис.45 демонстрирует первый шаг преобразования дерева A к его бинарному представлению. На втором шаге тоже самое делается с поддеревом B и т.д. 163 / + * * * B C B C A D Рис.44. Пример бинарного дерева Рис.45. Шаг преобразования дерева к бинарному Бинарное дерево на языке Си может быть описано следующими структурами данных: struct tree { int info; //информационное поле tree ltree,rtree; //указатели на левое и правое поддерево } К бинарным деревьям применяют следующие типовые операции: 1. Создание нового бинарного дерева, состоящего из одного узла с информационным полем . 2. Создание нового левого или правого «сына» (узла) для текущего узла. 3. Чтение информационного содержимого узла. 4. Определение указателя на левое или правое поддерево. 5. Удаление куста или листа дерева. 6. Удаление левого или правого поддерева для узла. 7. Обход дерева. 8. Сравнение деревьев. 9. Соединение деревьев. Пример 40. Рассмотрим реализацию основных процедур и функции для работы с деревьями. tree MakeTree(tree node, int x) { if(node.value == NULL) { tree* p = new tree; B 1 B 2 B N A . . . B 1 B 2 B N A B B 3 . . . 164 ⇒ p->value = x; node = *p; } else { if((node).value > x) MakeTree(*node.pleft, x); else MakeTree(*node.pright, x); } return node; } void SetLeft (tree *p,int x) // создание левого сына для узла с указателем p { *p->ltree = NewNode(x); } void SetRight(tree *p,int x) // создание правого сына для узла с указателем p { *p->rtree = NewNode(x); } int GetInfo (tree *p) // чтение значения информационного поля узла p { if (p != NULL) return p->info; else return(0); } tree GetLeftTree (tree *p) // выдать значение указателя на левое поддерево // узла p { if (p != NULL) return *p->ltree; //else return(NULL); } tree GetRightTree (tree *p) //выдать значение указателя на правое поддерево // узла p { if (p != NULL) return *p->ltree; // else return (tree)NULL; } void DelLeaf (tree *p) // Удалить в дереве «лист» { if (p != NULL) free(p); } Рассмотрим более подробно задачу обхода дерева. Обход дерева – это последовательный обход всех узлов дерева. Фактически во время обхода нужно составить список всех узлов дерева. Поскольку дерево по определению является рекурсивной структурой данных, то и обход дерева как правило осуществляется рекурсивно. Существует три способа рекурсивного обхода бинарного дерева: обход с префиксным порядком; обход с инфиксным порядком; обход с суффиксным (или постфиксным) порядком. 165 Префиксный порядок обхода дерева определяется в виде списка узлов следующим образом: Если дерево не пусто, то префиксный порядок это: 1. Корень дерева. 2. Узлы левого поддерева в префиксном порядке. 3. Узлы правого поддерева в префиксном порядке. Например, пусть дано дерево, указанное вна рис. примере 48, тогда префиксный обход дерева это следующая последовательность узлов: / +*AB*CD*BC. Иногда префиксный порядок называют обходом дерева сверху вниз. Инфиксный порядок обхода дерева определяется в виде списка узлов следующим образом: Если дерево не пусто, то инфиксный порядок это: 1. Узлы левого поддерева в инфиксном порядке. 2. Корень дерева. 3. Узлы правого поддерева в инфиксном порядке. Для нашего примера это будет: A*B+C*D/B*C Суффиксный порядок обхода дерева определяется в виде списка узлов следующим образом: Если дерево не пусто, то суффиксный порядок это: 1. Узлы левого поддерева в суффиксном порядке. 2. Узлы правого поддерева в суффиксном порядке. 3. Корень дерева. Для нашего примера это будет: AB*CD*+BC*/. Суффиксный порядок обхода иногда называют обходом дерева снизу вверх. Заметим, что инфиксный порядок обхода бинарного дерева в нашем примере совпал с самим алгебраическим выражением, только без скобок, суффиксный порядок – совпал с ОПЗ выражения, а результат префиксного обхода является обратным инфиксному, т.е. сначала указывается операция, затем операнды, – именно так записываются функции и процедуры на языке Паскаль. 166 С обходом дерева как правило совмещаются некоторые действия над проходимой вершиной. Например, в случае суффиксного обхода, можно совместить обход с операцией удаления куста дерева. void PrefixObhod (tree *p) { if (p !=NULL) // Если дерево не пусто, то префиксный порядок это: { printf ("%d", p->info); //обработка узла, например напечатем его инф.часть PrefixObhod (p->ltree); // Узлы левого поддерева в префиксном порядке PrefixObhod (p->rtree); // Узлы правого поддерева в префиксном порядке } } void InfixObhod (tree *p) { if (p != NULL) // Если дерево не пусто, то инфиксный порядок это: { InfixObhod (p->ltree); // Узлы левого поддерева в инфиксном порядке printf ("%d", p->info); //обработка узла, например напечатем его инф.часть InfixObhod (p->rtree); // Узлы правого поддерева в инфиксном порядке } } void DelSubTree (tree *p) //процедура удаление куста p с использованием суффиксного обхода { if (p != NULL) // Если дерево не пусто, то суффиксный порядок это: { DelSubTree (p->ltree); // Узлы левого поддерева в суффиксном порядке DelSubTree (p->rtree); // Узлы правого поддерева в суффиксном порядке free(p); //обработка узла, например удалим узел } } void DelLeftTree (tree *p) //удаление левого поддерева для узла p { if (p != NULL) { DelSubTree (p->ltree); p->ltree = NULL; } } void DelRightTree (tree *p) //удаление правого поддерева для узла p { if (p != NULL) { DelSubTree (p->rtree); p->ltree = NULL; } } Сравнение деревьев производится путём сравнения информационной части (информационных полей) соответствующих деревьев, начиная с корня. Функция должна сравнивать информационные части узлов дерева, а далее рекурсивно 167 сравнивать левые и правые поддеревья. Фактически функция осуществляет обход дерева сверху вниз. Выходом из рекурсии в данном случае будет сравнение значений указателей (в том числе и пустых). Для равных деревьев одновременно указатели будут обнулены и станут равными. В случае различия, это равенство не пройдет. Если же оба указателя отличны от пустых, т.е. указывают на поддеревья, то сравниваются их информационные части и соответственно левые и правые потомки. Если все эти три сравнения совпадают, то делается заключение о совпадении сравниваемых деревьев. Напишем функцию, которая будет выдавать истинное значение, если два дерева равны, и ложное значение в противном случае. bool TreeEqual(tree *p1, tree *p2) { if (p1 == p2) return true; else if ((p2 != NULL) && (p1 != NULL)) return ((p1->info = p2->info) && TreeEqual(p1->ltree, p2->ltree) && TreeEqual(p1->rtree, p2->rtree)); else return false; } Приложение 1. Стандартные библиотеки языка Си В языке Си стандартные функции собраны в различных библиотеках. Для использования этих функций необходимо подключить к проекту соотаетствующие библиотеки с помощью конструкции #include. Ниже представлены некоторые библиотеки языка Си, а также их состав. Таблица 19. Библиотеки языка Си Имя Назначение библиотеки complex.h Набор функций для работы с комплексными числами ctype.h Содержит функции, используемые для классификации символов по их типам или для конвертации между верхним и нижним регистрами независимо от используемой кодировки errno.h Для проверки кодов ошибок, возвращаемых библиотечными функциями iostream Содержит функции контроля чтения и записи стандартных потоков limits.h Содержит заранее заданные константы, определяющие специфику реализации свойств целых типов signal.h Функции для управления различными исключительными условиями math.h Функции для вычисления основных математических функций stdio.h Реализует основные возможности ввода и вывода в языке Си stdlib.h Вспомогательные функции, которые могут быть использованы в разнообразных программах string.h Для работы с различными видами строк 168 time.h Для конвертации между различными форматами времени и даты Таблица 20. Состав библиотеки complex.h Имя функции Описание cabs, cabsf, cabsl Абсолютное значение комплексного числа cacos, cacosf, cacosl Комплексный арккосинус cacosh, cacoshf, cacoshl Комплексный гиперболический арккосинус carg, cargf, cargl Аргумент комплексного числа casin, casinf, casinl Комплексный арксинус casinh, casinhf, casinhl Комплексный гиперболический арксинус catan, catanf, catanl Комплексный арктангенс catanh, catanhf, catanhl Комплексный гиперболический арктангенс ccos, ccosf, ccosl Комплексный косинус ccosh, ccoshf, ccoshl Комплексный гиперболический косинус cexp, cexpf, cexpl Комплексная экспонента cimag, cimagf, cimagl Мнимая часть комплексного числа clog, clogf, clogl Натуральный логарифм комплексного числа conj, conjf, conjl Комплексное сопряжённое число cpow, cpowf, cpowl Степень комплексного числа cproj, cprojf, cprojl Проекция на римановскую сферу creal, crealf, creall Действительная часть комплексного числа csin, csinf, csinl Комплексный синус csinh, csinhf, csinhl Комплексный гиперболический синус csqrt, csqrtf, csqrtl Комплексный квадратный корень ctan, ctanf, ctanl Комплексный тангенс ctanh, ctanhf, ctanhl Комплексный гиперболический тангенс Таблица 21. Состав библиотеки ctype.h Имя функции Проверяет, является ли аргумент… isalnum …буквой или цифрой isalpha …буквой iscntrl …управляющим символом isdigit …цифрой isgraph …символом, имеющим графическое представление islower …буквой в нижнем регистре isprint …символом, который может быть напечатан ispunct …символом, имеющим графическое представление, но не являющимся при этом буквой или цифрой isspace …разделительным символом isupper …буквой в верхнем регистре isxdigit …цифрой шестнадцатиричной системы счисления Таблица 22. Состав библиотеки errno.h Имя функции Описание E2BIG Список аргументов слишком длинный EACCES Отказ в доступе EAGAIN Ресурс временно недоступен EBADF Неправильный дескриптор файла EBADMSG Неправильное сообщение 169 EBUSY Ресурс занят ECANCELED Операция отменена ECHILD Нет дочернего процесса EDEADLK Обход тупика ресурсов EDOM Ошибка области определения EEXIST Файл существует EFAULT Неправильный адрес EFBIG Файл слишком велик EINPROGRESS Операция в процессе выполнения EINTR Прерванный вызов функции EINVAL Неправильный аргумент EIO Ошибка ввода-вывода EISDIR Это каталог EMFILE Слишком много открытых файлов EMLINK Слишком много связей EMSGSIZE Неопределённая длина буфера сообщения ENAMETOOLONG Имя файла слишком длинное ENFILE Слишком много открытых файлов в системе ENODEV Нет такого устройства ENOENT Нет такого файла в каталоге ENOEXEC Ошибка формата исполняемого файла ENOLCK Блокировка недоступна ENOMEM Недостаточно памяти ENOSPC Памяти на устройстве не осталось ENOSYS Функция не реализована ENOTDIR Это не каталог ENOTEMPTY Каталог непустой ENOTSUP Не поддерживается ENOTTY Неопределённая операция управления вводом-выводом ENXIO Нет такого устройства или адреса EPERM Операция не разрешена EPIPE Разрушенный канал ERANGE Результат слишком велик EROFS Файловая система только на чтение ESPIPE Неправильное позиционирование ESRCH Нет такого процесса ETIMEDOUT Операция задержана EXDEV Неопределённая связь Таблица 23. Состав библиотеки iostream.h Имя функции Описание cin Соответствует стандартному вводу. В общем случае он позволяет читать данные с терминала пользователя cout Соответствует стандартному выводу. В общем случае он позволяет выводить данные на терминал пользователя cerr Соответствует стандартному выводу для ошибок. В этот поток мы направляем сообщения об ошибках программы Таблица 24. Состав библиотеки limits.h 170 Имя Описание Типичное значение 32- битной программы Типичное значение 64- битной программы Стандартный минимум или максимум диапазона значений CHAR_BIT Число бит в байте 8 8 ≥ 8 SCHAR_MIN Минимальное значение для знакового char −128 −128 ≤ -127 SCHAR_MAX Максимальное значение для знакового char +127 +127 ≥ +127 UCHAR_MAX Максимальное значение для беззнакового char +255 +255 ≥ +255 CHAR_MIN Минимальное значение для char −128 −128 ≤ -127(если char представлено как знаковый char; иначе 0) CHAR_MAX Максимальное значение для char +127 +127 ≥ +127 (если char представлено как знаковый char; иначе +255) MB_LEN_MAX Максимальная многобайтовая длина символа по всем локалям различается, обычно от 4 различается, обычно от 4 ≥ 1 SHRT_MIN Минимальное значение для short int −32,768 −32,768 ≤ -32,767 SHRT_MAX Максимальное значение для short int +32,767 +32,767 ≥ +32,767 USHRT_MAX Максимальное значение для беззнакового short int +65,535 +65,535 ≥ +65,535 INT_MIN Минимальное значение для int −2,147,483,648 −2,147,483,648 ≤ -32,767 INT_MAX Максимальное значение для int +2,147,483,647 +2,147,483,647 ≥ +32,767 UINT_MAX Максимальное значение для беззнакового int +4,294,967,295 +4,294,967,295 ≥ +65,535 LONG_MIN Минимальное значение для long int −2,147,483,648 −9,223,372,036,854 ,775,808 ≤ -2,147,483,647 LONG_MAX Максимальное значение для long int +2,147,483,647 +9,223,372,036,854 ,775,807 ≥ +2,147,483,647 ULONG_MAX максимальное значение для беззнакового long int +4,294,967,295 +18,446,744,073,70 9,551,615 ≥ +4,294,967,295 LLONG_MIN Минимальное значение для long long int −9,223,372,036,85 4,775,808 −9,223,372,036,854 ,775,808 ≤ -9,223,372,036,854,775,807 LLONG_MAX Максимальное значение для long long int +9,223,372,036,85 4,775,807 +9,223,372,036,854, 775,807 ≥ +9,223,372,036,854,775,807 |