СТА: Лабораторная работа №1 - Динамические структуры данных и АТД

Версия 2.0, 22 сентября 2013г.

(С) 2012-2013, Зайченко Сергей Александрович, к.т.н, ХНУРЭ, доцент кафедры АПВТ

Правила выполнения лабораторной работы

1. Лабораторная работа выполняется либо бригадой из 2 человек, либо индивидуально. Если студент претендует на оценку “отлично”, работа должна выполняться полностью индивидуально.

2. В работе на выбор студента предлагаются варианты трех уровней сложности:

• Базовый уровень - оценка в интервале 15-20 баллов.
• Углубленный уровень - оценка в интервале 21-25 баллов.
• Амбициозный уровень - оценка не менее 25 баллов + бонусные баллы на усмотрение преподавателя.

3. Реализовывать задачи необходимо исключительно на языке программирования С++.

4. Работа оценивается не только по корректности функционирования решений задач, но и по культуре оформления исходного кода в читабельном виде, адекватности разбиения решения на модули и функции.

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

6. Защита работы:

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

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

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

Литература к лабораторной работе

1. Р. Седжвик “Алгоритмы на С++”:
• Глава 3 “Элементарные структуры данных”
• Глава 4 “Абстрактные типы данных”
2. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн “Алгоритмы. Построение и анализ”, 2 издание:
• Глава 10 “Элементарные структуры данных” (подразделы 10.1-10.3)
3. А. Ахо, Д. Хопкрофт, Д. Ульман “Структуры данных и алгоритмы”:
• Глава 2 “Основные абстрактные типы данных” (подразделы 2.1-2.4)
4. Д. Кнут “Искусство программирования”:
• Том 1, глава 2, раздел 2.2 “Линейные списки”

Исходные данные

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

1. Реализация вектора целых чисел (integer_vector.hpp, integer_vector.cpp).
2. Реализация односвязного списка целых чисел (integer_list.hpp, integer_list.cpp).
3. Реализации стека целых чисел (integer_stack.hpp, integer_stack_vector_impl.cpp, integer_stack_list_impl.cpp, integer_stack_array_impl.cpp).
4. Реализации очереди целых чисел (integer_queue.hpp, integer_queue_list_impl.cpp, integer_queue_cyclic_array_impl.cpp).

Эти реализации можно использовать непосредственно как готовую библиотеку, либо использовать как начальную точку для собственного решения.

Выдавать данные файлы за собственные решения настоятельно не рекомендуется :)

Решения на основе примитивных массивов и других идеях, не относящиеся к динамическим структурам данных, не будут засчитаны.

Варианты базового уровня

Вариант №1.

1. Пользователь вводит в программу через консоль последовательность положительных целых чисел, завершая ввод нулем либо отрицательным числом. Затем пользователь вводит неотрицательное число, означающее позицию P в последовательности. Программа выводит на отдельных строках, во-первых, все числа меньшие либо равные числу в позиции P, во-вторых все числа большие P. Порядок выводимых чисел должен соответствовать изначальному порядку ввода. Если позиции P не существует, программа выводит соответствующее сообщение об ошибке.

Пример ввода:

4 2 3 7 5 1 8 9 6 0 <Enter >

4 <Enter>

Пример вывода:

4 2 3 5 1

7 8 9 6

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

Вариант №2:

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

Пример ввода:

1 2 5 6 7 1 2 3 4 8 9 10 11 0 <Enter>

Пример вывода:

5 6 7

1 2 3 4

8 9 10 11

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

Вариант №3:

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

Пример ввода:

1 2 3 4 5 6 7 8 9 0 <Enter>

4 3 <Enter>

Пример вывода:

1 2 3 4 8 9

2. Опираясь на готовую реализацию односвязного списка целых чисел из лекционного материала (integer_list.hpp, integer_list.cpp), разработайте аналогичную реализацию и тестовую программу, реализующую двусвязный список со всеми операциями.

Вариант №4:

1. Пользователь вводит в программу через консоль последовательность положительных целых чисел, завершая ввод нулем либо отрицательным числом. Затем пользователь в цикле вводит некоторые числа, означающие позиции P. Программа на каждое введенное число выводит значение из введенной в начале последовательности, соответствующее позиции P. Если позиция не существует, программа печатает сообщение об ошибке и продолжает работу. Программа завершается вводом Ctrl+Z.

Пример ввода:

1 2 3 4 5 6 7 8 9 0 <Enter>

5 7 2 <Ctrl+Z> <Enter>

Пример вывода:

6 8 3

2. Реализуйте АТД “очередь” на основе односвязных списков для элементов, являющихся экземплярами следующей структуры:

structPoint3D

{

floatm_x, m_y, m_z;

};

Вариант №5:

