Проблемы абстрактных типов данных

Модульное проектирование в совокупности с выделением абстрактных типов данных приводит к централизации реализации и управления над типом в модуле. Это приводит к более структурному коду основной программы.

Например, в программной системе требуется реализовать операции со стеком. То есть с абстрактной структурой типа «список» с ограничением доступа (включение и извлечение) только на одном конце. Иногда такую процедуру обслуживания называют LIFO (Last In First Out).

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

Две основные операции PUSH и POP (включить и извлечь) очевидно могут быть определены void Push_Stack(char Item) и void Pop_Stack(char *Item). Такое определение подчеркивает для программиста тот факт, что обе процедуры изменяют состояние стека.

Если процедуру извлечения определить как функцию char Pop_Stack(), то изменение стека (удаление из него верхнего элемента) скорее придется рассматривать как побочный эффект. То есть, кроме прямого результата — вычисления значения, функция производит еще что-то, возможно влияющее на ее глобальное окружение. С другой стороны, для вспомогательной функции просмотра элемента вершины стека форма char Check_Top() достаточно очевидна, т. к. изменение состояния стека при ее выполнении не происходит.

Дополнительно полезно определить пару функций проверки (вычисления) пред условий для операций со стеком. int Is_Stack_Empty() - функция проверки пустого стека и int Is_Stack_Full() - функция проверки полностью заполненного стека.

Is_Stack_Empty() является средством проверки возможности извлечь элемент из стека или обратиться к его верхнему элементу. Истинность этой функции запрещает применение операций Check_Top и Pop_Stack. В свою очередь, истинность функции Is_Stack_Full не разрешает применять операцию включения Push_Stack.

Проводя анализ введенных пяти операций нашего абстрактного типа можно сделать вывод, что мы имеет операции конструкторы: Push_Stack, Pop_Stack, которые можно рассматривать одновременно и как селекторы. «Чистый» селектор Check_Top. Но и его можно еще рассматривать как преобразователь типа «стек» в «символ», что будет не совсем верно, т. к. сам стек не является в явном виде параметром операции. Кроме того, имеются типичные операции проверки Is_Stack_Empty и Is_Stack_Full.

Чего же у нас нет? Нет операций ввода-вывода — они реализуются с элементами стека стандартными средствами обработки символьных значений. И, главное, нет начального конструктора, который задал бы исходное состояние пустого стека. Нет и операций копирования.

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

В итоге наших рассуждений h-файл для модуля Char_Stack (char_stack.h) выглядит так:

void Push_Stack(char Item);

/*====================================================

Операция записи символа в стек.

Предусловие Is_Stack_Full() == 0

Если предусловие нарушено,

состояние стека не изменяется.

=====================================================*/

void Pop_Stack(char *Item);

/*====================================================

Операция извлечения символа из стека.

Предусловие Is_Stack_Emty() == 0

Если предусловие нарушено,

состояние параметра не изменяется.

=====================================================*/

char Pop_Stack();

/*====================================================

Операция проверки символа, находящегося в вершине стека.

Предусловие Is_Stack_Emty() == 0

Если предусловие нарушено,

возвращается символ с кодом '/0'.

=====================================================*/

int Is_Stack_Empty();

/*====================================================

Операция проверки пустого стека.

Is_Stack_Emty() == 1 если в стеке нет ни одного элемента.

=====================================================*/

int Is_Stack_Full();

/*====================================================

Операция проверки пустого стека.

Is_Stack_Full() == 1 если стек заполнен полностью.

=====================================================*/

Программный код самого модуля char_stack.c может выглядеть следующим образом:

#include ”char_stack.h”

define MAX_ITEM_NUMBER 20

char Stack[MAX_ITEM_NUMBER];

int Top = 0; /* Изначально стек пуст */

void Push_Stack(char Item);

/*====================================================

Операция записи символа в стек.

=====================================================*/

{

if (Is_Stack_Full() == 0) /* Если стек не полон */

{ /* Включить элемент в стек */

Stack[Top++] = Item;

}

}

void Pop_Stack(char *Item);

/*====================================================

Операция извлечения символа из стека.

=====================================================*/

{

if (Is_Stack_Emty() == 0) /* Если стек не пуст */

{ /* Извлечь элемент из стека */

Item* = Stack[--Top];

}

}

char Pop_Stack();

/*====================================================

Операция копирования вершины стека.

=====================================================*/

