- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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 swaps(char** a, char** b) {
char *c = *a;
*a = *b; *b = c;
}
main() {
char* arrs[] = {"first", "second", "third",
"fourth", "fifth"};
int i, n = sizeof(arrs)/sizeof(*arrs);
for(i = 0; i < n; i++) printf("%d: %s\n", i+1, arrs[i]);
swaps(&arrs[0], &arrs[2]);
swaps(&arrs[1], &arrs[4]);
printf("--------\n");
for(i = 0; i < n; i++) printf("%d: %s\n", i+1, arrs[i]);
system("PAUSE");
return 0;
}
Вопрос №56. Многомерные прямоугольные массивы.
Синтаксис языка С допускает, чтобы при определении массива его элементами были массивы (одинакового размера!). В этом случае приходим к понятию многомерного прямоугольного массива. Например, популярный математический объект «матрица» может быть представлен двумерным массивом:
matr
– массив из 3-х элементов, каждый из
которых является массивом из 3-х элементов
#include <stdlib.h>
main() {
int matr[3][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int i, n = 3, j, m = 3;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++)
printf("%4d", matr[i][j]);
printf("\n");
}
system("PAUSE");
return 0;
}
Вопрос №57. Двумерные массивы неопределенного размера.
Можно задать двумерный массив неопределенного (по первому измерению!) размера :
#include <stdio.h>
#include <stdlib.h>
main() {
int matr[][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}};
int i, n = sizeof(matr)/sizeof(*matr);
int j, m = 3;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++)
printf("%4d", matr[i][j]);
printf("\n");
}
system("PAUSE");
return 0;
}
Вопрос №58. Многомерные массивы и указатели.
По аналогии с одномерными массивами можно предположить, что справедливо соотношение: x[i][j] эквивалентно *(*(x+i)+j) . Проверим это:
#include <stdio.h>
#include <stdlib.h>
main() {
int matr[][3] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
{10, 11, 12}};
int i, n = sizeof(matr)/sizeof(*matr);
int j, m = 3;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++)
printf("%4d", matr[i][j]);
printf("\n");
}
printf("[1,1]->%4d\n",*(*(matr+1)+1));
printf("[3,2]->%4d\n",*(*(matr+3)+2));
system("PAUSE");
return 0;
}
Вопрос №59. Многомерные массивы нерегулярной структуры.
С помощью указателей можно сконструировать необычные, «зубчатые» массивы, в которых каждая строка может иметь свой размер, например так:
# include <stdio.h>
#include <stdlib.h>
main() {
int m1[] = {1, 2};
int m2[] = {5, 3, 4, 7, 9, 2};
int m3[] = {3, 8, 5};
int *matr[] = {m1, m2, m3};
printf("[1,1]->%4d\n",*(*(matr+1)+1));
printf("[1,5]->%4d\n",*(*(matr+1)+5));
printf("[2,2]->%4d\n",*(*(matr+2)+2));
printf("[1,1]->%4d\n", matr[1][1]);
printf("[1,5]->%4d\n", matr[1][5]);
printf("[2,2]->%4d\n", matr[2][2]);
system("PAUSE");
return 0;
}
Вопрос №60. Динамические многомерные массивы.
Используя указатели и динамическое выделение памяти сконструируем зубчатый массив специального вида - нижнюю треугольную матрицу размера n (n вводится с клавиатуры), заполненную числовыми значениями по следующему правилу:
#include <stdio.h>
#include <stdlib.h>
main() {
int i, j, n;
int **t;
printf("n: "); scanf("%d", &n);
t = (int **)calloc(n, sizeof(**t));
for(i = 0; i < n; i++) {
t[i] = (int *)calloc(i+1, sizeof(*t));
for(j = 0; j <= i; j++) t[i][j] = i-j+1;
}
for(i = 0; i < n; i++) {
for(j = 0; j <= i; j++)
printf("%4d",t[i][j]);
printf("\n");
}
system("PAUSE");
return 0;
}
Лекция 11. Указатели и массивы (продолжение).
Вопрос №61. Свойство константности (const) и проблема надежности программ. Объекты программы, к которым применимо свойство const.
Свойство константности объекта задаётся описателем const и символизирует запрет на выполнение операций записи в память.
Это свойство можно задать для разных объектов программы:
- переменных,
- параметров функций,
- возвращаемых из функций значений.
Контроль за корректным использованием свойства const выполняет компилятор, поэтому ошибки обнаруживаются на ранних стадиях создания программы, что повышает ее надежность.
Вопрос №62. Константные указатели. Варианты использования const при объявлении указателей.
С помощью описателя const можно сделать неизменяемым как указатель, так и область памяти, на которую он ссылается.
…
m ain() {
int a = 5, b = 7;
int *p1 = &a;
*p1 = 3; // ok!
p1 = &b; // ok!
const int *p2 = &a; //констант. область памяти
*p2 = 9; // err!
p2 = &b; // ok!
int *const p3 = &a; //констант. указатель
*p3 = 9; // ok!
p3 = &b; // err!
const int *const p4 = &a; //и указ., и обл. пам. конст.
*p4 = 6; // err!
p4 = &b; // err!
…
}
Вопрос №63. Функция main и аргументы командной строки.
В операционной среде, обеспечивающей поддержку С, имеется возможность передать аргументы (параметры) запускаемой программе
с помощью командной строки. В момент вызова функции main она получает два аргумента. В первом, обычно называемом argc (от argument count – счетчик аргументов), содержится число, равное количеству аргументов, заданных в командной строке. Второй, argv (от argument vector – вектор аргументов), является указателем на массив символьных строк, содержащих сами аргументы, - по одному в строке.
#include <stdio.h>
#include <stdlib.h>
main(int argc, char *argv[]){
while (argc-- > 0)
char
*argv[] = char **argv
printf("\n");
system("PAUSE");
return 0;
}
Вопрос №64. Определение понятий rvalue и lvalue. Особенности использования функций, возвращающих lvalue.
Если тип возвращаемого значения функции отличен от void, то в результате вызова функции получается, как правило, некоторое значение, которое может быть использовано как операнд в выражении. Например, для подсчета среднего значения массива может быть использован следующий фрагмент:
double sum(double *x, int n); // прототип функции sum ...
sr = sum(m, 100)/100;
В данном примере функция возвращает так называемое rvalue, иначе говоря, значение. Термин rvalue происходит от read value – значение для чтения, или от right value – правое значение – по его месту относительно операции присваивания.
В некоторых случаях типом возвращаемого значения функции может быть тип, дающий lvalue, иначе говоря, адрес. Термин lvalue происходит от location value – значение местоположения, или от left value – левое значение – также по его месту относительно оператора присваивания. Следовательно, вызов такой функции может располагаться слева от оператора присваивания.
Внимание!
Необходимо с осторожностью обращаться с lvalue, возвращаемыми из функций и не допускать, чтобы из функций возвращались адреса несуществующих объектов, например, локальных переменных, объявляемых внутри функции.
Вопрос №65. Указатели на функции. Объявление указателей на функции. Объявление указателя на функцию как типа данных.
В программировании для Windows широко применяется техника функций обратного вызова (callback functions). Функции обратного вызова – это указатели на функции, через которые могут быть вызваны функции. Пример указателя на функцию:
#include <stdio.h>
#include <stdlib.h>
int f(int k) {
printf("Call f : k = %6d\n", k);
return 100*k;
}
int f1(int k) {
printf("Call f1: k = %6d\n", k);
return 1000*k;
}