1. Пользователь вводит в программу через консоль последовательность чисел. Каждое число начинается с новой строки. Если число положительное, оно заносится в память. Если число отрицательное - последнее введенное число удаляется из памяти. Если удалять нечего, выводится сообщение об ошибке и продолжается ввод. Если число равно 0, последовательность завершается. После каждой операции ввода программа выводит на экран текущее содержимое накопленной последовательности через пробел на отдельной строке.

Пример ввода:

1 <Enter>

2 <Enter>

3 <Enter>

-1 <Enter>

0 <Enter>

Пример вывода:

1 2

1 2 3

1 2

2. Реализуйте АТД “очередь” на основе циклических массивов для элементов, представляющих собой массивы действительных чисел double, передаваемые в виде пары аргументов - указатель на начало массива + количество элементов. В очередь могут быть помещены массивы разной длины. Копировать массивы не требуется, можно рассчитывать на то, что внешняя среда не будет уничтожать блоки, в которых хранятся массивы, до их выхода из очереди.

Вариант №6:

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

Пример ввода:

1 2 3 4 5 6 7 8 9 0 <Enter>

4 <Enter>

Пример вывода:

9 8 7 6 5 1 2 3 4

2. Реализуйте АТД “стек” на основе векторов для элементов - комплексных чисел:

structComplex

{

floatm_real, m_imaginary;

};

Вариант №7:

1. Пользователь вводит в программу через консоль последовательность целых чисел. Каждое число начинается с новой строки. Если число положительное, оно заносится в память. Если вводится число -1, программа выводит на экран текущее состояние вводимой последовательности. Если вводится число -2, программа удаляет из памяти наиболее раннее из введенных чисел, сохранившихся в памяти. Если удалять нечего, программа выводит сообщение об ошибке и продолжает ввод. Ввод числа 0 означает конец ввода последовательности и выход из программы.

Пример ввода:

1 <Enter>

2 <Enter>

3 <Enter>

-1 <Enter>

-2 <Enter>

-1 <Enter>

0 <Enter>

Пример вывода:

1 2 3

2 3

2. Реализуйте АТД “очередь” на основе односвязного списка для элементов, являющихся векторами целых чисел ( т.е., очередь векторов ).

Вариант №8:

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

Пример ввода:

1 2 3 4 5 0<Enter>

2 <Enter>

6 7 8 0 <Enter>

Пример вывода:

1 2 6 7 8 3 4 5

2. Реализуйте АТД “стек” на основе массива фиксированного размера для элементов, являющихся односвязными списками целых чисел ( т.е., стек списков )

Вариант №9:

1. Пользователь вводит в программу через консоль последовательность целых чисел произвольной длины, заканчивая ввод нажатием комбинации клавиш Ctrl+Z. После того как в программу введено 5 чисел, на каждое новое вводимое число программа выводит элементы введенной последовательности с самого начала по одному с сохранением изначального порядка.

Пример ввода:

1 <Enter>

2 <Enter>

3 <Enter>

4 <Enter>

5 <Enter>

6 <Enter>

7 <Enter>

8 <Enter>

9 <Enter>

<Ctrl+Z> <Enter>

Пример вывода:

1 // после ввода числа 6

2. Внесите дополнительные усовершенствования в реализацию вектора целых чисел:

• предоставьте функцию для резервирования места в векторе под будущие элементы, чтобы избежать лишних аллокаций:
  
  voidIntegerVectorReserve ( IntegerVector & _v, int_nCells );

• предоставьте функцию для уменьшения размера выделенного блока до размера, необходимого для хранения уже внесенных значений:
  
  voidIntegerVectorShrinkToFit ( IntegerVector & _v );

• предоставьте функцию, которая возвращает число ячеек имеющихся в наличии для вставки до следующего роста вектора:
  
  intIntegerVectorRemainingCapacity ( constIntegerVector & _v );

Продемонстрируйте работоспособность решения при помощи тестовой программы.

Вариант №10:

1. Пользователь вводит в программу через консоль последовательность положительных целых чисел, завершая ввод нулем либо отрицательным числом. Затем пользователь вводит число X. Если число X больше либо равно текущему первому элементу последовательности в памяти, ничего не происходит. Если же число X меньше, первый элемент последовательности удаляется из памяти. Независимо от значения X, программа выводит текущее состояние хранимой последовательности на каждом шаге. Процесс ввода числа X и возможного изменения последовательности повторяется до тех пор, пока последовательность в памяти не окажется пустой.

Пример ввода:

1 2 3 4 5 0 <Enter>

5 <Enter>

0 <Enter>

1 <Enter>

0 <Enter>

1 <Enter>

0 <Enter>

Пример вывода:

1 2 3 4 5

2 3 4 5

3 4 5

4 5

2. Дополните реализацию односвязных списков следующими операциями:

• Операция подсчета суммы элементов:

intIntegerListAccumulate ( constIntegerList & _list );

• Операция проверки является ли список упорядоченным по возрастанию:

