Вопрос 30. Структурный тип данных.

Структура, в отличие от массива и строки, может содержать элементы различных типов.

Описание структур может выполняться двумя способами. Первый - унаследован от С:

struct [<имя структуры>] {<описание полей>} [<список переменных>];

Как следует из формы, при описании структур в этом случае возможны два варианта:

а) описание структуры выполняется отдельно от объявления списка переменных, например:

struct student { char name[22];

char family[22];

int old; }; // описание структуры

struct student stud1, stud2, *ptrstud; // объявление переменных

б) описание структуры выполняется совместно с объявлением переменных (в этом случае имя структуре можно не присваивать), например:

struct { char name[22];

char family[22];

int old; } stud1, stud2, *ptrstud;

Второй способ описания структур появился позднее, когда в язык был введен оператор объявления нового типа typedef. С использованием этого оператора создается новый тип данных - структура, например:

typedef struct { char name[22];

char family[22];

int old; } student; // в данном случае студент - это имя нового типа данных. Соответственно возможно объявление переменных данного типа, например:

student stud1, stud2, *ptrstud; // объявляются две переменные типа student и один указатель на поле данного типа. В последнем случае память под размещение структуры надо запрашивать специально, например: ptrstud=new student;

Обращение к элементам структуры выполняется с указанием имени переменной и имени поля:

<имя переменной>.<имя поля>

Например:

stud1.family или (в том случае, если переменная задается своим адресом) (*ptrstud).family

Примечание. В том случае, если переменная задается адресом, удобнее использовать сокращенную форму записи обращения к элементу структуры: ptrstud->family вместо (*ptrstud).family

Статические и внешние структуры при объявлении можно сразу инициализировать. При этом значения полей указываются после знака равенства в фигурных скобках через запятую, например:

static student stud1={“Петр”,”Петров”,18},

*ptrstud={“Иван”,”Иванов”,19};

Возможно объявление массивов структур и структур, элементами которых являются вложенные структуры.

При разработке программ важным является выбор эффективного способа представления данных. Во многих случаях недостаточно объявить простую переменную или массив, а нужна более гибкая форма представления данных. Таким элементом может быть структура, которая позволяет включать в себя разные типы данных, а также другие структуры. Приведем пример, в котором использование структуры позволяет эффективно представить данные. Таким примером будет инвентарный перечень книг, в котором для каждой книги необходимо указывать ее наименование, автора и год издания. Причем количество книг может быть разным, но будем полгать, что не более 100. Для хранения информации об одной книге целесообразно использовать структуру, которая задается в языке С++ с помощью ключевого слова struct, за которым следует ее имя. Само определение структуры, т.е. то, что она будет содержать, записывается в фигурных скобках {}. В данном случае структура будет иметь следующий вид:

struct book {
char title[100]; //наименование книги
char author[100]; //автор
int year; //год издания
};

Такая конструкция задает своего рода шаблон представления данных, но не сам объект, которым можно было бы оперировать подобно переменной или массиву. Для того чтобы объявить переменную для структуры с именем book используется такая запись:

struct book lib; //объявляется переменная типа book

После объявления переменной lib имеется возможность работать со структурой как с единым объектом данных, который имеет три поля: title, author и year. Обращение к тому или иному полю структуры осуществляется через точку: lib.title, lib.author и lib.year. Таким образом, для записи в структуру информации можно использовать следующий фрагмент программы:

printf(“Введите наименование книги: “);
scanf(“%s”,lib.title);
printf(“Введите автора книги: “);
scanf(“%s”,lib.author);
printf(“Введите год издания книги: “);
scanf(“%d”,&lib.year);

После этого в соответствующие поля будет записана введенная с клавиатуры информация и хранится в единой переменной lib. Однако по условиям задачи необходимо осуществлять запись не по одной, а по 100 книгам. В этом случае целесообразно использовать массив структур типа book, который можно задать следующим образом:

struct book lib[100];

В этом случае программу ввода и хранения информации по книгам можно записать в виде:

Листинг 3.5. Инвентарный перечень книг.

#include
struct book {
char title[100]; //наименование книги
char author[100]; //автор
int year; //год издания
};

