6_ Структуры и .

6 СТРУКТУРНЫЕ И ДИНАМИЧЕСКИЕ ТИПЫ

6.1 Определение структурного типа

При решении некоторых задач программистам удобно использовать наборы из объектов разных типов. Каждый такой набор язык Си позволяет рассматривать в качестве объекта нового, созданного пользователем, типа данных. Такие типы в языке Си получили название структурных. Формально структурным типом в языке Си называется именованный набор переменных. Его определение на­чи­на­ется со служебного слова struct. За ним следует вы­бранный программистом идентификатор, который называется идентификатором создаваемого струк­турного типа. Далее в фигурных скобках размещается список, состоящий из переменных и их типов. После каждой переменной, включая последнюю, ставится точка с запятой. Переменные, перечисленные в фигурных скобках, называются членами, полями или элементами структурного типа. Наглядно определение струк­тур­ного типа данных можно представить в виде сле­ду­ющей схемы:

struct Идентификатор {

Тип_1 Имя_1;

...

Тип_N Имя_N;

};

Структурные типы отличаются от встроенных типов только происхождением. Их создает сам программист. Рассмотрим несколько примеров определений структурных типов.

Пример 6.1 - Определения некоторых структурных типов

// Комплексные числа

struct Complex {

// Вещественная часть

double Real;

// Мнимая часть

double Ima;

};

// Точки плоскости с целочисленными координатами

struct Point {

// х - координата

int x;

// y - координата

int y;

};

// Векторы

struct Vector {

// Размерность вектора

int Dim;

// Адрес блока с компонентами

double* pVec;

};

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

struct AA{

AA x;

int num;

};

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

struct AA{

AA* pАА;

int num;

};

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

Набор данных, хранящихся в переменных структурного типа, называется объектом или структурой. Если структурный тип не содержит указателей, то создать соответствующую структуру очень просто. Для этого необходимо поместить в приложение нужную команду. Она начинается с идентификатора структурного типа. За ним следует выбранное программистом имя структуры, знак равенства и фигурные скобки со списком данных. Как всегда, команда заканчивается точкой с запятой. Для наглядности команду можно представить в виде следующей схемы

Тип Имя={

Объект_1,

...

Объект_n

};

Создать структурную переменную еще проще: достаточно указать идентификатор структурного типа и имя переменной.

Тип Имя;

Пример 6.2 - Создание структур и структурных переменных

// Создание структур ранее определенных типов

Complex a={1.1, 2.2}, b={3.3, 4.4};

// Создание структурных переменных

Point pt1, pt2;

Если структурный тип содержит указатели, то для создания соответствующей структуры приходится использовать бинарные операции выбора члена структуры. Они имеют второй приоритет и обозначаются знаками “.” (точка) и “->” (стрелка вправо). В первом случае левым операндом является имя структуры, а правым – имя одного из ее членов (переменных). Например, если a и b – имена структур типа Complex, то результатом вычисления выражений a.Real и a.Ima будут значения переменных Real и Ima структуры a, а результатом вычисления выражений b.Real и b.Ima будут значения переменных Real и Ima структуры b. Во втором случае левый операнд должен быть адресом структуры, а правый, как и в первом случае, - ее членом. Узнать адрес структуры по ее имени можно с помощью знакомой операции получения адреса, обозначаемой символом &. Поэтому результатом вычисления выражений (&a)->Real и (&a)->Ima будут значения переменных Real и Ima структуры a.

Продолжим создание структуры, содержащей адреса. Вначале требуется создать соответствующую структурную переменную. Затем, используя операцию выбора, определить каждый член структуры. В качестве примера создадим структуру ранее определенного типа Vector/

Пример 6.3 – Создание структуры (объекта) типа Vector

// Компоненты вектора

double vec[]={1.1, 2.2, 3.3};

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

Vector v;

// Создание структуры

v.Dim=3;

v.pVec=new double[3];

v.pVec[0]=vec[0], v.pVe[1]=vec[1], v.pVec[2]=vec[2];

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

6.2 Свойства структурных типов

