книги / Программирование на языке Си
..pdf302 |
Программирование на языке Си |
Имитация абстрактных типов данных. При решении кон кретных прикладных задач бывает удобным выделить набор типов данных, наиболее полно соответствующих понятиям и объектам предметной области. Такие типы данных обычно от сутствуют в языке программирования, но их можно сконструи ровать и ввести как производные типы. Одновременно с такими специализированными данными (точнее, с производными типа ми для их представления) для каждого типа вводится набор операций, удобный для обработки этих данных. Тип данных и набор операций над объектами этого типа совместно определя ют абстрактный тип данных, ориентированный на представле ние понятий предметной области решаемой задачи. В языке Си программист имеет возможность вводить абстрактные типы данных с помощью структур, отображающих собственно дан ные, и функций, определяющих операции над данными.
В качестве примера введем абстрактный тип данных для ра циональных дробей. Выше в §6.1 введен и поименован с помо щью typedef как fraction структурный тип для представления рациональных дробей.
Определим функции, реализующие операции над рациональ ными дробями:
input() |
- |
ввод дроби; |
out() |
- |
вывод дроби на дисплей; |
add( ) |
- |
сложение; |
sub() |
- |
вычитание; |
m ult() |
- |
умножение; |
divide() |
- деление. |
|
Этот набор операций можно легко расширить, введя, напри мер, функции для приведения дробей к одному знаменателю, для сокращения дроби, для выделения целой части неправиль ной дроби и т.д. Но для демонстрации особенностей примене ния структур в функциях при определении абстрактного типа данных перечисленного набора операций вполне достаточно.
Оформим определение структурного типа "рациональная дробь" и набор прототипов перечисленных выше функций для операций над дробями в виде следующего файла:
Глава 6. Структуры и объединения |
|
|
303 |
||
/* Файл fract.h |
- абстрактный тип |
*/ |
|||
|
|
"рациональная дробь" |
|||
typedef struct rational_fraction |
|
|
|||
{ |
|
|
|
|
|
int numerator; /* Числитель */ |
|
|
|||
int denominator; /* Знаменатель */ |
|
типа */ |
|||
} fraction; /* |
Обозначение структурного |
||||
/* Прототипы функций для работы с дробями: |
*/ |
||||
void input (fraction * pd); |
|
|
|
||
void out |
(fraction dr); |
|
|
|
|
fraction add (fraction drl, fraction dr2); |
|||||
void sub |
(fraction drl, fraction dr2, |
|
|
||
fraction |
fraction * pdr); |
fraction |
dr2); |
||
* mult |
(fraction drl, |
||||
fraction |
divide |
(fraction *pdl, |
fraction |
*pd2); |
|
Обратите внимание, что применение typedef позволило уп ростить название структурного типа. Вместо конструкции struct rational fraction в прототипах функций и далее в программе ис пользуется более короткое обозначение fraction.
Определения функций, реализующих перечисленные опера ции над рациональными дробями, объединим в один файл сле дующего вида:
/*Файл fract.c - определения функций |
*/ |
||||
|
для работы |
с дробями |
|||
#include <stdio.h> |
/*' Для |
exit() |
и malloc() */ |
||
#include <stdlib.h> |
|||||
void |
input (fraction |
* pd) |
/* Ввод |
дроби |
*/ |
{ |
|
|
|
|
|
int N; |
|
|
|
|
|
printf("\n Числитель:"); |
|
|
|
||
scanf("%d", pd -> numerator); |
|
|
|||
printf("Знаменатель:"); |
|
|
|
||
scanf("%d", &N); |
|
|
|
|
|
if |
(N == 0) |
|
|
|
|
|
{ |
|
|
|
|
|
printf("\n Ошибка! Нулевой знаменатель!"); |
||||
|
exit (0); /* Завершение программы |
*/ |
|||
pd |
} |
|
|
|
|
-> denominator=N; |
|
|
|
||
>
304 |
Программирование на языке Си |
/* Изобразить дробь на экране: */ void out (fraction dr)
{
printf("Рациональная дробь:");
printf("%d/%d", dr.numerator, dr .denominator);
}
/* |
Сложение |
дробей: |
|
*/ |
|
fraction add |
(fraction drl, fraction dr2) |
||||
{ |
fraction dr; |
|
|
||
|
|
|
|||
|
dr.numerator = drl.numerator * dr2.denominator |
||||
|
|
|
+ drl.denominator * dr2.numerator; |
||
|
dr.denominator = drl.denominator * |
||||
|
return dr; |
|
dr2.denominator; |
||
> |
|
|
|
||
Вычитание |
дробей: |
|
|||
/* |
*/ |
||||
void |
sub (fraction drl, fraction dr2, |
||||
{ |
|
fraction |
* pdr) |
||
|
-> numerator=drl.numerator * dr2.numerator |
||||
pdr |
|||||
|
|
- dr2.numerator * drl.denominator; |
|||
|
pdr -> denominator=drl.denominator * |
||||
} |
|
dr2.denominator; |
|||
Умножение |
дробей: |
|
|||
/* |
*/ |
||||
fraction * mult (fraction drl, fraction dr2) |
|||||
{ |
fraction * mul; |
|
|
||
|
|
|
|||
|
mul=(fraction *) malloc (sizeof (fraction)); |
||||
|
mul |
-> numerator=drl.numerator * |
|||
|
mul |
|
|
dr2.numerator; |
|
|
-> denominator=drl.denominator * |
||||
|
return mul; |
|
dr2.denominator; |
||
) |
|
|
|||
|
|
|
|
|
|
/* |
Деление дробей: |
*/ |
|||
fraction divide (fraction * pdl, fraction * pd2)
{
fraction d;
d ,numerator = pdl ~> numerator * pd2 ->
Глава 6. Структуры и объединения |
305 |
denominator;
d.denominator = pdl -> denominator * pd2 -> numerator;
return d;
>
Приведенный набор функций демонстрирует все возможные сочетания возвращаемых значений и параметров функций при работе со структурами. Обратите внимание, что функции add(), divide() возвращают структуру типа fraction, которую нужно "разместить" в соответствующей структуре вызывающей про граммы. Функция sub() предусматривает передачу результата через параметр-указатель fraction * pdr. Функция mult() форми рует динамический объект типа fraction и возвращает его адрес. В основной программе после обращения к mult( ) корректно бу дет освободить динамическую память с помощью функции free().
Следующая программа демонстрирует работу с рациональ ными дробями с помощью введенных функций:
#include "fract.h" /* Файл прототипов */ |
|
||||||||
#include |
"fract.c" |
/* Файл определений |
функций */ |
||||||
void main |
( |
) |
|
|
|
|
|
|
|
{ |
|
|
b, |
|
Определили три |
|
|
||
fraction а |
/* |
*/ |
|
||||||
|
|
|
|
|
дроби-структуры |
|
|||
fraction *р; /* Указатель на дробь */ |
|
||||||||
printf("\n Введите дроби:"); |
|
|
|
||||||
input(&а); |
|
|
|
|
|
|
|||
input(&Ь); |
|
/* Сложение дробей */ |
|||||||
с = |
add(а, Ь); |
|
|||||||
out(с); |
|
|
/* Вывод дроби |
*/ |
*/ |
||||
р = mult(а, Ь); |
|
/* Умножение дробей |
|||||||
out(*р); |
|
|
/* Вывод дроби, |
адресуемой |
|||||
free(р); |
|
|
|
указателем |
*/ |
|
*/ |
||
|
|
/* |
Освободить |
память |
|||||
с = |
divide(&а, &Ь) |
/* |
Деление дробей */ |
|
|||||
out |
|[с) ; |
|
|
/* |
Вывод дроби |
*/ |
|
||
> |
|
|
|
|
|
|
|
|
|
20 -3 1 2 4
306 |
Программирование на языке Си |
Результаты выполнения программы:
Введите дроби: Числитель: 5 Знаменатель: 4 Числитель: 2 Знаменатель: 3
Рациональная дробь: 23/12 Рациональная дробь: 10/12 Рациональная дробь: 15/8
Обратите внимание на необходимость явного освобождения памяти после выполнения функции mult(), внутри тела которой для результата (для структуры типа fraction) явно выделяется память, и указатель на этот участок памяти передается в вызы вающую программу. После печати результата out(*p) библио течная функция free(p) освобождает память.
6.4. Д инам ические инф орм ационны е структуры
Статическое и динамическое представление данных. В языках программирования типы данных и определения пере менных (как объектов заданных типов) нужны для того, чтобы определить требования к памяти для каждого из этих объектов и фиксировать диапазон (пределы) значений, которые могут при нимать эти объекты (переменные). Для базовых типов (int, long, double и т.д.) требования к памяти и диапазоны возможных зна чений определяются реализацией языка (компилятора). Из базо вых типов формируются производные, такие, как массивы и структурные типы. Для производных типов требования к памяти заложены в их определениях. Таким образом, определив массив или структурный тип, программист зафиксировал требования jc памяти в самом определении. Например, на основании опреде ления double аггау[18] в памяти для массива йпгау[ ] будет выде лено не менее 18* sizeof (double) байт.
Глава 6. Структуры и объединения |
307 |
С помощью определения struct mixture
{
int ii; long 11;
char cc [8];
};
не только задается состав структурного типа с названием struct mixture, но и утверждается, что каждый объект структурного типа struct mixture потребует для размещения не менее
sizeof (int) + sizeof (long) + 8* sizeof (char)
байт. Точный объем позволяет определить операция sizeof (struct mixture).
Вводимые таким образом объекты позволяют представить только статические данные. Однако во многих задачах требует ся использовать более сложные данные, представление которых (конфигурация, размеры, состав) может изменяться в процессе выполнения программы. О таких изменяемых данных говорят, используя принятый в информатике термин "динамические ин формационные структуры ".
Односвязный список. Наиболее простая динамическая ин формационная структура - это односвязный список, элементами (звеньями) которого служат объекты, например, такого струк турного типа:
struct имя структурного типа
{
элементы структуры', /* данные */
struct имя структурного типа * указатель;
};
В каждую структуру такого типа входит указатель на объект того же типа, что и определяемая структура.
Чтобы продемонстрировать некоторые особенности обработ ки простых динамических информационных структур, разрабо-
20*
308 |
Программирование на языке Си |
таем программу, в которой определим структурный тип для представления звеньев односвязного списка и решим такую простейшую задачу: "Ввести с клавиатуры произвольное коли чество структур, объединяя их в односвязный список, а затем вывести на экран дисплея содержимое введенного списка в по рядке формирования его звеньев".
Анализ динамических информационных структур удобнее всего выполнять с помощью их графического изображения. На рис. 6.3 приведены схема односвязного списка и обозначения, которые будут использованы в программе. Для работы со спи ском понадобятся три указателя: beg - на начало списка; end - на последний элемент, уже включенный в список; гех - указа тель для "перебора" элементов списка от его начала .
Начало списка
beg ---------- ►! данные указатель
Т—
данные указатель I
гех ---------- ►
данные | указатель
__ х_
end- данные указатель
(последний элемент списка)
Рис. 6.3. Односвязный динамический список
Следующая программа решает сформулированную задачу.
#±nclude <stdlib.h> #include <stdio.h>
/* Определение структурного типа "Звено списка":*/ struct cell {
char sign [10]; int weight; struct cell * pc;
};
Глава 6. Структуры и объединения |
309 |
void main()
{
/* Указатель для перебора Звеньев списка: */ struct cell * rex;
struct cell * beg=NULL; /* Начало списка */ struct cell * end=NULL; /* Конец списка */ printf("\пВведите значения структур:\n"); /* Цикл ввода и формирования списка */
do
{ /* Выделить память для очередного эвена
|
списка: */ |
|
|
|
rex=(struct cell *)malloc( |
|
|
cell)); |
|
|
sizeof(struct |
|||
/* Ввести значения элементов Эвена: */ |
||||
printf("sign="); |
|
|
|
|
scanf("%s",S rex->sign); |
|
|
|
|
printf("weight="); |
|
|
|
|
scanf("%d",& rex->weight); |
|
|
|
|
if (rex->weight == 0) |
|
|
|
|
{ |
|
|
|
|
free(rex); |
ввода |
списка */ |
||
break; /* Выход из цикла |
||||
} |
|
*/ |
|
|
/* Включить эвено в список: |
Список пуст*/ |
|||
if (beg==NULL && end=NULli) /* |
||||
beg=rex; |
|
существующий |
||
else |
/* Включить звено в уже |
|||
|
список */ |
|
|
|
end->pc=rex; |
|
|
|
|
end=rex; end->pc=NULL;
>
while(1); /* Конец ввода списка */ /* Напечатать список */ printf("ХпСодержимое списка:"); rex=beg;
while (rex!=NULL)
{
printf("\nsign=%s\tweight=%d",rex->sign, rex->weight);
rex=rex->pc;
)
310 |
Программирование на языке Си |
Пример выполнения программы:
Введите данные о структурах: Sign=sigma
weight=16
Sign=omega
weight=44
Sign=alfa
weight=0
Содержимое списка: Sign=sigma weight=16 Sign=omega weight=44
Обратите внимание, что при вводе данных о третьем элемен те списка введено нулевое значение переменной weight и соот ветствующий элемент в список не включен.
В программе ввод данных, т.е. заполнение односвязного спи ска структур, выполняется в цикле. Условием окончания цикла служит нулевое значение, введенное для элемента int weight, очередной структуры.
Формирование списка структур происходит динамически. Указатели beg, end инициализированы нулевыми значениями - вначале список пуст.
Обратите внимание на преобразование типов (struct cell *) при выделении памяти для структуры типа struct cell. Функция malloc() независимо or типа параметров всегда возвращает ука затель типа void *, а слева от знака присваивания находится указатель гех типа struct cell *.
Используется явное приведение типов, хотя это не обяза тельно - тип void * совместим по операции присваивания с ука зателем на объект любого типа.
Остальные особенности программы поясняются коммента риями в ее тексте.
Рекурсия при обработке списка. Даже такая простая струк тура, как динамический односвязный список, представляет со бой конструкцию, которую удобно обрабатывать с помощью рекурсивных процедур. Рассмотрим ту же задачу об односвяз
Глава 6. Структуры и объединения |
311 |
ном списке, но оформим формирование списка и вывод списка на экран дисплея в виде рекурсивных функций. Сделаем это с целью показать на этом простом примере особенности рекур сивной обработки динамических информационных структур.
В каждом звене списка содержатся полезная информация (данные) и ссылка (адрес) на следующее звено списка. Если та кая ссылка нулевая, то список пройден до конца. Для начала просмотра списка нужно знать только адрес его первого эле мента.
Рассмотрим, какие действия должны выполнять функция ре курсивного формирования списка и функция его рекурсивного просмотра с выводом данных о звеньях списка на экран дис плея.
Функция рекурсивного заполнения списка ниже в программе имеет прототип:
struct cell * input (void);
Она возвращает указатель на сформированный и заполнен ный данными с клавиатуры динамический список. Предполага ется, что при каждом вызове этой функции формируется новый список. Функция заканчивает работу, если для очередного звена списка введено нулевое значение переменной weight. В против ном случае заполненная с клавиатуры структура подключается к списку, а ее элементу struct cell * рс присваивается значение, которое вернет функция input(), рекурсивно вызванная из тела функции. После этого функция возвращает адрес очередного звена списка, т.е. значение указателя struct cell * pc.
Прежде чем рассматривать текст функции input( ), помещен ный в приведенной ниже программе, еще раз сформулируем ис пользованные в ней конструктивные решения.
1.При каждом обращении к этой функции в основной памя ти формируется новый список, указатель на начало кото рого возвращает функция.
2.Выделение памяти для звеньев списка и заполнение значе ниями элементов звеньев (структур) зависит от тех значе ний, которые пользователь присваивает элементам.