Борис Пахомов Санкт Петербург бхв петербург 2013 удк 004. 4 Ббк 32. 973. 26018. 2 П
 Скачать 17.38 Mb.
|
|
Обращение к элементам структур Мы видели, что после объявления структуры (а это фактически тип данного, имя которого равно имени структуры) можно объявить некую переменную типа этой структуры или указатель этого типа (указатель на эту структуру. Если вы объявили переменную типа структуры, то чтобы обратиться к элементам структуры, надо после имени переменной поставить точку, а если вы объявили указатель на структуру, то после имени указателя на данную структуру надо поставить стрелку вправо ( -> ). Затем нужно к этим именам приписать имя члена структуры, к которому надо обратиться. Если требуется обратиться к членам вложенной структуры, то следует продолжить операции сточкой или стрелкой вправо с именем подструктуры, а затем с именем ее члена. Примеры обращения к членам экземпляров структуры emp[0].name , emp[521].salary , emp[121].hiredate.year Глава 7. Работа с указателями и структурами данных Допустим, p=&emp[1] . В этом случае p->adress — это адрес работника, который содержится в экземпляре структуры emp[1] , а год поступления на работу — p-> hiredate->year . Однако существуют некоторые ограничения членом структуры может быть любой тип данных ( int , float , массив, структура, но элемент структуры не может иметь тот же тип, что и сама структура. Например Такое объявление структуры неверно, т. к. t не может иметь тип r . При этом указатель на тот же тип разрешен. Например struct r {int s; struct r Такое объявление верно в языке С членом структуры не может быть функция, а указатель на функцию может быть членом структуры. Например struct r { int s; (*comp)(char *a,char *b); Такое объявление верно в С+ функция может быть членом структуры. Дело в том, что в С+ структуры рассматриваются как класс, те. для членов структуры могут быть определены спецификации доступа к памяти, определяемые для членов класса public всегда определена по умолчанию, protected и private их мы рассмотрим при изучении классов. В листинге 7.6 приведен текст простейшей программы, в которой функция является членом структуры (результат работы этой программы показан на рис. 7.6); Листинг 7.6 // 7.6_2011.cpp #include "stdafx.h" #include #include //------------------------------------------------------------- int main() { struct aaa { public: определена по умолчанию (приведена для примера) 124 Часть I. Изучение языка С/С++ int i; int f(int a) //функция-член структуры { объявлена прямо в структуре return(-a); }; }bbb; int a; a=bbb.f(15); printf("a=%d\n",a); _getch(); } Рис 7.6. Результат работы программы из листинга 7.6 в языке С внешнюю или статическую структуру можно инициализировать. Например, имеем шаблон struct date { int day; день недели int month; номер месяца int year; год char monthname[4]; название месяца В этом случае можем инициализировать структуру struct date Инициализация массива структур будет задаваться так struct a {char *s; int i;}m[3]={"u1",0, "u2",0, "u3",0 присваивать значения одной структуры другой разрешено только для экземпляров одной структуры. Например, существует структура struct A {int i; char d}a,a1; и struct B{int i; char В этом случае можно выполнить a=a1; или a1=a; . Но операцию выполнить нельзя, т. ка и b считаются относящимися к шаблонам разного типа (у их шаблонов разные имена и этого достаточно, чтобы считать их разными, хотя по структуре они совпадают. Глава 7. Работа с указателями и структурами данных Структуры и функции Функция может возвращать структуру или указатель на структуру. Например, если объявить структуру mystruct func1(void); , то функция func1() возвратит структуру. Для структуры mystruct *func2(void); функция func2() возвратит указатель на структуру (функция сама ничего не возвратит мысами должны этого добиться с помощью С, который это позволяет сделать. Структура может передаваться в качестве аргумента функции следующими способами непосредственно void func1(mystruct через указатель void func2(mystruct в языке С+ через ссылку void func3(mystruct Чем отличаются понятия "ссылка" и "указатель Ссылка — это непосредственно адреса указатель — переменная, содержащая адрес (подобное различие существует между константой и переменной. Программы со структурами Приведем примеры программ, где используются функции, имеющие на входе структуру и возвращающие либо саму структуру, либо указатель на нее. Функция возвращает структуру В листинге 7.7 приведен пример программы, в которой функция возвращает структуру. Листинг 7.7 // 7.7_2011.cpp #include "stdafx.h" #include #include #include #include #include #define eof -1 #define maxline 1000 126 Часть I. Изучение языка С/С++ //-------Ввод строки с клавиатуры int getline(char s[],int lim) { int c,i; for(i=0; i //----------------------------------------- struct key { char *keyword; int keycount; }tab[]={"break",0, "case",0, "char",0, "continue",0, "end",0 },bbb; struct key BinaryInStruc(char *word,struct key tab[],int n) Ищет в массиве структур слово, находящееся в word n — размерность массива, которая должна быть задана не больше, чем количество инициализированных элементов массива. Возвращает структуру (элемент массива tab[]), в которой находится слово, заданное в word, либо tab[] последнего обработанного индекса (можно было бы возвратить tab[] любого существующего индекса, в котором значение keycount равно –1 (сигнал того, что заданное слово в массиве структур не обнаружено { int low,high,mid,cond; low=0; high=n-1; while(low <= high) { mid=(low+high)/2; if((cond=strcmp(word,tab[mid].keyword)) < 0) high=mid — 1; if(cond < 0) { high=mid — 1; continue; } if(cond > 0) { low=mid + 1; continue; } Глава 7. Работа с указателями и структурами данных tab[mid].keycount=0; return(tab[mid]); найдено } //while tab[mid].keycount=-1; return(tab[mid]); не найдено } //------------------------------- int main() { char s[maxline]; int c; do { printf("Enter your new string >"); getline(s, maxline); bbb =BinaryInStruc(s,tab,5); if(bbb.keycount!= -1) printf("Found string = %s\n",bbb.keyword); else printf("not found\n"); // _getch(); } while((c=getchar()) != eof) здесь, как ив операторе getline(), надо использовать а не getch(), иначе не будет останова на вводе в getline() при повторном обращении */ ; конец оператора do...while нам надо было, чтобы тело while выполнилось хотя бы один раз } //main() Рассмотрим функцию BinaryInStruc , возвращающую структуру struct key BinaryInStruc(char *word,struct key tab[],int Сама структура определена до объявления функции объявлен шаблон key и поэтому шаблону задан массив структур tab[] и один экземпляр bbb . Массив структур инициализирован заданы значения только символьных строк, т. к. мы собираемся искать нужную строку, задавая на входе ее образец. Массив упорядочен по возрастанию строк, т. к. для поиска будет применяться метод деления отрезка пополам. Алгоритм этого метода рассматривался нами ранее. Значение keycount для поиска не используется, а применяется только для возврата если не найдена структура, в которой содержится заданное с клавиатуры слово, то возвращается структура, у которой значение keycount будет равно –1. В теле функции реализован метод двоичного поиска концы отрезка, на котором располагаются индексы массива tab[] , постоянно находятся в переменных low и high , а средняя точка — в переменной mid . Сравнение значений в word и tab[] осуществляется с помощью уже рассмотренной функции strcmp(word,tab[mid]. keyword) . Если в средней точке строки в переменной word ив переменной tab[mid] 128 Часть I. Изучение языка С/С++ значения keyword совпадают, то возвращается таблица структур в этой точке, иначе возвращается таблица структур в последней средней точке со значением keycount , равным –1. В основной программе запрашивается слово, которое вводится функцией getline() , а затем передается вместе с массивом структур (таблицей tab[] ) в качестве параметров функции BinaryInStruc() , возвращающей структуру, значение которой, в свою очередь, присваивается экземпляру bbb этого же шаблона (как мы видели ранее, эту операцию можно применить к структурам одинаковых шаблонов. Результат работы программы показан на рис. 7.7. Рис 7.7. Результат работы программы листинга Функция возвращает указатель на структуру Изменим предыдущую программу так, чтобы функция возвращала вместо индекса массива указатель на структуру, в которой найдено или не найдено заданное слово листинг 7.8). Листинг 7.8 // 7.8_2011.cpp #include "stdafx.h" #include #include #include #include #include #define eof -1 #define maxline 1000 Ввод строки с клавиатуры int getline(char s[],int lim) Глава 7. Работа с указателями и структурами данных { int c,i; for(i=0; i //----------------------------------------- struct key { char *keyword; int keycount; }tab[]={"break",0, "case",0, "char",0, "continue",0, "end",0 },*bbb; struct key *BinaryInStruc(char *word,struct key tab[],int n) Ищет в массиве структур слово, находящееся в word n — размерность массива, которая должна быть задана не больше, чем количество инициализированных элементов массива. Возвращает указатель на структуру типа key, в которой находится слово, заданное в word, либо возвращает NULL (сигнал того, что заданное слово в массиве структур не обнаружено { int cond; struct key *low =&tab[0]; здесь low и high — это указатели на первый и последний элементы таблицы struct key *high=&tab[n-1]; struct key *mid; здесь будет указатель на средний элемент таблицы while(low <= high) указатели можно сравнивать { mid=low + (high — low)/2; разность между указателями — это число элементов массива, которое можно делить, а поскольку операция деления "/" даст целое число, то его можно прибавить к указателю low*/ if((cond=strcmp(word,mid->keyword)) < 0) { high=mid — 1; от указателя можно вычесть целое число, в результате получим указатель на предыдущий элемент continue; } 130 Часть I. Изучение языка С/С++ if(cond > 0) { low=mid + 1; continue; } return(mid); найдено (возврат указателя на найденный элемент таблицы, те. на структуру } //while return(NULL); не найдено } //------------------------------- int main() { char s[maxline]; int c; do { printf("Enter your new string >"); getline(s, maxline); bbb =BinaryInStruc(s,tab,5); //bbb объявлен как указатель на структуру типа key if(bbb != NULL) printf("Found string = %s\n",bbb->keyword); else printf("not found\n"); // _getch(); } while((c=getchar()) != eof) ; конец оператора do...while требовалось, чтобы тело while выполнилось хотя бы один раз } //main() Пояснения к этой программе даны в ее тексте. Результат работы совпадает с результатом работы предыдущей программы и показан на рис. 7.8. Рис 7.8. Результат работы программы листинга 7.8 Глава 7. Работа с указателями и структурами данных Программа упрощенного расчета заработной платы одному работнику В этой программе создана функция расчета, которой передается в качестве параметра указатель на структуру (листинг 7.9). Результат расчета показан на рис. 7.9. Листинг 7.9 // 7.9_2011.cpp // #include "stdafx.h" #include #include #include #define eof -1 #define maxline 1000 Ввод строки с клавиатуры int getline(char s[],int lim) { int c,i; for(i=0; i //----------------------------------------- struct zrp структура данных по зарплате { char *name; имя работника float stavka; оплата за один рабочий день float nalog; величина налога }emp[]={"Ivanov",200,0.1, "Petrov",300,0.2, "Sidorov",400,0.3 }; Здесь задан массив экземпляров структур одна структура содержит данные на одного работника. Массив сразу проинициализирован.*/ Функция начисления зарплаты одному работнику. RabDn — количество отработанных дней 132 Часть I. Изучение языка С/С++ float zarplata(struct zrp *z,int RabDn) { return(z->stavka * RabDn * (1 — z->nalog)); } //------------------------------- int main() { char c,s[maxline]; struct zrp *p1; определение размера массива int RazmMas = sizeof(emp)/sizeof(zrp); do { ввод номера работника m: printf("enter emp's number >"); getline(s, maxline); int i=atoi(s); if(i < RazmMas) контроль количества заданных элементов массива p1=&emp[i]; else goto m; ввод количества отработанных дней printf("enter work's days amount >"); getline(s, maxline); i=atoi(s); float zp = zarplata(p1,i); обращение к функции расчета зарплаты printf("%s %6.2f\n",p1->name,zp); } while((c=getchar()) != eof) ; конец оператора do-while } //main() Рис 7.9. Расчет зарплаты одному работнику Глава 7. Работа с указателями и структурами данных Рекурсия в структурах В структурах возможна рекурсия, те. структуры могут ссылаться сами на себя. Допустим, у нас имеется списковая структура типа Слово (cтрока символов, "Счетчик количества каждого искомого слова в тексте, Указатель на предыдущую структуру, в которой встречается данное слово, "Указатель на последующую структуру, в которой встречается данная строка. Такая структура может быть представлена в виде рекурсивного шаблона c указателем на такую же структуру struct tnod //(***) { char *word; int count; struct tnod *left; struct tnod *right; Если, например, p=&t , то доступ к элементам структуры будет таким p->word, p->left, Приведем пример программы, подсчитывающей количество встречающихся вне- котором тексте слов. Эта программа передает введенные с клавиатуры слова специальной функции, которая по ним строит в памяти так называемое "двоичное дерево. Двоичное дерево — это такая конструкция, которая отображает связь между данными исходя из того, что данные находятся в так называемых узлах. Под узлом понимается переменная типа "структура" (ее еще называют записью. Первая запись двоичного дерева (его корень) содержит один узел. В узле содержится некая полезная информация, для обработки которой мы и строим само дерево, а также два указателя на нижестоящие узлы. Из корневого узла "вырастают" всего две "веточки левый нижний узел первый указатель) и правый нижний узел (второй указатель. Из каждого из этих узлов тоже "вырастает" по две "веточки" и т. д. Можно сказать, что в такой конструкции каждый узел — это тоже двоичное дерево (корень, из которого выходят две "веточки"). В нашем случае двоичное дерево строится так никакой узел этого дерева не содержит более двух ближайших потомков (детей в корневом узле слова нет первое поступившее слово записывается в корневой узел, а остальные поступающие будут распределяться так если поступившее слово меньше первого, то оно записывается в левое поддерево, если больше корневого — в правое каждое слово будет находиться в структуре типа (***) ; слово записывается в переменную word , а счетчик count в данной структуре устанавливается в единицу слово пока что встретилось (в нашем случае, введено) один раз. 134 Часть I. Изучение языка С/С++ Если встретится еще такое же слово, ток счетчику count в данной структуре добавится единица. При этом в корневой структуре в переменной left формируется указатель на структуру, в которую записалось слово меньшее, чем слово в корневой структуре. Если же поступило слово, которое больше слова в корневой структуре, то оно записывается, как уже говорилось, в отдельную структуру (узел, а указатель на этот узел записывается в переменную right корневой структуры. Потом вводится третье слово. Оно опять сравнивается со словами, находящимися в структурах дерева (***) , начиная с корневой структуры и далее по тем же принципам, что описаны ранее. Если поступившее слово меньше корневого, то дальнейшее сравнение идет в левой части дерева. Это означает, что из корневой структуры выбирается указатель, хранящийся в переменной left , по нему отыскивается следующее (меньшее, чем в данном узле) слово, с которыми станет сравниваться поступившее. Если поступившее слово меньше, то из нового узла извлекается указатель, хранящийся в переменной left , и по нему выбирается следующий "левый" узел и т. д. Если же больше узла нет (в последнем узле left будет нуль, то поступившее слово записывается в новый формируемый узел, в обе части left и right которого записываются нули (признак того, что этот узел последний. Если жена каком-то этапе поступившее слово оказывается больше, чем слово в левом узле, то рассматривается указатель right этого узла и по нему определяется структура (узел, где находится следующее (меньшее этого) слово, с которым станет сравниваться поступившее. Если оно окажется больше, то дальше пойдет проверка следующей "правой" структуры и сравнение с ее данными, если же меньше, то процесс перейдет на левую часть поддерева движение по сравнению пойдет полевым" структурам. В итоге получим двоичное дерево от каждого узла будут выходить не более двух подузлов и таких, что в левом подузле всегда будет слово, меньшее, чем в самом узле, а в правом подузле всегда будет находиться слово большее, чем в в самом узле. Так как физически каждое слово будет находиться в отдельной структуре типа, тов этой же структуре в переменных left и right будут располагаться указатели на структуры, где хранятся подузлы данной структуры. И все это дерево располагается в памяти. Программа, реализующая рекурсию в структурах, приводится в листинге 7.10. На рис. 7.10 отражен результат выполнения этой программы. Листинг 7.10 // 7.10_2011.cpp #include "stdafx.h" #include #include #include #include Глава 7. Работа с указателями и структурами данных #define maxline 1000 #define eof -1 int fix=0; глобальная для печати дерева Ввод строки с клавиатуры int getline(char s[],int lim) { int c,i; for(i=0; i //--------------------------------- struct tnod базовый узел { char *word; значение переменной — символьная строка в узле слово) int count; здесь накапливается число встреч данного слова struct tnod *left; левый потомок здесь хранится указатель на левый подузел, те. на структуру, в которой хранится слово, меньшее данного. Если слов меньших данного нетто здесь хранится нуль */ struct tnod *right; правый потомок здесь хранится указатель на правый подузел, те. на структуру, в которой хранится слово, большее данного. Если слов больших данного нетто здесь хранится нуль */ }; char *strsave(char *s) // C++ позволяет объявлять без слова struct Функция выделяет по malloc() память по длине строки s, ив эту память помещает саму строку s, а затем выдает указатель на начало помещенной в буфер строки. */ { char *p; p=(char *)malloc(sizeof(strlen(s)+1)); т. к. malloc() выдает указатель типа void, то принудительно приводим его к типу char, чтобы согласовать с р if((p != NULL)) strcpy(p,s); return(p); } //--------------------------------- tnod *NodAlloc(void) Функция выделяет память под структуру tnod и возвращает указатель на эту память { tnod *p=p=(tnod *)malloc(sizeof(tnod)); 136 Часть I. Изучение языка С/С++ return(p); } //---------------------------------- tnod *MakeTree(tnod *p,char *w) Эта функция формирует двоичное дерево. p — указатель на структуру, по которой будет создаваться новый узел или будут проверяться старые узлы. w — слово, поступающее для его поискав дереве. Если такое слово уже есть, тов счетчик структуры, где оно обнаружено, добавляется единица подсчитывается, сколько одинаковых слов. Если такого слова в дереве нетто для него образуется новый узел (новая структура) */ { int cond; if(p==NULL) появилось новое слово. Для этого слова еще нет узла и его надо создать { p=NodAlloc(); выделяется память под новый узел p->word=strsave(w); введенное слово по strsave() записывается в память и на него выдается указатель */ p->count = 1; // слово пока единственное p->left=p->right= NULL; т. к. это слово пока последнее в дереве, то этот узел не указывает наследующие (меньшие — слева или большие — справа) слова дерева } else if((cond=strcmp(w,p->word))==0) /* слово не новое, тогда оно сравнивается со словом в узле, на который указывает указатель р p->count++; в этом узле — такое же слово, поэтому добавляем к счетчику единицу else if(cond < 0) слово меньше того, которое в узле, поэтому его помещаем в левую часть дерева опять же с помощью этой функции. Ее первая часть создаст узел в динамической памяти, поместит в него слово, в левые и правые подузлы поместит нули, т. к. пока дальше этого слова ни справа, ни слева ничего нет, а в левую часть узла- предка поместит указатель на эту структуру */ p->left=MakeTree(p->left,w); else if(cond > 0) p->right=MakeTree(p->right,w); слово больше того, которое в узле, поэтому мы его помещаем в правую часть дерева опять же с помощью этой же функции ее первая часть создаст узел в динамической памяти, поместит в него слово, в левые и правые подузлы поместит нули, т. к. пока дальше этого слова ни справа, ни слева ничего нет, а в правую часть узла-предка поместит указатель на эту структуру */ return(p); Глава 7. Работа с указателями и структурами данных Возвращает указатель на область, где создана новая структура, или на структуру, в которую добавлена единица, т. к. поступившее слово совпало со словом в этой структуре } //----------------------------- int TreePrint(tnod *p) //left_right=1 при выводе левого узла //left_right=2 при выводе правого узла Эта функция печатает или выводит на экран все дерево, рекурсивно себя вызывая { if(p != NULL) //p всегда указывает на начало дерева р — дерево существует { /*Left = ссылка на левый подузел, right — на правый. Эти ссылки могут быть нулевыми дерево дальше не идет printf("Count word repetition=%d word's value=%s\n",p->count,p->word); TreePrint(p->left); выводит левый узел TreePrint(p->right); выводит правый узел } return(0); } //------------------------------------------------------------- #pragma argsused int main() { tnod *pp; char s[maxline]; pp=NULL; int i=0; printf("Enter your words: >\n"); while(getline(s,maxline)-1) /*getline() возвращает количество введенных символов Когда нажимаем только { pp=MakeTree(pp,s); // формирует очередной узел // рр всегда указывает на начало дерева } //while TreePrint(pp); вывод дерева _getch(); } Физическая структура дерева приведена на рис. 7.11. 138 Часть I. Изучение языка С/С++ |