{

if (Is_Stack_Emty() == 0) /* Если стек не пуст */

{ /* Копировать вершину стека */

return(Stack[Top - 1]);

}

else /* Если стек пуст */

{ /* Вернуть символ с нулевым кодом */

return('/0');

}

}

int Is_Stack_Empty();

/*====================================================

Операция проверки пустого стека.

=====================================================*/

{

return (Top == 0);

}

int Is_Stack_Full();

/*====================================================

Операция проверки пустого стека.

=====================================================*/

{

return (Top == MAX_ITEM_NUMBER);

}

Приведенный пример кода выглядит более понятным, нежели реализация стека прямо по ходу программы. Обратим внимание на ряд деталей.

Наличие определений функций предусловий в заголовочном файле, который мы включили в модуль обеспечивает не только согласованность типов параметров, но и возможность обращения к функциям проверки предусловий Is_Stack_Emty() и Is_Stack_Full() до их объявления в модуле.

Определение размера стека через константу MAX_ITEM_NUMBER позволяет упростить при необходимости изменение его размера. А применение операций Top++ при записи в стек и -—Top при извлечении верхнего элемента обеспечивает компактность записи без потери наглядности.

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

Рассмотренный выше тип «стек» представлял собой статический тип данных. Он был единственным и представлялся самим модулем Char_Stack. Мы не могли с его помощью создать еще один стек, например, для хранения операндов выражения. Способом реализации типа «стек» с более гибкой структурой может быть стек, реализованный на списке с указателями.

Создание стека — создание указателя на его головной элемент. Пустой стек — указатель со значением NILL. Включение нового элемента — создание структуры: значение, указатель на следующий; копирование включаемого значения в созданный элемент и подключение нового элемента в качестве вершины стека.

Что является отличительной чертой такого способа реализации АТД?

1. Тип объявляется в модуле — импортере как указатель (как правило на структуру).

2. Память переменной АТД (указателя) распределена в модуле - импортере.

3. Начальное состояние переменной АТД никак не определено. Обязательно нужен начальный конструктор. До его применения невозможно определение предусловий.

4. Как правило, размещение новых значений в подобном АТД связано с обращением к модулю управления динамической памятью, что с одной стороны увеличивает гибкость, снимая статические ограничения на размер структуры, но, с другой стороны, создает опасность динамического выхода за границы допустимой памяти.

Заметим, конкретно для стека возможна и смешанная стратегия реализации. Суть ее в том, что при создании стека отводится память сразу подо все его будущие элементы. Так сказать, по максимуму. Это приводит к его первичной инициализации (состояние «пустой») и дает возможность легко следить за переполнением (мы знаем и храним максимально возможное количество элементов).

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

Объявив в коде две переменных Stack_1 и Stack_2 типа стек, пользователь может забыть создать переменную Stack_2. При компиляции эта ошибка не будет обнаружена. Аналогичная ситуация складывается для операций удаления переменных абстрактного типа потому, что если абстрактный тип использует динамическую память, то автоматический «сборщик мусора» не сможет освободить выделенную память, за пользователя, который сам не сделал это явно (например, забыл удалить s1).

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

Еще одним неудобством становится необходимость практически всегда реализовывать операции сравнения и копирования для АТД и в пользовательской программе использовать только их. При этом наглядность таких действий несколько снижается – следующая строка:

А=В;

выглядит понятнее чем:

fraction_copy(A,B);

Рассмотрим еще один пример – реализации и использования абстрактного типа данных множество. В некоторых языках программирования, например Modula-2, множество является стандартным типом данных, но в Си такой тип отсутствует. Для примера рассмотрим множество символов расширенной таблицы ASCII, т.е. элементами множества могут быть любые символы char. Для хранения такого множества можно использовать массив с длиной равной количеству всех значений char, т.е. 256 элементов. Для символов, принадлежащих конкретному множеству, значение элемента с номером, соответствующем ASCII коду символа, устанавливается в 1. Остальные элементы массива равны нулю.

Такое представление множества в памяти избыточно. Для указания наличия или отсутствия элемента во множестве достаточно лишь двух значений – да/нет (т.е. 1 бита), но такого типа в Си нет. Упаковывать отдельные биты в Можно использовать boolean, но он занимает как минимум 1 байт, а в некоторых случаях при выравнивании может занимать и больше. В примере использован тип int, что еще более расточительно, но во-первых, тип boolean не существовал в ранних версиях Си, а во-вторых, использование целочисленного значения впоследствии позволит усовершенствовать рассматриваемый тип множество (например, допустить тристабильную логику – элемент есть/нет/не известно).

