Автоматические и динамические переменные
В некоторых случаях без динамических переменных не удается обойтись, но их
количество можно уменьшить за счет тщательного проектирования структуры про-
граммы и применения процедурной абстракции. Большинство переменных в про-
граммах из предыдущих лекций являются автоматическими переменными. Они ав-
томатически создаются, когда начинает выполнятся блок (или функция), где эти пе-
ременные объявлены. При выходе из блока (или функции) переменные автоматически
уничтожаются. Поэтому в хорошо структурированной программе не слишком много
операторов для создания и уничтожения переменных.
(ПРИМЕЧАНИЕ. В Си++, кроме автоматических и динамических, существуют статические пере-
менные. Для объявления статической переменной в ее операторе описания надо перед названием ти-
па данных добавить служебное слово "static". Статические переменные существуют в течение все-
го времени выполнения программы. Вместо статических переменных чаще используются глобальные
константы, которые объявляются в заголовочных файлах или в начале исходных файлов.)
Связные списки
В этом параграфе кратко рассматривается одна из разновидностей абстракт-
ных типов данных (abstract data type, ADT) – связный список. Связный список интере-
сен тем, что при его реализации применяются указатели. О других абстрактных типах
данных более подробно будет говориться в последующих лекциях.
Связный список состоит из узлов. В каждом узле хранятся некоторые данные и
указатель на следующий узел списка (рис. 9). В программе, работающей со списком,
обычно есть еще один отдельный указатель, ссылающийся на первый узел списка
("pointer" на рис. 9). В указатель последнего узла принято записывать значение
"NULL".
Размер связных списков, в отличие от массивов, можно изменять динамически
(во время выполнения программы можно добавлять/удалять отдельные узлы в любом
месте списка).
Рис. 9.. Структура связного списка.
Далее будем рассматривать реализацию на Си++ связного списка для хранения
символьных строк. Сначала определим на Си++, из чего состоит "узел" нашего спи-
ска. Для этого надо объединить строку и указатель в тип данных "узел". Это делается
с помощью оператора описания структуры. Оператор "struct" позволяет создать
новый тип данных, в отличие от оператора "typedef", который, по существу, предна-
значен для присвоения нового имени уже существующему типу данных.
|
Структура – это набор разнотипных переменных (в противоположность масси-
ву, состоящему из элементов одного типа). Применительно к нашей задаче, тип "node"
это
структура,
состоящая
из
символьного
массива
размером
MAX_WORD_LENGTH и указателя на такую же структуру:
struct node
char word[MAX_WORD_LENGTH];
node* ptr_to_next_node;
};
Обратите внимание на точку с запятой после закрывающей фигурной скоб-
ки "}".Слово "struct" является служебным словом Си++ (это аналог "record" в Пас-
кале). Возможно описание узла с применением нового типа данных "указатель на
узел":
struct node;
typedef node* node_ptr;
struct node
{
char word[MAX_WORD_LENGTH];
node_ptr ptr_to_next_node;
};
В строке "struct node;" имя "node" является пустым описанием. Оно напоми-
нает прототип (описание) функции – детали структуры "node" определяются в после-
дующих строках. Пустое определение позволяет в следующей строке с помощью опе-
ратора "typedef" объявить новый тип данных "указатель на структуру node".
5.1 Операторы "." и "->"
После определения структуры "node (узел)" в программе можно объявлять пе-
ременныеэтоготипа:
node my_node, my_next_node;
Для доступа к полям (внутренним переменным) структуры "my_node" надо
пользоваться оператором "." (точка):
cin >> my_node.word;
my_node.ptr_to_next_node = &my_next_node;
Допустим, что в программе были объявлены указатели на узлы, а сами узлы
списка были созданы динамически:
node_ptr my_node_ptr, another_node_ptr;
my_node_ptr = new node;
another_node_ptr = new node;
В таком случае для доступа к полям узлов можно пользоваться совместно опе-
раторами "звездочка" и "точка":
cin >> (*my_node_ptr).word;
(*my_node_ptr).ptr_to_next_node = another_node_ptr;
Более кратко эти выражения записываются с помощью специального операто-
ра "->", который предназначен для доступа к полям структуры через указатель:
|
|
cin >> my_node_ptr->word;
my_node_ptr->ptr_to_next_node = &my_next_node;
Другимисловами, имена "my_node_ptr->word" и "(*my_node_ptr).word" обозна-
чают одно и то же – поле "word" структуры типа "node", на которую ссылается указа-
тель "my_node_ptr ".
5.2 Создание связного списка
Ниже приведена функция создания связного списка для хранения символьных
строк, которые пользователь вводит с клавиатуры. Указатель "a_list" ссылается на
первый узел нового списка (на "голову" списка). Для завершения ввода данных поль-
зователь должен ввести специальный завершающий символ (точку).
void assign_list( node_ptr& a_list )
{
node_ptr current_node, last_node;
assign_new_node( a_list );
cout << "Введите первое слово";
cout << "(или '.' для завершения списка): ";
cin >> a_list->word;
if ( !strcmp( ".", a_list->word ) )
{
delete a_list;
a_list = NULL;
}
current_node = a_list;
/* СТРОКА 13 */
while ( current_node != NULL )
{
assign_new_node( last_node );
cout << "Введите следующее слово";
cout << "(или '.' для завершения списка): ";
cin >> last_node->word;
if ( !strcmp( ".", last_node->word ) )
{
delete last_node;
last_node = NULL;
}
current_node->ptr_to_next_node = last_node;
current_node = last_node;
}
}
Фрагментпрограммы 5.1.
Функция "assign_new_node(...)" для создания нового узла аналогична
функции "assign_new_int(...)" из программы 1.5.
Порядок действий функции "assign_list(...)" поясняется на рис. 10-16. На
рис. 10 показано состояние программы после выполнения вызова:
assign_new_node( a_list );
Рис. 10.. Состояние программы 5.1 после создания нового списка.
Предположим, что пользователь напечатал слово "мой". Тогда после 13-й стро-
ки программа окажется в состоянии, показанном на рис. 11.
Рис. 11.. Состояние программы после заполнения данными первого узла.
После первой строки в теле цикла "while" программа перейдет в состояние,
показанное на рис. 12.
Рис. 12.. В хвост списка был добавлен новый узел.
Далее, если пользователь напечатал слово "список", то после итерации цикла
"while" программа будет в состоянии, как на рис. 13.
Рис. 13. Последний узел списка заполнен данными и в предыдущий узел по-
мещен соответствующий указатель.
После выполнения первой строки во второй итерации цикла "while" состояние
программы см. рис. 14.
Рис. 14.. В хвост списка был добавлен новый узел.
Допустим, в ответ на следующий запрос пользователь напечатает ".". Тогда
после завершения цикла "while" программа будет в состоянии, как на рис. 15.
|
|
|
|
|
Рис. 15.. Был удален последний узел списка.
Символ "." сигнализирует о том, что пользователь захотел прекратить ввод
данных для списка. Поэтому функция "assign_list(...)" завершается и при выходе
из нее автоматически уничтожаются локальные переменные-указатели "current_node"
и "last_node" (которые были объявлены в теле функции). После возврата из функции
состояние программы будет таким, как на рис. 16.
Рис. 16.. Состояние программы 5.1 после выхода из функции ввода списка с
клавиатуры.
Структуры данных
Структурой в языке C называется совокупность логически связанных переменных различных типов, сгруппированных под одним именем для удобства дальнейшей обработки.
Структура – это способ связать воедино данные разных типов и создать пользовательский тип данных. В языке Pascal подобная конструкция носит название записи.
Определение структуры
Структура – тип данных, задаваемый пользователем. В общем случае при работе со структурами следует выделить четыре момента:
- объявление и определение типа структуры,
- объявление структурной переменной,
- инициализация структурной переменной,
- использование структурной переменной.
Определение типа структуры представляется в виде
struct ID
{
<тип><имя 1-го элемента>;
<тип> <имя 2-го элемента>;
…………
<тип> <имя последнего элемента>;
};
Определение типа структуры начинается с ключевого слова struct и содержит список объявлений, заключенных в фигурные скобки. За словом struct следует имя типа, называемое тегом структуры (tag – ярлык, этикетка). Элементы списка объявлений называются членами структуры или полями. Каждый элемент списка имеет уникальное для данного структурного типа имя. Однако следует заметить, что одни и те же имена полей могут быть использованы в различных структурных типах.
Определение типа структуры представляет собой шаблон (template), предназначенный для создания структурных переменных.
Объявление переменной структурного типа имеет следующий вид:
struct ID var1;
при этом в программе создается переменная с именем var1 типа ID. Все переменные, использующие один шаблон (тип) структуры, имеют одинаковый набор полей, однако различные наборы значений, присвоенные этим полям. При объявлении переменной происходит выделение памяти для размещения переменной. Шаблон структуры позволяет определить размер выделяемой памяти.
В общем случае, под структурную переменную выделяется область памяти не менее суммы длин всех полей структуры, например,
struct list
{
char name[20];
char first_name[40];
int;
}L;
В данном примере объявляется тип структура с именем list, состоящая из трех полей, и переменная с именем L типа struct list,при этом для переменной L выделяется 64 байта памяти.
Отметим, что определение типа структуры может быть задано в программе на внешнем уровне, при этом имя пользовательского типа имеет глобальную видимость (при этом память не выделяется). Определение типа структуры также может быть сделано внутри функции, тогда имя типа структуры имеет локальную видимость.
Создание структурной переменной возможно двумя способами: с использованием шаблона (типа) или без него.
Создание структурной переменной pt на основе шаблона выполняется следующим образом:
struct point //Определение типа структуры
{
int x;int y;
};
……
struct point pt; //Создание структурной переменной
Структурная переменная может быть задана уникальным образом:
struct //Определение анонимного типа структуры
{
char name[20];
char f_name[40];
char s_name[20];
} copymy; //Создание структурной переменной
При размещении в памяти структурной переменной можно выполнить ее инициализацию. Неявная инициализация производится для глобальных переменных, переменных класса static. Структурную переменную можно инициализировать явно при объявлении, формируя список инициализации в виде константных выражений.
Формат: struct ID name_1={значение1, … значениеN};
Внутри фигурных скобок указываются значения полей структуры, например,
struct point pt={105,17};
при этом первое значение записывается в первое поле, второе значение – во второе поле и т. д., а сами значения должны иметь тип, совместимый с типом поля.
Над структурами возможны следующие операции:
- присваивание значений одной структурной переменной другой структурной переменной, при этом обе переменные должны иметь один и тот же тип;
- получение адреса переменной с помощью операции &;
- осуществление доступа к членам структуры.
Присваивание значения одной переменной другой выполняется путем копирования значений соответствующих полей, например:
struct point pt={105,15},pt1;
pt1=pt;
В результате выполнения этого присваивания в pt1.x будет записано значение 105, а в pt1.y – число 15.
Работа со структурной переменной обычно сводится к работе с отдельными полями структуры. Доступ к полю структуры осуществляется с помощью операции. (точка) посредством конструкции вида:
имя_структуры.имя_поля_структуры;
при этом обращение к полю структуры представляет собой переменную того же типа, что и поле, и может применяться везде, где допустимо использование переменных такого типа.
Например,
struct list copy = {"Ivanov","Petr",1980};
Обращение к "Ivanov" имеет вид copy.name. И это будет переменная типа указатель на char. Вывод на экран структуры copy будет иметь вид:printf("%s%s%d\n",copy.name,copy.first_name,copy.i);
Структуры нельзя сравнивать. Сравнивать можно только значения конкретных полей.
Структуры и функции
Структуры могут быть переданы в функцию в качестве аргументов и могут служить в качестве возвращаемого функцией результата.
Существует три способа передачи структур функциям:
- передача компонентов структуры по частям;
- передача целиком структуры;
- передача указателя на структуру.
Например, в функцию передаются координаты двух точек:
void showrect(struct point p1,struct point p2)
{
printf("Левый верхний угол прямоугольника:%d %d\n",
p1.x, p1.y);
printf("Правый нижний угол прямоугольника:
%d %d\n", p2.x, p2.y);
}
При вызове такой функции ей надо передать две структуры:
struct point pt1={5,5},
pt2={50,50};
showrect(pt1,pt2);
Теперь рассмотрим функцию, возвращающую структуру:
struct point makepoint (int x,int y) /*makepoint – формирует точку по компонентам x и y*/
{
struct point temp;
temp.x = x;
temp.y = y;
return temp;
}
Результат работы этой функции может быть сохранен в специальной переменной и выведен на экран:
struct point buf;
buf=makepoint(10,40);
printf("%d %d\n",buf.x,buf.y);
После выполнения этого фрагмента на экран будут выведены два числа: 10 и 40.
Указатели на структуру
Если функции передается большая структура, то эффективнее передать указатель на эту структуру, нежели копировать ее в стек целиком. Указатель на структуру по виду ничем не отличается от указателей на обычные переменные.
Формат: struct point *pp;
где pp – указатель на структуру типа struct point, *pp – сама структура, (*pp).x и (*pp).y – члены структуры.
Скобки (*pp).x необходимы, так как приоритет операции (.) выше приоритета операции (*). В случае отсутствия скобок *pp.x понимается как *(pp.x).
Инициализация указателя на структуру выполняется так же, как и инициализация указателей других типов: struct point var1, *S1; здесь var1 – структурная переменная, *S1 – указатель на структуру.
Для определения значения указателя ему нужно присвоить адрес уже сформированной структуры:
S1 = &var1;
Теперь возможно еще одно обращение к элементам структуры:
(*S1).name.
Указатели на структуры используются весьма часто, поэтому для доступа к ее полям была введена короткая форма записи. Если р – указатель на структуру, то p → <поле структуры>зволяет обратиться к указанному полю структурной переменной.
Знак → (стрелка) вводится с клавиатуры с помощью двух символов: '–' (минус) и '>' (больше). Например, pp → x; pp → y.
Операторы доступа к полям структуры (.) и (→) вместе с операторами вызова функции () и индексами массива [] занимают самое высокое положение в иерархии приоритетов операций в языке C.
Указатели на структуру используются в следующих случаях:
· доступ к структурам, размещенным в динамической памяти;
· создание сложных структур данных – списков, деревьев;
· передача структур в качестве параметров в функции.
Массивы структур
При необходимости хранения некоторых данных в виде нескольких массивов одной размерности, но разного типа, возможна организация массива структур. Наглядно массив структур можно представить в виде таблицы, где столбцы таблицы представляют собой поля структуры, а строки – элементы массива структур.
Например, имеется два разнотипных массива:
char c[N];
int i[N];
Объявление
struct key
{
char c;
int i;
} keytab[N];
создает тип структуры key и объявляет массив keytab[N], каждый элемент которого есть структура типа key.
Возможна запись:
struct key
{
char c;
int i;
};
struct key keytab[N];
Инициализация массива структур выполняется следующим образом:
struct key
{
char c;
int i;
} keytab[]={
'a', 0,
'b', 0
};
В этом примере создается массив на две структуры типа key с именем keytab. Рассмотрим обращение к полю структуры в этом случае – для примера выведем на экран содержимое массива:
for(int i=0;i<2;i++)
printf("%c %d\n",keytab[i].c,keytab[i].i);
При обращении к полю структуры сначала происходит обращение к элементу массива (keytab[i]), а затем только обращение к полю структуры (keytab[i].c).
Доступ к полю элемента массива структур может быть получен через константу-указатель на массив и смещение внутри массива, например, доступ к полю элемента массива с номером i следует записать следующим образом:
(*(keytab+i)).c или (keytab+i)→ c.
Массив структур также может быть передан в функцию в качестве аргумента, передача массива происходит через указатель на массив.
Пример программы, в которой массив точек формируется и выводится на экран с помощью функций:
#include <stdio.h>
#define N 5
struct point
{
int x,y;
};
void form_mas(struct point* mas, int n)
{
printf("Enter koordinates!\n");
for(int i=0;i<n;i++)
{
printf("x→");
scanf("%d",&mas[i].x);
printf("y→");
scanf("%d",&mas[i].y);
}
}
void print_mas(struct point* mas, int n)
{
printf(" x y\n");
for(int i=0; i<n; i++)
printf("%4d %6d\n",(mas+i)→x,(mas+i)→y);
}
int main()
{
struct point Points[N];
form_mas(Points,N);
print_mas(Points,N);
return 0;
}
Функция form_mas() заполняет массив точек, который передан в функцию через указатель mas. Параметр функции n определяет количество элементов массива. Доступ к элементу массива – через операцию . (точка). Выражение &mas[i].x вычисляет адрес элемента структуры mas[i].x, так как операция & имеет более низкий приоритет, чем операции [] и · (точка).
Функция print_mas() выводит массив на экран. Передача массива в функцию происходит также через указатель mas. Параметр n – количество элементов массива. Доступ к элементу массива – через операцию → (стрелка).
Вложенные структуры
Полем структурной переменной может быть переменная любого типа, в том числе другая структурная переменная. Поле, представляющее собой структуру, называется вложенной структурой.
Тип вложенной структуры должен быть объявлен раньше. Кроме того, структура не может быть вложена в структуру того же типа.
Объявление вложенной структуры:
struct point
{
int x,y;
};
struct rect
{
struct point LUPoint, RDPoint;
char BorderColor[20];
};
struct rect Rect;
В переменной Rect два поля LUPoint (точка, соответствующая левому верхнему углу прямоугольника) и RDPoint (точка, соответствующая правому нижнему углу) представляют собой вложенные структуры. Для доступа к полю вложенной структуры следует сначала обратится к внешней структуре, затем к вложенной: Rect.LUPoint.x.
Пример создания и использования вложенной структуры:
struct rect Rect={10,5,50,25,"White"};
printf("Параметры прямоугольника:\n");
printf("Координаты левого верхнего угла %d %d\n", Rect.LUPoint.x, Rect.LUPoint.y);
printf("Координаты левого верхнего угла %d %d\n", Rect.RDPoint.x, Rect.RDPoint.y);
printf("Цвет границы: %s\n", Rect.BorderColor);
В качестве поля структуры также можно использовать указатели на любые структуры, в том числе на структуры того же типа:
struct PointList
{
int x,y;
struct PointList* LastPoint;
};
Структуры, имеющие в своем составе поля-указатели на такую же структуру, используются для создания сложных структур данных – списков, деревьев.
Использование синонима типа
Ключевое слово typedef позволяет в программе создать синоним типа, который может использоваться для объявления переменных, параметров функций. Синоним можно создать для любого существующего типа (int, float и т. д.), в том числе для пользовательского типа – структуры или массива.
Пример 1. Создание синонима структуры:
typedef struct point
{
int x,y;
} POINT;
Идентификатор POINT представляет собой синоним типа point. С помощью синонима POINT можно объявить переменную:
POINT pt1;
или передать переменную в функцию:
void ShowRect(POINT pt1,POINT pt2);
Пример 2. Создание синонима массива:
typedef float mas[4][5];
Идентификатор mas обозначает тип – двумерный массив, состоящий из четырех строк и пяти столбцов. Этот идентификатор можно использовать для объявления переменной – массива A:mas A;
или для передачи массива в функцию:
void FormMas(mas A,int m,int n);
Объединения
Объединение – это тип данных, позволяющий переменным различного типа использовать одну и ту же область памяти. Для объявления объединения используется ключевое слово union. Объединение, так же как и структура, содержит несколько полей. Однако в любой момент времени доступно только одно поле. Под объединение выделяется столько памяти, сколько требуется для размещения самого большого поля. Все поля поочередно используют выделенную память для хранения своих значений.
Определение типа:
union tag
{
тип1 переменная1;
тип2 переменная2;
……
};
где tag – имя типа.
Объявление переменной:
union tag u1;
или
union tag
{
тип1 переменная1;
тип2 переменная2;
……
} u1;
Инициализация объединения может быть выполнена при объявлении, при этом тип инициализирующего значения должен соответствовать первому полю объединения:
union tag
{
int i;
doubled;
} u={10};
Доступ к полю объединения осуществляется с помощью операций – · (точка) и → (стрелка).
printf("%d",u.i);
Результат: 10.
union tag *p=&u;
printf("%d", p→i);
Результат: 10.
При обращении к полям объединения следует помнить, какое поле размещалось в памяти последним. Если пытаться извлекать данные с помощью поля другого типа, значение может быть прочитано неправильно.
Пример
union tag
{
int i;
double d;
} u={1.2};
printf("%d\n",u.i); //Вывод на экран числа 1
printf("%lf\n",u.d); //Вывод на экран числа 0
Ответ «1» получен потому, что инициализация должна соответствовать типу первого поля – int;ответ «0» – следствие того, что данные типа int прочитаны полем типа floatнеправильно.
Случайные числа
Иногда в C++ для начинающих программистов возникает необходимость использовать различные случайные значения, например, для проверки правильности работы написанной программы сортировки чисел, требуется проверить как будет действовать программа, чтобы проверить действие работы такой программы требуется вводить различные значения и их может быть много. Для ввода случайных различных значений как раз и используют генератор значений. Также его очень часто используют в играх – простейший пример угадай число. Для создания паролей, да и вообще много где.
Такой генератор значений на C++ пишется очень просто:
| #include <stdlib.h> #include <iostream.h> int main() { srand(time(0)); cout<<rand()%2; return 0; } |
При каждом новом запуске такой программы на экран будет выводиться случайным образом либо 0 - либо 1.
Если разбирать этот маленький кусочек кода C++, то можно пояснить следующее команда srand вызывается для того, чтобы при необходимости каждый раз генерировать новые случайные значения.
А команда для вызова случайно генерированных значений объявляется как rand- Когда объявили команду randоткрываем и закрываем фигурные скобки, после чего указываем диапазон случайных значений (В нашем приведенном примере мы указали, что нам нужно использовать 2 случайных значения). По умолчанию диапазон случайных значений начинает отсчет от нуля.
Написанным нами кодом мы объяснили генератору случайных значений, что нам нужны 2 значения, генерированных случайным образом.
0 и 1 = 2 значения, а так как по умолчанию в генераторе случайных значений отсчет идет от нуля, то наша программа и будет выводить на экран либо 0 - либо 1 (что как раз соответствует двум значениям)
Если бы мы написали:
| #include <stdlib.h> #include <iostream.h> int main() { srand(time(0)); cout<<rand()%101; return 0; } |
то у нас бы выводился набор разных случайных значений от 0 до 100 (101 значение)
Чтобы указать какие именно значения нужно использовать, в команде rand сразу после закрывающейся круглой скобки ставится знак % и пишутся нужные нам случайные значения.
| int main() { srand(time(0)); cout<<rand()%201; return 0; } |
Выведет нам на экран случайно генерированные числа от 0 до 200
Но нам может потребоваться диапазон не от нуля, а от другого значения, например чтобы генератор случайных значений выбирал числа из диапазона 200-400 - тогда мы просто прибавляем к нашему генератору необходимое число: После прибавления начальная точка диапазона (по умолчанию ноль)- меняется
| int main() { srand(time(0)); cout<<rand()%201+200; return 0; } |
Такой генератор случайных значений будет выдавать нам случайные значения в диапазоне чисел 200-400
Сложного тут ничего нет.
Выводим на экран случайные значения испоьзуя Цикл for в С++
| #include<iostream.h> #include<stdlib.h> int main() { srand(time(0)); int i; for (i=1; i<=500;i++) cout<<rand()%201+200; getch(); //Ожидание нажатия клавиши return 0; } |
Присваиваем переменной случайное значение и выводим полученное значение переменной на экран:
| int main() { srand(time(0)); int i; i=rand()%200+200; cout<<i; getch(); //Ожидание нажатия клавиши return 0; } |
Переменная будет принимать случайное значение от 200 до 400
Иногда,если вы сомневаетесь в правильно написанном диапазоне можно использовать цикл while
| #include <stdlib.h> #include <iostream.h> int main() { system("CLS"); //Чистим экран srand(time(0)); //Запускаем генератор int i; //В i будем запоминать значения while (i!=400) //Например, вы сомневаетесь, что 400 входит,ставите в цикл { i=rand()%201+200; //Ваш диапазон запоминаем в i cout<<i<<" "; //Выводим i на экран } cin.get(); //Ожидаем нажатие Enter return 0; } |
Этот пример иногда полезен, например вам точно надо указать диапазон, а вы путаетесь, можно проверить. Если в этом примере ввести число не входящее в диапазон, то цикл станет бесконечным и программа не завершится. Весь фокус прост. Если же число входит в диапазон, то цикл завершится когда его встретит.
Иногда требуется генерация больших чисел.
| #include <stdlib.h> #include <iostream.h> #include <time.h> void main() { system("CLS"); long long i=0; srand(time(0)); for (int k=0;k<20;k++) { i=(double)rand()/(RAND_MAX+1)*(999999-100000)+100000; cout<<i<<" "<<endl; } cin.get(); } |