int main()
{
int cnt_book = 0, ch;
struct book lib[100];
do
{
printf(“Введите наименование книги: “);
scanf(“%s”,lib[cnt_book].title);
printf(“Введите автора книги: “);
scanf(“%s”,lib[cnt_book].author);
printf(“Введите год издания книги: “);
scanf(“%d”,&lib.year);
printf(“Нажмите q для завершения ввода: ”);
cnt_book++;
}
while(scanf(“%d”,ch) == 1 && cnt_book < 100);
return 0;
}

Данный пример показывает удобство хранения информации по книгам. Тот же алгоритм в общем случае можно реализовать и без структуры, но тогда пришлось бы использовать два двумерных массива символов и один одномерный массив для хранения года издания. Несмотря на то, что формально такая запись была бы корректной с точки зрения языка С++, но менее удобна в обращении.

Структуры можно автоматически инициализировать при их объявлении подобно массивам, используя следующий синтаксис:

struct bool lib = {
“Евгений Онегин”,
“Пушкин А.С.”,
1995
};

При выполнении данного фрагмента программы в переменные структуры title, author и year будет записана соответственно информация: “Евгений Онегин”, “Пушкин А.С.”, 1995. Здесь следует обратить внимание, что последовательность данных при инициализации должна соответствовать последовательности полей в структуре. Это накладывает определенные ограничения, т.к. при инициализации необходимо помнить последовательность полей в структуре. Стандарт C99 допускает более гибкий механизм инициализации полей структуры:

struct book lib = {.year = 1995,
.author = “Пушкин А.С.”,
.title = “Евгений Онегин” };

или

struct book lib = {.year = 1995,
.title = “Евгений Онегин” };

или

struct book lib = {.author = “Пушкин А.С.”,
.title = “Евгений Онегин”,
1995 };

В первом и во втором примерах при инициализации указываются наименования полей через точку. При этом их порядок и число не имеет значения. В третьем примере первые два поля указаны через имена, а последнее инициализируется по порядковому номеру – третьему, который соответствует полю year.

В некоторых случаях имеет смысл создавать структуры, которые содержат в себе другие (вложенные) структуры. Например, при создании простого банка данных о сотрудниках предприятия целесообразно ввести, по крайней мере, две структуры. Одна из них будет содержать информацию о фамилии, имени и отчестве сотрудника, а вторая будет включать в себя первую с добавлением полей о профессии и возрасте:

struct tag_fio {
char last[100];
char first[100];
char otch[100];
};
struct tag_people {
struct tag_fio fio; //вложенная структура
char job[100];
int old;
};

Рассмотрим способ инициализации и доступ к полям структуры people на следующем примере.

Листинг 3.6. Работа с вложенными структурами.

int main()
{
struct people man = {
{“Иванов”, “Иван”, “Иванович”},
“Электрик”,
50 };
printf(“Ф.И.О.:%s %s %s\n”,man.fio.last,man.fio.first,
man.fio.otch);
printf(“Профессия: %s \n”,man.job);
printf(“Возраст: %d\n”,man.old);
return 0;
}

В данном примере показано, что для инициализации структуры внутри другой структуры следует использовать дополнительные фигурные скобки, в которых содержится информация для инициализации полей фамилии, имени и отчества сотрудника. Для того чтобы получить доступ к полям вложенной структуры выполняется сначала обращение к ней по имени man.fio, а затем к ее полям: man.fio.last, man.fio.first и man.fio.otch. Используя данное правило, можно создавать многоуровневые вложения для эффективного хранения и извлечения данных.

Структуры, как и обычные типы данных, можно передавать функции в качестве аргумента. Следующий пример демонстрирует работу функции отображения полей структуры на экран.

Листинг 3.7. Передача структур через аргументы функции.

#include
struct tag_people {
char name[100];
char job[100];
int old;
};
void show_struct(struct tag_people man);
int main()
{
struct tag_people person = {“Иванов”,”Электрик”,30};
show_struct(person);
return 0;
}
void show_struct(struct tag_people man)
{
printf(“Имя: %s\n”,man.name);
printf(“Профессия: %s\n”,man.job);
printf(“Возраст: %d\n”,man.old);
}

 

Структура – тип данных, задаваемый пользователем. В общем случае при работе со структурами следует выделить четыре момента:

- объявление и определение типа структуры,

- объявление структурной переменной,

