1. Этапы
проектирования программы. Проектирование сверху вниз. Примеры.
Этапы создания программы:
1. Постановка задачи и выяснение всех деталей
2. Формулировка задачи на языке спецификации
3. Детализация общего плана задачи
4. Обозначение содержания программы и описание модулей
5. Кодирование
6. Объединение и отладка всей программы
7. Сопровождение
При написании программы следует разбивать задачу на подзадачи (модули), которые могут быть разбиты на более мелкие подзадачи, двигаясь от сложного к простому.
2. Модульное
программирование. Определение модуля. Независимость. Примеры.
В модульной программе отдельные её части, предназначенные для решения каких-то частных задач, организованы в подпрограммы. В такой организации есть 2 преимущества:
- один и тот же фрагмент можно использовать многократно как в одной, так и в разных программах;
- если программы писать небольшими частями, их легче читать, тестировать и отлаживать, у них более чёткая логическая структура.
Модуль - последовательность операторов, к которым можно обратиться по имени (процедуры и функции)
Модули должны:
1) решать конкретную задачу;
2)
быть независимыми от входных данных, от остальной программы и от других
модулей.
В модуле должны обрабатываться критические ситуации – то есть он должен быть работоспособным во всех случаях, независимо от того, с какими параметрами его вызывают (если вызывают с ошибочными параметрами, модуль должен сообщать об ошибке, а не вешать компьютер).
См.
так же в вопросе №3: область определения и область значения модуля.
3. Модульное
программирование. Область определения. Область значений. Побочные эффекты.
Примеры.
Модульное
программирование см. в вопросе №2.
Область определения модуля задаётся количеством входных параметров и типом каждого из них. Область значений модуля представляет собой тип значения, возвращаемого модулем.
В языке C модулями являются функции, которые могут возвращать значение стандартного или пользовательского типа, либо не возвращать никакого значения (тип void). Область определения и область значения модуля всегда постоянны, и при вызове модуля они должны строго учитываться.
В связи с этим существуют побочные эффекты:
1) Количество отсылаемых параметров должно быть всегда одинаковым. Правда, C++ позволяет создавать процедуры с переменным количеством входных параметров (например, printf). Но это, скорее, исключение.
2) Если модуль работает с пользовательским типом, имеющим какое-то данное пользователем название, например, List, и мы хотим использовать этот модуль в другой программе, где описан точно такой же тип, но названный Spisok, модуль не будет работать. Придётся либо редактировать модуль из первой программы, либо изменить название типа во второй программе, что повлечёт за собой и изменение других модулей во второй программе.
4. Структурное кодирование. Базовый набор структур. Базовые структуры в языке Си. Примеры.
Структурное кодирование - одна из трех составляющих структурного программирования. В его основе лежит способ написания программ, при котором вся программа строится только из базовых структур.
К основным базовым структурам относятся:
1. Последовательность - операторы выполняются последовательно.
2. Простой выбор - в
зависимости от условия выполняются разные цепочки операторов. Примеры см. в
вопросах №17, №19.
3. Повтор с предусловием - определенная последовательность операторов повторяется, пока условие истинно. Примеры см. в вопросах №21, №22.
В языке СИ двумя наиболее часто используемыми базовыми структурами являются условный оператор if…else… и универсальный цикл for(…). Подробнее о них см. в вопросах №19 и №22. Примером простого выбора так же является так называемое условное выражение, или тринарный оператор (см. в вопрос №17), а примером цикла с предусловием – while(…)… (см. в вопрос №21).
5. Структурное
кодирование. Расширение базового набора структур. Вложение структур.
Дополнительные структуры в языке Си. Примеры.
Структурное кодирование
- см. вопрос №4.
Расширение базового набора структур:
4. Повтор с
постусловием - последовательность операторов выполняется до
тех пор, пока условие не станет ложным. Отличается от повтора с предусловием
тем, что выполняется хотя бы один раз. В языке Си это цикл do…while(…). Cм.
вопрос №21.
5. Многовариантный выбор - в зависимости от значения выражения выполняются различные цепочки операторов. В языке Си это переключатель switch(…)of … Cм. вопрос №20.
Структуры могут вкладываться друг в друга.
6. Кодирование
сверху вниз. Метод пошаговой детализации. Пример.
При написании программы
следует разбивать задачу на подзадачи (модули), которые могут быть разбиты на
более мелкие подзадачи, двигаясь от сложного к простому. В дальнейшем написание
программы сводится к написанию отдельных модулей.
7. Эффективность программ. Критические области
программы. Пример.
8. Эффективность программ. Примеры оптимизации циклов.
9. Эффективность программ. Примеры оптимизации ветвлений.
При написании участка программы, содержащего несколько операторов ветвления, нужно учитывать следующие возможности оптимизации:
1) если последовательно идёт несколько операторов ветвления с одинаковыми условиями, их следует объединить в один.
2а) если последовательно идёт несколько операторов ветвления с разными условиями, то каждый последующий оператор должен вызываться лишь в том случае, если не выполнилось предыдущее условие (для этого его нужно вкладывать в раздел else предыдущего оператора).
2б) операторы ветвления при этом желательно располагать в таком порядке, чтобы первым делом выполнялся тот оператор, условие которого окажется истинным в большинстве случаев, и наоборот.
3) если последовательно идёт несколько операторов ветвления с частично различающимся и частично совпадающими условиями, их следует расположить таким образом, чтобы не проверять лишний раз одни и те же условия (для этого нужно разделить один из операторов на две части, и вложить их в основной раздел и в раздел else другого оператора).
4) если условиями нескольких операторов ветвления являются равенства или неравенства некоторым числовым значениям, их лучше переписать в виде переключателя switch.
5) если в переключателе switch требуется, чтобы после выполнения одних действий не совершались другие, нужно писать после этих действий инструкцию break.
6) условия в switch нужно располагать в таком порядке, чтобы первым делом выполнялись те проверки, условия которых окажутся истинным в большинстве случаев, и наоборот.
10. Отладка и
тестирование программ. Примеры.
Отладка и тестирование являются неотъемлемыми этапами разработки программы.
Для отладки программ в среде Borland C++ используются трассировка (F7), пошаговое выполнение (F8), выполнение до курсора (F4) и т.д. Значения переменных при этом можно наблюдать в окне Watch.
Тестирование программы нужно проводить со всеми возможными вариантами входных параметров. Во время тестирования перед запуском программы надо сначала определить для себя, какой результат должен получиться при вводимых входных значениях и какие модули и операторы будут задействованы при выполнении программы с этими входными значениями, а какие нет. Во избежание "гуляющих ошибок" желательно протестировать программу на разных машинах.
11. Базовые типы
языка Си. Объявление и определение переменных. Примеры.
Переменная - ячейка памяти, содержащая некоторую величину, которая во время работы программы может менять своё значение, и к которой можно обратиться по имени. В языке Си имя переменной (идентификатор) может состоять из больших и малых букв латинского алфавита, цифр и знака _, и не должно начинаться с цифры.
Тип переменной определяет размер ячейки, диапазон значений переменной и операции, которые можно производить со значением переменной.
Базовыми типами в Си являются:
int - целочисленный тип;
размер: 2 байта (16 бит); операции: +, -, *, /, %, унарный минус; диапазон: от
-32767 до 32768.
char - код символа; размер: 1 байт (8 битов);
float – числа с плавающей точкой; размер: 6 байт (48 бит); операции: +, -, *, /; диапазон: от -2.9·10-39 до 1,7·1038.
double – числа с плавающей точкой двойной точности.
Типы данных в языке Си являются абстрактными.
Новая переменная в Си может быть описана в любой части программы перед первым использованием этой переменной. Описывать переменные можно только один раз. При описании указывается тип переменной, например: int i. После слова, указывающего тип, может идти любое количество имён переменных.
Перед использованием переменной в программе нужно присвоить ей начальное значение (инициализировать). Инициализация может быть произведена одновременно с объявлением, например: int i=0.
12. Квалификаторы.
Назначение. Примеры.
В языке Си используется четыре квалификатора (short, long, signed и unsigned) для расширения набора стандартных типов переменных. Они пишутся через пробел перед названием типа при описании переменной. Ещё один квалификатор (const) указывает, что описывается не переменная, а константа.
Квалификаторы short и long можно использовать с типами int и double, а квалификаторы signed и unsigned с типами int и char. signed и unsigned могут быть использованы одновременно с short или long. signed – указывает, что один бит отводится для обозначения знака числа (+/-). unsigned – указывает, что тип принимает только положительные значения. long увеличивает, а short уменьшает вдвое количество байт, выделяемых для хранения значения переменной. Примеры:
short int – "короткое целое"; размер: 1 байт (8 бит); диапазон: от -128 до 127. (Вместо short int можно писать просто short, например: short i=5).
long int – "длинное целое"; размер: 4 байта (32 бита); диапазон: от -2147483648 до 2147483647. (Вместо long int можно писать просто long).
unsigned int – "беззнаковое целое"; размер: 2 байт (16 бит); диапазон: от 0 до 65535.
unsigned short int – "беззнаковое короткое целое"; размер: 1 байт (8 бит); диапазон: от 0 до 255.
unsigned long int – "беззнаковое длинное целое"; размер: 4 байта (32 бита); диапазон: от 0 до 4294967295.
unsigned char – "беззнаковый символ"; размер: 1 байт (8 бит); диапазон: от 0 до 255.
signed char – "знаковый символ"; размер: 1 байт (8 бит); диапазон: от -128 до 127.
Тип char без квалификатора может быть как знаковым, так и беззнаковым, в зависимости от версии компилятора.
13. Константы в
языке Си. Различные способы определения констант. Примеры.
Константа - величина, имеющая фиксированное значение, задающееся перед выполнением программы.
В языке Си есть три способа определения констант:
1) с использованием
квалификатора const.
Например: const float pi=3.14;
2) с использованием оператора enum. Например: enum month{JAN,FEB,MAR} или enum month{JAN=1,FEB,MAR}. (В первом случае константам присвоятся следующие значения: JAN=0, FEB=1, MAR=2. Во втором случае начальное значение сдвинется: JAN=1, FEB=2, MAR=3).
3) с использованием директивы #define. Например: #define FILE_NAME "data.txt". (При использовании такого способа задания констант во время компиляции перед запуском в тексте программы все слова FILE_NAME будут найдены и заменены на "data.txt". В отличие от первых двух способов директива #define позволяет задавать не только числовые, но и строковые константы).
14. Операции в языке
Си. Примеры.
Простейшим оператором в Си явл-ся вызов функции.
Арифметические операции в языке Си:
+ - сложение;
– - вычитание;
* - умножение;
/ - полиморфный оператор: если оба операнды целые – целочисленное деление (результат – целое); если хотя бы один операнд является числом с плавающей точкой, то второй тоже приводится к вещественному типу (результат деления имеет вещественный тип);
% - взятие остатка от деления (для целочисленных типов).
Операции отношения в языке Си:
> - больше;
<= - не больше;
< - меньше;
>= - не меньше;
== - равно;
!= - не равно.
В языке Си результат операции отношения хранится в целочисленном типе. Если результат равен 0, это говорит о ложности. Ненулевое значение – истинность. Например, выражение 5>4 даст в результате 0. Результатом операции 7!=2 будет число, отличное от нуля (в большинстве версий компилятора это будет 1 или –1).
Логические операции:
&& - логическое и;
|| - логическое или;
! - логическое нет.
Результатом логической
операции тоже будет целое число, равное или неравное нулю.
Простейшей операцией является вызов функции.
15. Выражения.
Правила приведения типов в языке Си. Примеры.
Выражения состоят из операндов и операций. Тип результата выражения зависит от типа операции и, иногда, от типа операндов.
В языке Си можно производить операции над двумя значениями разных типов. При этом один из операндов будет преобразован к типу другого операнда (для этого в оперативной памяти выделится ячейка для временного хранения получившегося значения), затем будет произведена операция, и тип результата будет тем же, каким был тип используемых при вычислении операндов.
Приведение осуществляется по следующим правилам:
- если один из операндов типа long double, то второй будет приведён к long double.
- иначе если один из операндов double, то второй будет приведён к double.
- иначе если один из операндов float, то второй будет приведён к float.
- иначе если один из операндов long int, а второй unsigned int, то, если есть перекрытие, повышение до long int, если нет перекрытия, повышение до unsigned int.
- иначе если один из
операндов long int,
то второй будет приведён к long int.
- иначе если один из операндов unsigned int, то второй будет приведён к unsigned int.
- в противном случае оба операнда приводятся к int.
Вся эта ботва называется "Обычные арифметические преобразования".
Примеры ошибок, возникающих благодаря этой ботве:
В результате выполнения следующей программы
#include
<stdio.h>
void main()
{
long a=-1;
unsigned long b=1;
if (a>b)
printf("-1 > 1");
}
printf выполнится вопреки всякому здравому смыслу. Вывод один: не хрен программировать на Си, лучше работайте в Паскале. Да нет, не хрен использовать квалификаторы. Нет, лучше на дизайн поступать и платить $1600, а не 800. А лучше вообще не платить!!!.
16. Операторы
инкремента, декремента, присваивания. Примеры.
Операцией инкремента называется увеличение целочисленного значения на единицу, а операцией декремента, соответственно, уменьшение на единицу.
В языке Си эти операции осуществляются с помощью операторов инкремента (++) и декремента (--). Например: i++; j--; или ++i; --j; Причём в Си эти операторы можно применять не только к целочисленным переменным, но и к числам с плавающей точкой (например, если float f=3.14, то действие f++ занесёт в f значение 4,14).
Присваивание переменной
значения в языке Си осуществляется при помощи оператора присваивания (=). Например: i=10;
Кроме того, в языке Си
можно объединять операции присвоения и изменения значения. Например, вместо k=k+i;
можно писать k+=i; то есть, объединить операцию
присвоения и сложения. Точно так же можно писать k-=i;
k*=i; k/=i; k%=i;
Эти операции (кроме %=) допустимы как с целочисленными переменными, так и с числами с плавающей точкой.
Например:
i+=4; - значение i увеличится на 4;
i%=4; - значение i – остаток от деления i на 4;
Возможны следующие объединения операции присваивания и инкремента (или декремента), имеющие разные результаты:
n=i++; // n=5; i=6;
n=++i; // n=6; i=6;
17. Условное
выражение в языке Си. Примеры.
Условное выражение, или так называемый тринарный оператор, записывается в языке Си в следующем виде:
выражение1 ? выражение2 : выражение3;
Выражением 1 может быть любое арифметическое или логическое выражение, результат которого равен или неравен нулю. Если выражение 1 вернёт значение, неравное нулю, то тринарный оператор вернёт значение, возвращаемое выражением 2. А если значение выражения 1 равно нулю, значение тринарного оператора будет равно значению, возвращаемому выражением 3. Таким образом, тринарный оператор всего-навсего представляет собой укороченную запись условного оператора if. Например, запись
переменная = выражение1 ? выражение2 : выражение3;
аналогична записи
if (выражение1) переменная = выражение2; else переменная = выражение3;
Обратите внимание, что после выражения 1 перед знаком "?" не должно стоять точки с запятой, как и после выражения 2 перед знаком ":", ну а после выражения 3 должна стоять точка с запятой.
Пример. Следующая строчка:
printf("%d
\n", a>b?a:b );
аналогична записи
if (a>b)
printf("%d \n", a); else printf("%d \n", b);
то есть, на экран будет выведено наибольшее из двух значений.
18. Составной
оператор в языке Си. Примеры использования.
Когда в тексте программы нужно представить цепочку последовательно стоящих операторов в качестве одного составного оператора, используют операторные скобки, которые в языке Си выглядит так: { }.
Например:
#include
<stdio.h>
void main()
{
float a, b, c=b=a=0;
scanf("%e", &a);
scanf("%e", &b);
if (b!=0)
{
c=a/b;
printf("%e", c);
}
else printf("Низя делить на ноль!");
}
Обратите внимание, что, в отличие от Паскаля, где перед закрывающей операторной скобкой end; можно было не ставить точку с запятой после инструкции, например:
begin
c:=a/b;
writeln(c)
end;
в языке Си после каждой инструкции должна стоять точка с запятой.
19. Оператор
if-else. Синтаксис. Вложенные операторы if-else. Примеры.
Оператор выбора if-else в Си имеет следующий синтаксис:
if (выражение) инструкция1;
else инструкция2;
Например:
if (a<b) printf("%d",a);
else z=b;
Операторы выбора могут вкладываться друг в друга.
См. также вопрос 9.
20. Переключатель
switch. Синтаксис. Примеры.
Switch – многовариантный выбор.
switch (выражение) {
case константа1: инструкция1;
case константа2: инструкция2;
case константа3: инструкция3;
default: инструкция;
}
switch имеет свойство проваливаться на следующий уровень. Чтобы этого не происходило, в конце каждой ветви нужно ставить оператор досрочного завершения break;
Примеры:
int a=1;
switch
(a){
case 1:a++;
case 2:a++;
case 3:a++;
default a++;
}
результат: a=5;
int a=1;
switch
(a){
case 1:a++;break;
case 2:a++; break;
case 3:a++; break;
default a++; break;
}
результат: a=2;
21. Циклы с условием
в языке Си. Синтаксис. Примеры.
while – цикл с предусловием
его синтаксис:
while(выражение) <инструкция>
цикл while выполняется, пока (выражение) истинно.
Например:
while(a<100){
b:=a;
a++;
}
do <инструкция> while(выражение) – цикл с постусловием
цикл do while выполняется, пока (выражение) истинно.
Например:
do a++
while(a<4);
22. Цикл for. Синтаксис. Примеры.
for это цикл со счетчиком
for(выр1;выр2;выр3)<инструкция>
выр1 – инициализация
выр2 - условие
выр3 – вызов функции
Любое из выр1, выр2, выр3 может быть пропущено.
Внутри цикла возможны любые операции со счетчиком
Значение счетчика известно после выхода из цикла
Пример:
for(int i=0;i<10;i++) s+=i; //сумма всех чисел от 0 до 10.
for(;;){} – бесконечный цикл.
23. Инструкции break
и continue. Примеры.
break – оператор досрочного завершения блока.
if(условие) break;
for(i=0;i<10;i++){
if (i==5) break;
else
printf ("%d",i); //напечатает 01234
}
continue - оператор досрочного завершения инструкции
continue (внутри цикла) – текущая операция завершается, выполняется следующая
for(i=0;i<10;i++){
if
(i==5) continue;
else
printf ("%d",i); //напечатает 012346789
}
24. Структура
программы на языке Си.
1) Подключаем модули при помощи директивы #include. Например: #include <stdio.h> Здесь же можно использовать другие директивы, например, #define.
2) Описываются глобальные константы (можно описать и глобальные переменные, но это зло).
3) Перечисляем прототипы
используемых функций. Например:
void printlist(ref head);
4) Основная часть программы:
void main(){
…
}
5) Реализация процедур.
25. Функции в языке Си. Фактические, формальные параметры. Способы
передачи параметров. Примеры.
Наличие функций – это суть модульного программирования.
Задание функций:
<Тип Возвращаемого Результата> <Имя Функции>(<Формальные параметры>){
<Последовательность операторов>
}
Теперь рассмотрим всё по частям:
Тип Возвращаемого Результата:
Это может быть любой тип данных Си, или любой описанный пользователем тип, или указатель на него. Если функция возвращает фигу с маслом (то есть ничего не возвращает) то типом результата будет void,
Например, void printList(lnode*root){…}
Имя Функции:
Название функции (как и переменной) может состоять из больших и малых букв латинского алфавита, цифр и знака _, и не должно начинаться с цифры.
Формальные параметры:
В теле функции мы работаем с формальными параметрами. При выполнении функции над переданными ей параметрами (фактическими) будут выполняться те же действия, что и с формальными параметрами при её описании. При задании параметров сначала указывается тип параметра, потом его имя (Всё как у переменной!), параметры перечисляются через запятую, тип указывается каждый раз снова.
Например, char getSymbol(int n, int m, char**matrix){…}
Если функция не принимает никаких параметров, то скобки () всё равно необходимо написать, пусть даже и пустые.
Например,
void makeStackOverflow(){
double a_place1=4354354353544354;
double a_place2=8987987988987978;
double a_place3=7676575675667477;
makeStackOverflow();
}
Последовательность операторов:
Здесь всё как и в теле программы (ФУНКЦИИ mian() ) про return см. в вопросе №26.
Передача параметров:
Дети, запомните: в Си параметры передаются по значению! Если нужно изменить значение, то необходимо передать функции указатель на эту переменную.
Например: void increment(int*x){(*x)++;}
Но если мы изменим сам указатель, x=NULL; то с переменной ничего плохого не случится (разве что мы её уже не изменим). Если в теле функции необходимо изменить указатель, то лучше сделать его возвращаемым значением. Хотя, можно, конечно, и передавать указатель на указатель на указатель на указатель на указатель на указатель на указатель на указатель………… (С) Copyright Миронов А. С.
26. Функции в языке Си. Прототипы функций. Инструкция return.
Возвращаемый результат. Примеры.
См. вопрос №25.
По сути, прототип функции – это первая строка описания функции (там где имя), только вместо открывающей фигурной скобки – точка с запятой « ; ». Прототипы функций пишутся перед описанием всех функций (после #include’ов и описаний типов). Без прототипа функция не видна и, даже если она описана, компилятор будет выдавать ошибку, что вот “function fuckMironov(&Tozik); should have a prototype” не мешало бы. Хотя в нашем компиляторе это срабатывает только тогда, когда функция упоминается до её описания.
Инструкция return завершает выполнение функции с возвращением результата, равного значению переменной или константы, стоящей после return, также там может стоять вызов функции. Тип значения, стоящего после return должен совпадать с типом возвращаемого значения.
Например:
Прототип:
int getMark(char*answer);
Функция:
int
getMark(char*answer){
if(answer!=NULL)
return 5;
else
return 4;
}
27. Область видимости переменных, функций. Примеры.
См. вопрос №28.
Внешние переменные видны в той функции, в которой они описаны, а так же во всех функциях, являющихся для этой функции внутренними.
Не являющиеся глобальными переменные, в том числе и статические, видны в тех функциях, в которых они описаны.
Глобальная переменная, как и глобальная функция, может быть видна в другой функции, если она описана в тексте программы перед описанием этой функции. Помимо этого, функция будет видна в других функциях, если её прототип предшествует в тексте программы этим функциям.
28. Внешние, автоматические, статические переменные. Время жизни,
назначение, инициализация. Примеры.
Внешние переменные описываются вне тех функций, в которых они используются. Их могут использовать разные функции, поэтому эти переменные ещё называются глобальными. Можно описать глобальную переменную вне всех функций в начале программы, и тогда её значение смогут изменять все функции программы.
Можно описать переменную в какой-то функции и затем её использовать в функции, являющейся внутренней для этой функции. Тогда такая переменная будет называться локально-глобальной.
В Си есть ещё и статические переменные, которые не являются внешними. При выходе из функции не теряются, а будут снова доступны этой функции при следующем вызове. При этом в других частях программы эти переменные не доступны.
static int a;
static int b=32544;
Ещё есть регистровые переменные, которые заносятся в регистр для пущей важности, извините, для скорейшего доступа.
register float c=45.5656;
Но места в регистре мало,
если его не хватает, то переменная заносится в обычную область памяти.
Каждая переменная существует в пределах той функции, в которой она описана. Соответственно, глобальная переменная, описанная вне функций, существует всё время, пока работает программа. Статическая переменная тоже существует всё время, пока работает программа, независимо от того, где она описана.
См. также вопрос №11.
29. Рекурсивные
функции в Си. Примеры.
Рекурсивной называется процедура, вызывающая саму себя или другую процедуру, которая, в свою очередь, обращается к первой процедуре; возможны и более сложные конструкции. В первом случае рекурсия называется прямой, а во втором - косвенная. Глубина рекурсии – это количество рекурсивных вызовов подпрограммы. Глубина рекурсии – конечная величина.
void recurs(формальные параметры)
{
if (!<условие выхода из рекурсии>) recurs(другие формальные параметры);
}
30. Статические
массивы в языке Си. Объявления, инициализация. Примеры.
Статический массив – массив, размер которого задан на момент компиляции.
Статические массивы в Си объявляются: тип имя_массива[размер]
например: int a[9];
При описании можно инициализировать массив:
float d[]={1.0, 2.4, 5.2, 7.4}; При этом размер массива не задаётся.
В статическом массиве в Си нумерация начинается с нулевого элемента.
Символьный массив (строковый) занимает на один байт больше из-за "\0" – символа конца строки.
31. Строки в Си.
Объявления, инициализация, структура. Примеры.
Строка в си представляет из себя массив типа char, последний элемент которого содержит символ "\0" – символа конца строки.
Объявляется char str_name[str_size];
Индексация идет с 0. (т. е. первый символ имеет индекс 0)
32. Указатели в Си.
Типы указателей, определение, использование. Операторы & и *. Примеры.
Указателем называется переменная, содержащая адрес другой переменной. Для того, чтобы описать в программе переменную указатель, надо использовать символ "*". Тип указателя должен соответствовать типу переменной. Например: в переменную, описанную следующим образом: char *a; можно поместить адрес любой переменной типа char.
Оператор взятия адреса
(&) возвращает адрес переменной. Например: char b, *a; a=&b;
Оператор косвенного
доступа (*) возвращает значение, хранящееся по указанному адресу. Например,
если a=&b, то *a вернёт значение, хранящееся в b.
Для того, чтобы хранить в какой-то переменной адрес другой переменной, являющейся указателем, надо описать эту переменную как указатель на указатель. Например:
int **m, *n, p; {p – целочисленная переменная, n – указатель на целочисленный тип, m – указатель на указатель на целочисленный тип.}
n=&p; m=&n;
или: m=&&p;
для взятия адреса:
p=*n; n=*m; p=**m;
33. Функции.
Передача указателя, как параметра функции. Указатель, как
результат,
возвращаемый функцией. Примеры.
См. вопрос №25.
34. Связь между
указателями и массивами. Примеры.
Так как в языке Си каждый элемент массива имеет адрес, на единицу отличающийся от адреса предыдущего элемента, мы можем посылать в функцию не адреса всех элементов массива, а только адрес первого элемента. Например:
int *a, b[10]; {указатель на целочисленный тип и статический массив целочисленных переменных}
a=&(b[0]); {заносим в a адрес первого элемента массива;}
printf("%d, %d, %d",*a, *(a+1), *(a+5)); {выводим на экран значения первого, второго и шестого элементов массива.}
Вместо сложной записи &(b[0]) в Си можно писать просто b, так как разработчики языка позаботились о том, чтобы это было одно и то же. (То есть, если имеется статический массив b[10], то b возвращает адрес первого элемента этого массива.)
35. Создание
динамических массивов с использованием указателей. Примеры.
См. вопрос №34.
Использование указателей позволяет создавать в Си динамические массивы. Но для этого нам ещё потребуется выделять под массив область в динамической памяти. Для этого используется функция malloc(), содержащаяся в модуле <stdlib.h>. Вызвав её, мы выделим область памяти определённого размера для определённого типа, например:
(char*)malloc(100); выделит 100 байт для типа char.
Так как переменные большинства типов занимают размер более 1 байта (например, int – 2 байта), то нам необходимо выделить количество памяти, кратное размеру типа данных. Например: (int*)malloc(200); выделит память для 100 переменных типа int.
Чтобы нам не задумываться о том, сколько байт занимает тот или иной тип, мы можем воспользоваться функцией sizeof. Например, sizeof(int) вернёт значение 2. Таким образом мы можем писать (int*)malloc(100*sizeof(int)); чтобы выделить память для ста переменных int.
Функция malloc не только выделяет память, но и возвращает адрес первого элемента выделенной области памяти, чтобы мы потом могли эту область использовать. Поэтому а программе мы используем malloc так:
int *a;
a=(int*)malloc(100*sizeof(int));
Теперь у нас есть массив из ста переменных int, с которым мы можем работать так же, как если бы он был описан при помощи строчки int a[100];
Для того, чтобы освободить
занятую память, используется процедура free(). В скобках указывается адрес первого элемента массива. Например:
free(a);
36. Структуры.
Синтаксис, объявление, инициализация, доступ к членам структуры. Примеры.
Структура - это составной тип данных, имеющий название и поля. Поля – это члены структуры. Структура описывается в качестве пользовательского типа данных при помощи зарезервированного слова struct. Например:
struct MyType {
int
pole1;
char
pole2, pole3;
int *pole4;
};
Количество полей может быть любым, и все они могут иметь разный тип. Причём это может быть и пользовательский тип, описанной в другой структуре. После закрывающей фигурной скобки должна стоять точка с запятой, причём перед этой точкой с запятой можно перечислить глобальные переменные, которым будет задан этот тип.
Чтобы описать переменную пользовательского типа в программе, пишем, например:
struct MyType a;
При этом слово struct можно и не писать: MyType a;
Чтобы обратиться к полю структуры, используется оператор "." (точка). Например:
a.pole1=5; a.pole2='s'; a.pole4=a.&(pole1).
37. Структуры и
функции. Структура, как параметр функции. Структура, как результат,
возвращаемый функцией. Примеры.
Структуры можно передавать в качестве параметра и принимать как результат, точно так же, как и переменные обычных типов.
В качестве примера возьмём структуру MyType, описанную в вопросе №36. Мы можем описать функцию, возвращающую результат типа MyType:
struct MyType MyFunc();
При этом слово struct можно опустить.
Точно так же можно передавать в функцию значение типа MyType:
int MyFunc(MyType a);
38. Указатель на
структуру. Оператор sizeof. Примеры.
Для хранения адреса структуры можно описать переменную как указатель на структуру, например: MyType *adr;
Чтобы поместить в
переменную adr адрес
структуры, пишем: adr=MyType; (та же история, что с
адресом массива – см. вопрос №34).
А вот для того, чтобы создать массив переменных пользовательского типа (естественно, массив будет динамическим), нам понадобится функция sizeof (см вопрос №35), так как кто его знает, сколько наш пользовательский тип байт занимает.
Например:
MyType *MassStruc;
MassStruc=(MassStruc*)malloc(50*sizeof(MassStruc));
Имеем массив из 50 переменных типа MassStruc.
39. Структуры со ссылками на себя. Связный список. Основные операции. Примеры.
Структуры со ссылками на себя
– см. вопрос №40.
Одним из примеров такой
структуры является элемент связанного списка.
В структуре элемента связанного списка имеется поле, которое может содержать указатель на следующий элемент списка.
Основные операции: добавление, удаление и поиск элемента.
Добавление может осуществляться разными способами. Наиболее простой способ – когда каждый элемент добавляется в голову списка. Чуть сложнее способ, когда новый элемент добавляется в конец списка. Упорядоченное добавление элементов в список ещё сложнее.
40. Структуры со
ссылками на себя. Дерево поиска. Основные операции. Примеры.
Структуры со ссылками на себя имеются поля, тип которых совпадает с типом самой структуры. Такое описание структуры называется рекурсивным.
Одним из примеров такой структуры является элемент двоичного дерева поиска.
В структуре элемента дерева поиска имеются такие поля, как указатель на левый элемент (который имеет меньшее значение) и правый (который имеет большее значение).
Корнем дерева называется указатель на первый элемент дерева. Элементы, которые не ссылаются на другие элементы, называются терминальными. Остальные элементы называются внутренними узлами дерева.
Максимальное количество уровней определяет высоту дерева.
Основные операции: поиск, добавление, удаление элемента, обход.
Поиск осуществляется следующим образом: если корень дерева не является тем элементом, который мы ищем, то переходим к поиску в левое поддерево (если искомое значение меньше) или в правое (если больше).
При построении дерева поиска определяется место, куда следует записать очередное значение по следующему алгоритму:
- если дерево пустое, элемент записывается в корень;
- если добавляемый элемент имеет значение меньше, чем у корня, этот же алгоритм вызывается для левого элемента корня;
- если добавляемый элемент имеет значение больше, чем у корня, этот же алгоритм вызывается для правого элемента корня.
Обход можно осуществлять тремя способами: сверху вниз, снизу вверх и слева направо. В результате обхода получаем упорядоченную последовательность.