Количество операций, допустимых над структурами, ограничено. Кроме рассмотренных операций получения адреса и доступа к членам, разрешается разыменовывать структурные переменные. К од­но­тип­ным структурам можно применять операцию присваивания. В самом деле, пусть A – некоторый структурный тип, состоящий из переменных Var_1,...,Var_N. Если a и b переменные типа A, то по команде

a=b;

будут выполнены следующие операции:

a.Var_1=b.Var_1;

...

a.Var_N=b.Var_N;

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

Пример 6.5. ...

Структуры можно объединять в массивы...

Наконец, отметим, что формально два структурных типа, определенные ниже,

struct S1 {int i; float f;};

struct S2 {int i; float f;};

являются разными. Поэтому, если

S1 a={1, 2.3f}, b;

S2 c;

то присваивание вида

b=a;

будет допустимым, а присваивание

с=а;

приведет к сообщению об ошибке из-за несовпадения типов операндов операции присваивания.

Структуры можно использовать в качестве возвращаемых значений и параметров функций.

Пример 6.4 - Функция сложения комплексных чисел

Complex AddComplex(Complex comX, Complex comY) {

// Выделение памяти для суммы

Complex comZ;

// Вычисление суммы

comZ.Real=comX.Real+comY.Real;

comZ.Ima=comX.Ima+comY.Ima;

// Определение возвращаемого значения

return comZ;

}

// Определение типа

struct Person{

// Фамилия

char* m_szName;

// Год рождения

int m_ Year;

// …

};

// Конструктор

Person CreatePersont(char* szName,int Year){

Person temp;

int len=strlen(szName);

temp.m_szName=new char[len+1];

strcpy(temp.m_szName,szName);

temp.m_Year=Year;

return temp;

}

// Деструктор

void DeletePerson (Person* a){

delete[] a.m_szName;

}

// Отображение

void DisplayPerson (Person a){

printf(“Name: %s”,a.m_szName);

printf(“Year: %d”,a.m_Year);

}

6.3 Списки

Структуры широко применяются для хранения информации в задачах, возникающих в самых различных областях человеческой деятельности. Например, при приеме на работу работодатель желает знать фамилию, имя, дата рождения, образование, семейное положение, адрес и некоторые другие сведения о своем работнике. Для их хранения используется набор из объектов разных типов, то есть структура. Очевидно, что на каждого сотрудника создается отдельная структура. Подобная ситуация возникает и при организации учета товаров на складах или книг в библиотеках. На каждую единицу хранения создается ин­ди­ви­ду­аль­ная структура. В перечисленных выше задачах количество подлежащих хранению структур (число сотрудников, количество товара, число книг) изменяется во времени произвольным об­ра­зом. Поэтому использование массива в подобных случаях создает дополнительные проблемы. При каждом изменении количества хранящихся структур приходится корректировать его длину. Один из способов их преодоления заключается в применении для хранения и доступа к объектам, количество которых может изменяться в ходе работы с приложением, принципиально новых типов данных, получивших название динамических типов. Рассмотрим один из примеров динамического типа, получивший название списка.

Списком принято называть упорядоченную совокупность од­­но­тип­ных структур, называемых узлами или элементами списка. Для их упорядочивания используется вспомогательная переменная (указатель), которую добавляют в каждый узел. Указатель содержит адрес следующего узла. По определению, указатель последнего в списке узла должен равняться нулю (NULL) соответствующего структурного типа. Остальные переменные каждого узла исполь­зу­ют­ся для хранения информации пользователя. Количество узлов в списке называется его длиной. Список считается заданным, если определен тип его узлов и адрес первого из них. Пусть Node - выбранный прог­­­рам­мистом иден­ти­фи­катор структурного типа, объекты которого будут узлами списка. Тогда указатель pHead для хранения адреса первого элемента списка будет иметь тип Node*. Если pHead=(*Node)0, то в списке нет ни одного элемента. Такой список на­зы­вается пустым.

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

Пример 6.2. Создание списка. Добавление узла в список

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

// Узел списка

struct Node{

// Данные

char* m_szName;

// Год рождения

int m_Year;

// …

// Указатель на следующий узел

Node* m_pNext;

};

// Добавление в начало списка

