Контрольная работа

Часть I – Статические структуры
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных (раздел 1 конспекта лекций) и области их эффективного использования, а также возможности языка С++ для создания и обработки статических структур.
2. Разработать программу с пользовательскими функциями для решения следующей задачи:

• в соответствии с индивидуальным вариантом (табл. 1) составить структуру данных, описывающую заданную предметную область;
• написать подпрограммы:
• добавления записи;
• вывода записей на экран;
• удаления записи, указанной ее порядковым номером;
• изменение данных записи, указанной ее порядковым номером;
• вывода на экран записей, удовлетворяющих некоторому критерию;
• в основной программе организовать простое текстовое меню, посредством которого реализовать обработку данных при помощи вызова подпрограмм.

3. Протестировать программу. Данные следует вводить псевдореальные (не бессмысленные).

Часть II – Дисциплина обслуживания
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить теоретический материал по программированию статических структур данных с заданной дисциплиной обслуживания (раздел 2 конспекта лекций) и области их эффективного использования, а также возможности языка С++ для создания и обработки структур с заданной дисциплиной обслуживания.
2. На базе структуры, разработанной при выполнении части I, реализовать обработку данных посредством заданной дисциплины обслуживания, выбранной согласно последней цифре пароля:

• нечетная цифра – LIFO (стек);
• четная цифра – FIFO (очередь);

3. Посредством пользовательских функций реализовать следующие операции:

• добавление новой записи (с проверкой на переполнение);
• извлечение записи (с исключением) и возвращение ее в основную программу для вывода на экран;
• определение числа хранимых записей;
• очистка структуры.

4. Провести тестирование реализованных функций.
5. Разработать пользовательскую функцию вывода на экран записей, удовлетворяющих заданному критерию, и протестировать ее выполнение. Функция должна вызывать функцию извлечения записи и осуществлять ее проверку на соответствие параметрам. При соответствии выводить запись на экран, иначе отбрасывать. В результате проведенного анализа структура должна оказаться пустой.

Часть III – Линейные односвязные списки
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить понятие линейного односвязного списка (раздел 3 конспекта лекций) и возможности языка программирования С++ для создания и обработки односвязных списков.
2. Разработать программу на языке С++ для решения следующей задачи:
В соответствии с индивидуальным вариантом задания (табл. 1) реализовать динамическую структуру данных, описывающую предметную область в виде линейного односвязного списка, и процедуры:

• добавления элемента в начало списка;
• добавления элемента в конец списка;
• удаления элемента из начала списка;
• удаления элемента из конца списка;
• удаления из списка элемента, указанного его порядковым номером;
• изменение данных элемента списка, указанного его порядковым номером;
• вывода элементов списка на экран.

3. Протестировать программу.

Часть IV – Двусвязные и кольцевые списки
1. На основе материалов конспекта лекций, рекомендуемой литературы и материалов сети Интернет изучить понятие двусвязного и кольцевого списка (раздел 4 конспекта лекций) и возможности языка программирования С++ для создания и обработки таких списков.
2. Выполнить преобразование кода, разработанного при выполнении задания части III, сделав список:

• нечетная цифра – однонаправленным кольцевым;
• четная цифра – двунаправленным кольцевым;

3. Предусмотреть такие процедуры работы со списком:

• добавления элемента в заданную позицию списка;
• изменение данных элемента списка в заданной позиции;
• удаления элемента из заданной позиции списка;
• вывода элементов списка на экран.

Таблица 1. Варианты заданных предметных областей (ХХ –2 последние цифры пароля)

Лабораторная работа №1

Тема: Линейные односвязные списки.
Цель: изучение и освоение использование структур и линейных списков.
Минимальный набор конструкций языка С++, необходимых для программирования односвязного списка:
// Статическая структура, описывающая узел списка
struct list{
int info;
list *next;
};
// Функция инициализации списка с 1 узлом и данными параметра а
list * init(int a){
list *lst = new list;
(*lst).info = a;
(*lst).next = NULL;
return lst;
}
// Функция вывода списка на консоль
void printlist(list * lst){
list * p = lst;
cout << "LIST:" << endl;
while (p != NULL)
{
cout << (*p).info << " ";
p = (*p).next;
}
cout << endl;
}
// Функция добавления элемента в список
list * additem(list * lst, int item){
if (lst == NULL)
lst = init(item);
else
{
list * tmp = lst;
while ((*tmp).next != NULL) tmp = (*tmp).next;
list * p = new list;
tmp->next = p;
p->info = item;
p->next = NULL;
}
return lst;
}
Задание:

1. На основе материалов конспекта лекций (раздел 3) и рекомендуемой литературы изучить теоретический материал по программированию односвязного списка.
2. Сформировать однонаправленный список целых чисел заданной (см. табл. 1) длины и вывести его на экран.
3. Рассчитать заданный (см. табл. 1) показатель на основе значений элементов списка и вывести значение показателя на экран.
4. Выполнить заданную (см. табл. 1) обработку списка и вывести обработанный список на экран.

Таблица 1 - Индивидуальные задания к лабораторной работе №1

Лабораторная работа №2

Тема: Двусвязные списки
Цель работы: изучить понятие и способы описания двусвязных списков и освоить их программную реализацию средствами языка С++.
Задание

1. На основе материалов конспекта лекций (раздел 3) и рекомендуемой литературы изучить теоретический материал по программированию двусвязного и кольцевого списка.
2. Составить программу на языке С++, в которой реализовать двусвязный список целых чисел. Предусмотреть операции добавления, изменения и удаления элемента в указанной позиции.
3. Сформировать список произвольных целых чисел (не менее 10 элементов) и вывести его на экран.
4. В соответствии с индивидуальным вариантом (табл. 2) обработать данные списка. При этом не использовать дополнительные списки или массивы. Обработанные данные вывести на экран.
5. Модифицировать программу для работы с кольцевым двусвязным списком и протестировать ее работу.
6. Сравнить реализации обоих списков и сделать выводы.

Таблица 2 - Индивидуальные задания к лабораторной работе №2

Лабораторная работа №3

Тема: Бинарные деревья
Цель работы: изучить понятие и способы описания бинарных деревьев и освоить их приемы программирования алгоритмов их обработки.
Задание

1. На основе материалов конспекта лекций (раздел 5) и рекомендуемой литературы изучить теоретический материал по программированию бинарных деревьев.
2. Сформировать дерево (деревья) двоичного поиска и вывести его (их) на экран.
3. Выполнить обработку данных на этом бинарном дереве (табл. 3, задание 1) и вывести обработанное дерево на экран.
4. На полученном бинарном дереве найти заданную характеристику (табл. 3, задание 2) и вывести ее на экран.

Таблица 3 - Индивидуальные задания к лабораторной работе №3