5.4. Иерархия типов данных и функций
«На острове – дуб, на дубе – сундук,
в сундуке – заяц, в зайце – утка, в утке – яйцо,
в яйце – игла, а на ее конце – Кощеева смерть».
Русская народная сказка.
Иерархический принцип построения системы состоит в том, что более сложные компоненты составляются из более простых, ранее определенных. До сих пор с иерархией в языках программирования мы сталкивались при вызове функций (см. 3.4). В соответствии с принципом модульного программирования, если при решении задачи отдельные ее части являются относительно независимыми подзадачами, то последние оформляются в виде модулей (функций) с последующим вызовом из главной функции.
Однако речь пока не шла о данных. Если говорить о различных способах их представления в программе (типах данных), то их определение образует иерархическую систему: более сложные (производные) создаются из определенных ранее. Для начала рассмотрим самый естественный случай иерархического представления данных, когда массивы и структурированные переменные включаются друг в друга по принципу «матрешки». В нашем примере речь идет о таблице «пользователей», представленной массивом структурированных переменных. В каждой записи фигурируют строки (массивы символов) – имя и пароль и даты: дата регистрации и множество дат посещений (массив). Дата, в свою очередь, представлена структурированным типом. Все массивы имеют счетчики текущей размерности. Основная таблица также включена в структурированный тип. Таким образом, все данные в программе представлены единственной переменной TT структурированного типа table.
//------------------------------------------------------54-01.cpp
// Иерархия типов данных и функций
// Уровень 1. Представление даты
struct date{ int dd,mm,yy;}
// Уровень 1. Представление строки таблицы (записи)
const int NP=100;
struct user{
char name[20],pass[10]; // имя и пароль
date birth; // дата регистрации
int np; // текущая размерность в массива дат
date SS[NP]; // массив дат посещений
double credit;};
// Уровень 3 - представление таблицы
struct table{
user TBL[N]; // массив структурированных переменных
int nn;}; // текущая размерность массива
// Уровень 4 - основная программа
table TT;
К переменной TT можно последовательно применять операции, извлекая каждый раз очередную вложенную компоненту, например:
TT.TBL – массив – таблица пользователей;
TT.nn - текущая размерность таблицы;
TT.TBL[i] – строка таблицы с записью об i-ом пользователе;
TT.TBL[i].SS – массив дат посещений для i-го пользователя;
TT.TBL[i].np – текущее количество записей в массиве SS
TT.TBL[i].SS[j] – дата j-го посещения i-ым пользователем;
TT.TBL[i].SS[j].dd – день j-го посещения i-ым пользователем.
Каждое из этих выражений имеет свой собственный тип, так TT.TBL[i] является структурированной переменной типа user, а TT.TBL[i].np – является целым. Операции обработки данных можно применять только к базовым типам, поэтому, если обращаться к компонентам, начиная с переменной TT, то придется пользоваться такими вот громоздкими выражениями.
рис.54-1. Иерархия типов данных и функций
Можно пойти по другому пути. Для каждого промежуточного типа данных ввести функции, работающие с ним и получающие переменную соответствующего типа в качестве формального параметра. Тогда естественным образом параллельно с иерархией представления данных возникает иерархия функций. Каждая из них, получая в качестве формального параметра переменную (структуру, массив), выделяет составляющую ее компоненту и передает следующей функции в качестве фактического параметра. Такое решение дает следующие эффекты:
программа становится модульной «естественным образом». Обработкой каждого типа данных занимается отдельный набор функций;
исчезают громоздкие последовательности выражений, они распадаются на части. Каждая функция использует свою часть цепочки действий по обращению к составляющим переменную компонентам;
формальные параметры передаются по ссылке (отображаются на исходную переменную и ее компоненты).
//-------------------------------------------------------------------------------------
// Уровень 1. Функция, работающая с датой
void saveDate(date &D, FILE *fd){
fprintf(fd,”%d %d %d ”,D.dd,D.mm,D.yy);
}
// Уровень 2. Функция, работающая с записью о пользователе
void saveUser(user &U,FILE *fd){
fprintf(fd,”%s\n%s\n”,U.name,U.pass);
saveDate(U.birth,fd);
fprintf(fd,”\n%d\n”,U.np);
for (int i=0;i<U.np;i++) saveDate(U.SS[i],fd);
}
// Уровень 3. Функция, работающая с массивом записей (таблицей)
void saveTable(user T[], int n, FILE *fd){
fprintf(fd,”%d\n”,n);
for (int i=0;i<n;i++) saveUser(T[i],fd);
}
// Уровень 4. Структура, содержащая таблицу, и основная программа
table TT;
void main(){
TT.nn=0;
…
saveTable(TT.TBL,TT.nn);}
Выражения становятся еще более компактными, если для структурированных типов использовать встроенные в них функции (см.5.3). В них, благодаря контексту текущей переменной (объекта), исчезает необходимость использовать формальные параметры, а поля текущей структурированной переменной доступны непосредственно по их именам.
//------------------------------------------------------54-01.cpp
// Иерархия типов данных и функций
// Уровень 1. Представление даты
struct date{
int dd,mm,yy;
void setDate(int dd0, int mm0, int yy0){ // встроенная функция установки даты
dd=dd0; mm=mm0; yy=yy0; }
void getDate(){ // встроенная функция чтения даты
printf("\nday:"); scanf("%d",&dd);
printf("month:"); scanf("%d",&mm);
printf("year:"); scanf("%d",&yy); // непосредственный доступ по имени поля
}
int cmpDate(date &T){ // встроенная функция сравнения дат
if (yy!=T.yy) return yy-T.yy;
if (mm!=T.mm) return mm-T.mm;
return dd-T.dd;
} // встроенные функции работы с файлом
void loadDate(FILE *fd){ fscanf(fd,"%d%d%d",&dd,&mm,&yy); }
void saveDate(FILE *fd){ fprintf(fd,"%d %d %d ",dd,mm,yy); }
void showDate(){ printf("%02d.%02d.%04d ",dd,mm,yy); }
};
При использовании встроенных функций они также вызываются по цепочке, только синтаксис этого вызова отличается от обычного: Функция, встроенная в структурированный тип верхнего уровня, выбирает поле структуры, с которой она работает, и вызывает в ней встроенную функцию.
//------------------------------------------------------54-01.cpp
// Уровень 1. Представление строки таблицы (записи)
const int N=100;
const int NP=100;
struct user{
char name[20],pass[10]; // имя и пароль
date birth; // дата регистрации
int np; // текущая размерность в массива дат
date SS[NP]; // массив дат посещений
double credit;
void setUser(char nm[], char ps[], date b0){
strcpy(name,nm); strcpy(pass,ps); birth=b0; np=0;
}
void addDate(date d0){ // встроенная функция добавления даты посещения
if (np!=NP) SS[np++]=d0; }
void showUser(){ // встренная функция просмотра
printf("%20s %10s ",name,pass);
birth.showDate(); // вызов встроенной функции для поля birth
printf("%2d\n",np);
}
void showDate(){
for (int i=0;i<np;i++) { // вызов встроенной функции для поля SS[i]
SS[i].showDate(); printf("\n"); }
}
void loadUser(FILE *fd){ // встроенная функция загрузки из файла
fscanf(fd,"%s%s",name,pass);
birth.loadDate(fd); // вызов встроенной функции для поля birth
fscanf(fd,"%d",&np);
for (int i=0;i<np;i++) SS[i].loadDate(fd);
}
int cmpUser(user &T,int mode){ // встроенная функция сравнения записей
switch (mode){
case 0: return strcmp(name,T.name); // сравнение по имени
case 1: return birth.cmpDate(T.birth); // сравнение по дате регистрации
case 2: return np-T.np; // сравнение по числу посещений
}}
};
// Уровень 3 - представление таблицы
struct table{
user TBL[N]; // массив структурированных переменных
int nn; // текущая размерность массива
void loadTable(char nm[]){ // встроенная функция загрузки из файла
FILE *fd=fopen(nm,"r");
if (fd==NULL) return;
fscanf(fd,"%d\n",&nn);
if (nn>=N) return; // вызов встроенной функции для поля TBL[i]
for (int i=0;i<nn;i++) TBL[i].loadUser(fd);
fclose(fd);
}
void sortTable(int mode){ // встроенная функция сортировки выбором
int i,j,k;
for (i=0;i<nn;i++){ // вызов встроенной функции сравнения записей
for(j=k=i; j<nn;j++)
if (TBL[j].cmpUser(TBL[k],mode)<0) k=j;
user cc=TBL[i]; TBL[i]=TBL[k]; TBL[k]=cc;
}
}};
На уровне главной функции main остается только интерактивная компонента общения с пользователем в режиме командной строки и вызов необходимых встроенных функций для структурированной переменной TT типа table.
//------------------------------------------------------54-01.cpp
// Уровень 4 - основная программа
table TT; // структурированная переменная типа «таблица»
void main(){
while(1){
printf("\na(dd),v(iew),l(oad),s(ave),o(rd by),d(ate)\nwhat to do:");
switch(getch()){
case 'a': printf("\nname:"); scanf("%s",c1);
printf("password:"); scanf("%s",c2);
d0.getDate();
TT.addUser(c1,c2,d0);
break;
case 'o': printf("\nsort mode (0-by name, 1-by date, 2-by count(np)):");
TT.sortTable(getch()-'0'); …………}}}
Лабораторный практикум
Определить структурированный тип и набор функций для работы с таблицей записей, реализованной в массиве структур. В перечень функций входят:
ввод записи таблицы с клавиатуры;
загрузка и сохранение таблицы в текстовом файле;
просмотр таблицы;
сортировка таблицы в порядке возрастания заданного поля;
поиск в таблице элемента с заданным значением поля или с наиболее близким к нему по значению;
удаление записи;
изменение (редактирование) записи;
вычисление с проверкой и использованием всех записей по заданному условию и формуле (например, общая сумма на всех счетах).
Перечень полей структурированной переменной:
Фамилия, номер счета, сумма на счете, дата последнего изменения.
Номер страницы, номер строки, текст изменения строки, дата изменения.
Название экзамена, дата экзамена, фамилия преподавателя, количество оценок, оценки.
Фамилия, номер зачетной книжки, факультет, группа,
Фамилия, номер читательского билета, название книги, срок возврата.
Наименование товара, цена, количество, процент торговой надбавки.
Номер рейса, пункт назначения, время вылета, дата вылета, стоимость билета.
Фамилия, количество оценок, оценки, средний балл.
Фамилия, дата поступления, дата отчисления.
Регистрационный номер автомобиля, марка, пробег.
Фамилия, количество переговоров (для каждого - дата и продолжительность).
Номер телефона, дата разговора, продолжительность, код города.
Номер поезда, пункт назначения, дни следования, время прибытия, время стоянки.
Название кинофильма, сеанс, стоимость билета, количество зрителей.
Вопросы без ответов
Определить значения переменных после выполнения действий над статическими данными.
//------------------------------------------------------54-02.cpp
//------------------------------------------------------- 1
struct man1 {
char name[20];
int dd,mm,yy;
char *zodiak;
man1 *next; }
A1= {"Петров",1,10,1969,"Весы",NULL },
B1= {"Сидоров",8,9,1958,"Дева",&A1 },
*p1 = &B1;
void F1() { char c1,c2,c3,c4;
c1 = A1.name[2]; c2 = B1.zodiak[3]; c3 = p1->name[3]; c4 = p1->next->zodiak[1]; }
//------------------------------------------------------- 2
struct man2 {
char name[20];
char *zodiak;
man2 *next;
} C2[3] = {
{"Петров","Весы",NULL },
{"Сидоров","Дева",&C2[0] },
{"Иванов","Козерог",&C2[1] }};
void F2() { char c1,c2,c3,c4;
c1 = C2[0].name[2]; c2 = C2[1].zodiak[3];
c3 = C2[2].next->name[3]; c4 = C2[2].next->next->zodiak[1]; }
//------------------------------------------------------- 3
struct tree3 {
int vv;
tree3 *l,*r; }
A3 = { 1,NULL,NULL }, B3 = { 2,NULL,NULL },
C3 = { 3, &A3, &B3 }, D3 = { 4, &C3, NULL },
*p3 = &D3;
void F3() { int i1,i2,i3,i4; i1 =A3.vv; i2 = D3.l->vv; i3 =p3->l->r->vv; i4 = p3->vv; }
//------------------------------------------------------- 4
struct tree4 {
int vv;
tree4 *l,*r;
} F[4] =
{{ 1,NULL,NULL }, { 2,NULL,NULL },
{ 3, &F[0], &F[1] }, { 4, &F[2], NULL }};
void F4() { int i1,i2,i3,i4; i1 = F[0].vv; i2 = F[3].l->vv; i3 = F[3].l->r->vv; i4 = F[2].r->vv; }
//------------------------------------------------------- 5
struct list5 {
int vv;
list5 *pred,*next;
};
extern list5 C5,B5,A5;
list5 A5 = { 1, &C5, &B5 }, B5 = { 2, &A5, &C5 }, C5 = { 3, &B5, &A5 }, *p5 = &A5;
void F5() { int i1,i2,i3,i4;
i1 = A5.next->vv; i2 = p5->next->next->vv;
i3 = A5.pred->next->vv; i4 = p5->pred->pred->pred->vv; }
//------------------------------------------------------ 6
struct dat7 { int dd,mm,yy; }
aa = { 17,7,1977 },
bb = { 22,7,1982 };
struct man7 {
char name[20];
dat7 *pd;
dat7 dd;
char *zodiak; }
A7= {"Петров", &aa, { 1,10,1969 }, "Весы" },
B7= {"Сидоров", &bb, { 8,9,1958 }, "Дева" },
*p7 = &B7;
void F7() { int i1,i2,i3,i4; i1 = A7.dd.mm; i2 = A7.pd->yy; i3 = p7->dd.dd; i4 = p7->pd->yy; }
//------------------------------------------------------ 7
struct dat8 { int dd,mm,yy; };
struct man8 {
char name[20];
dat8 dd[3];
} A8[2] = {
{"Петров", {{1,10,1969},{8,8,1988},{3,2,1978}}},
{"Иванов",{{8,12,1958},{12,3,1976},{3,12,1967}}}
};
void F8() { int i1,i2; i1 = A8[0].dd[0].mm; i2 = A8[1].dd[2].dd; }
//------------------------------------------------------ 8
struct man9 {
char name[20];
char *zodiak;
man9 *next;
} A9= {"Петров","Весы",NULL },
B9= {"Сидоров","Дева",&A9 },
*p9[4] = { &B9, &A9, &A9, &B9 };
void F9() { char c1,c2,c3,c4;
c1 = p9[0]->name[2]; c2 = p9[2]->zodiak[3];
c3 = p9[3]->next->name[3]; c4 = p9[0]->next->zodiak[1]; }
