1.4. Задание на выполнение
Дано множество А, состоящее из n элементов. Значение n и значения элементов множества вводить с клавиатуры. Предусмотреть обработку не корректно введенных данных. Написать программу, выводящую на экран булеан множества А.
Использовать алгоритм генерации всех подмножеств.
Использовать алгоритм получения кода Грея.
Использовать реализацию кода Грея с помощью стека. Стек организовать в виде массива.
Использовать реализацию кода Грея с помощью стека. Стек организовать в виде линейного однонаправленного списка.
Практическое занятие № 2. «Представление множеств упорядоченными списками»
1.1. Цель работы
Программно реализовать представление множеств упорядоченными списками и основные операции над множествами.
1.2. Представление множеств упорядоченными списками
Если рассматриваемое множество не велико, то с точки зрения экономии памяти, множества достаточно часто представляются в виде списков элементов. Элемент списка в этом случае представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список описывается указателем на первый элемент.
Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на общем алгоритме типа слияния. Общая идея алгоритма типа слияния состоит в следующем: алгоритм параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение происходит в том множестве, в котором текущий элемент меньше.
1.3. Поверка включения слиянием
Даны проверяемые множества А и В, которые заданы указателями a и b.
Если A
B,
то функция возвращает 1, в противном
случае 0.
1. Pa = a; Pb = b;
2. Пока ( Pa != NULL and Pb != NULL)
2.1. Если (Pa.i<Pb.i ) // сравнение текущих информационных
// полей.
То вернуть 0 // элемент множества А отсутствует
//в множестве В
Иначе Если (Pa.i >Pb.i )
То Pb = Pb.n //перейти к следующему
// элементу в множестве В.
Иначе Pa:=Pa.n; Pb:=Pb.n // Выполнить переход
// в обоих множествах
3. Конец цикла
4. Если (Pa = NULL ) То вернуть 1 // на выходе 1, если достигнут
Иначе вернуть 0 // конец списка А.
5. Конец
1.4. Вычисление объединения слиянием
Даны объединяемые множества А и В, которые заданы указателями a и b.
1. Pa = a; Pb = b; c = NULL;
2. Пока (Pa != NULL and Pb!=NULL)
2.1. Если (Pa.i<Pb.i ) // сравнение информационных полей
// текущих элементов
То d = Pa.i; Pa = Pa.n // добавлению подлежит элемент
// множества А
Иначе Если ( Pa.i >Pb.i )
То d = Pb.i; Pb = Pb.n // добавлению подлежит
// элемент множества B
Иначе d = Pb.i ; Pa = Pa.n; Pb = Pb.n
// в этом случае Pa.i = Pb.i, можно взять любой
// элемент
2.2. Добавить d в конец списка с.
3. Конец цикла
4. Если (Pa != NULL)
То добавить в конец списка с оставшиеся элементы из А
5. Если (Pb != NULL)
То добавить в конец списка с оставшиеся элементы из B
6. Конец