Объединения разнотипных данных
Лекция №25. Структуры и объединения
План:
1. Структура как тип и совокупность данных;
2. Объединения разнотипных данных;
3. Примеры с использованием структур и объединений.
Из основных типов языка С++ пользователь может конструировать произвольные типы, например, структуры и объединения, такие типы называют АТД (агрегатные типы данных). Вместе с массивами структуры и объединения отнесены к структурированным типам.
Такие определяемые пользователем типы данных, как стек, комплексные числа и колоды карт являются примерами реализации АТД. Значительная часть процесса объектно-ориентированного проектирования заключается в придумывании АТД, соответствующих задаче. Хороший АТД не только моделирует основные черты данной задачи, но часто также может использоваться в других программах.
Структура как тип и совокупность данных
Тип структуры позволяет программисту объединить компоненты в переменную с одним именем. Каждая структура включает в себя один или несколько объектов (переменных, массивов, указателей, структур и т. д.), называемых элементами структуры(structure members). Поскольку члены структуры бывают различных типов, программист может создавать агрегаты (данных), позволяющие описывать сложные данные.
В качестве простого примера определим структуру, описывающую игральную карту. Метки на карте, представляющие её достоинство, называются очками (pips). Например, тройка пик имеет достоинство (значение очков) – 3, и значение масти – пики. Можно объявить тип структуры, как показано в следующем фрагменте.
|
|
|
В файле poker1.cpp
Enum suit (clubs, diamonds, hearts, spades); // масти
Typedef int pips; // pips является синонимом Int
Struct card { // карта
Suit s;
Pips p; // от 1 до 13 соответствует Т, 2, …. , В, Д, К
};
В С++ имя структуры или теговое имя (tag name) является типом. В данном объявлении struct – это ключевое слово, card – теговое имя структуры, а переменные p и s – это элементы структуры. Переменная р будет принимать значения от 1 до 13, что соответствует картам от туза до короля. Она является переменной типа pips, объявленного с помощью ключевого слова typedef и созданного как синоним int. Объявление с таким именем придаёт программе документированность и сводит сложные объявления к ясным идентификаторам. Объявление struct card можно рассматривать как «чертёж»: оно создаёт тип card, но не фактические экземпляры. Объявление
Card c 1, c 2
выделяет память для идентификаторов с1 и с2 типа card. Для доступа к членам структур с1 и с2 используется оператор выбора члена структуры, представляющий собой точку «.». допустим, мы хотим присвоить с1 значение, соответствующее пятёрке бубен, а с2 – дамы пик. Можно написать:
|
|
|
c1.p = 5;
c1.s = diamonds;
c2.p = 12;
c2.s = spades;
Конструкция вида
переменная_структуры.имя_элемента
используется как переменная – точно таким же образом, как простая переменная или элемент массива. Имя элемента должно быть уникальным внутри данной структуры. Поскольку член структуры всегда должен предваряться идентификатором переменной (теговым именем) структуры, никакой путаницы между членами, имеющими одинаковые имена в разных структурах, не возникает.
Пример :
Struct fruit {
Char name[15];
Int calories;
};
Struct vegetable {
Char name[15];
Int calories;
};
fruit a;
vegetable b;
Сделав такое объявление, можно обращаться к a.calories и b.calories безо всякой двусмысленности.
Вообще, структура объявляется ключевым словом struct, за ним следует идентификатор (теговое имя), затем в фигурных скобках идёт список объявлений членов. Теговое имя необязательно, но если оно есть, то должно отражать суть моделируемого АТД. Когда теговое имя отсутствует, объявление структуры является безымянным и может использоваться только для немедленного (следующего сразу за объявлением безымянной структуры) объявления переменный этого типа, например:
Struct {
Int a, b, c;
} triples [2] = { {3, 3, 6}, {4, 5, 5} };
|
|
|
Оператор указателя структуры
С++ предоставляет оператор указателя структуры -> для доступа к членам структуры посредством указателя. С клавиатуры этот оператор вводится как знак «минус», за которым следует знак «больше». Если переменной-указателю присвоен адрес структуры, то доступ к элементу структуры может быть осуществлён с помощью конструкции вида:
Указатель_на_структуру -> имя_члена
То же самое можно задать и так:
(*Указатель_на_структуру).имя_члена
Операторы « -> » и «.», также как () и [], имеют самый высокий приоритет и выполняются слева направо. Проиллюстрируем их использование на простых примерах:
Объявления и присваивания
Card cd, *pc = &cd;
Card deck[52];
cd.p = 5;
cd.s = spades;
deck[0] = cd;
Выражение
Cd.p
cd.suit
deck[0].p
(*pc).suit
Эквивалентное выражение
pc -> p
pc -> suit
deck -> p
pc -> suit
Значение
5
spades
5
spades
Пример: стек
Стек – одна из наиболее полезных структур данных. Стек позволяет вставлять и удалять данные, причём выполнение этих операций осуществляется исключительно над вершиной стека 9то есть над самым верхним его элементом). Такой порядок называется «первым пришёл, последним вышел» (last-in-first-out, LIFO). По идее, стекведёт себя как стопка подносов: поднос оказывается наверху, если предыдущий забрали, или «опускается» в стопке вниз, если сверху положили ещё один. Структура данных, основное назначение, которой – хранение информации, называется контейнером (container),
|
|
|
Стек допускает следующие операции: push(поместить), pop(извлечь), top(вершина), empty(пусто) и full(заполнен). Операция push помещает значение в стек, pop извлекает значение из стека и удаляет его, top возвращает верхнее значение в стеке, empty проверяет, не пуст ли стек, а full проверяет, не полон ли он. Стек является типичным АТД.
Реализуем стек как тип данных С++ для хранения символьных значений, используя структуру так, как она понимается в базовом языке. Реализация будет использовать символьный массив фиксированной длины для хранения содержимого стека. Вершиной стека будет член с именем top, принимающий целые значения. Различные операции со стеком будут реализованы в виде функций, список аргументов каждой из которых включает в качестве параметра указатель на ch_stack. Это позволит изменять стек и избежать его копирования при вызове по значению.
В файле ch_stac1.h
Const int max_len = 1000;
Enum { empty = -1, full = max_len – 1};
Struct ch_stack {
Char s[max_len];
Int top;
};
// стандартный набор операций с ch_stack
void reset(ch_stack* stk) //обнуление стека
{
stk -> top = empty;
}
void push(ch_stack* stk, char c)
{
stk -> s[++stk -> top] = c; //приоритет: ++(stk -> top)
}
char pop(ch_stack* stk)
{
return (stk -> s [stk -> top--] );
}
char top(ch_snack* stk)
{
return (stk -> s [stk -> top] );
}
bool empty (const ch_stack* stk)
{
return (stk -> top == empty);
}
bool full(const ch_stack* stk)
{
return (stk -> top == full);
}
Разбор функции ch_stack
Объявление struct создаёт новый тип – ch_stack. В нём два элемента: элемент-массив s и целый элемент top.
Функция reset используется для инициализации. Члену top присваивается значение empty. Конкретный ch_stack, с которым работает эта функция, является аргументом, передаваемым как адрес.
Операция помещения в стек (push) реализована как функция двух аргументов. Член top увеличивается на единицу. Значение c помещается вершину ch_stack. Эта функция полагает, что ch_stack не заполнен. Операция извлечения из стека (pop) реализована таким же образом; в ней предполагается, что ch_stack не пуст. Возвращается значение вершины стека, и член top уменьшается на единицу.
Функции empty и full возвращают значение типа bool. Каждая из них проверяет член top на соответствующее условие. Например, перед вызовом push() программист может проверить, что ch_stack не полон, для того чтобы функция push() работала корректно. Эти функции не изменяют ch_stack, на который они направлен. Поэтому мы можем объявить аргументы-указатели как const. Во всех функциях аргумент ch_stack передаётся как адрес, а для доступа к членам используется оператор указателя структуры ->.
При условии, что описанные выше объявления находятся в файле ch_stac1.h, можно проверить операции со стеком с помощью следующей программы, которая помещает символы строки в стек и извлекает их, печатая символы в обратном порядке.
В файле ch_stac1.cpp
#include “ch_stac1.h”
#include <iostream.h>
int main()
{
ch_stack s;
char str[40] = {“Всем привет!”};
int i = 0;
cout << str << endl; //печать строки
reset (&s);
while (str[i] && !full(&s)) //помещение в стек
push(&s, str[i++] );
while (!empty(&s)) //печать обращённой строки
cout << pop(&s);
cout << endl;
}
Вывод этой программы выглядит так:
Всем привет!
!тевирп месВ
Отметим, что одним из фактических аргументов в каждой из функций является &s, то есть адрес переменной типа ch_stack, объявленной в main(). Мы задаём этот аргумент, поскольку функции ожидают адрес переменной типа ch_stack.
Объединения разнотипных данных
Объединение (union) можно рассматривать как структуру, све элементы которой при размещении в памяти имеют нулевое смещение от начала. Тем самым все элементы объединения размещаются в одном и том же участке памяти. Размер участка памяти, выделяемого для объединения, определяется максимальной из длин его элементов.
Это произвольный тип, синтаксис которого такой же, как и у структур, за исключением того, что ключевое слово union заменяет strust. Объявление объединения позволяет интерпретировать его значение как набор типов входящих в него членов. Объединение инициализируется значением в фигурных скобках, причём оно присваивается первому члену объединения. Рассмотрим общий вид объявления объединения:
Union имя_объединяющего_типа { элементы_объединения };
Пример объединяющего типа:
Union mixture { double d;
Long e[2];
Int k[4]; };
Введя тип объединения, можно определять конкретные объединения, их массивы, а также указатели и ссылки на объединения:
Mixture mA, mB[4]; //объединение и массив объединений
Mixture *pmix; // указатель на объединение
Mixture& rmix = mA; // ссылка на объединение
Для обращения к элементу объединения можно использовать либо уточнённое имя:
Имя_объединения.имя_элемента
либо конструкцию, включающую указатель:
указатель_на_объединение -> имя_элемента
(*указатель_на_объединение). имя_элемента
либо конструкцию, включающую ссылку:
ссылка_на_объединение.имя_элемента
Примеры:
mA.d = 64.8;
mB[2].E[1] = 10L;
pmix = &mB[0];
pmix->E[0] = 66;
cin >> (*pnix).K[1];
cin >> rmix.E[0];
Заносить значения в участок памяти, выделенный для объединения, можно с помощью любого из его элементов. То же самое справедливо и относительно доступа к содержимому участка памяти, выделенного для объединения. Если бы элементы объединения имели одинаковую длину и одинаковый тип, а отличались только именами, то использование объединения было бы подобно применению ссылок. Просто один участок памяти в этом случае имел бы несколько различных имён:
Union { int ii, int jj } unij;
Unij.ii = 15; //изменение содержимого;
Cout << unij.jj; //вывод содержимого
Основное назначение объединений – обеспечить возможность доступа к одному и тому же участку памяти с помощью объектов разных типов. Необходимость в таком механизме возникает, например, для выделения из внутреннего представления (из кода) объекта определённой части. Например, следующее объединение с именем сс позволяет выделить из внутреннего представления целого числа его отдельные байты:
Union { char hh[2];
Int ii;} cc;
Здесь символьный массив char hh[2] и целая переменная int ii – элементы объединения – соответствуют одному участку памяти:
Участок памяти,
выделенный
объединению сс
Используем введённое объединение с именем сс для решения небольшой конкретной задачи, связанной с доступом к буферу клавиатуры ПЭВМ типа IBM PC. В MS-DOS принято, нажатие на любую клавишу клавиатуры ПЭВМ приводит к занесению в буфер клавиатуры (буфер клавиатуры – это специально зарезервированный участок памяти) целого двухбайтового числа. Каждый байт этого целого числа имеет самостоятельное смысловое значение. Байт с младшим адресом содержит так называемый ASCII-код клавиши, а старший (с большим адресом) содержит дополнительный код, называемый скэн-кодом клавиши. В библиотеке компилятора С++ имеется специальная функция int bioskey(int b); позволяющая получить доступ к буферу клавиатуры. Параметр int b функции bioskey() позволяет выбрать режим её использования. Обращение boiskey(1) проверяет наличие в буфере хотя бы одного кода. Если буфер пуст, то bioskey(1) возвращает ненулевое значение.
Как только в буфере появится код (от нажатия клавиши), функция bioskey(1) возвратит ненулевое значение. Прочитать тот код, который занесён в буфер, и очистить буфер от этого кода позволяет обращение к функции bioskey() с нулевым значением параметра. При обращении bioskey(0) функция выбирает из буфера клавиатуры очередной двухбайтовый код и возвращает его как целое число (двухбайтовое). Выделить из этого числа отдельные байты очень просто с помощью объединения. Следующая программа получает и выводит на экран значения кодов, поступающих в буфер клавиатуры ПЭВМ, работающей под управлением MS-DOS:
#include <bios.h> //для функции bioskey()
#include <iostream.h>
void main()
{ union {char hh[2]; int ii; } cc;
unsigned char scn, //скэн-коды
asc; //ASCII-коды
cout << “\nВыход из программы по Ctrl+Z”;
cout << “\n\nSCAN | ASCII”;
do { //цикл до Ctrl+Z
cout << “\n”;
while (bioskey(1) == 0); //До появления кода
cc.ii = bioskey(0);
asc = cc.hh[0];
scn = cc.hh[1];
cout << “ “ << int(scn) << “ | “;
cout << int(asc) << “ “ << asc;
} //выход из цикла по Ctrl+Z, когда asc == 26 и scn == 44:
while (asc != 26 || scn != 44);
}
Результат выполнения программы:
SCAN | ASCII
34 | 103 g
35 | 104 h
36 | 106 j
24 | 111 o
44 | 26
Для ASCII_кода печатается не только числовое значение, но и соответствующий ему экранный символ.
Обратите внимание на внутренний цикл while с проверкой значение bioskey(1). Он прерывается только при появлении внешнего события – при нажатии на клавишу. Значение bioskey(1) становится при этом отличным от 0, и следует переход ук оператору с обращением bioskey(0).
Возвращаемое целое значение заносится в элемент объединения cc.ii, а потом из объединения выбираются отдельные однобайтовые коды (scn, asc). Внешний цикл будет прерван при появлении кодов asc ==26 и scn == 44 (сочетание клавиш Ctrl+Z). После этого программа прекращает выполнение.
Объединение может быть безымянным:
// в файле weekend.cpp
enum week { sun, mon, tues, weds, thurs, fri, sat }; //дни недели
union {
int i;
week w;
};
i = 5;
if (w == sat || w == sun) //суббота или воскресение
cout << “Выходной!”;
Объявление безымянного объединения позволяет использовать идентификаторы отдельных членов как переменные. Имена членов должны быть уникальными в пределах области видимости; кроме того, никакие другие переменные безымянного типа объявлять нельзя. Безымянное объединение, объявленное в области видимости файла, должно быть статическим (static).
Усовершенствуем стек, переделав его в виде объединения различных типов. Суть в том, что стек является структурой данных, полезной для хранения значений любых типов. Такой стек можно использовать для обработки разнородных значений , применяя метод LIFO:
Enum type { int_type, dbl_type, chr_type, str_type };
Union rainbow {
Int i;
Double x;
Char c;
Char* p;
};
struct rbdata {
type t;
rainbow d;
};
struct u_stack {
rbdata s[max_len];
int top;
};
Структура данных u_stack более гибкая, за что приходится расплачиваться дополнительной памятью, которая требуется для хранения переменной t типа type для каждого из элементов. Операции стека кодируются так же, как в ch_stack. Например, push():
Void push(u_stack* stk, str[i++] )
{
stk -> s[++stk -> top = c;
}
При использовании u_stack член t отслеживает, значение какого типа содержится в каждом элементе стека.
Дата добавления: 2020-12-12; просмотров: 120; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!