- •Ответы по дисциплине «Основы алгоритмизации и программирования»
- •Запись алгоритма Евклида на языке с
- •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() {
Имя массива – это константный указатель на его начало.
Из этого утверждения следуют важные соотношения (здесь Т – имя типа):
x[i] эквивалентно *(x+i)
T X[] эквивалентно t *X
Вопрос №52. Определение массива. Способы задания размера массива.
При работе с массивами имеется одно затруднение – размер массива (количество элементов) должен быть известен в момент выделения памяти массиву компилятором. Проблем не возникает в следующих случаях:
размер массива задается константным выражением
размер массива задается выражением, в которое входят константы и внешние по отношению к блоку, в котором производится определение массива, переменные (и эти переменные получили значения!)
размер массива не задается, а определяется списком инициализации
…
#define N 100
int n1 = 10;
Int main() {
int n = 20;
int a[N], b[30], c[n1];
int g[] = {1, 2, 3, 4};
{
int d[n];
}
}
Вопрос №53. Динамические массивы. Освобождение памяти. Функции calloc и free.
В тех случаях, когда размер массива невозможно знать заранее (например, эта величина вводится человеком), можно использовать динамические массивы, память для которых выделяется динамически системной функцией
Void *calloc(size_t n, size_t r)
где n – количество элементов массива, r – размер элемента в байтах.
Функция возвращает нетипизированный указатель на начало массива.
В программировании встречается неприятная ситуация, которая называется «утечка памяти». Эта ситуация может возникнуть при использовании динамического выделения памяти функцией calloc. Для устранения этой ситуации рекомендуется освобождать неиспользуемую память с помощью функции
Void free(void *p)
где p – нетипизированный указатель, получивший значение в результате вызова calloc.
#include <stdio.h>
#include <stdlib.h>
int sum(int m[], int n) {
int i, s;
for(i=0, s=0; i<n; s+=m[i++]);
return s;
}
Int main() {
int i, n, *z;
Void *p;
printf("input n : "); scanf("%d", &n);
z = (int *)(p = calloc(n, sizeof(*z)));
for(i=0; i<n; i++) z[i] = 2*i+1;
printf("summa = %d\n", sum(z, n));
free(p);
system("PAUSE");
return 0;
}
Лекция 10. Указатели и массивы (продолжение).
Вопрос №54. Символьные указатели. Различие между определением строк с помощью массивов и с помощью символьных указателей.
Язык С не имеет отдельного типа данных для работы со строками символов и они представляются массивами символов char[].
Например, строковая константа “I am a string” будет представлена в памяти символьным массивом из 14 элементов (13 символов+’\0’).
Рассмотрим два способа определения объектов программы, с помощью которых можно работать со строками:
char amessage[] = “I am a string” ; /* массив */
char *pmessage = “I am a string” ; /* указатель */
В первом случае amessage – это массив, занимающий 14 байтов памяти, заполненных символами из строковой константы и каждый символ в этом массиве можно изменять. При этом переменная amessage всегда будет указывать на один и тот же участок памяти и её значение изменить нельзя.
Во втором случае pmessage – указатель размером 4 байта. С его помощью можно также получить доступ к любому символу строковой константы, но изменять символы нельзя. Кроме того, переменная pmessage в дальнейшем может получить другое значение, например, в результате присваивания:
pmessage = “I am another string” ;
Вопрос №55. Массивы указателей (массивы строк).
Так как указатели являются обычными переменными, их можно хранить в массиве. Создадим объект «массив строк», проинициализируем его и выполним перестановку некоторых элементов этого массива:
#include <stdio.h>
#include <stdlib.h>