2015-01-30
506
HАИМЕНОВАНИЕ: Динамические структуры данных
1.ЦЕЛЬ РАБОТЫ: Научится использовать динамические структуры данных
2.ПОДГОТОВКА К ЗАНЯТИЮ:
2.1. Изучить предложенную литературу.
2.2. Подготовить бланк отчёта.
3.ЛИТЕРАТУРА:
3.1 Белов В.В., Чистякова В.И. Программирование в Delphi: процедурное, объектно-ориентированное, визуальное. Учебное пособие. – М.: Горячая линия – Телеком, 2009
3.2 Голицына О.Л., Попов И.И. Основы алгоритмизации и программирования. – Форум, 2010
3.3Семакин И.Г., Шестаков А.П. Основы алгоритмизации и программирования. – М.: Издательский центр «Академия», 2008
3.4Семакин И.Г., Шестаков А.П. Основы программирования. – М.: Издательский центр «Академия», 2008
4. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ:
4.1. Персональный IBM PC.
5.ЗАДАНИЕ:
5.1 Сформировать список строк и а) сохранить его в текстовом файле; б) сохранить его в обратном порядке в текстовом файле. Использовать рекурсию.
5.2 Сформировать список строк из текстового файла.
5.3 Написать функцию, которая вычисляет среднее арифметическое элементов непустого списка.
|
|
|
5.4 Написать процедуру присоединения списка L2 к списку L1.
5. 5 Написать функцию, которая создает список L2, являющийся копией списка L1, начинающегося с данного узла.
5.6 Написать функцию, которая подсчитывает количество вхождений ключа в списке.
5.7 Написать функцию, которая удаляет из списка все вхождения ключа.
5.8 Многочлен 
задан своими коэффициентами, которые хранятся в форме списка. Написать функции:
– Equal(p, q), проверяющую на равенство многочлены p и q;
– Summa(p, q, r), которая строит многочлен r = p + q.
5.9 Вычислить значение многочлена в целочисленной точке x. Коэффициенты вводятся с клавиатуры и динамически размещаются в памяти.
5.10 Сформировать список целых чисел и упорядочить их по неубыванию.
5.11 Сформировать два списка, отсортировать их объединить в один, не нарушая порядка.
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ:
6.1 По предложенной литературе изучить необходимый материал;
6.2 Выполнить задания практического занятия и записать листинг программы;
6.3 Дать ответы на контрольные вопросы;
7. СОДЕРЖАНИЕ ОТЧЕТА:
7.1 Наименование и цель работы
7.2 Код программы
7.3 Записать результат (листинг) выполненых заданий.
7.4 Ответы на контрольные вопросы
7.5 Вывод о проделанной работе
8. КОНТРОЛЬНЫЕ ВОПРОСЫ:
8.1 Что такое указатели? Какие значения они могут принимать? Какие операции возможны над указателями?
8.2 Что представляют собой динамические структуры данных? Для чего они используются? Чем отличаются от данных статического типа?
8.3 Какие стандартные процедуры существуют в языке Pascal для работы с указателями?
8.4 Зачем различать типы указателей?
|
|
|
8.5 Какие операции требуется выполнить для вставки и удаления элемента списка?
8.6 Сколько элементов может содержать список?
8.7 Можно ли для построения списка обойтись одной переменной?
ПРИЛОЖЕНИЕ:
Для работы с динамическими структурами данных используются указатели. Указатели представляют собой специальный тип данных. Они принимают значения, равные адресам размещения в оперативной памяти соответствующих динамических переменных.
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. На самый первый элемент (голову списка) имеется отдельный указатель.
Из определения следует, что каждый элемент списка содержит поле данных (оно может иметь сложную структуру) и поле ссылки на следующий элемент. После ссылки последнего элемента должно содержать пустой указатель (nil).
Число элементов связанного списка может расти или уменьшаться в зависимости от того, сколько данных мы хотим хранить в нем. Чтобы добавить новый элемент в список, необходимо:
1. Получить память для него;
2. Поместить туда информацию;
3. Добавить элемент в конец списка (или начало).
Элемент списка состоит из разнотипных частей (хранимая информация и указатель), и его естественно представить записью. Перед описанием самой записи описывают указатель на нее:
Type { описание списка из целых чисел }
PList = ^TList;
TList = record
Inf: Integer;
Next: PList;
end;
