Поразрядные операции. Реализация АТД «Множество»

Последний пример имеет несколько большие размеры и демонстрирует один из вариантов реализации абстрактного типа «Множество» (считаем, что основной набор операций, выполняемый над множествами, известен.). Имеются различные способы реализации данного абстрактного типа. Приведем реализацию множества из ограниченного количества элементов на основе битового массива (аналог типа set в Паскале). Как и в Паскале, ограничим множество 256 элементами (например, множество символов). Следовательно, битовый массив должен иметь размер 256 бит или 32 байта, поэтому будем использовать массив из 32 элементов размером 1 байт (используем тип unsigned char). Значение каждого бита равно 1, если соответствующий символ присутствует в множестве, и 0 – в противном случае.

Большинство языков программирования содержит набор поразрядных операций, т. е. операций, которые выполняются над каждым битом операндов по отдельности. Так, в языке С++ имеются операции поразрядного логического И (&), ИЛИ (|), НЕ (~) и поразрядные сдвиги содержимого ячейки памяти вправо (>>) или влево (<<) на один разряд. Эти операции выполняются очень быстро, поэтому желательно использовать их везде, где представляется такая возможность.

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

Допустим, нам надо установить в 1 третий бит (биты нумеруются справа налево, начиная с нуля), оставив все остальные биты в элементе неизменными. Для этого выполним над данным элементом поразрядную операцию ИЛИ с числом 8 (в двоичном представлении 00001000). Для установки этого же бита в 0 необходимо произвести поразрядную операцию И с двоичным числом 11110111, которое соответствует инверсии числа 8 (~8). Для того, чтобы посмотреть значение третьего бита, выполняем операцию И с числом 8.

Для доступа к другим битам вместо числа 8 используются другие степени двойки. Удобно записать эти значения в специальный массив, в приведенном листинге это массив mask.

#include <iostream.h>

typedef unsigned char CHAR; // этот тип включает значения от 0 до 255

const CHAR mask[8]={1,2,4,8,16,32,64,128};

struct set

{ CHAR data[32]; // массив из 32 байт или 256 бит

set();

void add(CHAR C); // добавляем символ C в множество

void addstr(CHAR *s); // добавляем символы строки s в множество

void del(CHAR C); // удаляляем символ C из множества

void delstr(CHAR *s); // удаляем символы строки s из множества

bool in(CHAR C); // возвращает true, если символ С есть во множестве

};

// реализация функций

set::set()

{ for (int i=0; i<32; i++) data[i]=0; // делаем множество пустым

}

void set::add(CHAR C)

{ CHAR n=C/8, k=C%8;

// устанавливаем в 1 k-й бит n-го элемента

data[n] = data[n] | mask[k];

}

void set::addstr(CHAR *s)

{ CHAR n,k;

for (int i=0; i<strlen(s); i++) add(s[i]);

}

void set::del(CHAR C)

{ CHAR n=C/8, k=C%8;

// устанавливаем в 0 k-й бит n-го элемента

data[n] = data[n] & (~mask[k]);

}

void set::delstr(CHAR *s)

{ CHAR n,k;

for (int i=0; i<strlen(s); i++) del(s[i]);

}

bool set::in(CHAR C)

{ CHAR n=C/8, k=C%8;

return (data[n] & mask[k]) > 0;

}

// внешние функции для работы с множествами

set join(set s1,set s2) // объединяем множества s1 и s2

{ set s;

for (int i=0; i<32; i++) s.data[i] = s1.data[i] | s2.data[i];

return s;

}

set intersect(set s1,set s2) // пересекаем множества s1 и s2

{ set s;

for (int i=0; i<32; i++) s.data[i] = s1.data[i] & s2.data[i];

return s;

}

set dif(set s1,set s2) // вычитаем s2 из s1

{ set s;

for (int i=0; i<32; i++) s.data[i] = s1.data[i] & (~s2.data[i]);

return s;

}

void print(set s) // выводим символы множества s на экран

{ CHAR c;

for(c=0; c<255; c++) if (s.in(c)) cout<<c;

c=255; if (s.in(c)) cout<<c; cout<<endl;

}

void main()

{ set s1,s2;

s1.addstr("abc"); s2.addstr("def"); s2.add('g');

s1=join(s1,s2); print(s1);

s2.delstr("ghij"); print(s2);

set s3=intersect(s1,s2); print(s3);

s1=dif(s1,s3); print(s1);

}

 

Линейные структуры данных

К линейным структурам данных относятся различные виды линейных списков.

Линейный список представляет собой такой способ организации совокупности элементов одного типа, при котором, каждый элемент, кроме первого, имеет одного предшественника (предыдущий элемент) и каждый элемент, кроме последнего, имеет одного преемника (следующий элемент). Если последний элемент имеет в качестве преемника первый элемент, а первый в качестве предшественника — последний, то такой список называют кольцевым (циклическим).

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

Далее будет рассмотрено два основных подхода к обработке линейных списков — итеративная обработка списка с выделенным текущим элементом и рекурсивная обработка списка. При изложении первого подхода отдельно рассмотрим однонаправленные и двунаправленные списки (Л1-списки и Л2-списки [12]), а также особенности кольцевых списков.

Изложение материала строится так. Сначала каждая структура рассматривается на логическом уровне как абстрактный тип данных. Затем рассматриваются различные способы реализации с небольшими фрагментами программного кода на С++. В заключение приводятся примеры программ, использующих данные структуры.

2.1. АТД "Стек", "Очередь", "Дек"