void InsertHead(Node** ppHead, char* szName, int Year){

Node* pNode=new Node;

if(!pNode) {

printf("Error: Memory!\n");

return;

}

int len=strlen(szName);

pNode->m_szName=new char[len+1];

strcpy(pNode->m_szName,szName);

pNode->m_Year=Year;

pNode->m_pNext=*ppHead;

*ppHead=pNode;

}

// Удаление списка

void DeleteList(Node** ppHead){

if(*ppHead){

Node* pNext;

for(Node* p=*ppHead; p>0; p=pNext){

pNext=p->m_pNext;

delete[] p->m_szName;

delete p;

}

*ppHead=0;

}

printf("The list is destroyed!\n");

}

// Отображение списка

void DisplayList(Node* pHead){

if(pHead)

for(Node* p=pHead; p>0; p=p->m_pNext){

printf(“Name: %s\n”,p->m_szName);

printf(“Year: %d\n”,p->m_Year);

}

else

printf(“The List is empty!\n”);

}

// Вычисление длины

int LengthList(Node* pHead){

int len=0;

for(Node* p=pHead; p>0; p=p->m_pNext)

len++;

return len;

}

// Главная функция

void main(void){

char szName[255];

int Year;

char ch, temp;

Node* pHead=0;

printf("\t\t\tMenu\n");

printf("Dest-d, Insert-i, Length-l, Show-s, Exit-e\n");

do{

printf("Select an operation: ");

scanf("%c%c", &ch, &temp);

switch(ch){

case 'd':

case 'D':

// Удаление списка

DeleteList(&pHead);

break;

case 'e':

case 'E':

// Завершение приложения

if(pHead){

printf("Impossible! Destroy a list!\n");

break;

}

return;

case 'i':

case 'I':

// Добавление в список

printf("Name: ");

scanf("%s%c", szName, &ch);

printf("Year: ");

scanf("%d%c", &Year, &ch);

InsertHead(&pHead,szName,Year);

break;

case 'l':

case 'L':

// Вычисление длины

printf("Length=%d\n", LengthList(pHead));

break;

case 's':

case 'S':

// Отображение списка

DisplayList(pHead);

break;

default:

printf("Bad command!\n");

}

}while(1);

}

6.4 Стек и очередь на основе списка

Стеком и очередью программисты называют запоминающие устройства для хранения объектов фиксированного типа с определенными правилами записи и чтения. Прочитать (получить) из стека можно только тот объект, который записан в него последним. При этом сам прочитанный объект из стека должен быть удален. Из очереди можно прочитать (получить) только тот объект, который записан в нее раньше всех остальных. Как и при чтении из стека, прочитанный объект из очереди должен быть удален. Для создания стека или очереди обычно используются массивы или списки. В первом случае длина создаваемого стека (или очереди) ограничена длиной массива. Во втором случае ограничением служит размер свободной (или дисковой, если список хранится на диске) памяти.

Воспользуемся рассмотренным в предыдущем пункте списком для создания стека. Для этого определим функцию GetHead(), которая возвращает данные из первого узла стека, а затем удаляет его. Так как в узле хранятся два объекта, то для их возвращения в функцию GetHead(), кроме указателя ppHead с адресом списка, включены два дополнительных параметра. Указатель szName на char должен быть адресом массива. Туда копируется символьная строка (имя). А указатель pYear на int долен быть адресом переменной типа int. Туда копируется переменная Year. Отметим, что в главной функции такие переменные уже существуют. Они используются в качестве буферов при вводе данных, помещаемых в список.

void GetHead(Node** ppHead, char* szName, int* pYear){

if(!*ppHead){

printf(“The list is empty!\n”);

return;

}

strcpy(szName,(*ppHead)->m_szName);

*pYear=(*ppHead)->m_Year;

Node* p=(*ppHead)->m_pNext;

delete (*ppHead);

*ppHead=p;

}

Если список используется в качестве очереди, то данные должны читаться из его последнего узла (они раньше всех оказались в списке). После завершения чтения данных, узел требуется удалить.

void GetTail(Node** ppHead, char* szName, int* pYear){

if(!*ppHead){

printf(“The list is empty!\n”);

return;

}

Node* pPre=*ppHead;

for(Node* pCur=*ppHead;pCur->m_pNext>0;pCur=pCur->m_pNext)

pPre=pCur;

strcpy(szName,pCur->m_szName);

*pYear=pCur)->m_Year;

delete (pCur);

pPre->m_pNext=0;

}

// Стек на основе списка

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

// Структура для хранения информации

struct Info{

// Фамилия

char* m_szName;

// Год рождения

int m_Year;

// Остальное...

};

// Узел списка

struct Node{

// Данные

Info m_Date;

// Указатель на следующий узел

Node* m_pNext;

};

// Методы для работы со стеком

// Уничтожение структуры

void Delete(Info* pData);

// Уничтожение стека

void DeleteList(Node** ppHead);

// Получение из стека

Info GetHead(Node** ppHead);

// Вставка в начало стека

void InsertHeade(Node** pHead, Info Data);

// Вычисление длины

int LengthList(Node* pHead);

// Создание структуры с клавиатуры

void Read(Info* pData);

// Отображение данных из структуры

void Show(Info Data);

// Отображение стека

void ShowList(Node* pHead);

void main(void){

Node* pHead=0;

Info Data, Resp;

char ch, temp;

printf("\t\t\tMenu\n");

printf("Dest-d, Get-g, Insert-i, Length-l, Show-s, Exit-e\n");

do{

printf("\nSelect an operation: ");

scanf("%c%c", &ch, &temp);

switch(ch){

case 'd':

case 'D':

// Уничтожение списка

if(pHead){

DeleteList(&pHead);

pHead=0;

}

else

printf("The list is empty!\n");

break;

case 'e':

case 'E':

// Завершение приложения

if(pHead){

printf("Impossible! Destroy a list!\n");

break;

}

return;

case 'g':

case 'G':

// Получение из стека

if(pHead){

Resp=GetHead(&pHead);

Show(Resp);

delete[] Resp.m_szName;

}

else

printf("The stack is empty!\n");

break;

case 'i':

case 'I':

// Включение в список

Read(&Data);

InsertHeade(&pHead, Data);

break;

case 'l':

case 'L':

// Вычисление длины

printf("Length=%d\n", LengthList(pHead));

break;

case 's':

case 'S':

// Отображение списка

if(pHead)

ShowList(pHead);

else

printf("The list is empty!\n");

break;

default:

printf("Bad command!\n");

}

}while(1);

}

// Ввод данных с клавиатуры

void Read(Info* pData){

char szName[100];

printf("Name: ");

char ch;

scanf("%s%c", szName, &ch);

int Len=strlen(szName);

int Year;

printf("Year: ");

scanf("%d%c", &Year, &ch);

pData->m_szName=new char[Len+1];

strcpy(pData->m_szName, szName);

pData->m_Year=Year;

}

// Отображение данных из структуры

void Show(Info Data){

printf("Name: %s\n", Data.m_szName);

printf("Year: %d\n", Data.m_Year);

}

// Вставка в начало списка

void InsertHeade(Node** ppHead, Info Data){

Node* p=new Node;

if(p){

p->m_Date=Data;

p->m_pNext=*ppHead;

*ppHead=p;

}

else{

printf("Error: Memory!\n");

exit(-1);

}

}

// Отображение списка

void ShowList(Node* pHead){

for(Node* p=pHead; p>0; p=p->m_pNext)

Show(p->m_Date);

}

// Уничтожение списка

void DeleteList(Node** ppHead){

Node* pTemp;

for(Node* p=*ppHead; p>0; p=pTemp){

pTemp=p->m_pNext;

delete[] p->m_Date.m_szName;

delete p;

}

printf("The list is destroyed!\n");

}

// Получение из стека

Info GetHead(Node** ppHead){

if(*ppHead){

Node* p=*ppHead;

*ppHead=(*ppHead)->m_pNext;

Info Date=p->m_Date;

delete p;

return Date;

}

else{

printf("The stack is empty!\n");

Info Date={"", 0};

return Date;

}

}

// Вычисление длины

int LengthList(Node* pHead){

int len=0;

for(Node* p=pHead; p>0; p=p->m_pNext, len++)

;

return len;

}

// Очередь на основе списка

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

// Структура для хранения информации