boolIntegerListIsSorted ( constIntegerList & _list );

• Операция разделения списка на два списка по указанному элементу (все элементы левее не включая указанный попадают в первый список, разделяющий элемент и все последующие за ним - во второй список):

voidIntegerListSplice ( IntegerList & _sourceList,

IntegerList::Node * _pSplitNode,

IntegerList & _targetList1,

IntegerList & _targetList2 );

Варианты углубленного уровня

Вариант №11:

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

Вариант №12:

В дисковом файле, путь к которому передается первым аргументом командной строки, содержатся записи о людях по 1 строке на человека в следующем формате:

<фамилия> <возраст>

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

Вариант №13:

В дисковом файле, путь к которому передается первым аргументом командой строки, содержатся строки с произвольным текстом. Напишите программу, которая читает строки из указанного файла и в конце выводит последовательность самых длинных строк, в порядке их появления в файле. Пояснение:

• пусть очередная строка, извлеченная из файла, содержит N символов, и все предыдущие строки содержали менее N-символов
• если среди следующих строк не найдется таких, длина которых равна или больше N, то в конце программы выдастся данная единственная строка
• если среди следующих строк найдутся такие, длина которых равна N, однако строк с длиной больше N не найдется, в конце программы выдадутся все строки, имеющие длину N
• если среди следующих строк найдется строка, длина которой M, при чем M > N, следует взять в качестве нового N значение M и применить аналогичные критерии ко всем остальным строкам в файле

Вариант №14:

В двух дисковых файлах, пути к котором передается первым и вторым аргументами командной строки соответственно, содержатся записи о перечислениях на банковские счета, по одной записи на строку в текстовом формате:

<НОМЕР_ИЗ_ЦИФР> <СУММА_ДЕЙСТВИТЕЛЬНОЕ_ЧИСЛО>

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

Варианты амбициозного уровня

Вариант №15:

Реализуйте АТД “дек” (очередь с двумя концами) на основе сегментированного массива - несколько блоков фиксированной длины, хранящие данные, и служебный блок-директория, содержащий указатели на блоки данных. Обработайте все возможные ошибки.

Сегментированный массив моделируется следующим образом:

structIntegerDeque

{

// Количество ячеек в массиве-директории

intm_directorySize;

// Количество ячеек в каждом блоке данных

intm_blockSize;

// Массив-директория: указатели на блоки данных

int** m_pDirectory;

// Индексы верхней и нижней позиции из занятых ячеек в директории

intm_frontBlockIndex, m_backBlockIndex;

// Количество занятых элементов в первом и последнем блоках

intm_frontUsed, m_backUsed;

};

Графически данную структуру можно изобразить следующим образом:

Должны поддерживаться следующие операции:

• CLEAR ( DEQUE )
• IS_EMPTY( DEQUE ) : bool
• PUSH_FRONT( DEQUE, VALUE )
• POP_FRONT( DEQUE )
• FRONT ( DEQUE ) : VALUE
• PUSH_BACK ( DEQUE, VALUE )
• POP_BACK( DEQUE )
• BACK ( DEQUE ) : VALUE

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

Вариант №16:

Имеется стандартная колода карт для игры “пьяница” (4 масти - пики, трефы, бубны, черви - карты от 6 до туза). Программа должна создать двух виртуальных игроков и случайным образом распределить карты между ними. На каждом ходу игроки берут карту сверху колоды:

• если карта одного игрока больше карты другого по старшинству, тот, чья карта больше, забирает карту другого игрока, и кладет обе карты под низ своей колоды
• исключение - карта 6 считается старше карты ТУЗ
• если карты одинаковы по старшинству:
• от каждого игрока берется еще две карты
• независимо от соотношения первых дополнительных карт, сравниваются вторые дополнительные карты
• если одна из вторых дополнительных карт старше, обладающей ей игрок забирает все участвовавшие в розыгрыше карты и кладет под низ своей колоды
• если карты одинаковы по старшинству, процесс с двумя дополнительными картами продолжается
• игра завершается когда, один из игроков остается без карт либо сделано 5000 ходов

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

Контрольные вопросы

1. Основные виды памяти в программах. Особенности сегментов кода, данных, стека.
2. Динамическая память. Особенности работы. Утечки памяти. Фрагментация.
3. Динамически растущие массивы. Структура и основные операции.
4. Связные списки. Структура и основные операции.
5. Выбор между связными списками и векторами. Основные факторы.
6. Понятие “абстрактный тип данных” (АТД). Отличие от понятия “структура данных”.
7. АТД “последовательность”. Основные операции. Способы реализации.
8. АТД “стек”. Основные операции. Принцип реализации стеков фиксированного размера.
9. АТД “очередь”. Основные операции. Принцип реализации на основе связных списков.
10. АТД “очередь”. Принцип реализации на основе циклического массива.