Перед использованием множества следует обнулить массив, чтобы получить пустое множество. Далее путем добавления нужных элементов можно получить требуемое множество.

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

Основные операции над множеством – это добавление элемента, проверка наличия элемента, объединение, вычитание и пересечение множеств. Отсюда можно сформировать set.h файл с определением типа и заголовками операций.

----- файл set.h -----

/*

date: 10 May 2011

description: Set type

*/

/* Definition of the Set type */

typedef struct {

int elems[255];

} Set;

/**********************************************************************

*

* Name: initSet

*

* Purpose: prepares the Set to work with

* (should be called before using Set variable)

* Input: s – new set

* Output: s – set prepared to work with

* Return: none

*

********************************************************************/

void initSet(Set *s);

/**********************************************************************

*

* Name: initFromStringSet

*

* Purpose: prepares the Set to work with

* (can be called instead of initSet(…))

* Input: s – new set,

* str – string with elements to add to the set

* Output: s – set prepared to work with,

* containing elements from string str

* Return: none

*

********************************************************************/

void initFromStringSet(Set *s, char *str)

/**********************************************************************

*

* Name: addElemSet

*

* Purpose: adds the element to the set

* (if element already exists – does nothing)

* Input: s – set, elem – element to add

* Output: s – set with added element

* Return: none

*

********************************************************************/

void addElemSet(Set *s, char elem);

/**********************************************************************

*

* Name: removeElemSet

*

* Purpose: removes the element from the set

* (if element already exists – does nothing)

* Input: s – set, elem – element to delete

* Output: s – set with no element elem

* Return: none

*

********************************************************************/

void removeElemSet(Set *s, char elem);

/**********************************************************************

*

* Name: isInSet

*

* Purpose: check whether the element is in the set

* Input: s – set

* Output: none

* Return:

* -1 is in set

* 0 is not in set

*

********************************************************************/

int isInSet(Set s, char elem);

/**********************************************************************

*

* Name: unionSet

*

* Purpose: unions two sets

* Input: s1 – set one, s2 – set two

* Output: s1 – union result

* Return: none

*

********************************************************************/

void unionSet(Set *s1, Set s2);

// deducts set s2 from set s1

// input: s1 – set one, s2 – set two

// output: s1 – deduct result

void substrSet(Set *s1, Set s2);

/**********************************************************************

*

* Name: intersectSet

*

* Purpose: intersects two sets

* Input: s1 – set one, s2 – set two

* Output: s1 – intersection result

* Return: none

*

********************************************************************/

void intersectSet(Set *s1, Set s2);

/**********************************************************************

*

* Name: isEqualSet

*

* Purpose: compares two sets

* Input: s1 – set one, s2 – set two

* Output: none

* Return:

* 1 sets are equal

* 0 not equal

*

********************************************************************/

int isEqualSet(Set s1, Set s2);

/**********************************************************************

*

* Name: copySet

*

* Purpose: copies set s1 to set s2

* Input: s1 – set one, s2 – set two

* Output: s1 – copy of s2

* Return: none

*

********************************************************************/

void copySet(Set *s1, Set s2);

/**********************************************************************

*

* Name: isEmptySet

*

* Purpose: check whether the set is empty

* Input: s1 – set one, s2 – set two

* Output: none

* Return:

* 1 set is empty

* 0 not empty

*

********************************************************************/

int isEmptySet(Set s);

/**********************************************************************

*

* Name: printSet

*

* Purpose: prints set

* Input: s1 – set to print

* Output: prints set on th screen (standard output)

* Return: none

*

********************************************************************/

void printSet(Set s);

----- файл set.c -----

//

// author: O.

// date: 10 May 2011

// description: Set type

//

#include "set.h"

#include <stdio.h>

void initSet(Set *s) {

int i;

for (i = 0; i < 255; i++) {

(*s).elems[i] = 0;

}

}

void initFromStringSet(Set *s, char *str) {

int i;

while(*str!= '\0') {

i = (int)*str;

(*s).elems[i] = 1;

str++;

}

}

void addElemSet(Set *s, char elem) {

int i;

i = (int)elem;

(*s).elems[i] = 1;

}

void removeElemSet(Set *s, char elem) {

int i;

i = (int)elem;

(*s).elems[i] = 0;

}

int isInSet(Set s, char elem) {

int i;

i = (int)elem;

if (s.elems[i] == 1) {

return 1;

} else {

return 0;

}

}

void unionSet(Set *s1, Set s2) {

int i;

for (i=0; i < 255; i++) {

(*s1).elems[i] = ((*s1).elems[i] | s2.elems[i]);

}

}

void substrSet(Set *s1, Set s2) {

int i;

for (i=0; i < 255; i++) {

(*s1).elems[i] = ((*s1).elems[i] - s2.elems[i]);

if ((*s1).elems[i] < 0) {

(*s1).elems[i] = 0;

}

}

}

void intersectSet(Set *s1, Set s2) {

int i;

for (i=0; i < 255; i++) {

(*s1).elems[i] = ((*s1).elems[i] & s2.elems[i]);

}

}

int isEqualSet(Set s1, Set s2) {

int i;

for (i=0; i < 255; i++) {

if (s1.elems[i]!= s2.elems[i]){

return 0;

}

}

return 1;

}

void copySet(Set *s1, Set s2) {

int i;

for (i=0; i < 255; i++) {

(*s1).elems[i] = s2.elems[i];

}

}

int isEmptySet(Set s) {

int i;

for (i=0; i < 255; i++) {

if (s.elems[i] == 1){

return 0;

}

}

return 1;

}

void printSet(Set s){

int i;

for (i=0; i < 255; i++) {

if (s.elems[i] == 1){

printf("%c",(char)i);

}

}

}

Пример использования множества показан далее. Он будет помещен в отдельный файл «setexample.c», в который будет импортироваться реализованный тип данных путем включения заголовочного файла «set.h».

----- файл setexample.c -----

/*

date: 10 May 2011

description: Set type

*/

#include <stdio.h>

#include "set.h"

int main() {

Set s1, s2;

/* Do not forget to do it! */

initFromStringSet(&s1, "abcde");

initSet(&s2);

addElemSet(&s2,'a');

addElemSet(&s2,'b');

printf("\n s1: ");

printSet(s1);

printf("\n s2: ");

printSet(s2);

removeElemSet(&s1,'a');

printf("\n s1: ");

printSet(s1);

unionSet(&s1, s2);

printf("\n s1: ");

printSet(s1);

substrSet(&s1, s2);

printf("\n s1: ");

printSet(s1);

addElemSet(&s1,'a');

intersectSet(&s1, s2);

printf("\n s1: ");

printSet(s1);

return 0;

}

Из реализации данного относительного не сложного типа виден ряд правил, которые необходимо учитывать при разработке АТД.

Во-первых, это необходимость в импортере всегда использовать операцию создания, которая в примере реализована функцией initSet и функцией initFromStringSet. Т.к. массив в Си не инициализируется по умолчанию, то если в основной программе перед работой со множеством не вызвать initSet (или initFromStringSet) то во множестве могут оказаться «лишние» элементы. При этом компилятор сам не может отследить корректность использования функций создания. Это целиком задача программиста.

Во-вторых, необходимо самостоятельно реализовать функции копирования и сравнения.

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

Несмотря на то, что массивы эффективнее передавать по ссылке, чтобы не копировать большой объем информации в память стека при передаче параметров, в данном примере переменные типа Set передаются по ссылке только в те функции, где они должны быть изменены. Это уменьшает вероятность случайного изменения значения переменно типа Set в остальных функциях и позволяет отражать в самом заголовке функции – происходит ли внутри нее изменением множества или нет.

В качестве примера использования множества рассматривается задача проверки символов введенной строки на допустимость. Допустим, необходимо проверить, является ли введенная строка шестнадцатеричным числом. Тогда можно сказать, что допустимый алфавит (т.е. допустимое множество) – это символы «0123456789ABCDEF» и все символы строки должны принадлежать этому алфавиту (множеству).

/* sample code - how Set can be used */

Set s3;

char str[100];

int i;

initFromStringSet(&s3,"0123456789ABCDEF");

printf("\nEnter HEX number: ");

scanf("%s", str);

i = 0;

while(str[i]!= '\0') {

if (isInSet(s3, str[i]) == 0) {

printf("You entered not a HEX number!");

break;

}

i++;

}

Дата добавления: 2014-12-26