- инициализация структурной переменной,

- использование структурной переменной.

Определение типа структуры представляется в виде

struct ID

{

<тип> <имя 1-го элемента>;

<тип> <имя 2-го элемента>;

…………

<тип> <имя последнего элемента>;

};

Определение типа структуры начинается с ключевого слова struct и содержит список объявлений, заключенных в фигурные скобки. За словом struct следует имя типа, называемое тегом структуры (tag – ярлык, этикетка). Элементы списка объявлений называются членами структуры или полями. Каждый элемент списка имеет уникальное для данного структурного типа имя. Однако следует заметить, что одни и те же имена полей могут быть использованы в различных структурных типах.

Определение типа структуры представляет собой шаблон (template), предназначенный для создания структурных переменных

 

Создание структурной переменной возможно двумя способами: с использованием шаблона (типа) или без него.

Создание структурной переменной pt на основе шаблона выполняется следующим образом:

struct point //Определение типа структуры

{

int x;int y;

};

……

struct point pt; //Создание структурной переменной

Структурная переменная может быть задана уникальным образом:

struct //Определение анонимного типа структуры

{

char name[20];

char f_name[40];

char s_name[20];

} copymy; //Создание структурной переменной.

 

Вопрос 31. Массивы в языке С++. Связь массивов и указателей.

Массив- конечная последовательность элементов одного и того же типа. Каждый элемент массива имеет селектор (индекс, номер). С его помощью можно определить любой элемент.

double t[48];

В С++ индексы всегда начинаются с 0, поэтому в данном случае последний индекс- 47.

double t[48];

double *tt= &t или =&t[0]

Имя массива система понимает как указатель на этот массив.

cout << *tt; //значение 1-го элемента массива

cout << *t << t[0];

Чтобы получить доступ к 3-му элементу массива, можно:

t[3] или *(t+3)

int a []= {3,4,5,6,7,8,9); Можно объявить массив, не указывая явно, сколько в нем элементов. При этом система должна знать, сколько места в памяти будет этот массив занимать.

Каждому массиву при обработке нужно задать еще один параметр: сколько элементов в нем в действительности находится.

Исключение: массивы символов. char t [ ]= { ‘7’, ‘6’, ‘5’ };

Каждый символ занимает 1 байт. Символьные массивы отличаются от всех остальных тем, что после символов стоит значок- символ, означающий, что перечисление символов закончено.

char t [ ]= { ‘7’, ‘6’, ‘5’ }; \0 -1 символ

Поэтому в памяти выделяется 4 байта.

Если задать char [3]= {‘7’, ‘6’, ‘5’};,мы допустим ошибку, т.к. 1 место уже занято \0. Поэтому в символьных массивах лучше не указывать [x] Т.е. лучше оставлять[ ].

Последовательность символов – строка.

{ ‘7’, ‘6’, ‘5’}= “765”

char t[ ] = “765”;

0. Массив представляет собой переменную, которая может хранить одно или несколько значений одного и того же типа.

1. Для объявления массива вам следует указать тип, имя массива, а также количество значений, хранящихся в массиве.

2. Значения внутри массива называются элементами массива.

