- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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 Insert_head_l1(List1 *l, double z) {
Node1* p = (Node1*)calloc(1, sizeof(Node1));
p->elem = z; p->next = l->head;
l->head = p;
}
Void Insert_back_l1(List1 *l, double z) {
Node1* p = (Node1*)calloc(1, sizeof(Node1));
p->elem = z; p->next = NULL;
if (l->head == NULL) {l->head = p; return;}
Node1* q = l->head;
while (q->next) q = q->next;
q->next = p;
}
Вопрос №84. Алгоритм извлечения элемента из однонаправленного списка.
Задача извлечения элемента из однонаправленного списка имеет две разновидности:
извлечение первого элемента или
извлечение последнего элемента.
Тексты двух функций, реализующих извлечение элемента в голове списка Extract_head_L1 и в хвосте списка Extract_back_L1.
Int Extract_head_l1(List1 *l, double *z) {
Node1 *p = l->head;
if (p == NULL) return 0;
*z = p->elem;
l->head = p->next;
free(p);
}
Int Extract_back_l1(List1 *l, double *z) {
Node1 *p = l->head, *p1;
if (p == NULL) return 0;
if (p->next == NULL) {
*z = p->elem; l->head = NULL;
free(p); return 1; }
for (p1 = p->next; p1->next; p = p1, p1 = p->next);
*z = p1->elem; p->next = NULL;
free(p1); return 1;
}
Лекция 16. Связанные списки (продолжение).
Вопрос №85. Алгоритм обращения однонаправленного списка.
Построим алгоритм решения одной простой задачи для однонаправленного списка: перестроить список так , чтобы хвост стал головой и наоборот – голова стала хвостом (т.е. выполнить реверсирование списка). На рисунке показан один цикл обращения. Слева от пунктира – перестроенный список, справа – исходный.
Void reverse_l1(List1 *l) {
Node1 *r = l->head, *y, *t;
if (r == NULL) return; // список пуст
y = r->next; // начальная установка
r->next = NULL; // голова стала хвостом
while (y) {
t = y->next; y->next = r; r = y; y = t;
}
l->head = r;
}
Вопрос №86. Алгоритм сортировки однонаправленного списка.
Рассмотрим еще одну задачу – сортировка списка вставками.
do { // цикл по неотсортированному списку
a->next = t->next;
for (x = b; ;x = x->next) // цикл по отсортированному списку
if ((x->next == NULL) || (x->next->elem > t->elem)) {
t->next = x->next; x->next = t; break; }
} while (t = a->next);
Исходный код функции sort_l1
Void sort_l1(List1 *l) {
if ((l->head == NULL) || (l->head->next == NULL)) return;
Node1* a = (Node1*)calloc(1, sizeof(Node1));
a->next = l->head->next->next;
Node1* t = l->head->next;
Node1* b = (Node1*)calloc(1, sizeof(Node1));
b->next = l->head; l->head->next = NULL;
Node1* x;
do {
a->next = t->next;
for (x = b; ;x = x->next)
if ((x->next == NULL) || (x->next->elem > t->elem)) {
t->next = x->next; x->next = t;
break;
}
} while (t = a->next);
l->head = b->next;
}
Лекция 17. Связанные списки (продолжение).
Вопрос №87. Использование ограничителей в однонаправленных списках.
Многие задачи обработки списков можно упростить, если использовать так называемые ограничители – фиктивные узлы, которые не содержат полезной информации, а значимым в ограничителе является только указатель. Так, для рассмотренного на прошлой лекции однонаправленного списка ограничитель может быть помещен перед первым узлом списка:
С использованием ограничителя изменится определение структуры для списка – не нужно отдельно описывать узел списка, а также изменится алгоритм инициализации списка:
typedef struct List1 {
double elem; struct List1 *next; } List1;
List1* init_L1() {
List1 *l = (List1*)calloc(1, sizeof(List1));
l->next = NULL; return l;
}
Вопрос №88. Рекурсивный алгоритм обхода списка.
Вернемся к задаче вывода на печать однонаправленного связанного списка. Эта задача была решена путем прохождения в цикле всех узлов списка от «головы» к «хвосту» и распечатки (вывода на экран) содержимого каждого узла.
Заметим, что эта задача является частным случаем задачи обхода списка – посещения всех его узлов и выполнения некоторых действий в каждом узле и может быть решена не только с помощью циклического алгоритма, но и с помощью рекурсии. Во втором случае появляются две основные возможности:
обработать узел, а затем следовать связи (в этом случае узлы посещаются по порядку), или
следовать связи, а затем обработать узел (в этом случае узлы посещаются в обратном порядке).
Модернизируем функцию печати списка, введя две вспомогательных функции: visit, которая выполняет «полезную работу» в узле (т.е. просто печатает его содержимое) и рекурсивную функцию traverse, которая и выполняет обход списка: