Вопрос 2.2. Структура хранения множества.

Множество - набор элементов

• Для множества определены операции:

- проверка наличия элемента

- добавление элемента

- удаление элемента

• Теоретико-множественные операции

-объединение

- пересечение

- вычитание

Универс U - множество всех элементов

Конкретизация (допущения и ограничения)

• элементы множества проиндексированы (каждому элементу соответствует уникальный индекс)

• множество индексов элементов составляют непрерывный диапазон целых значений

Тогда любое множество A(включенное)U может быть

описано характеристическим вектором

Нумерация бит в битовой строке - слева направо

Нумерация элементов в массиве - слева направо,

биты элемента - справа налево

Байты двухбайтового элемента располагаются в ОП в обратном порядке (сначала байт с младшими битами, затем байт со старшими битами) - поддержка отображения на аппаратном уровне

При реализации целесообразно выделить базовый класс TBitField, обеспечивающий представление битовых строк

-последовательность разработки

-создание стандартного класса

class TBitField { private:

int BitLen; // длина битового поля - макс, к-во битов TELEM *рМет; // память для представления битового поля int MemLen; // к-во эл-тов Мем для представления бит.поля // методы реализации

int GetMemlndex (const int n) const; // индекс Мем для бита n (#02) TELEM GetMemMask (const int n) const; // битовая маска для бита n (#03) public:

TBitField(int len); // (#01)

TBitField(const TBitField &bf); // (#П1) -TBitField(); // (#C)

// доступ к битам

int GetLength (void) const; // получить длину (к-во битов) (#0)

void SetBit (const int n); // установить бит (#04)

void ClrBit (const int n); // очистить бит (#П2)

int GetBit (const int n) cons; // получить значение бита (#JI1) // битовые операции

int operator==(const TBitField &bf); // сравнение (#05)

TBitField & operator=(const TBitField &bf); // присваивание (#ПЗ) TBitField operator] (const TBitField sbf); // операцмя "или" (#06) TBitField operators (const TBitField &bf); // операцмя "и" (#Л2) TBitField operator- (void); // отрицание (#C)

friend istream Soperator»(istream &istr, TBitField &bf); // (#07)

friend ostream &operator<<(ostream Sostr, const TBitField &bf); // (#П4)

};

// Структура хранения битового поля

// бит.поле - набор битов с номерами от 0 до BitLen

// массив рМем рассматривается как последовательность MemLen элементов // биты в эл-тах рМем нумеруются справа налево (от младших к старшим) // 08 J12 П4 С2 #endif

class TSet { private:

int MaxPower; // максимальная мощность множества TBitField BitField; public:

TSet (int mp);

TSet(const TSet &s); // конструктор копирования

TSet(const TBitField &bf); // конструктор преобразования типа

operator TBitFieldO;

// доступ к битам

int GetMaxPower (void) const; // максимальная мощность множества

void InsElem (const int n); // включить элемент в множество

void DelElem (const int n); // удалить элемент из множества

int IsMember (const int n) const; // проверить наличие элемента в мн-е

// теоретико-множественные операции

int operator==(const TSet &s); // сравнение

TSet & operator=(const TSet &s); // присваивание

TSet operator+ (const int n); // включение элемента в множество

TSet operator- (const int n); // удаление элемента из множества

TSet operator+ (const TSet &s); // объединение

TSet operator* (const TSet &s); // пересечение

TSet operator- (void); // дополнение

friend istream ^operator»(istream &istr, TSet &bf);

friend ostream &operator«(ostream sostr, const TSet &bf);

};

#endif

Не нашли, что искали? Воспользуйтесь поиском: