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

(4 часа)

Динамические структуры данных - односвязные и двусвязные списковые структуры

Цель работы:

Изучение организации списковых структур и построение реальных структур данных на базе списков.

Домашнее задание:

1. Освоить организацию адресного типа (указатели) в Object Pascal и построение динамического списка.

2. Изучить алгоритмы. Позволяющие работать со списковыми структурами различной организации:

а) линейный и кольцевой стек;

б) линейная и кольцевая очередь;

в) дек.

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

1. Открыть проект Delphi Stuctures.

2. На главной форме в главное меню проекта добавить пункт «Лабораторная работа №5», при выборе которого должно появляться окно модуля «DinamicStuct». Для этого модуль DinamicStuct с формой добавить в проект.

3. Установить на форму модуля DinamicStuct компоненты, обеспечивающие ввод исходных данных и вывод результатов работы программы в соответствии с вашим вариантом задания (табл. 5.1), а также управляющую кнопку для запуска программного кода при нажатии на кнопку (событие onClic) в работающей программе. Для ввода и вывода в этих задачах использовать компоненты класса Tmemo.

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

5. отладить приложение на тестовых примерах и продемонстрировать работу смоделированной структуры данных преподавателю.

6. Составить отчет о выполненной лабораторной работе, в который должны войти:

а) задание, в соответствии с вариантом;

б) блок-схема решения задачи;

в) программа решения задачи;

г) распечатка формы с демонстрацией работы смоделированной структуры данных.

7. Защитить работу преподавателю.

Таблица 5.1

№ вар.	Содержание задания
1.	Организовать программно линейный односвязный список следующей структуры: Опишите в программе запись, в поле bukv которой заносится буква. Порождая записи, поместить их в стек, а затем «вытолкнуть» их из списка, получив буквы в порядке, обратном исходному. Проверьте работу примера для исходного набора букв: const A: array [1.. 9] of char =(‘A’, ’P’, ‘Y’, ‘T’, ‘K’, ‘Y’, ’P’, ‘T’, ‘C’).
2.	С помощью стека, организованного в соответствии со структурой вар. 1 организовать получение палиндрома, в котором вторая половина является зеркальным отражение первой без последнего символа. Первую половину вводить с клавиатуры. Например:
3.	Программно организазать очередь в виде однонаправленого списка из элементов типа rec: Type ptr =^ rec; rec = record key: integer; s: ptr; end; var t: rec; Заполняются ссылки на первое ипоследнее звенья списка. Во входном файле задана последовательность из равного количества положительных и отрицательных целых чисел, за которой следует нуль. Ввести эти числа и вывести их, чередуя положитедльные числа (на нечетных местах) с отрицательными (на четных), причем исходный взаимный порядок как среди положительных, так и среди отрицательных чисел должен быть сохранен.
4.	Многочлен P(х) = anxn + an-1xn-1 +… + a1x + a0 с целыми коэффициентами можно представить в виде списка, элементы которого расположены по убыванию степеней одночленов: Описать на Object Pascal тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками-многочленами: а) логическую функцию Equal(p,q), проверяющую на равенство многочлены p и q; б) функцию Value(p,x), вычисляющую значение p в точке x; в) процедуру Dif(p,q), которая строит многочлен p-производную многочлена q; г) процедуру Addit(p,q,r), которая строит многочлен p-сумму многочленов q и r.
5.	Кольцевым списком называется однонаправленный список, в последнем звене которого вместо Nil указывается ссылка на первое звено: Пусть L - кольцевой список с элементами типа Type prt =^ rec rec = record; key: integer; s: ptr; end; а E - величина типа rec. Описать и отладить: а) процедуру, которая строит кольцевой список L и выводит в компонент класса TstringGrid таблицу: t1 t2 … tn-1 tn t2 t3 … tn t1 t3 t4 … t1 t2 -- - - - - - - - - - tn t1 … tn-2 tn-1 б) процедуру, которая строит кольцевой список L и функцию, которая удаляет из непустого списка L последний элемент. в) процедуру, которая строит кольцевой список L и функцию, которая добавляет в конец списка L новый элемент.

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

1 Определения типизированного и обобщенного указателя.

2 Что такое линейный цепной список, и алгоритмы основных операций при работе с ним.

3 Принцип работы кольцевого списка.

4 Организация стека на базе линейного и кольцевого списка.

5 Организация очереди на базе линейного и кольцевого списка.