3. Первый элемент массива хранится как элемент 0 (array[OJ), индекс последнего элемента массива на единицу меньше размера массива.

4. Программы часто используют индексные переменные для обращения к элементам массива.

5. Если функция воспринимает массив как параметр, она должна указать тип и имя, но не размер массива.

6. Если программа передает массив в функцию, она, как правило, передает и параметр, который сообщает функции количество элементов содержащихся в массиве.

Так как C++ передает массив в функцию с помощью адреса массива функция может изменять значения, содержащиеся в массиве.

Несколько переменных одного типа можно объединить под одним именем. Такая переменная будет представлять собой массив.

Массив – это тип данных, представляющий собой ограниченный набор упорядоченных элементов одного и того же типа, имеющих одно и то же имя.

Элементом массива является переменная. Количество элементов массива определено заранее при объявлении массива. Все элементы упорядочены – каждому присвоен порядковый номер, который называется индексом. Доступ к конкретному элементу массива осуществляется с помощью индекса. В языке C все массивы располагаются в отдельной непрерывной области памяти. Первый элемент массива имеет наименьший адрес, а последний – наибольший.

Элементы массива могут быть как простыми переменными, так и составными. Элемент массива может иметь несколько индексов. Количество индексов переменной определяет размерность массива. Размерность массивов в языке C не ограничена, но чаще используются одномерные и двумерные массивы. Начальное значение индекса элемента массива для каждого измерения в C – нуль.

Одномерные массивы

Как и другие переменные, массив должен быть объявлен. Существует несколько способов объявления массива.

Общая форма объявления одномерного массива имеет следующий вид:

<класс> тип имя [размер]

где класс – необязательный элемент, определяющий класс памяти (extern, static, register);

тип – базовый тип элемента массива;

имя – идентификатор массива;

размер – количество элементов в массиве.

Доступ к элементу массива осуществляется с помощью имени массива и индекса. Индекс элемента массива помещается в квадратных скобках после имени. Нижнее значение индекса всегда нуль.

Таким образом, элементами массива, состоящего из Nэлементов, являются переменные с индексами

a[0],a[1],…,a[N–1].

В качестве N в описании должна стоять целая положительная константа.

Объем памяти, необходимый для хранения массива, определяется типом элемента массива и количеством элементов, входящих в массив.

Для одномерного массива требуемый объем памяти вычисляется следующим образом:

Объем памяти в байтах = sizeof(базовый тип элемента)× длина массива.

Во время выполнения программы не проверяется ни соблюдение границ массива, ни его содержимое. Задача проверки и соответственно корректности выполнения программы возложена на программиста.

В языке C массивы при объявлении можно инициализировать. Общая форма инициализации массива аналогична инициализации переменной:

<класс> тип имя [размер] = {список значений};

Список значений представляет собой список констант, перечисленных в фигурных скобках через запятую. Типы констант должны быть совместимы с типом массива. Первая константа присваивается первому элементу массива, имеющему индекс нуль, вторая – второму и так далее. После закрывающей фигурной скобки точка с запятой обязательна:

static float x[5]={7.5,0,–3.2,0,4};

В этом случае будет создан массив на 5 элементов. Если в списке инициализации задать количество элементов меньше, чем задано в объявлении массива, то остальные элементы принимаются равными нулю. Если в списке инициализации задать количество элементов больше, чем задано в объявлении массива, это вызовет ошибку при компиляции программы.

При инициализации допустима и следующая форма объявления:

<класс> тип имя [] = {a₀,a₁,…,a_М–1};

Компилятор сам создает массив из М элементов, присваивая им значения a₀, a₁,…, a_М–1.

Двумерные массивы

Стандартом C определены многомерные массивы. Простейшая форма многомерного массива – двумерный массив, т. е. массив одномерных массивов.

Описание двумерного массива выглядит следующим образом:

<класс> тип имя [N1] [N2];

где N1,N2 – количество строк и столбцов.

Массив в памяти располагается по строкам:

ID[0][0],…,ID[0][N2–1],

…

ID[N1–[0],…,ID[N1–1][N2–1], где ID – имя массива.

Как и в случае одномерных массивов, возможна инициализация двумерных массивов:

int a[2][3]=

{

{1,–2,7},

{2,–3,9}

};

Пример программы

Что напечатает ЭВМ?

# include <stdio.h>

int main()

{

int a[2][3]=

{

{6,–1},

{–3,2}

};

int i,j;

for (i=0;i<2;++i)

for (j=0;j<3;++j)

printf("\n a[%d,%d]=%d",i,j,a[i][j]);

}

Ответ: a[0,0]=6, a[0,1]=–1, a[0,2] = 0, a[1,0]=–3, a[1,1]=2, a[1,2]=0.

Массивы и указатели

В языке C массивы и указатели тесно связаны друг с другом. Например, когда объявляется массив в виде int a[25], то при этом не только выделяется память для 25 элементов массива, но и формируется указатель с именем a, значение которого равно адресу первого по счету (нулевого) элемента массива. Доступ к элементам массива может осуществляться через указатель с именем a. С точки зрения синтаксиса языка указатель a является константой, значение которой можно использовать в выражениях, но изменить это значение нельзя.

Поскольку имя массива является указателем-константой, допустимо, например, такое присваивание:

int a[25];

int *ptr;

ptr=a;

В этом примере в переменную-указатель ptr записывается адрес начала массива a, т. е. адрес первого элемента массива.

Также справедливы следующие соотношения: например, имеется массив a[N], тогда истинными будут следующие сравнения:

a==&a[0];

*a==a[0].

Указатели можно увеличивать или уменьшать на целое число:

ptr=a+1;

Теперь указатель ptr будет указывать на второй элемент массива a, что эквивалентно &a[1].

При увеличении указателя на единицу адрес, который он представляет, увеличивается на размер объекта связанного с ним типа, например:

int a[25];

int *ptr=a;

ptr+=3;

Первоначально указатель ptr указывал на начало массива a. После прибавления к переменной ptr числа 3 значение указателя увеличилось на 3*sizeof(int), а указатель ptr теперь будет указывать на четвертый элемент массива a. Указатель можно индексировать точно так же, как и массив. На самом деле компилятор преобразует индексацию в арифметику указателей, например,ptr[3]=10 представляется как *(ptr+3)=10.

К указателям типа void арифметические операции применять нельзя, так как им не ставится в соответствие размер области памяти.

Таким образом, в языке C для доступа к элементам массива существует два различных способа. Первый способ связан с использованием обычных индексных выражений в квадратных скобках, например, a[7]=3 или a[i+2]=5. При таком способе доступа записываются два выражения, причем второе выражение заключается в квадратные скобки. Первое из этих выражений должно быть указателем, а второе – выражением целого типа. Указатель, используемый в индексном выражении, не обязательно должен быть константой, указывающей на какой-либо массив, это может быть и переменная-указатель. В частности, после выполнения присваивания ptr=a доступ к седьмому элементу массива можно получить как с помощью константы-указателя a в форме a[7], таки переменной-указателя ptr в форме ptr[7].

Второй способ доступа к элементам массива связан с использованием адресных выражений и операции косвенной адресации в форме *(a+3)=10 или *(a+i+2)=5.

При реализации на компьютере первый способ приводится ко второму, т. е. индексное выражение приводится к адресному. Для приведенных примеров обращение к элементу массива a[3]преобразуется в *(a+3).

Для доступа к начальному элементу массива, т. е. к элементу с нулевым индексом, можно использовать просто значение указателя a или ptr, поэтому любое из присваиваний

*a=2;

a[0]=2;

*(a+0)=2;

*ptr=2;

ptr[0]=2;

*(ptr+0)=2;

присваивает начальному элементу массива значение 2.

Многомерные массивы в языке C – это массивы массивов, т. е. массивы, элементами которых, в свою очередь, являются массивы. При объявлении таких массивов в памяти компьютера создается несколько различных объектов. Например, при выполнении объявления двумерного массива int a2[4][3] в программе создается указатель a2, который определяет в памяти местоположение первого элемента массива и, кроме того, является указателем на массив из четырех указателей. Каждый из этих четырех указателей содержит адрес одномерного массива, представляющего собой строку двумерного массива и состоящего из трех элементов типа int, и позволяет обратиться к соответствующей строке массива.

Таким образом, объявление a2[4][3] порождает в программе три разных объекта: указатель с идентификатором a2, безымянный массив из четырех указателей и безымянный массив из двенадцати чисел типа int. Для доступа к безымянным массивам используются адресные выражения с указателем a2. Доступ к элементам массива указателей осуществляется с указанием одного индексного выражения в форме a2[2] или *(a2+2). Для доступа к элементам двумерного массива чисел типа int должны быть использованы два индексных выражения в формеa2[1][2] или эквивалентных ей *(*(a2+1)+2) и (*(a2+1))[2]. Следует учитывать, что с точки зрения синтаксиса языка C указатель a2 и указатели a2[0], a2[1], a2[2], a2[3]являются константами, и их значения нельзя изменять во время выполнения программы.

Размещение трехмерного массива происходит аналогично. Так, например, объявление float a3[3][4][5] порождает в программе, кроме самого трехмерного массива из 60 чисел типаfloat, массив из четырех указателей на тип float, массив из трех указателей на массив указателей на float и указатель на массив массивов указателей на float.

При размещении элементов многомерных массивов они располагаются в памяти подряд по строкам, т. е. быстрее всего изменяется последний индекс, а медленнее – первый. Такой порядок дает возможность обращаться к любому элементу многомерного массива, используя адрес его начального элемента и только одно индексное выражение.

Например, обращение к элементу a2[1][2] можно осуществить при помощи указателяptr2, объявленного в форме int *ptr2=a2[0], как обращение ptr2[1×3+2] (здесь 1 и 2 – это индексы используемого элемента, а 3 – число элементов в строке) или какptr2[5]. Заметим, что внешне похожее обращение a2[6] выполнить невозможно, так как указателя с индексом 6 не существует.

Для обращения к элементу a3[2][3][4] из трехмерного массива тоже можно использовать указатель, описанный как float *ptr3=a3[0][0], с одним индексным выражением в формеptr3[2×20+3×5+4] или ptr3[59].

 

Массивы и функции

Использование указателей в качестве формальных параметров функции дает возможность передавать из вызывающей подпрограммы в функцию не само значение или массив значений, а адрес переменной (адреса фактических аргументов).

В частности, при работе с массивами не требуется использовать в качестве формальных аргументов массив. Это может быть указатель того же типа, что и тип элемента массива. В подпрограмму в этом случае можно передавать адрес начального элемента массива.

Пример программы

Задан одномерный массив из N элементов. Найти значение максимального элемента массива.

Поиск максимума оформить в виде функции max:

# include <stdio.h>

# define N 3

int max(int k,int* b) //b – указательна целое,

//k – количество элементов в массиве

{

int i,m1;

m1=*b; //*b – значение 1-го эл-та массива (с индексом 0)

for(i=1;i<k;i++)

{

b++;//Переход к следующему элементу массива

if (m1<*b)m1=*b; //*b – значение текущего эл-та массива

}

return(m1);

}

int main()

{

static int A[N]={1,7,3};

printf("\n max=%d",max(N,&A[0]));

return 0;

}

Рассмотрим теперь пример программы с двумерным массивом. Дан двумерный массив, состоящий из трех строк и четырех столбцов. Найти максимальный элемент каждой строки, используя ранее созданную функцию max:

int main()

{

static int B[3][4]={3,5,1,6,8,3,7,3,2,6,9,3};

printf("\n 1 row: max=%d",max(4,B[0]));

printf("\n 2 row: max=%d",max(4,B[1]));

printf("\n 3 row: max=%d",max(4,B[2]));

return 0;

}

При вызове функции max использовались указатели на начало строк массива, каждая строка массива содержит 4 значения.

Результат работы программы:

1 row: max=6
2 row: max=8
3 row: max=9.

Рассмотрим передачу двумерного массива в функцию. В качестве параметров функции передается адрес начала массива и количество элементов в строке массива, соответствующее объявлению массива в вызывающей функции (int A2[][N]), а также два целых числа m и n, имеющие смысл фактического количества строк и столбцов, используемых в массиве. Они не должны превышать значения количества строк и столбцов соответственно, заданные при объявлении массива.

В примере используются следующие функции: ввод двумерного массива input_mas(), вывод на экран двумерного массива в виде таблицы output_mas(), вычисление суммы элементов массива, имеющих одинаковые номера столбцов и строк int diagonal():

#include <stdio.h>

#define N 4

#define M 3

void input_mas(int A2[][N],int m,int n);

void output_mas(int A2[][N],int m,int n);

int diagonal(int A2[][N],int m,int n);

void main()

{

int mas[M][N];

input_mas(mas,M,N);

output_mas(mas,M,N);

printf("Summa elementov diagonali = %d\n", diagonal(mas,M,N));

return 0;

}

void input_mas(int A2[][N],int m,int n)

{

int i,j;

printf("Wwedite chisla->");

for(i=0;i<M;i++)

for(j=0;j<N;j++)

scanf("%d",&A2[i][j]);

}

void output_mas(int A2[][N],int m,int n)

{

int i,j;

printf("Wwedeno:\n");

for(i=0;i<M;i++)

{

for(j=0;j<N;j++) printf("%7d",A2[i][j]);

printf("\n");

}

}

int diagonal(int A2[][N],int m,int n)

{

int i,j,summa=0;

for(i=0;i<M;i++)

for(j=0;j<N;j++)

if (i==j) summa+=A2[i][j];

return summa;

}