struct Info{

// Фамилия

char* m_szName;

// Год рождения

int m_Year;

// Остальное...

};

// Узел списка

struct Node{

// Данные

Info m_Date;

// Указатель на следующий узел

Node* m_pNext;

};

// Методы для работы со стеком

// Уничтожение структуры

void Delete(Info* pData);

// Уничтожение стека

void DeleteList(Node** ppHead);

// Получение из стека

Info GetHead(Node** ppHead);

// Вставка в начало стека

//void InsertHeade(Node** pHead, Info Data);

void InsertTail(Node** pHead, Info Data);

// Вычисление длины

int LengthList(Node* pHead);

// Создание структуры с клавиатуры

void Read(Info* pData);

// Отображение данных из структуры

void Show(Info Data);

// Отображение стека

void ShowList(Node* pHead);

void main(void){

Node* pHead=0;

Info Data, Resp;

char ch, temp;

printf("\t\t\tMenu\n");

printf("Dest-d, Get-g, Insert-i, Length-l, Show-s, Exit-e\n");

do{

printf("\nSelect an operation: ");

scanf("%c%c", &ch, &temp);

switch(ch){

case 'd':

case 'D':

// Уничтожение списка

if(pHead){

DeleteList(&pHead);

pHead=0;

}

else

printf("The list is empty!\n");

break;

case 'e':

case 'E':

// Завершение приложения

if(pHead){

printf("Impossible! Destroy a list!\n");

break;

}

return;

case 'g':

case 'G':

// Получение из стека

if(pHead){

Resp=GetHead(&pHead);

Show(Resp);

delete[] Resp.m_szName;

}

else

printf("The stack is empty!\n");

break;

case 'i':

case 'I':

// Включение в список

Read(&Data);

InsertTail(&pHead, Data);

break;

case 'l':

case 'L':

// Вычисление длины

printf("Length=%d\n", LengthList(pHead));

break;

case 's':

case 'S':

// Отображение списка

if(pHead)

ShowList(pHead);

else

printf("The list is empty!\n");

break;

default:

printf("Bad command!\n");

}

}while(1);

}

// Ввод данных с клавиатуры

void Read(Info* pData){

char szName[100];

printf("Name: ");

char ch;

scanf("%s%c", szName, &ch);

int Len=strlen(szName);

int Year;

printf("Year: ");

scanf("%d%c", &Year, &ch);

pData->m_szName=new char[Len+1];

strcpy(pData->m_szName, szName);

pData->m_Year=Year;

}

// Отображение данных из структуры

void Show(Info Data){

printf("Name: %s\n", Data.m_szName);

printf("Year: %d\n", Data.m_Year);

}

// Вставка в начало списка

void InsertHeade(Node** ppHead, Info Data){

Node* p=new Node;

if(p){

p->m_Date=Data;

p->m_pNext=*ppHead;

*ppHead=p;

}

else{

printf("Error: Memory!\n");

exit(-1);

}

}

// Вставка в конец списка

void InsertTail(Node** ppHead, Info Data){

Node* p=new Node;

if(p){

p->m_Date=Data;

p->m_pNext=0;

// Поиск хвоста

if(!(*ppHead))

*ppHead=p;

else{

Node* pTail;

for(Node* pCur=*ppHead; pCur>0;

pTail=pCur, pCur=pCur->m_pNext)

// Пустой оператор

;

pTail->m_pNext=p;

}

}

else{

printf("Error: Memory!\n");

exit(-1);

}

}

// Отображение списка

void ShowList(Node* pHead){

for(Node* p=pHead; p>0; p=p->m_pNext)

Show(p->m_Date);

}

// Уничтожение списка

void DeleteList(Node** ppHead){

Node* pTemp;

for(Node* p=*ppHead; p>0; p=pTemp){

pTemp=p->m_pNext;

delete[] p->m_Date.m_szName;

delete p;

}

printf("The list is destroyed!\n");

}

// Получение из стека

Info GetHead(Node** ppHead){

if(*ppHead){

Node* p=*ppHead;

*ppHead=(*ppHead)->m_pNext;

Info Date=p->m_Date;

delete p;

return Date;

}

else{

printf("The stack is empty!\n");

Info Date={"", 0};

return Date;

}