- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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() {
Int main(void) {
int i = 2;
int (*pf)(int);
pf = f; printf("1: %6d\n", pf(i++));
pf = f1; printf("2: %6d\n", pf(i++));
system("PAUSE");
return 0;
}
В предыдущем примере был использован указатель на функцию pf как самостоятельная переменная. Синтаксис языка С допускает объявить указатель на функцию как тип данных, что позволяет использовать динамические переменные и массивы указателей.
#include <stdio.h>
# include <stdlib.h>
int f(int k) { … }
int f1(int k) { … }
typedef int (*D)(int);
Int main() {
int i = 2;
D p[] = {f, f1};
D p1 = f;
printf("%d \n", (*p)(i++));
printf("%d \n", p[1](i++));
printf("%d \n", p1(i++));
system("PAUSE");
return 0;
}
Вопрос №66. Общее правило, разбора сложных объявлений
(на примере int (*(*(*fun)())[])();)
Язык С часто обвиняют за чрезмерно сложный синтаксис объявлений, особенно тех, которые содержат в себе указатели на функции. Например:
int *f(); функция f, возвращающая указатель на int
int (*f)(); указатель на функцию f, возвращающую int
Приоритет оператора * ниже, чем приоритет (), поэтому во втором случае скобки необходимы. Ещё пример:
int *daytab[13]; массив из 13 указателей на int
int (*daytab)[13]; указатель на массив из 13 чисел типа int
И ещё одно (очень запутанное!) объявление:
int (*(*(*fun)())[])();
Его следует понимать так: «fun – это указатель на функцию, возвращающую указатель на массив указателей на функции, возвращающие int».
Рассмотрим общее правило (которое называется правило «право-лево»), позволяющее разбирать любые «запутанные» объявления.
Правило «право-лево»
При описании этого правила необходимо помнить следующие 3 операции:
() - функция, возвращающая...
[] - массив из...
* - указатель на...
Первые две имеют наивысший приоритет, а третья – более низкий.
Процесс разбора объявления итеративный:
Шаг 1. Находим имя, с которого начинается разбор, и записываем начало предложения «Имя есть...».
Шаг 2. Начинаем движение вправо для поиска () или []. Если справа оказывается (), то в конструируемое предложение вместо многоточия подставляем: «функция, возвращающая...» и в итоге получаем: «Имя есть функция, возвращающая...».
Если справа [], то подставляем «массив из…» и получаем «Имя есть массив из...». Таким образом мы идём вправо до тех пор, пока не дойдём до конца объявления или правой ) скобки.
Шаг 3. После этого начинаем перемещаться влево. Если слева обнаруживается что-то отличное от упомянутых выше операций (то есть не (), [], *), то просто добавляем к уже имеющемуся предложению. Если же там что-то из этих трёх операций, то к предложению добавляем соответствующий текст. И так перемещаемся до начала объявления или левой ( скобки. Если обнаружена (, то переходим к шагу 2. Если дошли до начала объявления, разбор закончен.
Рассмотрим сложный пример:
int (*(*(*fun)())[])();
^^^
Hаходим имя и записываем: «fun есть...». Шаг вправо, но там ), и потому идём влево
int (*(*(*fun)())[])();
^
и получаем «fun есть указатель на...». Продолжаем двигаться влево, но тут (. Идём вправо
int (*(*(*fun)())[])();
^^
получаем «fun есть указатель на функцию, возвращающую...». Шаг вправо, но там ), и потому идём влево. Получаем
int (*(*(*fun)())[3])();
^
«fun есть указатель на функцию, возвращающую указатель на...». Слева опять (, поэтому идём вправо. Получаем
int (*(*(*fun)())[])();
^^
«fun есть указатель на функцию, возвращающую указатель на массив...».
И снова справа ), поэтому перемещаемся влево и получаем
int (*(*(*fun)())[])();
^
«fun есть указатель на функцию, возвращающую указатель на массив указателей на...». Снова разворот вправо, т.к. обнаруживается ( , и получаем
int (*(*(*fun)())[])();
^^
«fun есть указатель на функцию, возвращающую указатель на массив указателей на функции, возвращающие...».
Обнаруживаем конец описания, переключаемся на движение влево и получаем окончательную расшифровку этого очень сложного и запутанного описания:
int (*(*(*fun)())[])();
^^^
«fun есть указатель на функцию, возвращающую указатель на массив указателей на функции, возвращающие int».
Лекция 12. Структуры.
Вопрос №67. Определение понятия «структура». Поля (члены) структуры. Определение структуры и определение переменных типа «структура». Инициализация структур. Определение понятия «составное имя».
Структура – это набор нескольких именованных переменных, объединённых в единое целое под общим именем.
Входящие в структуру переменные называются элементами, полями или членами структуры. Члены структуры имеют произвольные типы и уникальные в пределах структуры имена. Доступ к членам структуры производится по составному имени, включающему имя структуры и имя члена структуры.
Пример:
struct {int x; int y;} pt1, pt2;
pt1.x = 3; pt1.y = 6;
pt2 = pt1;
Синтаксис языка С позволяет отделить описание «внутреннего устройства» структуры от определения конкретных переменных, имеющих это внутреннее устройство:
struct point {int x; int y;};
struct point pt1, pt2;
Такой подход позволяет рассматривать первое объявление как новый, структурный тип данных, а второе – как определение переменных этого типа.
Замечание. Допускается совмещать объявление структурного типа и объявление переменных этого типа:
struct point {int x; int y;} pt1, pt2;
Вопрос №68. Структуры в качестве аргументов функций и возвращаемых значений.
#include <stdio.h>
#include <stdlib.h>
struct point { int x, y; };
struct rect {
struct point pt1, pt2;
};