- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •Int main() {
- •Эвристический алгоритм «ближайшего соседа»
- •Эвристический алгоритм «ближайших пар»
- •«Правильный» алгоритм поиска маршрута
- •Эволюция языка с bcpl → b → c → k&r c → ansi c → c99 → c1x
- •#Define имя текст_для_подстановки
- •123, 67543, 037, 07777, 0Xabf7, 0xffff, …
- •123456789L, 0xful (это просто число 15).
- •Определение символических констант в limits.H
- •Int lower, upper, step;
- •Int main() {
- •Int main() {
- •Int main() {
- •Всего операций: 47
- •If (условие) оператор
- •If (условие) оператор1 else оператор2
- •Int main() {
- •Int main() {
- •Int main() {
- •Int main() {
- •If (found)
- •Адресация памяти
- •Адреса объектов программы
- •Int fact(int n) {
- •О размерах участков памяти, выделяемых объектам
- •Правила адресной арифметики
- •Никакие другие операции к адресам неприменимы, т.Е. Адреса нельзя умножать, делить, складывать между собой и пр.
- •Имя массива – это константный указатель на его начало.
- •T X[] эквивалентно t *X
- •Int main() {
- •Void *calloc(size_t n, size_t r)
- •Void free(void *p)
- •Int main() {
- •Void *p;
- •Void swaps(char** a, char** b) {
- •Int main(void) {
- •Int main() {
- •Правило «право-лево»
- •Int pt_in_rect(struct point p, struct rect r) {
- •Int main() {
- •Int main() {
- •Int ival;
- •Void init(Vector*);
- •Void resize(Vector*, int);
- •Void push_back(Vector*, double);
- •Void push_s(Stack *st, double d) {
- •Void init_q(Queue *q) {
- •Void enqueue(Queue *q, double d) {
- •Int dequeue(Queue *q, double *d) {
- •Typedef struct Heap {Vector V;} Heap;
- •Void init_h(Heap *hp) {
- •Int Heap_Maximum(Heap *hp, double *z) {
- •Void Max_Heap_Insert(Heap *hp, double X){
- •Void Max_Heapify(Heap *hp, int I) {
- •Int l, r, largest;
- •Int Heap_Extract_Max(Heap *hp, double *z) {
- •Void Build_Max_Heap(Heap *hp) {
- •Void Insert_head_l1(List1 *l, double z) {
- •Void Insert_back_l1(List1 *l, double z) {
- •Int Extract_head_l1(List1 *l, double *z) {
- •Int Extract_back_l1(List1 *l, double *z) {
- •Void reverse_l1(List1 *l) {
- •Исходный код функции sort_l1
- •Void sort_l1(List1 *l) {
- •Void visit(List1* l) {
- •Void traverse(List1* l) {
- •Void Print_l1(List1 *l) {
- •Void Insert_l2(List2 *l, double z, int direction) {
- •Прямой обход (сверху вниз), при котором мы посещаем узел, а затем левое и правое поддеревья
- •Поперечный обход (слева направо), при котором мы посещаем левое поддерево, затем узел, а затем правое поддерево
- •Обратный обход (снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел.
- •Простой метод сортировки массива
- •Задача о взвешивании монет
- •1) Очевидно, что на последнем шаге процедуры взвешивания мы должны иметь дело максимум с 3 монетами, чтобы в при любом исходе взвешивания получить результат.
- •2) Задача предпоследнего шага – отобрать группу из 3-х монет. Это можно сделать, если в нашем распоряжении будет не более 9 монет (3 группы по 3 монеты).
- •3) Наконец, если у нас будет от 10 до 27 монет, мы сможем отобрать из них не более 9
- •Void mov(int n, char a, char c, char b) {
- •Int main() {
Void visit(List1* l) {
printf("%5.1f ", l->elem);
}
Void traverse(List1* l) {
if (l == NULL) return;
// visit(l); // печать списка в прямом направлении
traverse(l->next); // рекурсивный вызов
// visit(l); // печать списка в обратном направлении
}
Void Print_l1(List1 *l) {
if (l->next == NULL) printf("List is empty");
traverse(l->next);
printf("\n----------------\n");
}
Вопрос №89. Двунаправленный список: основные характеристики и внутреннее устройство.
Каждый узел двунаправленного списка содержит два указателя, один из которых – next указывает на «соседа» справа, а второй – prev – на «соседа» слева:
Определение структуры для двунаправленного списка и алгоритм его инициализации выглядят так:
typedef struct List2 {
double elem; struct List2 *prev, *next; } List2;
List2* init_L2() {
List2 *l = (List2*)calloc(1, sizeof(List2));
l->prev = l->next = NULL;
}
Вопрос №90. Циклический (кольцевой) список: основные характеристики и внутреннее устройство.
Двунаправленные списки на практике часто используются в форме кольцевых списков, вид которых иллюстрируется следующим рисунком:
Определение структуры для кольцевого списка и алгоритм его инициализации выглядят так:
typedef struct List2 {
double elem; struct List2 *prev, *next; } List2;
List2* init_L2() {
List2 *l = (List2*)calloc(1, sizeof(List2));
l->prev = l->next = l;
}
Вопрос №91. Алгоритм включения элемента в кольцевой список.
Использование фиктивного узла – ограничителя и наличие двух указателей в каждом узле позволяет существенно упростить задачу включения нового узла в кольцевой список и даже немного расширить возможности включения. Ниже представлен текст функции Insert_L2, которая выполняет включение нового узла как слева, так и справа от заданного узла, причем в качестве заданного узла может выступать и ограничитель.
Необходимость в специальных функциях «включить в начало» и «включить в хвост» отпадает, т.к. их заменяют вызовы универсальной функции Insert_L2 с параметрами «включить справа от ограничителя» и «включить слева от ограничителя» .
Void Insert_l2(List2 *l, double z, int direction) {
List2* p = (List2*)calloc(1, sizeof(List2));
p->elem = z;
if (direction < 0) { // включение слева
p->next = l; p->prev = l->prev;
l->prev = p; p->prev->next = p;
} else { //
p->next = l->next; p->prev = l;
l->next = p; p->next->prev = p;
}
}
На рисунке ниже приведена схема, объясняющая алгоритм включения элемента в кольцевой список:
p->next = l->next; p->prev = l;
l->next = p; p->next->prev = p;
Корневые деревья
Вопрос №92. Определение понятия «корневое дерево». Свойства корневых деревьев.
Понятие корневое дерево объединяет в себе различные «нелинейные» структуры данных, для узлов которых определены не только направления перемещения к другим узлам «вправо» и «влево», но и «вверх», «вниз-влево», «вниз-вправо» и др.
Общим признаком «древовидных» структур является наличие единственного корня – узла, для которого указатель «вверх» всегда равен NULL.
Узел корневого дерева, как и узел связанного списка, хранит «полезную» информацию и некоторое множество указателей, количество и назначение которых зависит от вида дерева.
Вопрос №93. Бинарное дерево: основные характеристики и внутреннее устройство.
Бинарное дерево – это разновидность корневого дерева, каждый узел которого (кроме корня) имеет единственного предка и не более двух потомков.
Вопрос №94. Алгоритм включение узла в бинарное дерево.
Рассмотрим две функции, позволяющие включить новый узел в бинарное дерево в качестве потомка заданного узла и последовательность их вызова для формирования примера.
Вопрос №95. Алгоритмы обхода бинарного дерева.
Рассмотрим задачу вывода на печать сформированного двоичного дерева. Эта задача является частным случаем задачи обхода дерева – посещения всех узлов дерева и выполнения некоторых действий в каждом узле.
Из теории известно, что существуют три основных порядка возможного посещения узлов бинарного дерева: