- •Билет 1. Концепция языка Си, его достоинства и недостатки
- •Билет 2. Представление целых чисел в эвм. Основные типы данных в Си и операции над ними. Особенности операций над вещественными числами.
- •Билет 3. Основные управляющие конструкции в Си. Понятие инварианта цикла и его применение.
- •Билет 4. Характеристика алгоритмов, программ, языков программирования и соответствия между ними.
- •Билет 5. Массивы и указатели в языке Си. Их представление, связь между ними.
- •Билет 6. Метод барьера и различные варианты его применения.
- •Билет 7. Процедуры и функции в Си. Формальные и фактические. Входные и выходные параметры, локальные и глобальные переменные.
- •Билет 8. Массивы и указатели в Си, связь между ними. Передача массивов и указателей как параметров процедур.
- •Билет 9. Представление строк и символов в Си. Операции над ними.
- •Билет 10. Понятие эффективности алгоритма, различные способы ее измерения.
- •Билет 11. Понятие рекурсии. Виды и характеристики.
- •Билет 12. Алгоритмы перебора с возвратом. Способы сокращения перебора.
- •Способы сокращения перебора
- •Билет 13. Алгоритмы оптимального поиска. Метод ветвей и границ.
- •Билет 14. Сортировка массивов. Простые методы.
- •Билет 15. Сортировка массивов. Усовершенствованные методы.
- •Билет 16. Алгоритм поиска подстроки в строке.
- •3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или
- •Билет 17. Алгоритм получения случайных чисел. Правильный выбор параметров линейного конгруэнтного генератора.
Билет 5. Массивы и указатели в языке Си. Их представление, связь между ними.
Массив - набор данных одного и того же типа, собранных под одним именем. Каждый элемент массива имеет свой порядковый номер, который называется индексом. Соответственно каждый элемент массива определяется именем массива и порядковым номером элемента. Индекс (номер элемента) в языке Си всегда целое число.
Указатель-это переменная, содержащая машинный адрес для создания и манипуляции структурами данных, динамического размещения памяти и вызова функции посредством ссылки.
Указатель может адресовать объект любого типа, включая агрегатные типы, такие как структуры или даже функции. Указатель описывается посредством индикатора (*), стоящего перед именем адресуемого объекта, этот знак косвенного обращения к данным означает "указать на". Указатель всегда ссылается на объект определенного типа (то есть он содержит адрес значения определенного типа). Перед использованием указатели следует проинициализировать, поскольку значение, содержащиеся в неинициализированных указателях, непредсказуемы, и наверняка, приведут к проблемам.
Символ звездочки (*)-это оператор косвенного обращения к объекту, который означает "указать на данные". Символ амперсенда (&)-это оператор адресации. Если объекту предшествует оператор адресации, то это-адрес, по которому хранится данный объект.
В языке СИ между указателями и массивами существует тесная связь. Например, когда объявляется массив в виде int array[25], то этим определяется не только выделение памяти для двадцати пяти элементов массива, но и для указателя с именем array, значение которого равно адресу первого по счету (нулевого) элемента массива, т.е. сам массив остается безымянным, а доступ к элементам массива осуществляется через указатель с именем array. С точки зрения синтаксиса языка указатель array является константой, значение которой можно использовать в выражениях, но изменить это значение нельзя.
Поскольку имя массива является указателем допустимо, например, такое присваивание:
int arrey[25];
int *ptr;
ptr=array;
Здесь указатель ptr устанавливается на адрес первого элемента масcива, причем присваивание ptr=arrey можно записать в эквивалентной форме ptr=&arrey[0].
Для доступа к элементам массива существует два различных способа. Первый способ связан с использованием обычных индексных выражений в квадратных скобках, например, array[16]=3 или array[i+2]=7. При таком способе доступа записываются два выражения, причем второе выражение заключается в квадратные скобки. Одно из этих выражений должно быть указателем, а второе - выражением целого типа. Последовательность записи этих выражений может быть любой, но в квадратных скобках записывается выражение следующее вторым. Поэтому записи array[16] и 16[array] будут эквивалентными и обозначают элемент массива с номером шестнадцать. Указатель используемый в индексном выражении не обязательно должен быть константой, указывающей на какой-либо массив, это может быть и переменная. В частности после выполнения присваивания ptr=array доступ к шестнадцатому элементу массива можно получить с помощью указателя ptr в форме ptr[16] или 16[ptr].
Второй способ доступа к элементам массива связан с использованием адресных выражений и операции разадресации в форме *(array+16)=3 или *(array+i+2)=7. При таком способе доступа адресное выражение равное адресу шестнадцатого элемента массива тоже может быть записано разными способами *(array+16) или *(16+array).
При реализации на компьютере первый способ приводится ко второму, т.е. индексное выражение преобразуется к адресному. Для приведенных примеров array[16] и 16[array] преобразуются в *(array+16).
Для доступа к начальному элементу массива (т.е. к элементу с нулевым индексом) можно использовать просто значение указателя array или ptr. Любое из присваиваний
*array = 2;
array[0] = 2;
*(array+0) = 2;
*ptr = 2;
ptr[0] = 2;
*(ptr+0) = 2;
присваивает начальному элементу массива значение 2, но быстрее всего выполнятся присваивания *array=2 и *ptr=2, так как в них не требуется выполнять операции сложения.
Операции с указателями
Над указателями можно выполнять унарные операции: инкремент и декремент. При выполнении операций ++ и -- значение указателя увеличивается или уменьшается на длину типа, на который ссылается используемый указатель.
Пример:
int *ptr, a[10];
ptr=&a[5];
ptr++; /* равно адресу элемента a[6] */
ptr--; /* равно адресу элемента a[5] */
В бинарных операциях сложения и вычитания могут участвовать указатель и величина типа int. При этом результатом операции будет указатель на исходный тип, а его значение будет на указанное число элементов больше или меньше исходного.
Пример:
int *ptr1, *ptr2, a[10];
int i=2;
ptr1=a+(i+4); /* равно адресу элемента a[6] */
ptr2=ptr1-i; /* равно адресу элемента a[4] */
В операции вычитания могут участвовать два указателя на один и тот же тип. Результат такой операции имеет тип int и равен числу элементов исходного типа между уменьшаемым и вычитаемым, причем если первый адрес младше, то результат имеет отрицательное значение.
Пример:
int *ptr1, *ptr2, a[10];
int i;
ptr1=a+4;
ptr2=a+9;
i=ptr1-ptr2; /* равно 5 */
i=ptr2-ptr1; /* равно -5 */
Значения двух указателей на одинаковые типы можно сравнивать в операциях ==, !=, <, <=, >, >= при этом значения указателей рассматриваются просто как целые числа, а результат сравнения равен 0 (ложь) или 1 (истина).