Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

Цель работы: исследовать и изучить списковые структуры данных, научиться писать программы по исследованию списковых структур на языке программирования.
Краткие теоретические сведения
Статические программные объекты – это объекты, которые порождаются непосредственно перед выполнением программы, существуют в течение всего времени ее выполнения и размер значений которых не изменяется по ходу выполнения программы.
Программные объекты, которые создаются в процессе выполнения программы, называют динамическими объектами.
Для работы с динамическими объектами предусматривается специальный тип данных – так называемый ссылочный тип. Значением этого типа является ссылка на какой – либо программный объект, по которой осуществляется непосредственный доступ к этому объекту. Для описания действий над динамическими объектами каждому такому объекту в программе сопоставляется статическая переменная ссылочного типа – в терминах этих ссылочных переменных и описываются действия над соответствующими динамическими объектами.
Чтобы связать элементы динамической структуры между собой, в состав элемента помимо информационного поля входят поля указателей (связок с другими элементами структуры) .

p1, p2 – указатели, содержащие адреса элементов, с которыми данный элемент связан.
Наиболее распространенными динамическими структурами являются связанные списки. С точки зрения логического представления различают линейные и нелинейные списки. В линейных списках связи строго упорядочены. Указатель предыдущего элемента дает адрес последующего элемента или наоборот.
К линейным спискам относятся односвязные и двусвязные списки.
К нелинейным – многосвязные списки.
Элемент списка в общем случае представляет собой комбинацию поля записи (информационного поля) и одного или нескольких указателей.

Под односвязными списками понимают упорядоченную последовательность элементов, каждый из которых имеет 2 поля: информационное поле info и поле указателя ptr .
Особенностью указателя является то, что он дает только адрес последующего элемента списка. У однонаправленных списков поле указателя последнего элемента в списке является пустым null.
Lst – указатель начала списка. Он представляет список как единое целое. Иногда список может быть пустым, т.е. в данном списке нет ни одного элемента. В этом случае lst = null.

Порядок выполнения работы
1. изучить краткие теоретические сведения;
2. по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
3. написать программу на языке С++(два варианта: с использованием STL, без использования STL);
4. отладить программу;
5. оформить отчет (в отчете должны быть: тема, цель работы, задание, листинг программы, тестовый пример, результаты работы программы.
Задания
1. Написать программу передвижения элемента списка на n позиций.
2. Создать копию списка.
3. Добавить элемент в начало списка.
4. Склеить два списка.
5. Удалить n-ый элемент из списка.
6. Вставить элемент после n-го элемента списка.
7. Создать список содержащий элементы общие для двух списков.
8. Упорядочить элементы в списке по возрастанию.
9. Удалить каждый второй элемент списка.
10. Удалить каждый третий элемент списка.
11. Упорядочить элементы списка по убыванию.
Варианты заданий
1. Список растений
2. Список футбольных команд
3. Список продуктов питания
4. Список СУБД
5. Список инструментальных средств разработки ПО
6. Список языков программирования
7. Список пород собак
8. Список пород кошек
9. Список алгоритмов
10. Список группы