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

№

Содержание задания

1

Даны списки L1 и L2. Сформировать список L, включив в него по одному разу элементы, которые входят хотя бы в один из списков L1 и L2.

2

Даны списки L1 и L2. Сформировать список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.

3

Даны списки L1 и L2. Сформировать список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в L2.

4

Даны списки L1 и L2. Сформировать список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой.

5

Определить входит ли, элемент Е в список L.

6

Подсчитать число вхождений элемента Е в список L.

7

Найти максимальный элемент в непустом списке L.

8

Заменить в списке L все вхождения элемента Е1 на Е2.

9

Написать программу, которая удаляет из списка L первое вхождение элемента Е, если такое есть.

10

Удалить из списка все вхождения элемента Е.

11

Построить список L1, элементами которого являются квадраты элементов списка L.

12

Написать программу, которая удваивает каждое вхождение элемента Е в список L.

13

Найти среднее арифметическое всех элементов непустого списка L.

14

Проверить, есть ли в списке L хотя бы два одинаковых элемента.

15

Определить, входит ли список L1 в список L2.

16

Проверить на равенство списки L1 и L2.

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

"Ссылочные типы данных"

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

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

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

Существуют типизированные и не типизированные указатели. Типизированный указатель ссылается только на переменные заданного типа.

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

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

Память под любую динамическую переменную выделяется процедурой NEW.

Освобождение памяти производится процедурой DISPOSE.

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

Выделение и освобождение динамической памяти при работе с нетипизированными указателями производится процедурами GETMEM и FREEMEM.

После того, как указатель приобрел некоторое значение, по адресу можно разместить некоторое значение.

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

Содержание работы

1. Разработать блок - схему алгоритма и написать текст программы задачи согласно варианту.

2. Отладить программу.

3. Выполнить тестовые примеры.

Содержание отчета

1. Блок - схема алгоритма.

2. Текст программы.

3. Результаты работы программы.

4. Выводы.

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

1. Какие переменные называются динамическими?

2. В каких случаях используются динамические переменные?

3. Какие указатели называются типизированными?

4. Данные типа POINTER.

5. Как осуществляется размещение в памяти динамических переменных?

6. Для чего используются процедуры MARK и RELEASE?

7. Каким образом осуществляется доступ к значению динамической переменной?

8. Понятие списка.

9. Какое значение имеют переменные ссылочного типа?

10. Дано описание переменных:

var

x,y:^integer;

r^:^char;

Какие операторы являются правильными, какие - нет и почему?

а) x:=y; б) y:=r; в) x:=nil; г) r:=nil;

д) if y=x then x^:=21; е) if x

Варианты заданий

1. Пусть стек представлен в виде цепного списка. Разработать алгоритм добавления нового элемента.

2. Пусть в памяти две строки представлены в виде цепных списков. Указатели списков x и y. Разработать алгоритм проверки совпадения строк.

3. Разработать алгоритм определения первой пары совпадающих элементов двух цепных списков.

4. Разработать алгоритм изменения порядка следования элементов в цепном списке на обратный.

5. Разработать алгоритм удаления элемента из цепного списка.

6. Разработать алгоритм преобразования цепного списка в последовательный.

7. Разработать алгоритм слияния двух цепных списков, элементы которых расположены в порядке возрастания.

8. Разработать алгоритм извлечения элемента из стека, представленного цепным списком.

9. Разработать алгоритм поиска в цепном списке элемента с минимальным значением.

10. Отсортировать элементы последовательного списка по убыванию.

11. Отсортировать элементы цепного списка по возрастанию.

12. Пусть в стек занесено 20 элементов. Выбрать элемент, расположенный сразу под самым верхним, а затем через один.

13. Разработать алгоритм поиска максимального элемента в последовательном списке.

14. Разработать алгоритм внесения элемента в цепной список.

15. Разработать алгоритм удаления из стека элемента, помещенного в него первым.

16. Разработать алгоритм удаления элементов последовательного списка по заданному признаку.

17. Пусть последовательный список содержит 25 элементов. Откорректировать список путем удаления каждого пятого элемента.

18. Задан список фамилий. Расположить их по алфавиту.

19. Разработать алгоритм преобразования последовательного списка в цепной.

20. Разработать алгоритм, который меняет местами первый и последний элементы списка.

21. Дан список L, построить два новых списка: L1 - содержит положительные элементы списка L, L2 - все остальные.

22. Разработать алгоритм преобразования списка по правилу: за каждым отрицательным элементом вставить нулевой элемент.

23. Даны два списка, вставить все элементы второго списка за первым положительным элементом первого списка.